Hamming code – 해밍 코드

해밍 부호(해밍符號, Hamming code)는 오류 정정 부호의 일종으로 리처드 해밍이 제안했다.
보통 해밍 부호라고 할 때는 해밍 (7,4) 부호를 가리킨다.
해밍 부호는 1비트 오류만 일어날 때는 오류를 정정할 수 있고, 2비트까지의 오류를 검출할 수 있다.

역사

해밍은 1940년대 벨 연구소에서 Bell Model V라는 컴퓨터를 이용해서 작업을 했다.
이 컴퓨터는 확실히 여러 면에서 오늘날의 컴퓨터와는 거리가 멀었다.
릴레이 회로로 만들어졌으며 입력도 천공카드를 이용했다. 천공카드를 이용했으므로
컴퓨터에 입력되는 자료들은 필연적으로 언제나 오류의 가능성이 있었다.
주중에는 컴퓨터의 관리자(operator)가 있으면서 입력에 오류가 발생했다는 경고등이 켜지면
직접 수정할 수 있었으나, 관리자가 없는 주말에는 에러가 발생한 채 프로그램이 실행되지 않고
다음 작업으로 넘어가기 일쑤였다.


해밍은 이런 문제로 인해 여러 차례 고생을 한 후에, 이 문제를 근본적으로 해결하기 위해 노력했다.
그후 몇 년 동안 오류를 수정하는 방법에 대해서 연구하면서 이와 관련된 여러가지의 효율적인 알고리즘을
만들어냈고 마침내 1950년에 해밍 부호를 발표했다. 해밍 부호는 오늘날에도 사용되고 있다.


패리티 비트

패리티 비트 (parity bit)는 주어진 비트열에 1이 짝수번 나오는지 홀수번 나오는지 추가적인 정보를
입력하는 방식
이다.
예를 들어, 어떤 비트열에 1이 홀수번 나오면 패리티 비트가 1이고 짝수면 0으로 정했다고 하자.
‘1101011’이라는 비트열에는 1이 3번 나오므로 패리티 비트가 1이 되어서 최종적으로 11010111’이라고
쓰는 방식이다.


패리티 비트는 여러가지 단점이 있다.


짝수 개의 오류가 발생하면 하면 오류를 검출하지 못하는 경우가 생길 수 있다. 예를 들어서 ‘0000’을 보내려고
패리티 비트 ‘0’을 추가해서 ‘00000’을 전송했는데 오류가 발생해서 ‘01010’이 전송되었다고 하자.
받는 쪽에서는 1이 두번 나오므로 패리티 비트가 제대로 0으로 설정되었다고 생각할 것이고, 결과적으로 오류를
검출하지 못하게 된다.
전송된 비트열에 오류가 발생했다는 것을 알았다 하더라도 오류가 발생하기 전의 제대로 된 내용을 알 수 없다.
예를 들어서 ‘001000’이라는 비트열을 받았다고 하자. 이 비트열에서 1이 한 번 나오기 때문에 전송중에 오류가
생겼다는 것을 알 수 있지만, 원래 비트열은 알 수가 없다. 따라서 결과적으로 데이터를 다시 전송해야 하는
문제가 있다. 데이터의 전송 과정에서 오류가 발생하므로 패리티 비트 자체에도 오류가 생길 수 있다.

해밍 부호를 만드는 방법

2의 거듭제곱번째 위치에 있는 비트들은 패리티 비트로 사용한다. (1, 2, 4, 8, 16, 32, 64, …번째 비트)
나머지 비트에는 부호화될 데이터가 들어 간다. (3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, …번째 비트)

 … 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 (굵게 표시한 부분이 패리티 비트가 들어가는 곳)
                 P4           P3   P2  P1

     P1의 패리티 값 : 1, 3, 5, 7, 9, 11, … 의 값들의 패리티 검사를 통해 정함
     P2의 패리티 값 : 2, 3, 6, 7, 10, 11, … 의 값들의 패리티 검사를 통해 정함
     P3의 패리티 값 : 4, 5, 6, 7, 12, 13, 14, 15, … 의 값들의 패리티 검사를 통해 정함
     P4의 패리티 값 : 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, …  의 값들의 패리티 검사를 통해 정함

     예> 7의 이진수 값은: 0 1 1 1   – 해밍코드 – >   0 1 1 P3 1 P2 P1 (even parity이용)
                   P1 1 1 0 : P1 = 0          P2 1 1 0 : P2 = 0          P3 1 1 0 : P3 = 0
                      결과 값 : 0 1 1 0 1 0 0

     또 다른 방법은 1의 값이 있는 위치를 각각 구한 다음 그 값들을 세로로 XOR 연산 하는 방법이 있다.
     위의 예를 이용해서 계산해보면, 1이 있는 위치가 6번째 자리, 5번째 자리, 3번째 자리이다.

                   6 : 1 1 0
                   5 : 1 0 1
                   3 : 0 1 1
            parity : 0 0 0   <-   이 값을 P3 P2 P1에 넣어주면 된다.

     오류 위치 찾는 방법은 위의 parity 값을 찾는 방법과 비슷하다. 오류를 찾으려고 하는 값의 1의 위치들을
     세로로 각각 xor 연산해서 나온 값이 오류 비트가 있는 위치이다.

     7의 해밍코드 값은 0110100 인 것을 알고 있다. 그런데 오류가 하나 생겨서 0100100이 수신됬다고 하자.
     이 값에 오류가 있는지 알아보려면 일단 1의 위치를 알아본다. 3, 6번째에 1이 있다.

                   6 : 1 1 0
                   3 : 0 1 1
            check : 1 0 1   <-   이 값이 오류 위치를 말한다. 10진수화 하면 5번째 비트에 오류가 있다.
                                        원래 값과 비교해보면 5번째 비트가 1에서 0으로 오류가 있는 것을 확인할 수 있다.

출처: 위키백과(해밍부호), 위키백과(Hamming code)

You may also like...

댓글 남기기