해밍 코드 오류 정정 설명(수식 포함)

Hamming(7,4)을 인코딩하고, 신드롬을 계산해 모든 단일 비트 위치를 정정하며, SECDED로 확장하고, 한계를 과장하지 않고 디코더를 검증하는 방법을 알아봅니다.

Denny

2026년 5월 7일약 7분 소요

Chalkboard feature illustration for “해밍 코드 오류 정정 설명(수식 포함)”

요약: Hamming(7,4)은 네 데이터 비트를 일곱 위치에 배치합니다. 세 개의 패리티 검사는 각 위치에 고유한 0이 아닌 3비트 열을 부여하므로, 한 비트가 뒤집히면 그 위치의 이진 인덱스와 같은 신드롬이 생깁니다. 디코더는 그 비트를 반전해 정정할 수 있습니다. 일반 Hamming(7,4)은 이중 비트 오류를 일부 단일 비트 오류와 구별할 수 없지만, 전체 패리티 비트를 추가하면 가정한 오류 한도 안에서 SECDED로 확장할 수 있습니다.

패리티 비트는 홀수 개 위치가 바뀌었다는 사실은 알릴 수 있지만, 어느 위치인지는 식별하지 못합니다. 해밍의 구성은 서로 겹치는 여러 패리티 검사를 사용합니다. 실패한 검사의 패턴인 신드롬은 주소처럼 작동합니다.

이 아이디어가 강력한 이유는 인코더, 검사기, 정정기를 모두 XOR 네트워크와 복호 논리로 만들 수 있기 때문입니다. 동시에 엄격한 경계도 있습니다. 확장 코드가 검사를 하나 더 추가하지 않는 한, 익숙한 정정 규칙은 보호 블록 안의 오류가 최대 하나라고 가정합니다.

비트 위치 배치

코드워드 위치는 1부터 번호를 매기고, 2의 거듭제곱 위치에 패리티를 둡니다.

위치	1	2	3	4	5	6	7
역할	$P_1$	$P_2$	$D_1$	$P_4$	$D_2$	$D_3$	$D_4$
이진 인덱스	001	010	011	100	101	110	111

각 패리티 검사는 이진 위치의 한 비트에 대응합니다.

$P_1$ 은 인덱스의 비트 0이 설정된 위치, 즉 1, 3, 5, 7을 포괄합니다.
$P_2$ 는 인덱스의 비트 1이 설정된 위치, 즉 2, 3, 6, 7을 포괄합니다.
$P_4$ 는 인덱스의 비트 2가 설정된 위치, 즉 4, 5, 6, 7을 포괄합니다.

모든 위치에는 고유한 0이 아닌 소속 패턴이 있습니다. 예를 들어 위치 5는 $5=101_2$ 이므로 검사 1과 4에 속합니다.

이 1부터 시작하는 관례는 편리할 뿐 신비로운 것은 아닙니다. 패리티 검사 행렬의 열은 단순히 1부터 7까지의 이진 레이블입니다.

짝수 패리티로 인코딩하기

각 패리티 비트는 자신이 포괄하는 전체 집합의 XOR이 0이 되도록 선택합니다.

P_1=D_1\oplus D_2\oplus D_4

P_2=D_1\oplus D_3\oplus D_4

P_4=D_2\oplus D_3\oplus D_4

이 식은 코드를 체계적으로 만듭니다. 원래 데이터는 위치 3, 5, 6, 7에 그대로 나타나고, 나머지 위치에는 패리티가 들어갑니다.

기대 검사값을 일관되게 바꾸면 홀수 패리티도 사용할 수 있습니다. 짝수 패리티에서는 모든 유효 코드워드의 신드롬이 0이므로 선형대수 형태가 특히 직접적입니다.

인코딩 예제: 데이터 1011

다음과 같이 둡니다.

D_1=1,\quad D_2=0,\quad D_3=1,\quad D_4=1

그러면 다음과 같습니다.

P_1=1\oplus0\oplus1=0

