'해밍코드 원리' 태그의 글 목록

'해밍코드 원리'에 해당되는 글 1건

2007.12.14 해밍코드 원리 6

해밍코드 원리

Network 2007. 12. 14. 12:47

해밍코드(Hamming code)는 오류를 검출한 후 교정까지 할 수 있는 코드이다.
해밍코드 조건식은 2^p ≥ m + p + 1 이다. 예를 들어 7개의 정보 비트가 있을때, p=3 이라고 가정해보자. 그러면 8 ≥ 7 + 3 + 1 은 성립하지 않는 식이 된다. p=4 라 가정하면 16 ≥ 7 + 4 +1 은 조건을 만족하는 식이 된다.
따라서 정보비트의 수는 7, 패리티 비트 수는 4가 되는 것이다.

(p: 패리티 비트 수, m: 정보 비트 수)

-P1 : 1,3,5,7,9,11
-P2 : 2,3,6,7,10,11
-P3 : 4,5,6,7
-P4 : 8,9,10,11

짝수 패리티의 경우 P1,P2,P3,P4 각각의 비트 번호에 해당되는 정보비트를 읽어서 1이 짝수이면 0이 패리티, 1이 홀수이면 1이 패리티 비트가 된다. <표1>처럼 패리티 비트와 정보 비트를 순서대로 나열하면 해밍코드가 되는 것이다.

<표1. 해밍코드 생성의 예>

해밍코드 복원방법으로는 오류가 발생한 해밍코드를 P4,P3,P2,P1 에 해당되는 비트를 읽어서 1이 짝수이면 0, 1이 홀수이면 1이 패리티 비트가 된다. 이 때, 이 패리티 비트들을 P4부터 순서대로 나열한 수를 10진수로 변환하면 그 10진수에 해당되는 비트의 자릿수가 오류가 있는 것이다. 따라서 이 자리를 반대 숫자로 바꿔주면 원래의 코드가 된다.

예를 들면, 표1의 해밍코드에서 비트번호 3번의 데이터가 1로 변경되었다고 하자. 그러면 P1은 1이 되고, P2도 1이 된다. 나머지 P3은 0, P4는 0 이 된다. 이제 P4부터 나열하면 0 0 1 1 이 되는데, 십진수로 변환하면 3이 된다. 따라서 비트번호 3에 오류가 있다는 것을 알게 되는 것이다.