컴퓨터가 데이터를 저장하거나 전송할 때 비트 하나가 0에서 1로, 또는 1에서 0으로 바뀔 수 있습니다. 단순 패리티는 오류가 났다는 사실은 알아낼 수 있지만 어느 비트가 바뀌었는지는 알려주지 못합니다. 해밍 부호(Hamming code)는 여러 패리티 검사를 서로 겹치게 배치해 단일 비트 오류의 위치를 계산하고 그 비트를 뒤집어 복구합니다. 핵심은 각 비트 위치에 이진수 주소를 붙이고, 주소의 각 자릿값을 담당하는 패리티 비트를 두는 것입니다. 수신 측에서 실패한 검사들을 모으면 오류 위치 자체가 이진수로 나타납니다.
패리티 하나로 알 수 있는 것
짝수 패리티를 쓰는 경우 데이터와 패리티 비트를 모두 합친 1의 개수가 짝수가 되도록 패리티 비트를 정합니다. 예를 들어 1011에는 1이 세 개 있으므로 패리티 1을 붙이면 전체 1이 네 개가 됩니다. 전송 중 비트 하나가 바뀌면 1의 개수의 홀짝이 달라져 검사가 실패합니다. 하지만 검사 결과는 ‘어딘가 한 비트가 달라졌다’는 한 가지 정보뿐입니다. 오류 후보가 여러 자리라면 어느 자리를 고쳐야 하는지 결정할 수 없습니다. 해밍 부호는 서로 다른 비트 묶음을 검사하는 패리티를 여러 개 두어 이 한계를 넘습니다.
패리티 비트는 왜 1, 2, 4, 8번에 놓을까
비트 위치를 1부터 매기고 이진수로 쓰면 1은 0001, 2는 0010, 3은 0011, 4는 0100처럼 표현됩니다. 1, 2, 4, 8은 이진수에서 단 하나의 자릿값만 1인 2의 거듭제곱입니다. 이 위치를 각각 p1, p2, p4, p8 패리티 비트로 사용합니다. p1은 위치 번호의 1의 자리가 1인 1, 3, 5, 7 등을 검사합니다. p2는 2의 자리가 1인 2, 3, 6, 7 등을 검사하고, p4는 4의 자리가 1인 4, 5, 6, 7 등을 검사합니다. 한 데이터 비트는 자기 위치의 이진 표현에 따라 여러 검사에 참여합니다.
(7,4) 해밍 부호는 데이터 4비트를 전체 7비트로 만듭니다. 위치 1, 2, 4에는 패리티가 들어가고 위치 3, 5, 6, 7에는 데이터가 들어갑니다. 자리 배열은 p1, p2, d1, p4, d2, d3, d4입니다. 짝수 패리티라면 p1은 1·3·5·7번, p2는 2·3·6·7번, p4는 4·5·6·7번의 XOR 결과가 0이 되도록 정합니다. XOR은 입력에 포함된 1의 개수가 홀수면 1, 짝수면 0을 내므로 패리티 계산에 그대로 사용할 수 있습니다.
예제로 (7,4) 부호 만들기
데이터 1011을 d1=1, d2=0, d3=1, d4=1 순서로 넣어 보겠습니다. 배열은 p1, p2, 1, p4, 0, 1, 1입니다. p1이 검사하는 데이터 위치 3, 5, 7에는 1, 0, 1이 있어 1이 두 개이므로 p1=0입니다. p2가 보는 3, 6, 7에는 1, 1, 1이 있어 1이 세 개이므로 p2=1입니다. p4가 보는 5, 6, 7에는 0, 1, 1이 있어 1이 두 개이므로 p4=0입니다. 따라서 전송할 7비트는 0110011입니다. 여기서는 설명을 위해 왼쪽을 1번 위치로 적었으며, 시스템의 비트 표기 순서는 구현 규약에 맞춰야 합니다.
신드롬이 곧 오류 위치가 되는 계산
전송 중 6번 비트가 바뀌어 0110001을 받았다고 하겠습니다. 수신 측은 같은 패리티 묶음을 다시 XOR합니다. p1 검사인 1·3·5·7번은 통과해 s1=0입니다. p2 검사인 2·3·6·7번은 실패해 s2=1이고, p4 검사인 4·5·6·7번도 실패해 s4=1입니다. 검사 결과를 자릿값으로 합치면 s4s2s1=110₂=6입니다. 바로 6번 비트가 잘못됐다는 뜻입니다. 해당 비트를 한 번 뒤집으면 원래 코드워드가 복원됩니다. 모든 검사가 통과해 신드롬이 000이면 단일 오류가 없다고 판단합니다.
이 계산은 우연히 맞는 요령이 아닙니다. 위치 6의 이진수 110은 p2와 p4의 검사에 포함되고 p1 검사에는 포함되지 않음을 나타냅니다. 6번 비트 하나가 바뀌면 정확히 p2와 p4만 실패하므로 실패 패턴이 110으로 되돌아옵니다. 위치 7은 111이므로 세 검사가 모두 실패하고, 위치 3은 011이므로 p1과 p2가 실패합니다. 각 위치가 서로 다른 검사 참여 패턴을 가지는 덕분에 신드롬이 오류 주소 역할을 합니다.
패리티 비트는 몇 개가 필요한가
데이터 비트가 m개이고 해밍 패리티가 r개라면 전체 길이는 n=m+r입니다. 단일 오류 위치 n개와 오류 없음 한 가지를 구별하려면 2ʳ개의 신드롬이 최소 n+1개 상태를 표현해야 합니다. 따라서 2ʳ≥m+r+1 조건을 만족하는 가장 작은 r을 고릅니다. 데이터가 4비트면 r=3일 때 8≥4+3+1이므로 (7,4) 부호가 됩니다. 데이터가 8비트면 r=4일 때 16≥8+4+1이므로 전체 12비트인 구성이 가능합니다. 패리티 수는 데이터 길이와 같은 속도로 늘지 않고 로그에 가깝게 증가합니다.
해밍 거리로 보는 단일 오류 정정
두 비트열에서 서로 다른 위치의 개수를 해밍 거리라고 합니다. 일반 해밍 부호의 최소 해밍 거리는 3입니다. 유효한 코드워드 두 개가 적어도 세 자리에서 다르므로 코드워드 하나에서 한 비트가 바뀌어도 다른 유효 코드워드보다 원래 코드워드에 더 가깝습니다. 최소 거리 d인 부호는 일반적으로 최대 ⌊(d−1)/2⌋개의 오류를 고칠 수 있습니다. d=3이면 단일 오류를 정정할 수 있습니다. 또한 두 비트 오류가 났을 때 수신 비트열이 유효 코드워드가 아니라는 사실을 검출할 수는 있지만, 일반 해밍 디코더가 이를 단일 오류 신드롬으로 오해해 잘못 고칠 수 있다는 점이 중요합니다.
일반 해밍 SEC와 확장 해밍 SECDED의 차이
기본 해밍 부호는 단일 오류 정정, 즉 SEC(Single Error Correction)를 제공합니다. 여기에 코드워드 전체를 검사하는 패리티 비트 하나를 더 붙이면 최소 거리가 4인 확장 해밍 부호가 됩니다. 이 방식은 단일 오류 정정과 이중 오류 검출을 함께 제공해 SECDED(Single Error Correction, Double Error Detection)라고 부릅니다. 모든 해밍 부호가 자동으로 SECDED인 것은 아닙니다. 전체 패리티가 없는 기본형과 추가된 확장형을 구별해야 합니다.
확장형에서는 해밍 신드롬과 전체 패리티를 함께 봅니다. 신드롬이 0이 아니고 전체 패리티도 실패하면 단일 비트 오류로 보고 신드롬 위치를 고칩니다. 신드롬이 0인데 전체 패리티만 실패하면 추가된 전체 패리티 비트 자체의 오류입니다. 신드롬이 0이 아니지만 전체 패리티는 통과하면 두 비트 오류로 판단해 검출만 하고 임의로 고치지 않습니다. 둘 다 통과하면 오류가 없다고 봅니다. 다만 세 비트 이상이 동시에 바뀌면 이 규칙으로 모든 경우를 확실히 구별할 수 없습니다.
체크디지트와 오류 정정 부호는 무엇이 다른가
바코드의 EAN-13 체크디지트나 카드 번호에 쓰이는 룬 알고리즘도 입력 오류를 찾지만 목적과 보장 범위가 다릅니다. 체크디지트는 사람이 번호를 잘못 입력하는 흔한 패턴을 적은 비용으로 검출하도록 설계되며, 보통 잘못된 위치를 알아내서 자동 복구하지는 않습니다. 해밍 부호는 이진 채널에서 정해진 수의 비트 오류를 수학적으로 검출하고 정정하도록 코드워드 사이의 거리를 확보합니다. 저장장치와 메모리, 통신 링크에서 오류 정정 코드가 쓰이는 까닭은 재전송이 어렵거나 오류 위치를 즉시 고쳐야 하는 상황이 있기 때문입니다.
구현할 때 놓치기 쉬운 점
- 위치는 1부터 번호를 매겨 1, 2, 4, 8번을 패리티로 둡니다.
- 짝수 패리티와 홀수 패리티 중 어느 규칙을 쓰는지 송수신 양쪽이 같아야 합니다.
- 신드롬 비트의 순서와 실제 배열의 왼쪽·오른쪽 표기를 혼동하지 않아야 합니다.
- 기본 해밍 부호는 SEC이며, SECDED에는 전체 패리티 비트가 하나 더 필요합니다.
- 두 비트 이상 오류를 임의로 단일 오류처럼 정정하지 않도록 확장형 판정표를 적용합니다.
- 버스트 오류와 다중 오류가 예상되면 더 강한 코드나 인터리빙 등 별도 대책이 필요합니다.
해밍 부호의 핵심은 패리티 비트의 개수보다 배치 원리입니다. 각 위치 번호를 이진수로 보고 1인 자릿값의 패리티 검사에 참여시키면, 실패한 검사들의 합이 오류가 난 위치 번호가 됩니다. 이 구조로 기본형은 비트 하나를 찾아 고칠 수 있고, 전체 패리티를 추가한 확장형은 두 비트 오류까지 구별해 검출할 수 있습니다. ‘2의 거듭제곱 위치’와 ‘신드롬은 오류 주소’라는 두 문장을 기억하면 전체 계산을 다시 구성할 수 있습니다.
오류 검출 능력은 가정한 오류 개수에 달려 있다
SECDED라는 이름은 단일 오류를 고치고 이중 오류를 검출한다는 보장을 말합니다. 세 비트 이상이 바뀌면 신드롬과 전체 패리티가 다른 저중량 오류처럼 보일 수 있어 항상 검출하거나 올바르게 정정한다고 보장할 수 없습니다. 실제 장치에서는 물리적으로 인접한 여러 비트가 한꺼번에 손상되는 버스트 오류도 생길 수 있습니다. 그래서 메모리 칩 사이에 한 코드워드의 비트를 분산하거나, 더 큰 최소 거리를 가진 BCH·리드-솔로몬 같은 부호를 목적에 맞춰 사용합니다. ‘해밍 부호가 오류를 고친다’는 문장에는 몇 비트 오류까지라는 조건이 반드시 붙어야 합니다.
오류 정정에는 저장 공간뿐 아니라 인코딩·검사 회로와 처리 시간도 듭니다. (7,4) 부호는 데이터 4비트에 패리티 3비트를 더하므로 작은 예제에서는 부가 비율이 큽니다. 데이터 블록이 커지면 필요한 패리티 수는 2ʳ≥m+r+1 조건에 따라 천천히 증가합니다. 하지만 부호 길이를 무작정 늘리면 한 코드워드 안에서 여러 오류가 날 가능성도 고려해야 합니다. 시스템 설계에서는 원시 비트 오류율, 오류가 독립적인지 뭉쳐 발생하는지, 재전송 가능 여부와 요구 신뢰도를 함께 보고 부호를 고릅니다.
참고 자료
- NASA Technical Reports Server, (7,4) Hamming Code and SECDED description: https://ntrs.nasa.gov/api/citations/20110008234/downloads/20110008234.pdf
- NIST Special Publication 652, Hamming code parity positions and correction: https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nbsspecialpublication652.pdf