P_2=1\oplus1\oplus1=1

P_4=0\oplus1\oplus1=0

그 값을 일곱 위치에 배치합니다.

위치	1	2	3	4	5	6	7
역할	$P_1$	$P_2$	$D_1$	$P_4$	$D_2$	$D_3$	$D_4$
비트	0	1	1	0	0	1	1

위치 1부터 위치 7까지 읽으면 코드워드는 다음과 같습니다.

일부 문헌은 코드워드를 반대 방향으로 표시합니다. 위치 관례를 명확히 정하고 일관되게 사용한다면 산술은 그대로 유효합니다.

신드롬 계산하기

수신 위치를 $R_1$ 부터 $R_7$ 까지라 하고, 전체 패리티 검사를 다시 계산합니다.

S_1=R_1\oplus R_3\oplus R_5\oplus R_7

S_2=R_2\oplus R_3\oplus R_6\oplus R_7

S_4=R_4\oplus R_5\oplus R_6\oplus R_7

신드롬은 다음과 같이 해석합니다.

S=(S_4S_2S_1)_2

변하지 않은 유효 코드워드에서는 $S=000$ 입니다. 정확히 한 위치 $i$ 가 뒤집히면, $i$ 를 포괄하는 각 검사가 토글됩니다. 그 결과 신드롬은 위치 $i$ 에 할당된 이진 열이 됩니다.

위치 5의 뒤집힘 정정하기

인코딩 예제에서 위치 5를 뒤집습니다.

sent:     0 1 1 0 0 1 1
received: 0 1 1 0 1 1 1
position: 1 2 3 4 5 6 7

이제 다음과 같습니다.

S_1=0\oplus1\oplus1\oplus1=1

S_2=1\oplus1\oplus1\oplus1=0

S_4=0\oplus1\oplus1\oplus1=1

따라서 다음이 됩니다.

S_4S_2S_1=101_2=5

단일 오류 가정하에서는 수신한 위치 5를 반전합니다. 정정된 워드는 다시 0110011이 되고, 위치 3, 5, 6, 7에서 데이터 1011을 얻습니다.

패리티 위치의 뒤집힘도 같은 방식으로 처리됩니다. 위치 2가 바뀌면 신드롬은 010이고, 정정기는 위치 2를 반전합니다.

행렬 관점

코드워드 벡터를 다음과 같이 두면

\mathbf r=[R_1\ R_2\ R_3\ R_4\ R_5\ R_6\ R_7]^T

하나의 패리티 검사 행렬은 다음과 같습니다.

H= \begin{bmatrix} 1&0&1&0&1&0&1\\ 0&1&1&0&0&1&1\\ 0&0&0&1&1&1&1 \end{bmatrix}

신드롬은 다음과 같습니다.

\mathbf s=H\mathbf r\pmod 2

H의 $i$ 번째 열은 $i$ 의 이진 표현을 $(S_1,S_2,S_4)^T$ 순서로 배열한 것입니다. 따라서 위치 $i$ 에 1이 있는 단일 비트 오류 벡터는 정확히 $i$ 번째 열을 반환합니다.

이 공식은 겹치는 원을 외우는 것보다 더 깔끔하게 확장됩니다. 또한 두 유효 코드워드를 XOR하면 또 다른 유효 코드워드가 된다는 선형성도 분명하게 보여 줍니다.

일반 해밍 코드가 두 오류를 안전하게 정정할 수 없는 이유

Hamming(7,4)의 최소 해밍 거리는 다음과 같습니다.

d_{\min}=3

최소 거리가 $d_{\min}$ 인 코드는 다음을 할 수 있습니다.

유효/무효만 판정할 경우 최대 $d_{\min}-1$ 개의 임의 오류를 검출하거나
가장 가까운 코드워드를 선택하여 최대 $\left\lfloor(d_{\min}-1)/2\right\rfloor$ 개의 오류를 정정할 수 있습니다.

