Hamming Code

개요

Hamming Code는 데이터에 여러 개의 parity bit를 삽입하고, 각 parity가 서로 다른 위치 집합을 검사하도록 만든 binary linear block code입니다. 수신 측은 parity 검사 결과를 syndrome으로 묶어 오류가 난 bit의 위치를 계산할 수 있습니다. 일반 Hamming code의 최소 거리는 3이므로 single-bit error를 정정하고 double-bit error를 검출할 수 있지만, 정정을 수행하는 decoder가 double-bit error를 항상 구분할 수는 없습니다.

메모리 시스템에서는 Hamming code에 전체 parity bit를 하나 더한 extended Hamming code가 널리 알려진 SECDED(Single-Error Correction, Double-Error Detection) 모델을 이룹니다. 예를 들어 64-bit data word에 7개의 위치 parity와 1개의 overall parity를 더하면 72-bit codeword가 되며, 이는 전통적인 ECC DIMM의 64+8 구성과 연결됩니다. 다만 실제 서버 controller는 Hamming과 동등한 확장 코드, Hsiao Code, symbol-based ECC 등을 선택할 수 있으므로 "ECC DIMM = 항상 동일한 Hamming 행렬"로 해석하면 안 됩니다.

그림 1. Hamming(7,4)의 위치 parity와 overall parity를 extended codeword로 확장한 예입니다. 위치 parity의 검사 결과는 syndrome을 만들고, overall parity는 single-bit와 double-bit 오류를 구분하는 추가 정보가 됩니다.

핵심 개념

코드 파라미터와 Hamming distance

[n, k, d] 표기에서 n은 codeword 전체 bit 수, k는 data bit 수, d는 codeword 사이의 최소 Hamming distance입니다. parity bit가 r개일 때 임의의 single-bit error 위치와 no-error 상태를 구별하려면 다음 조건이 필요합니다.

2^r >= k + r + 1

일반적인 완전 Hamming code는 n = 2^r - 1, k = 2^r - r - 1, d = 3인 형태입니다. 여기에 codeword 전체를 한 번 더 검사하는 overall parity bit를 추가하면 최소 거리가 4가 되어 extended Hamming code가 됩니다.

최소 거리 4는 두 bit 오류와 한 bit 오류를 decoder가 구분할 수 있게 해 줍니다. 단, 세 bit 이상 오류까지 항상 검출하거나 올바르게 정정한다는 뜻은 아닙니다. 일부 세 bit 오류는 single-bit 오류처럼 보일 수 있으므로, SECDED의 보장 범위를 넘어서는 오류 모델에는 별도 code나 retry 정책이 필요합니다.

위치 parity와 검사 범위

bit 위치를 1부터 세고, 2의 거듭제곱인 위치를 parity bit로 예약합니다. 따라서 Hamming(7,4)의 배치는 다음과 같습니다.

위치       1   2   3   4   5   6   7
내용      p1  p2  d1  p4  d2  d3  d4
이진 위치   001 010 011 100 101 110 111

각 parity bit는 자신의 위치 bit가 1인 모든 위치를 검사합니다.

이 배치에서는 각 codeword bit가 고유한 parity 조합에 참여합니다. 따라서 검사 실패가 p1과 p4에서 발생하면 1 + 4 = 5로 bit 5를 가리키는 식으로 오류 위치를 숫자로 복원할 수 있습니다. 실제 구현에서는 이 과정을 parity-check matrix H와 XOR 네트워크로 표현합니다.

패리티 방식과 행렬

이 문서의 예는 even parity를 사용합니다. 각 검사 집합의 1의 개수가 짝수가 되도록 parity bit를 설정하며, odd parity를 사용해도 encoder와 decoder가 같은 규칙을 따르면 기능은 동일합니다.

수신 vector를 r이라 할 때 syndrome은 다음처럼 계산합니다.

s = H * r^T   (연산은 GF(2), 즉 XOR)

정상 codeword는 s = 0입니다. 한 bit 오류가 위치 i에서 발생하면 syndrome은 parity-check matrix의 i번째 열이 되며, 표준 위치 배치에서는 그 열을 위치 i의 이진 표현으로 읽을 수 있습니다. 두 개 이상의 오류에서는 여러 열의 XOR가 되므로 single-bit 위치로 단정하면 안 됩니다.

