해밍코드 (Hamming Code)

해밍코드
해밍코드는 수신 데이터의 오류를 검출하고 에러 정정을 수행하는 코드로 수학자 리처드 웨슬리 해밍 (Richard Wesley Hamming)의 이름에서 유래되었다. 대부분의 마이크로칩 디바이스에 채택되어 사용중이다. 

패리티비트 수의 결정
해밍코드는 데이터비트와 에러검출과 수정을 위한 패리티비트로 구성되는 데 전송되는 데이터의 비트 수에 따라 페리티 비트의 수가 결정됩니다. 패리티비트의 수를 결정하는 식은 다음과 같다.

          (p : 패리티 비트 수 , d : 데이터 비트 수 )

일반적으로 데이터비트 수는 고정되며 패리티비트의 수는 조건을 만족하는 최소의 수로 정해진다. 만일 데이터비트 수가 8라고 한다면,

                                        2^p -1 > 8 + p
                                        2^p -1-p >= 8

이므로 p=4 이상이여야 식을 만족합니다. 

패리티비트의 위치
패리티비트는 최하위에서 부터 2^n 자리에 배치되고, 그 사이에 데이터가 배치됩니다. 아래 표는 8비트 데이타를 전송할 경우에 패리티비트의 위치를 나타낸 것입니다. 

12	11	10	9	8	7	6	5	4	3	2	1
D8	D7	D6	D5	P4	D4	D3	D2	P3	D1	P2	P1

각 패리티비트는 XOR 연산으로 구해집니다. XOR 연산은 합이 짝수일 경우에는 0, 홀수일 경우에는 1입니다. 

해밍코드를 이용한 전송 및 수신 오류 검출
만일 4비트의 데이터 1001을 헤밍 코드로 전송한다고 가정하면, 

   헤밍코드를 위한 패리티 비트 수 계산은 2^3-1-3 >= 4  이므로 3비트의 패리티비트가 필요합니다.

P1 =  D1, D2, D4 = 101 = 0
P2 =  D1, D3, D4 = 101 = 0
P3 =  D2, D3, D4 = 001 = 1

이 되어 실제 헤밍코드를 이용한 전송 데이타는  0011001 로 전송합니다. 수신측에서는 마찬가지로 P1, P2, P4에 대한 값을 분석하여 수정합니다. 

만일 전송간에 에러가 발생하여 P1, P2, P3의 패리티비트가 변경되었다면, 다음표에서 수정을 할 수 있다.

변화가 발생한 패리티비트	오류가 있는 비트
P1	P1
P2	P2
P1 과 P2	D3
P4	P4
P1 과 P4	D5
P2 와 P4	D6

 P1, P2, P4                          D7

참조자료
http://jhansol.tistory.com/29