[분산시스템특론] 6. 해밍 코드

섀넌의 정보이론

아날로그 데이터를 전송할 때는 먼저 인코딩 과정을 거쳐 bit 의 형태로 변형한 뒤 변형된 데이터를 채널을 통해 전송한다.

이때 채널을 통해 전송되는 데이터에는 잡음이 껴서 데이터가 손상될 수 있다. (패킷 오염)

따라서 정보를 수신하는 측에서는 잡음을 제거하고, bit 데이터를 디코딩하여 본래의 아날로그 데이터 형태로 변환하여 데이터를 수신한다.

 

잡음을 제거하는 방법 중 하나는 비트를 전송할 때 3번씩 전송해서 수신한 3개의 비트중 더 많은 값을 최종 비트로 결정하는 방법이 있다.

만약 bit 하나가 뒤바뀔 가능성이 10% 라고 한다면, 3개의 비트중 2개 이상의 비트가 뒤바뀔 가능성은 많이 낮아진다.

하지만 결국 0%는 아니기 때문에 이 방법이 완전한 방법은 아니다.

 

해밍 코드

그래서 해밍 코드를 사용하여 오류를 정정하는 방법이 있다.

해밍 코드는 parity 비트를 사용하여 오류를 정정한다.

 

원데이터가 1011 인 데이터가 있다고 해보자.

해밍코드는 원데이터의 1, 2, 4, .. (2의 거듭제곱 위치) 에 패리티 비트를 삽입한다.

그러면 xx1x011 이 된다.

 

1번 위치 패리티 비트는 위치 인덱스를 이진수로 표현했을 때 2^0 = 1 인 인덱스의 비트를 체크한다. (1 3 5 7)

2번 위치 패리티 비트는 위치 인덱스를 이진수로 표현했을 때 2^1 = 1 인 인덱스의 비트를 체크한다. (2 3 6 7)

4번 위치 패리티 비트는 위치 인덱스를 이진수로 표현했을 때 2^2 = 1 인 인덱스의 비트를 체크한다. (4 5 6 7)

 

그리고 그 비트를 체크해서 1의 개수를 세었을 때, 짝수 혹은 홀수가 되도록 맞춰준다.

이 예시에서는 짝수 패리티 비트를 사용한다고 해보자.

 

그러면

1번 패리티 비트의 값은 x 1 0 1 에서 1의 개수가 짝수가 되어야 하니 x = 0

2번 패리티 비트의 값은 x 1 1 1 에서 1의 개수가 짝수가 되어야 하니 x = 1

4번 패리티 비트의 값은 x 0 1 1 에서 1의 개수가 짝수가 되어야 하니 x = 0

 

결론적으로 7-비트 코드워드의 형태는 0110011 이된다.

 

이제 이 데이터를 그대로 전송하였고 6번 비트에서 오류가 발생했다고 해보자.

 

0110001 

 

오류를 정정하기 위해 각 패리티 비트의 담당 인덱스 비트들을 체크한다.

1번 패리티 비트의 경우 0 1 0 1 이므로 문제가 없다.

(3, 5, 7 비트는 정상)

2번 패리티 비트의 경우 1 1 0 1 이므로 1이 홀수개이다. 따라서 오류가 존재한다.

(2, 3, 6, 7 중 오류 존재, 3, 7 은 정상이므로 2, 6 중 하나에서 오류 발생)

4번 패리티 비트의 경우 0 0 0 1 이므로 1이 홀수개이다. 따라서 오류가 존재한다.

(4, 5, 6, 7 중 오류 존재, 따라서 2, 6 중 6에서 오류가 발생한 것을 탐지 가능)

 

따라서 6번 비트를 바꿔주면 원본 코드워드를 복원할 수 있다.

 

또는 패리티 비트의 담당 비트를 xor 연산했을 때

p0 = 0

p1 = 1

p2 = 1

 

이므로 이를 이진수로 표현한 110 은 십진수로 6 이므로 6번째 비트를 고쳐야 한다고 알 수도 있다.

 

이렇게 여분 비트를 활용하면 채널 용량이 정해져 있을 때, 어떤 범위 내에서는 오류 없이 안전하게 데이터를 전송할 수 있다.

지금은 오류 발생 확률을 10% 로 잡았지만, 오류 발생 확률이 점점 증가해서 50%가 되면 전송 후 비트의 값은 완전 랜덤과 같다.

이럴 때는 엔트로피(불확실성)가 제일 높으며, 데이터를 전송 가능한 채널의 용량도 0이 된다.

반면 오류 발생 확률이 0이거나 100 일 때는 확실하게 비트를 뒤집거나 안뒤집는 결정을 내릴 수 있으므로, 채널의 용량도 최대가 된다.