해밍코드(Hamming Code)

인터넷 상에 해밍코드에 관련된 글들이 많이 있으나 나름데로 정리할 필요가 있다 싶어 정리합니다.

해밍코드는 컴퓨터 스스로 데이터의 오류를 검출하고 수정하는 오류 수정하는 코드로 수학자 리처드 웨슬리 해밍(Richard Wesley Hamming)의 이름에서 유래되었습니다. 보통 에러 검출 코드들이 에러를 검출할 뿐 교정은 불가능한 것을 개선한 것으로, 대부분의 마이크로칩 디바이스에 채택되어 신뢰도를 높이는 데 사용되고 있습니다.

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

페리티 비트의 수 결정

여기서 p는 페리티 비트의 수이며, d는 데이터 비트의 수입니다. 위 식에서 일반적으로 데이터비트의 수는 고정되며, 페리티 비트의 수는 조건을 만족하는 최소의 수로 정해집니다.

//-------------------------------------------------------------------------------------

// 이 부분은 아래의 내용으로 수정합니다.

// 아울러 오류에 대해 이야기를 해 주신 Exclusive님께 감사의 마음을 표합니다.

// 데이터 비트를 8로 수정하기 보다 4로 두고 아래 식의 그림을 수정하는 것이 나을 듯 합니다.

// 시리얼 통신 등을 보면 1바이트 단위로 전송하므로 8비트는 좀 맞지 않은 듯 합니다.

// 가령 데이터비트의 수가 4라면 페리티 비트의 수는

//

// 페리티 비트가 3이라면 5이므로 위 식을 만족하지 않습니다.

// 패리티 비트가 4이라면 12이므로 위 식을 만족합니다.

// 결국 4부터 위 식을 만족한다는 것입니다. 그러므로 페리티 비트의 수는 4로 결정됩니다.

// ------------------------------------------------------------------------------

가량 데이터비트의 수가 4라면 패리티 비트의 수는 

(위 식에서는 데이터 비트를 4라고 해 놓고 식에는 8로 지정되어 있습니다. 이 부분부에서 잘못되었습니다.)

피리티 비트가 2라면 좌변의 식의 결과는 2이므로 위식을 만족하지 않습니다.

패리티 비트가 3이라면 좌변의 식의 결과는 5가 되므로 위 식을 만족하게 됩니다.

결국 3부터 위 식을 만족하게 됩니다. 그러므로 패리티 비트의 수는 3으로 결정합니다.

피리티 비트의 비치

최하위 1부터에서 부터 자리에 배치됩니다.

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

각 페리티 비트별 페리티 체크 비트를 보면 자신을 포함하여 각 비트의 위치 수 만큼 읽고 위치 수 만큼 건너띄는 방식으로 합니다. 예를 들어 8비트의 데이터 비트와 4비트의 패리티 비트가 있는 경우의 체크 비트는 아래와 같습니다. 단 페리티 계산 시 자신은 제외합니다.

1비트 : 1, 3, 5, 7, 9, 11

2비트 : 2, 3, 6, 7, 10, 11

4비트 : 4, 5, 6, 7, 12

8비트 : 8, 9, 10, 11, 12

예를 들어 빅엔디언 방식의 255라는 값을 규칙을 이용하여 짝수 페리티를 적용하였을 경우 아래와 같이 송신 될 것입니다.(위 규칙은 리틀엔디언 방식으로 설명하였는데 엑셀로 우찌 테스트하다 보니 빅엔디언이 되어 버렸습니다. 그러나 방식은 같습니다.)

111011101111

이 데이터를 수신측에서 받았을 때 9번 비트가 오류가 발생하여 아래와 같이 수신되었다고 했을 때

111011100111

각 페리티 비트를 체크하면 

1비트는 1이 되어야 하고

2비트는 0이 되어야 하고

4비트는 0이 되어야 하고

8비트는 1이 되어야 합니다.

이를 8비트 페리티 비트부터 나열해보면 아래와 같이 됩니다.

1001 => 9

죽 9번 비트가 오류라는 이야기 입니다. 그러므로 9번 비트 0을 1로 세트해서 오류를 수정합니다.