[컴] 해밍코드 Hamming code

패리티 비트

주어진 bit 열에 1 이 짝수개인지 홀수개인지에 대한 표시를 해 주는 것이다.
일반적으로 짝수개의 1이 있을 때 parity bit 을 0 이라고 하는데, 아래의 bit열에 parity bit 을 더한다면

11111111

의 bit열에 parity bit 은 '0' 이 되고 최종 bit 열은

111111110

이 된다.
이 parity bit 를 이용해서 원래 bit열에 1이 짝수개 있었구나, 또는 홀수개 있었구나를 판단해서 bit열에 error 가 발생했는지 여부를 확인할 수 있다.
그러나 눈치 빠르신 분은 알겠지만, '1'이 짝수개, 홀수개인지를 파악하기 때문에 error 가 짝수개로 발생해 버리면 error 가 발생했는지 모르게 되는 단점이 있다.

해밍이 개발한 시스템 명명법

학술적명명법(nomanclature)을 개발했는데,

(8,7) code

는 8개의 bit 를 가지고 있으며 이중 7개가 data bit 인 code 를 이야기 한다.

해밍코드

Hamming code에서는 이 parity bit 가 "2의 거듭제곱" 자리에 들어가게 된다. 그러니까 2^0(1), 2^1(2), 2^2(4) ... 에 parity bit 가 들어가게 되고 나머지 자리에 원래의 data 를 넣게 된다.

각자리에 들어가는 parity bit 을 만드는 법은 다음과 같다.    색의 자리의 parity bit 은    색에 있는 bit를 가지고 만들게 된다. 말로 풀어내면, 3번째, 5번째, 7번째 자리의 bit 들을 가지고 만든 parity bit 을 1번째 자리에 넣는다.

• P1(2^0 자리에 들어가는 parity bit) : 1, 2, 3, 4, 5, 6, 7, 8
• P2 : 1, 2, 3, 4, 5, 6, 7, 8
• P3 : 1, 2, 3, 4, 5, 6, 7, 8

만약
111
이라는 값에 hamming code 를 추가한다면, 일단 data bit 를 빈자리에 둔다.(아래 그림은 오른쪽이 lower address 이다.)

그러고 나서 paraty bit 을 구하면 된다.

• P1 : 1, 1  -> 0
• P2 : 1, 1  -> 0
• P3 : 1, 1 -> 0

References

1. 위키피디아, 해밍코드