#패러티 비트(Parity Bit)와 해밍 코드(Hamming Code)

※ 패러티 비트(Parity Bit)

정보 전달 과정에서 오류가 생겼는지 검사하기 위해 추가된 비트로, 짝수(even) 패러티와 홀수(odd) 패러티 비트가 있다.

	1의 개수 = 홀수	1의 개수 = 짝수
짝수 패러티 비트 (even parity bit)	1	0
홀수 패러티 비트 (odd parity bit)	0	1

만약 7 비트 데이터 1010001이 있다면, 패리티가 포함된 8비트의 데이터는 11010001 혹은 10100011이다. 패러티 비트는 오류 발생 여부만 알 수 있지, 오류를 수정할 수는 없다.

※ 해밍 코드(Hamming code)

해밍 코드를 이용하여 전체 데이터 비트의 어느 지점에서 오류가 발생했는지 검출할 수 있다.

해밍 코드를 구하기 위해서는 우선 추가될 패러티 비트의 개수를 구해야 하며, 아래의 식에서 p를 구하면 된다.

즉, p는 데이터 비트에 추가될 비트의 개수이며, 추가되는 각 비트의 자리는 이다.

예를 들어, 146의 2진 데이터 10010010가 있다고 하자. 이 데이터의 패러티 비트(p)는 4가 되며, 따라서 패러티 비트가 추가되는 자리는 , , , 이 될 것이고, 새롭게 구성되는 데이터 비트는 총 12자리가 될 것이다. 새롭게 구성된 데이터 비트는 아래와 같다.

12	11	10	9	8	7	6	5	4	3	2	1
1	0	0	1	P4	0	0	1	P3	0	P2	P1

패러티 비트는 다음의 과정에 따라 결정된다.

① 추가된 패러티 비트는 바로 다음 자리의 비트를 시작으로 전체 비트의 끝에 도달할 때까지 검사를 수행한다. ② 이 때, 다음 개의 비트를 검사한 후,  자리를 건너뛰어 검사를 계속한다. ③ 검사 도중에 다른 추가된 패러티 비트를 만난다면 그 비트를 포함한  자리를 건너뛴 후 ②를 수행한다. ④ 비트의 끝에 도달했다면, 1의 값을 가진 비트의 개수에 따라 그 패러티 비트 값을 결정한다.

이 과정에 따라 예시의 패러티 비트는 아래와 같으며, 예시에서는 짝수 패러티에 따라 값이 부여된다.

① P1은 3, 5, 7, 9, 11의 비트를 관찰하여, 비트 값이 1인 비트의 개수를 파악한다. 이 때, 1의 비트의 개수는 2개이며, P1의 비트는 0 이 된다.   ② P2는 3, 6, 7, 10, 11의 비트를 관찰하여, 비트 값이 1인 비트의 개수를 파악한다. 이 때, 1의 비트의 개수는 2개이며, P2의 비트는 0 이 된다.   ③ P3는 5, 6, 7, 11, 12의 비트를 관찰하여, 비트 값이 1인 비트의 개수를 파악한다. 이 때, 1의 비트의 개수는 2개이며, P3의 비트는 0 이 된다.   ④ P4는 9, 10, 11, 12의 비트를 관찰하여, 비트 값이 1인 비트의 개수를 파악한다. 이 때, 1의 비트의 개수는 2개이며, P4의 비트는 0 이 된다.

위의 과정에 따른 최종적인 해밍 코드는 아래와 같이, 100100010000가 된다.

12	11	10	9	8	7	6	5	4	3	2	1
1	0	0	1	0	0	0	1	0	0	0	0

만약 5번째 비트에 오류가 발생하여 해밍 코드가 아래와 같다고 하자.

12	11	10	9	8	7	6	5	4	3	2	1
1	0	0	1	0	0	0	0	0	0	0	0

이 경우, 5번째 비트를 검사했던 P1, P3의 경우에는 1의 비트 개수가 홀수개이므로, 비트 값으로 1로 설정되어야 한다. 하지만 이미 0으로 설정하였기 때문에 위의 해밍 코드는 오류가 발생한 비트로 판단될 수 있다.

참고 자료

https://ko.wikipedia.org/wiki/%ED%8C%A8%EB%A6%AC%ED%8B%B0_%EB%B9%84%ED%8A%B8

http://blog.naver.com/vanpelt/100138087430