오류 정정 부호
디지털 정보를 저장하거나 전달하는 과정에서는 다양한 오류가 발생할 수 있다. 정보 통신 과정의 신뢰성을 높이기 위해서는 오류를 검출하거나 정정하는 오류 제어 기술이 필요하다. 오류 제어는 역방향 오류 정정과 순방향 오류 정정의 두 가지 방식으로 구분된다.
역방향 오류 정정 방식에 따르면, 송신 측은 메시지를 ‘오류 검출 부호’로 부호화한 데이터 블록을 보내고, 수신 측은 이를 검사하여 오류가 검출될 경우 송신 측에 재전송을 요청한다. 오류 검출을 위해서는 송신 측과 수신 측이 주고받는 데이터 블록이 만족해야 할 규칙이 정의되어 있어야 한다. 오류 검출 부호의 가장 간단한 형태인 ‘패리티 비트’ 방식은 주고받는 데이터 블록에서 1의 개수가 짝수여야 한다는 규칙을 사용하는데, 송신 측은 이 규칙을 만족하도록 메시지에 1비트짜리 패리티 비트를 추가하여 데이터 블록을 만들어 보내고, 수신 측은 데이터 블록에서 1의 개수가 짝수인지 홀수인지를 확인하는 ‘패리티 검사’를 수행한다. 예를 들어 이 규칙을 사용하여 [1010010]의 7비트짜리 메시지를 주고받을 경우, 송신 측은 여기에 [1]의 패리티 비트를 추가하여 [10100101]이라는 데이터 블록을 보내고, 수신 측은 수신된 데이터 블록에서 1의 개수가 짝수면 정상으로 판단하여 메시지를 읽어 내고, 홀수면 오류가 발생한 것으로 판단하여 송신 측에 재전송을 요청한다.
패리티 비트를 이용한 오류 검출은 100%의 확실성을 보장하지 않는다. 짝수 개의 비트에서 오류가 발생하면 오류를 검출하지 못하기 때문이다. 예를 들어 [010]의 메시지에 패리티 비트를 추가하여 [0101]의 데이터 블록을 보냈는데, 중간에 오류가 발생하여 [0110]이 도착했다면 수신 측은 이를 정상으로 판단할 것이다. 보다 강력한 오류 검출 부호인 ‘체크 섬’ 방식은 데이터 블록을 바이트, 즉 8비트 단위로 더한 총합의 맨 뒤 8비트가 모두 0이어야 한다는 규칙을 사용한다. 예를 들어 [1111000000001111]이라는 2바이트짜리 메시지를 보낼 때에는 [00000001]이란 체크 섬이 뒤에 추가된 3바이트짜리 데이터 블록을 주고받게 된다([11110000]＋[00001111]＋[00000001] = [100000000]). 이러한 체크 섬 방식의 오류 검출은 오류 발생 시 그것을 오류로 인식할 확률이 패리티 비트 방식보다 훨씬 높다.
위의 두 방식은 모두 역방향 오류 정정 방식에 해당하므로 오류 검출 시 재전송을 요청해야 한다. 오류 검출 부호 대신 오류 정정 부호를 사용하는 순방향 오류 정정 방식은 오류 발생 여부뿐 아니라 오류 발생 위치까지 찾아내어 재전송 요청 없이 원본을 복원할 수 있다. ‘해밍 부호’는 순방향 오류 정정을 가능케 하는 가장 간단한 오류 정정 부호이다. 그중 가장 널리 사용되는 (7,4) 해밍 부호는 4비트의 메시지를 전송하기 위해 3개의 패리티 비트로 이루어진 패리티 부호를 뒤에 추가하여 7비트의 데이터 블록을 만들어 낸다. 패리티 부호의 첫째 자리, 곧 데이터 블록의 5번 비트는 2,3,4번 비트의 패리티 비트이고, 둘째 자리, 곧 데이터 블록의 6번 비트는 1,3,4번 비트에 대한, 셋째 자리, 곧 데이터 블록의 7번 비트는 1,2,4번 비트에 대한 패리티 비트이다. 수신 측에서는 데이터 블록에서 세 번의 패리티 검사를 수행하여 하나라도 홀수가 나오면 오류로 진단한다. 첫 번째 검사는 2,3,4,5번 비트에 대해, 두 번째 검사는 1,3,4,6번 비트에 대해, 세 번째 검사는 1,2,4,7번 비트로 이루어지며, 전송된 데이터에 아무런 오류가 없다면 세 검사 결과는 모두 짝수로 나올 것이다. 그러나 1비트의 오류가 있다면 그 비트가 포함된 패리티 검사의 결과가 홀수로 나오기 때문에, 오류 비트의 위치를 정확하게 알 수 있게 된다.
예를 들어 (7,4) 해밍 부호로 [1011]의 메시지를 보내려면 [010]의 패리티 부호가 덧붙여진 [1011010]의 데이터 블록을 전송하게 되며, 만약 여기서 2번 비트에 오류가 생겨 [1111010]을 전송받을 경우 세 번의 패리티 검사 중 첫 번째와 세 번째 검사는 홀수로 나오고 두 번째 검사는 짝수로 나온다. 홀수로 나온 두 검사는 공유하지만 짝수로 나온 검사는 공유하지 않는 검사 대상은 2번 비트뿐이므로, 수신 측은 2번 비트의 [1]이 원래는 [0]이었음을 알아내어 원본 [1011010]을 복원한 후 메시지 [1011]을 읽어낸다. 보다 긴 메시지를 해밍 부호로 보내려면 더 긴 패리티 부호가 필요한데, n개의 패리티 비트를 이용하는 해밍 부호는 최대 (2n-1)비트의 데이터 블록에서 오류를 바로잡을 수 있다.
해밍 부호를 이용한 오류 정정 역시 100%의 확실성을 보장하지는 않는다. 1비트의 오류가 있을 때는 그것을 항상 바로잡을 수 있지만, 2비트의 오류가 있을 경우에는 엉뚱한 위치에 오류가 있다고 착각해 실수를 하게 된다. 그러나 우리는 수신된 데이터 블록에 몇 비트의 오류가 있을지 미리 알 수 없다. 따라서 만약 해밍 부호를 이용해 2비트의 오류까지 검출하려면 오류 정정을 포기하고 오류 검출 후 재전송 요청을 하는 방식으로 설정을 해 두어야 한다. 한편 3개 이상의 비트에 오류가 있을 경우에는 아예 오류를 검출조차 못할 수 있다. 따라서 해밍 부호는 오류가 산발적으로만 발생하는 환경에서 사용해야 하며, 오류가 인접한 위치에 집단적으로 발생하는 ‘연집 오류’의 가능성이 높은 환경에서는 리드-솔로몬 부호와 같은 다른 오류 정정 부호를 사용하는 것이 좋다.