따라서 Hamming(7,4)은 하나의 오류를 정정할 수 있습니다. 정정을 시도하지 않는다면 두 비트 손상도 “코드워드가 아님”으로 검출할 수 있습니다. 하지만 0이 아닌 3비트 신드롬만으로는 그것이 하나의 오류에서 왔는지, 특정 두 오류의 쌍에서 왔는지를 알 수 없습니다.

표준 단일 오류 디코더가 이중 비트 오류를 보면, 두 오류 위치 열의 XOR은 세 번째 0이 아닌 열과 같습니다. 디코더는 그 세 번째 위치를 반전하여 전송된 코드워드와 세 비트만큼 다른 결과를 만듭니다. 이것은 이중 오류 정정이 아니라 오정정입니다.

항상 디코더가 가정하는 오류 모델을 명시해야 합니다. “신드롬이 0이 아니므로 그 위치를 뒤집는다”는 규칙은 시스템이 보호된 위치 중 잘못된 것이 최대 하나라고 확립한 경우에만 유효합니다.

확장 해밍 코드와 SECDED

7비트 해밍 워드 전체에 걸쳐 전체 패리티 비트 $P_0$ 를 추가합니다. 8비트 확장 코드는 $d_{\min}=4$ 이며, 코드워드에 오류가 둘 이하라는 가정 아래 단일 오류 정정, 이중 오류 검출(SECDED)을 지원합니다.

다음을 계산합니다.

위치 1–7에서 얻는 원래의 3비트 신드롬 S
수신한 8개 위치 전체의 전체 패리티 검사 P

짝수 전체 패리티의 경우는 다음과 같습니다.

신드롬 S	전체 검사 P	0–2개 오류에서의 해석	동작
000	0	오류 없음	수락
0이 아님	1	위치 1–7에 오류 하나	위치 S 정정
000	1	전체 패리티 위치 오류	정정하거나 패리티 비트 오류 보고
0이 아님	0	오류 둘	정정 불가로 보고, 단일 오류 정정 금지

이 조건은 중요합니다. 오류가 셋 이상이면 다른 표의 행을 흉내 낼 수 있습니다. SECDED는 무제한 오류 검출기가 아닙니다.

실제 메모리 및 통신 시스템은 단축 해밍 코드, 인터리빙, 심볼 지향 코드, BCH 또는 Reed–Solomon 코드, 저밀도 패리티 검사 코드, 곱 코드, 독점 방식을 사용할 수 있습니다. 보이는 데이터 폭과 검사 비트 폭만으로 시스템의 ECC 기능을 추론하지 마십시오.

일반 해밍 코드 크기 결정

$m$ 개의 데이터 비트와 $r$ 개의 해밍 패리티 비트에서는, 각 코드워드 위치와 오류 없음 상태에 필요한 모든 신드롬 패턴을 충분히 표현할 수 있어야 합니다.

2^r\ge m+r+1

완전 길이 이진 해밍 계열은 다음을 사용합니다.

n=2^r-1

k=n-r=2^r-r-1

패리티 비트 r	코드 길이 n	데이터 비트 k	완전 코드
3	7	4	Hamming(7,4)
4	15	11	Hamming(15,11)
5	31	26	Hamming(31,26)
6	63	57	Hamming(63,57)

단축 변형은 검사 구조를 유지하면서 선택된 데이터 위치를 생략합니다. 확장 변형은 전체 패리티 비트를 추가하여 거리를 3에서 4로 늘립니다.

오버헤드를 말할 때는 분모를 밝혀야 합니다. Hamming(7,4)은 데이터 비트 4개마다 검사 비트 3개를 추가합니다. 이는 페이로드 기준으로 75%의 오버헤드이고, 전송 워드에서는 3/7입니다. Hamming(63,57)은 6/57, 즉 페이로드 기준 약 10.5%를 추가하며, 검사 비트는 코드워드의 6/63, 약 9.5%를 차지합니다.

하드웨어 아키텍처

간단한 체계적 구현은 네 단계로 이루어집니다.

