오류 검출 코드 - 해밍코드(Hamming Code)

네트워크 통신을 하다보면 중간에 물리적인 장애물, 잡음 등으로 인해 데이터가 유실, 변경될 가능성이 있다. 그래서 데이터를 수신하는 수신부는 항상 수신받은 데이터가 정확한 데이터가 아닐 것이라는 의심을 가지고 오류를 검사해야 한다. 그 중 오류 검출과 수정을 한번에 할 수 있는 방법인 해밍 코드(Hamming Code)에 대해 알아보자.

해밍코드는 생성, 검출, 수정 3가지 단계를 가진다.

 

생성

해밍코드의 아이디어는 하나의 데이터단위에 대해 충분한 패리티비트를 추가해서 수신측으로 하여금 패리티비트로 오류를 검출하고 수정할 수 있도록 하는 것이다.

 

패리티 비트

짝수 패리티, 홀수 패리티로 나뉘며 데이터 단위를 구성하는 비트 중 1의 개수를 홀수/짝수로 만드는 비트이다. 1100110의 짝수 패리티는 0, 홀수 패리티는 1이 된다. 프로토콜에 따라 홀수 패리티를 사용할지 짝수 패리티를 사용할지 미리 송수신측이 동기화되어야 한다.

 

순서

1. 몇 개의 패리티비트를 추가할 지 계산한다.

위 부등식을 만족하는 최소 P를 구한다.

 

2. 패리티비트를 추가해서 새로운 데이터를 만든다.

위 내용만 보면 어떻게 만들어야하는지 이해가 잘 안될 수 있다. 실제 데이터를 가지고 해밍코드를 만들어보면서 위 내용이 어떤 의미인지 자세히 알아보자.

 

예제

원본 데이터 1001에 대해 해밍코드를 만들어보자. 순서에 따라 먼저 몇개의 패리티비트를 추가해야할지 계산한다.

위 부등식 검사를 통해 가장 적절한 P의 값은 3이라는 것을 알 수 있다. 4도 부등식을 만족하지만 P는 부등식을 만족하는 최소값이면 되기 때문에 3을 채택한다.

 

P를 구했으니 패리티비트 자리를 추가해서 새로운 데이터를 만든다.

공식을 통해 패리티 범위를 구한다.

이 예제에서는 짝수패리티로 해밍코드를 만든다.

따라서 원본 데이터 1001에 대한 해밍코드는 1001100이 된다.

검사 및 수정

해밍코드의 가장 큰 특징은 데이터의 재수신 없이 수신측에서 바로 오류를 검출하고 수정할 수 있다는 점이다. 위에서 만든 해밍코드를 수신측의 입장에서 해석하고 원본 데이터를 얻어내는 방법에 대해 알아보자.

정상적으로 수신했다면 1001100을 수신해야 하지만 검출과 수정을 해보기 위해 단일 비트 오류가 발생해서 1011100을 수신했다고 가정한다. 수신측은 이 통신이 짝수 해밍코드를 사용한 통신임을 미리 알고 있기 때문에 어떤 비트가 패리티비트인지 알고있다.

그리고 그 패리티비트가 어떤 범위에 대한 짝수패리티인지도 알고 있기 때문에 순서대로 패리티비트의 유효성을 검사하는 것으로 오류를 수정할 수 있다.

첫번째 비트부터 검사한다.

첫번째 패리티를 검사해봤더니 벌써 오류가 발생했음을 알 수 있다. 범위에 대한 짝수패리티는 1이기 때문에 1을 기록하고 넘어간다.

 

두번째 패리티를 검사해봤더니 정상이다. 범위에 대한 짝수패리티는 0이기 때문에 0을 기록하고 넘어간다.

 

세번째 패리티를 검사해봤더니 또 패리티가 맞지 않는다. 범위에 대한 짝수 패리티는 1이기 때문에 1을 기록한다. 결국 E는 5임을 구할 수 있다.

 

5번 비트를 0으로 바꿔서 1001100 즉, 원래 보내고자 했던 데이터를 얻을 수 있고, 해밍코드를 만들기 위해 추가한 (1, 2, 4) 번째 비트를 제거하고 1001이라는 원래 메시지를 얻을 수 있다.