Posted at 2007/10/15 17:03 //
in 용어 사전/전자 통신 //
by downright
해밍 부호(해밍符號, 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, …번째 비트)
