Hamming Code

우리가 컴퓨터 혹은 휴대폰으로 각종 정보들을 송, 수신합니다. 이 떄 그 메시지는 0, 1의 연속으로 오는데, 문제는 메시지를 주고받을 때 알 수 없는 이유로 메시지가 변조될 수가 있다는 것입니다.

즉 A가 B에게 01110010을 보내고 싶었는데 알 수 없는 이유로 B가 01100010를 받을 수도 있습니다. 그렇기 때문에 애초에 전송을 할 때, 이런 오류를 어느정도는 바로잡아줄 수 있도록 전송 방법을 정하고 싶습니다.

가장 간단한 방법은 보내고 싶은 메시지를 한 10번정도 보내는 것입니다. 예를 들어 1101110001010010을 보내고 싶다고 할 때, 이걸 여러 번에 걸쳐 전송을 하면

1101110001010010

1101110000010010

1101110001010010

1101100001010010

1101110001010110

1101110001010010

군데군데 에러가 발생하겠지만 다른 것들을 통해서 오류를 쉽게 바로잡을 수 있습니다. 하지만 이렇게 같은 걸 여러번 보내는건 별로 사용하고 싶지는 않은 방법입니다. 쉽게 말해서 1GB짜리 파일을 받고 싶은데 그것의 10배인 10GB를 실제로 받는다고 하면 누가 그렇게 하려고 할까요? 수업시간에 10000개의 bit중에 1개의 오류가 있으면 굉장히 많은 편이라고 한 것을 감안하면 이 방법은 너무나 비효율적입니다.

그렇게해서 두번째로 제시한 방법이, 메시지에 포함되어있는 1의 갯수가 홀수개인지 짝수개인지를 데이터 끝에 작성하는 방법입니다. 예를 들어 10010010이라고 하면 1이 3개이므로 실제로는 100100101을 전송하는 것입니다. 이 방식은 용량도 많이 잡아먹지 않고(8개 단위로 끊어서 생각하면 1.125배, 4개 단위로 끊어서 생각하면 1.25배가 됩니다.) 1bit error detection(1bit의 변화를 감지)이 가능합니다. 하지만 이 방식을 통해서 1bit error correction(어떤 1bit이 바뀐건지를 알아내어서 수정)은 불가능하고, 2bit error detection도 불가능합니다.   

그래서 용량도 많이 잡아먹지도 않고 correction, detection을 그럭저럭 효율적으로 해주는 방법에 대해 알아봅시다. 그 방법이 바로 (7-4) Hamming Code 입니다.

서술의 편의를 위해 A가 B에게 보내고 싶은 글의 내용을 메시지, 그리고 correction, detection을 위해 실제로 이것저것 붙여서 전송한 건 데이터라고 하겠습니다.

(7-4) Hamming Code는 아래와 같은 절차를 거칩니다.

1. 보내고싶은 메시지를 4bit 단위로 자른 이후에 열행렬로 만듭니다.

2. 그 행렬을 generating matrix(생성 행렬) G와 곱한 결과를 전송합니다. 이 때 2로 나눈 나머지를 전송해 0 혹은 1이 전송되도록 합니다.

3. 수신자는 전달받은 행렬을 Parity matrix(확인 행렬) H와 곱합니다. 마찬가지로 곱한 이후에 2로 나눈 나머지를 생각합니다.

4. 만약 syndrome(3에서 얻은 1*3 행렬)이 0이라면 오류가 없고 0이 아니면 오류가 있습니다.

(7-4) Hamming Code는 1.75배의 데이터를 전송하고, 1bit error correction이 가능하고, 2bit error detection이 가능합니다.

(7-4) Hamming Code에서 메시지 4bit당 parity bit(데이터 내용이 아닌, 데이터 내용의 확인을 위해 추가적으로 붙는 bit)가 3bit씩 달리게 됩니다.

일반적으로 1bit error correction이 가능하기 위해서는 메시지 N-bit당 parity bit M-bit라고 할 때 $N+M \leq 2^M-1$ 이어야 합니다. 직관적으로 잘 이해가 안갈수도 있는데 오류가 없는 경우(syndrome이 0인 경우)를 제외하고 syndrome으로 표현될 수 있는 가짓수가 전송받은 데이터(메시지 + parity bit)의 길이 이상이어야 오류가 있는 1개의 자리가 syndrome과 적어도 하나와는 대응될 수 있기 때문입니다. 직접 종이에 그려서 생각해보세요.

아무튼 (7-4) Hamming Code에서는 $4+3 \leq 2^3 - 1$ 로 깔끔하게 딱 떨어집니다. 즉 1bit error correction이 가능한 것입니다.

또한 2bit error detection이 가능하다는 것은 전송받은 4+3=7bit의 데이터 중에서 딱 2bit가 바뀌게 되었을 때 syndrome은 무조건 0이 아닌 다른 값이라는 것입니다. 하지만 어떤 2bit이 바뀐 것인지는 알아낼 수 없습니다.

대충 이정도면 필요한 얘기는 다 한것같은데 헷갈릴 수 있는 부분들을 정리해드리겠습니다.

1. 3bit 이상의 error는 detect한다는 보장이 없습니다. 즉 3bit 이상의 error가 발생했는데도 syndrome이 0일 수도 있습니다.

2. 1bit error correction은 주어진 데이터가 딱 1bit의 error만 가지고있다고 가정을 했을 때 가능합니다. 예를들어 parity가 001이라고 가정을 해봅시다. 그러면 우리가 7개의 bit 중에 1번째 bit가 잘못되었다고 생각을 하지만, 정확하게는 '데이터가 1bit의 error만 가지고 있다면 1번째 bit가 잘못된 것이다' 입니다. 즉, parity가 001이었지만 사실은 (2, 4)번째 bit가 잘못되었거나 (3, 5, 6)번째 bit가 잘못되었거나 할 수 있는 것입니다.