[Data] Error Correction

흔히 뭔가 정보를 표현할때 예를 드는 것중에 하나가 위와 같은 동전이다. 여기선 보통 head를 1, tail을 0으로 표현해서 정보를 나타내게 된다. 만약 이렇게 얻은 정보를 누군가에게 전달한다고 가정을 해보자.

이때 전달과정에서 뭔가의 오류가 발생한다면, 어떻게 될까? 분명 전달하고자 하는 사람은 head를 전달하고자 했음에도 최종적으로는 tail이 전달된 케이스가 그런 경우일텐데, 이렇게 한가지 정보가 잘못 전달된 케이스를 single bit error라고 한다. 당연히 이런 경우를 방지하기 위해서 이런 오류를 탐지하고 수정하는 절차가 필요할 것이다. 여러가지 방법이 있겠지만, 이론상으로 다루는 내용 중 하나가 바로 Hamming Distance라는 것이다.

 Hamming Distance란 원래의 정보와 전달된 정보를 비교했을 때, 오류가 발생한 bit의 갯수를 나타낸다. 

위와 같은 경우는 두개의 정보를 비교했을 때 오류가 발생한 bit이 2개이므로 HD는 2가 된다. 

 그런데 문제는 아까와 같이 정보량이 1 bit인 상태에서는 Hamming Distance를 통해서 오류를 찾을 수 없다는 것이다. 생각해보면 간단한게 만약 A가 0을 보내고 B가 1을 받았다고 가정했을 때 당연히 문제인것이지만 이때 A가 잘 못 보낸 것인지, B가 잘못 보낸 것인지를 알수 없는 케이스가 생긴다. 예를 들어서 B가 1을 정상적으로 받았기 때문에 A가 잘못보냈다고 할수도 있고, 혹은 A가 정상적으로 보냈기 때문에 B가 잘못 받았다고 할수도 있다. 이처럼 hamming distance와 정보 표현량이 같으면 오류가 정상적으로 인지되지 않는다는 문제가 발생한다. 이를 막기위해서 보통 데이터를 전달할 때 parity bit이라는 것을 추가해서 보낸다. 다음과 같은 케이스가 그렇다. 

기존에 전달했던 정보외에 빨간색으로 표현된 값이 parity bit인데, 이 bit이 나타내는 것은 원래 정보에 1의 갯수의 패턴을 나타내는 것이다.(홀수냐 짝수냐에 따라서 odd / even parity로 나뉜다.) 만약 1의 갯수가 0이라면 짝수이므로 0을 붙여줘서 00이 되는 것이고, 1의 갯수가 1이라면 홀수가 되므로 1이었던 정보는 11이 된다. 유의해야 될 것은 이 parity bit은 정보가 아니라는 것이다. 즉 손실이 되도, 그만 없어도 그만이 bit이라는 것이다.  그럼 이때 만약 10이라는 정보를 전달받았다고 가정했을 때, 00이나 11이 아니므로 error detection이 될 것이다. 그러면 어디서 오류가 발생했냐가 중요해질텐데, 만약 원래 정보를 나타내는 bit에 문제가 있었다면 그 bit을 바꿔준 뒤에 parity bit를 맞춰보면 된다. 반면 parity bit에서 오류가 발생한 경우는 앞에서 말했다시피 정보가 아닌 parity bit을 배제한 원래 정보는 제대로 전달되게 된다. 이런 개념을 잘 활용한다면 single bit error 뿐만 아니라 Multibit error가 발생한 케이스에 대해서도 error detection을 적용할 수 있다. 

다만 이런식으로 적용하는데 있어서 필요한 조건이 바로 hamming distance가 찾아내고자 하는 error bit의 크기보다 적어도 하나이상 커야 한다는 것이다.이 조건만 만족한다면, hamming distance를 통해서 error detection과 correction을 수행할 수 있게 된다. 

출처: 6.004.1x Computation Structures - Part 1: Digital Circuits