패리티 비트와 해밍 코드 (Parity Bit and Hamming Code)

패리티 비트(parity bit)와 해밍 코드(Hamming code)는 데이터가 저장되거나 전송되는 과정에서 비트가 뒤집히는 오류를 다루기 위한 대표적인 기법이다. 패리티 비트는 1의 개수를 맞추는 비트 하나를 덧붙여 홀수 개 비트의 오류를 검출만 할 수 있고, 해밍 코드는 여러 개의 패리티 비트를 겹치게 배치해 1비트 오류의 위치까지 찾아 정정할 수 있다. 두 기법은 오류 검출(error detection)과 오류 정정(error correction)의 차이를 보여주는 가장 기본적인 사례로, ECC 메모리와 통신 프로토콜의 바탕이 된다.

오류는 왜 생기고 어떻게 다루는가

전송 선로의 잡음, 우주 방사선에 의한 메모리 비트 반전, 저장 매체의 열화 등으로 0이 1로, 1이 0으로 바뀌는 오류는 언제든 발생할 수 있다. 이를 다루는 전략은 두 갈래다. 오류 검출은 오류가 났다는 사실만 알아내고 재전송을 요청하는 방식으로, 재전송이 가능한 네트워크 통신에 적합하다. 오류 정정은 수신한 데이터만으로 오류를 스스로 고치는 방식으로, 재전송이 불가능하거나 비싼 메모리, 위성 통신, 저장장치에 적합하다. 어느 쪽이든 원리는 같다. 원본 데이터에 잉여 정보(redundancy)를 계산해 붙이고, 받는 쪽에서 다시 계산해 일치 여부를 확인하는 것이다.

패리티 비트의 원리와 한계

패리티 비트는 데이터의 1의 개수가 짝수 또는 홀수가 되도록 덧붙이는 1비트다. 짝수 패리티(even parity)는 패리티 비트를 포함한 전체 1의 개수를 짝수로, 홀수 패리티(odd parity)는 홀수로 맞춘다. 예를 들어 데이터 1011001은 1이 4개이므로 짝수 패리티에서는 0을 붙여 10110010으로 보낸다. 수신 측은 1의 개수를 세어 홀수가 나오면 오류가 발생했음을 안다.

한계는 명확하다. 첫째, 비트 2개가 동시에 뒤집히면 1의 개수의 짝홀이 유지되어 오류를 놓친다. 즉 홀수 개의 비트 오류만 검출한다. 둘째, 오류가 있다는 사실만 알 뿐 몇 번째 비트가 잘못되었는지는 모르므로 정정이 불가능하다. 그래서 패리티는 오류율이 낮고 재전송이 쉬운 환경, 예를 들어 과거의 직렬 통신이나 일부 메모리의 단순 검사에 쓰였고, 더 강한 검출이 필요한 네트워크에서는 순환 중복 검사(CRC, Cyclic Redundancy Check) 같은 기법이 쓰인다.

해밍 코드의 동작 방식

해밍 코드는 패리티 비트를 여러 개 두되, 각 패리티 비트가 담당하는 데이터 비트의 집합을 서로 겹치게 설계해 오류 위치를 알아내는 기법이다. 비트 위치를 1부터 번호 매기고, 2의 거듭제곱 위치(1, 2, 4, 8, ...)에 패리티 비트를 배치한다. 위치 번호를 이진수로 썼을 때 특정 자리가 1인 모든 위치를 그 자리의 패리티 비트가 담당한다. 예를 들어 1번 패리티는 위치 1, 3, 5, 7을, 2번 패리티는 위치 2, 3, 6, 7을 검사한다.

데이터 4비트에 패리티 3비트를 붙이는 해밍(7,4) 코드로 예를 들면, 수신 측은 각 패리티 그룹을 다시 검사해 실패한 그룹의 패리티 위치 번호를 모두 더한다. 이 합을 신드롬(syndrome)이라고 하며, 신드롬이 0이면 오류가 없고, 0이 아니면 그 값이 바로 오류가 난 비트의 위치다. 예컨대 1번과 4번 그룹이 실패했다면 5번 위치의 비트가 뒤집힌 것이므로 그 비트를 반전시켜 정정한다. 여기에 전체 패리티 비트 하나를 더 추가한 확장 해밍 코드는 1비트 오류는 정정하고 2비트 오류는 검출하는 SECDED(Single Error Correction, Double Error Detection) 능력을 갖는다.