Systematic form에서는 data와 parity를 나누어 다음처럼 표현할 수 있습니다.

H = [ A | I_r ]
P = A * D^T

A는 data bit가 각 parity 식에 참여하는 연결을 나타내고 I_r은 parity bit 자신을 검사하는 항입니다. Hamming의 표준 위치 배치는 설명과 생성이 쉽고, Hsiao Code는 같은 SECDED 목표를 더 낮은 XOR 연결 수와 균형 잡힌 행렬로 구현하려는 변형입니다.

Syndrome과 오류 모델

syndrome은 오류가 있다는 사실보다 오류 위치를 표현하는 정보입니다. 다만 syndrome만으로는 오류 개수가 single인지 double인지 알 수 없기 때문에 extended Hamming에서는 overall parity 결과를 함께 사용합니다.

이 표는 최대 두 bit 오류라는 가정에서의 SECDED 판정표입니다. S != 0, P0 = 0을 모든 다중 오류의 정확한 진단으로 확대하면 안 되며, 세 bit 이상 오류에 대해서는 miscorrection 가능성이 남습니다.

비교/분석

ECC 방식 비교

Hamming과 Hsiao의 차이

Hamming code와 Hsiao Code는 모두 SECDED의 수학적 목표를 달성할 수 있지만 parity-check matrix를 만드는 방법이 다릅니다. 표준 Hamming은 위치의 이진 표현을 열로 사용하므로 규칙성이 좋습니다. Hsiao는 서로 다른 odd-weight 열을 선택해 같은 data 폭에서 XOR 연결 수와 fan-in을 줄이는 방향을 취합니다.

Hsiao의 상세 행렬 선택은 Hsiao Code 문서에서 다룹니다. Hsiao로 바꾼다고 chip-level failure나 burst error가 자동으로 정정되는 것은 아니며, 이런 오류에는 symbol mapping과 더 강한 code가 필요합니다.

DRAM ECC 계층 비교

Linux EDAC 문서는 일반적인 memory stick이 controller가 기대하는 64-bit data에 8-bit ECC를 더해 72-bit 폭을 구성한다고 설명합니다. 이는 물리적인 x4/x8 device 그룹화와 연계되지만, DDR 세대와 controller의 실제 mapping이 모두 같다는 의미는 아닙니다. DDR5 on-die ECC 역시 외부 side-band ECC와 보호 위치가 다르므로 두 계층을 하나의 Hamming decoder로 간주하면 안 됩니다.

오버헤드와 적용 기준

64-bit data에 8-bit check를 추가하는 대표 구성의 raw storage 오버헤드는 8/64 = 12.5%입니다. 실제 성능 영향은 ECC bit 전송 폭, controller pipeline, 오류가 없는 fast path, scrub 및 retry 정책에 따라 달라지므로 "ECC는 항상 12.5% 성능 저하"라고 해석하면 안 됩니다.

동작 원리

그림 2. 메모리 controller의 대표적인 외부 SECDED 경로입니다. write path에서는 data에서 check bit를 만들고, read path에서는 syndrome과 overall parity를 계산한 뒤 정정 또는 UE 경로를 선택합니다.

Hamming(7,4) 인코딩

[p1, p2, d1, p4, d2, d3, d4] 순서와 even parity를 사용하면 parity 식은 다음과 같습니다.

p1 = d1 XOR d2 XOR d4
p2 = d1 XOR d3 XOR d4
p4 = d2 XOR d3 XOR d4

예를 들어 data가 d1 d2 d3 d4 = 1 0 1 1이면 다음과 같이 계산됩니다.

p1 = 1 XOR 0 XOR 1 = 0
p2 = 1 XOR 1 XOR 1 = 1
p4 = 0 XOR 1 XOR 1 = 0

Hamming(7,4) codeword = 0 1 1 0 0 1 1
overall parity p0 = 0
Extended codeword   = 0 1 1 0 0 1 1 0

이 예에서 7-bit Hamming codeword의 1 개수는 4개이므로 overall parity는 0입니다. 실제 interface는 bit를 직렬로 보내는지, byte/lane에 어떤 순서로 배치하는지에 따라 표시 순서가 달라질 수 있으므로, 설계 문서에서는 논리 위치와 물리 lane mapping을 구분해야 합니다.