data ─▶ parity generator ─▶ codeword
                              │
received word ─▶ check matrix ─▶ syndrome
                                      │
                       syndrome decoder ─▶ one-hot flip mask
received word ─────────────────────────── XOR ─▶ corrected word ─▶ extract data

Hamming(7,4)의 경우는 다음과 같습니다.

인코더는 세 개의 패리티 식을 계산합니다.
검사기는 세 개의 신드롬 식을 계산합니다.
3-to-8 디코더는 원-핫 위치 마스크를 만들 수 있으며, 출력 0은 정정이 없음을 뜻합니다.
일곱 개의 XOR 게이트가 그 마스크를 적용합니다.
배선이 위치 3, 5, 6, 7을 추출합니다.

정확한 게이트 수와 타이밍은 XOR 트리 인수분해, 공유 항, 셀 라이브러리, FPGA 매핑에 따라 달라집니다. 폭이 넓은 디코더는 신드롬 계산과 정정을 파이프라인으로 나눌 수 있습니다. 플래그 또는 상태 레지스터가 “정정됨”과 “정정 불가”를 보고한다면, 그 신호들을 해당 데이터 파이프라인 단계와 정렬하십시오.

검증 계획

7비트 코드의 경우는 다음과 같습니다.

가능한 데이터 입력 16개를 모두 인코딩합니다.
인코딩된 모든 워드의 신드롬이 0인지 확인합니다.
각 코드워드에서 일곱 위치를 각각 개별적으로 뒤집습니다.
신드롬이 뒤집힌 위치와 같은지 확인합니다.
정정을 적용하고 16×7개의 모든 경우가 원래 데이터를 복구하는지 확인합니다.
대표적인 이중 비트 오류를 주입해 일반 단일 오류 디코더가 왜 오정정하는지 보입니다.

확장 8비트 버전의 경우는 다음과 같습니다.

전체 패리티 위치를 포함해 모든 단일 위치 테스트를 반복합니다.
각 데이터 워드에 대해 $\binom82=28$ 개의 모든 두 위치 패턴을 테스트합니다.
모든 쌍이 정정 불가로 보고되고 어느 것도 단일 오류로 정정되지 않는지 확인합니다.
S != 0이고 전체 패리티가 불일치할 때만 정정이 활성화된다는 어설션을 추가합니다.

기능 시뮬레이션은 테스트하거나 완전 열거한 비트 패턴에 대해 구현된 진리표를 증명합니다. 그러나 물리적 소프트 오류율을 제공하거나, 고장의 독립성을 확립하거나, 시스템 수준 신뢰성 분석을 대체하지는 않습니다.

흔한 설계 실수

위치를 0부터 번호 매기면서 신드롬은 여전히 1부터 시작하는 주소로 해석하는 실수.
관례를 문서화하지 않고 워드를 역순으로 표시하는 실수.
짝수 패리티 인코딩과 홀수 패리티 검사를 섞는 실수.
오류 수의 한계를 정하지 않고 0이 아닌 모든 신드롬을 정정하는 실수.
SECDED가 가중치 3 이상인 모든 오류를 검출한다고 여기는 실수.
검사 비트와 전체 패리티 비트도 실패할 수 있음을 잊는 실수.
서로 다른 분모를 쓰는 “오버헤드 비율”을 비교하는 실수.
ECC라고 표시된 모든 제품이 같은 코드를 구현한다고 가정하는 실수.

Hamming(7,4)이 가치 있는 이유는 전체 메커니즘이 보이기 때문입니다. 고유한 패리티 검사 열은 1비트 결함을 주소로 바꿉니다. 이를 이해하면 일반 패리티는 한 행짜리 검사 행렬로 보이고, 더 강한 블록 코드는 명시적 결함 모델에 맞춘 구조적 중복이라는 같은 핵심 아이디어의 더 큰 버전이 됩니다.

참고 문헌

R. W. Hamming, 「오류 검출 및 오류 정정 코드」, 벨 시스템 기술 저널, 1950