Syndrome 계산과 single-bit 정정

수신한 7-bit 부분 codeword를 r1..r7이라 하면 positional syndrome의 세 bit는 다음과 같습니다.

s1 = r1 XOR r3 XOR r5 XOR r7
s2 = r2 XOR r3 XOR r6 XOR r7
s4 = r4 XOR r5 XOR r6 XOR r7
S  = s1 + 2*s2 + 4*s4

위의 정상 codeword에서 bit 6이 뒤집히면 수신 값은 0 1 1 0 0 0 1이 됩니다.

s1 = 0
s2 = 1
s4 = 1
S  = 0b110 = 6

전체 8-bit를 XOR한 overall parity 결과는 1입니다. 따라서 S=6은 위치 6의 single-bit error를 가리키고, decoder는 해당 bit를 반전한 뒤 data 1011을 복원합니다. 오류가 p0에서만 발생하면 S=0, P0=1이므로 data bit를 건드리지 않고 overall parity bit만 수정합니다.

SECDED decoder 의사코드

다음은 논리 동작을 보여주는 설명용 의사코드입니다. 실제 RTL에서는 XOR tree의 fan-in, pipeline latency, bit ordering, CE/UE logging과 reset을 별도로 설계해야 합니다.

decode(received[1..7], p0):
    s1 = XOR(received[1], received[3], received[5], received[7])
    s2 = XOR(received[2], received[3], received[6], received[7])
    s4 = XOR(received[4], received[5], received[6], received[7])
    syndrome = s1 | (s2 << 1) | (s4 << 2)
    overall = XOR(received[1..7], p0)

    if syndrome != 0 and overall == 1:
        flip(received[syndrome])  # single-bit 오류를 정정하고 CE 기록
        report_corrected()
    elif syndrome == 0 and overall == 1:
        flip(p0)                  # overall parity bit 오류를 정정
        report_corrected()
    elif syndrome != 0 and overall == 0:
        report_uncorrectable()    # SECDED 모델에서 정정 불가 오류 보고
    else:
        pass                      # 오류 없음

syndrome != 0, overall == 0인 경우에는 오류가 두 bit라는 확정 진단보다 "SECDED가 정정할 수 없는 오류"로 처리하는 것이 안전합니다. 정확히 두 bit 오류라는 가정 아래에서는 double-bit error가 여기에 해당하지만, 더 많은 오류가 들어오면 같은 판정 패턴이 다른 오류 조합에서도 나올 수 있습니다.

64-bit DRAM ECC write/read 경로

64-bit data word에 대해 r=7개의 위치 parity가 조건 2^7 >= 64+7+1을 만족합니다. 여기에 overall parity를 하나 추가하면 8개의 check bit가 필요합니다.

Write path

1. memory controller가 CPU/cache line에서 보호할 64-bit data word를 받습니다.
2. parity-check matrix의 data 부분 A를 사용해 7개 positional parity를 XOR 계산합니다.
3. data와 7개 parity의 전체 XOR로 overall parity를 계산합니다.
4. 64 data + 8 check = 72-bit 논리 codeword를 DIMM의 data/ECC device 그룹에 기록합니다.

Read path

1. controller가 data와 check bit를 함께 읽어 72-bit 수신 word를 만듭니다.
2. parity XOR network가 positional syndrome과 overall parity를 병렬 계산합니다.
3. syndrome이 한 위치를 가리키고 overall parity가 odd이면 해당 bit를 반전합니다.
4. syndrome이 0이고 overall parity만 odd이면 overall parity bit 오류로 처리합니다.
5. double-bit로 분류되거나 correction 검증에 실패하면 data를 정상으로 전달하지 않고 UE/UCE, retry, poisoning 등의 RAS 정책으로 보냅니다.
6. 정정된 line은 CE counter와 주소·rank·device 위치를 기록하고, patrol scrub으로 재기록할 수 있습니다.

DRAM 적용 시 주의점

Hamming code가 제공하는 것은 논리 codeword 단위의 오류 정정입니다. 물리적인 DRAM device 고장을 정정하려면 다음 요소를 함께 정의해야 합니다.

• device 폭: x4 또는 x8 device의 한 출력이 codeword의 몇 bit/symbol에 매핑되는가
• codeword 범위: 하나의 burst, cache line, rank 접근 중 어디까지를 한 codeword로 묶는가
• interleaving: 한 물리 사건이 하나의 codeword에 집중되는가, 여러 codeword로 나뉘는가
• 오류 위치 정보: controller가 device timeout이나 link error를 erasure 위치로 알 수 있는가
• RAS 처리: CE/UE logging, scrub, retry, page offlining, spare device 정책을 어떻게 연결하는가

한 x4 DRAM device의 여러 출력이 하나의 codeword에 포함되면 단일 device failure가 여러 bit 오류로 나타날 수 있습니다. 이 오류가 SECDED의 두 bit 한계를 넘으면 Hamming code는 충분하지 않습니다. 이 경우 symbol-based ECC, Reed-Solomon, Chipkill 또는 다차원 parity가 필요하며, 어떤 기법을 선택하더라도 codeword와 device mapping을 함께 분석해야 합니다.

On-die ECC와 외부 SECDED의 경계

DDR5 on-die ECC는 DRAM die 내부의 cell array 저장 오류를 내부에서 처리하는 계층입니다. 반면 외부 side-band ECC는 memory controller가 DIMM에서 수신한 data와 check bit를 검사해 link·device·패키지 수준 오류를 다루는 계층입니다. on-die correction의 내부 syndrome과 정정 횟수는 일반적으로 controller가 직접 관찰하는 외부 SECDED syndrome과 다릅니다.

따라서 다음 두 문장은 서로 다른 주장입니다.

• "DRAM die 내부에서 일부 cell 오류를 on-die ECC로 보정한다."
• "controller가 64-bit data와 8-bit check를 사용해 외부 codeword를 SECDED로 검사한다."

두 계층을 함께 사용하면 보호 범위를 넓힐 수 있지만, on-die ECC가 외부 ECC를 자동으로 대체하거나 외부 Hamming decoder가 on-die 오류를 모두 보고한다고 가정하면 안 됩니다.

장단점

Hamming/SECDED는 오류가 드물고 single-bit 오류가 주된 메모리 read path에서 latency와 회로 비용의 균형이 좋습니다. 반대로 DRAM device 단위 장애나 높은 오류율 채널을 보호하려면 code 강도뿐 아니라 symbol mapping, interleaving, spare, retry를 포함한 시스템 설계가 필요합니다.

관련 기술

관련 문서

• ECC Error Correction: DRAM ECC 계층, SECDED, scrubbing의 개요
• Hsiao Code: SECDED parity-check matrix의 하드웨어 최적화
• Reed-Solomon Code: symbol 오류·erasure·Chipkill 설계
• DRAM 테스트/신뢰성: ECC, CE/UE, BIST와 scrub 운영
• DDR 내부 구조: rank·device·channel 데이터 경로
• Linux Memory EDAC: Linux 메모리 오류 관리의 배경

참고 문헌

Google의 현장 연구는 수백만 DIMM-day 규모의 관측에서 연간 8%를 넘는 DIMM이 오류를 경험하고, 관측된 오류율과 오류 유형이 당시의 단순한 soft-error 가정과 다를 수 있음을 보고했습니다. 이 결과는 Hamming code의 수학적 정정 범위와 별개로, CE 누적 관찰·scrub·모듈 교체 같은 RAS 운영이 필요한 이유를 보여줍니다.

핵심 정리

Hamming Code는 parity bit의 검사 결과인 syndrome으로 single-bit 오류 위치를 계산하는 binary linear block code입니다. 기본 Hamming code의 최소 거리는 3이며, overall parity를 추가한 extended Hamming code는 최소 거리 4의 SECDED 동작을 제공합니다. 64-bit data에 7개의 위치 parity와 1개의 overall parity를 더한 72-bit codeword는 전통적인 외부 DRAM ECC의 대표 모델이지만, 실제 controller는 Hsiao나 symbol-based ECC를 사용할 수도 있습니다. Hamming/SECDED만으로 DRAM chip failure와 다중 symbol 오류를 해결할 수 없으므로 device mapping, interleaving, RAS logging, scrub 및 더 강한 ECC 계층을 함께 검토해야 합니다.