한양과학기술고등학교

에듀테크 프로젝트 대시보드

해밍 코드 (Hamming Code)

해밍 코드 (Hamming Code / 오류 검출·정정)

전선·디스크·우주 통신에서 비트는 잡음 때문에 가끔 뒤집힌다(0↔1). 단순 패리티 1비트는 "오류가 났다"까지만 알려줄 뿐 어디가 틀렸는지는 모른다. 1950년 리처드 해밍은 패리티 비트 여러 개를 겹치게 배치해서, 오류가 난 위치를 이진수로 짚어내 스스로 고치는 코드를 만들었다. 아래는 데이터 4비트 + 패리티 3비트로 이루어진 Hamming(7,4) 코드다.

Hamming(7,4) 인코더 · 채널 · 디코더

데이터 4비트:

수신된 코드워드 — 아무 비트나 눌러 잡음(비트 뒤집기)을 넣어 보세요

데이터 비트를 바꾸면 패리티 p1·p2·p4 가 자동으로 다시 계산됩니다.
전송 코드워드
–
신드롬 (p4 p2 p1)
000
지목된 오류 위치
없음

왜 고칠 수 있나 — 3원 벤 다이어그램

각 원은 패리티 하나의 "감시 구역"이다. 규칙: 원 안의 1의 개수는 항상 짝수가 되도록 패리티 비트를 정한다. 비트 하나가 뒤집히면, 그 비트가 든 원들만 "홀수"가 되어 경보(1) 를 울린다. 울린 원들의 교집합이 딱 한 칸 — 바로 거기가 오류다.

C1 = p1·d1·d2·d4  ·  C2 = p2·d1·d3·d4  ·  C3 = p4·d2·d3·d4

핵심 아이디어: 위치 = 신드롬

패리티 비트는 2의 거듭제곱 자리(1, 2, 4)에 놓고, 자기 자리 비트가 켜진 위치만 감시한다
위치1
001		2
010		3
011		4
100		5
101		6
110		7
111
내용p1p2d1p4d2d3d4
p1 감시 (…1)✓·✓·✓·✓
p2 감시 (…1.)·✓✓··✓✓
p4 감시 (1..)···✓✓✓✓
  • 디코더는 세 패리티를 각각 다시 검사해 어긋나면 1, 맞으면 0 을 적는다 → s = (s4 s2 s1).
  • 이 신드롬 s를 이진수로 읽으면 그대로 오류가 난 위치가 된다. s=000 이면 오류 없음, s=101 이면 5번 비트를 뒤집어 정정.
  • 패리티를 1·2·4번 에 둔 이유: 각 위치 번호의 이진 표현에서 켜진 자리 = 그 위치를 감시하는 패리티. 겹침이 유일해진다.
  • 한계: Hamming(7,4)는 1비트 오류는 정정, 2비트 오류는 "뭔가 틀렸다"까지만(엉뚱한 위치를 고칠 수 있음). 전체 패리티 1비트를 더한 SECDED (8,4) 는 2비트 검출까지 가능.

파이썬으로 보는 인코딩 & 정정

# 위치 1..7, 패리티는 1·2·4번 자리 (1-index)
def encode(d1, d2, d3, d4):
    bits = [0]*8                      # bits[1..7] 사용
    bits[3], bits[5], bits[6], bits[7] = d1, d2, d3, d4
    for p in (1, 2, 4):        # 감시 위치의 XOR 이 0이 되도록
        bits[p] = 0
        bits[p] = reduce(xor, (bits[i] for i in range(1, 8) if i & p))
    return bits[1:]

def decode(recv):                   # recv: 길이 7 리스트
    b = [0] + list(recv)
    syndrome = 0
    for p in (1, 2, 4):
        if reduce(xor, (b[i] for i in range(1, 8) if i & p)):
            syndrome += p            # 어긋난 패리티의 자리값을 더한다
    if syndrome:                     # 0이 아니면 그 위치를 뒤집어 복구
        b[syndrome] ^= 1
    return [b[3], b[5], b[6], b[7]], syndrome
  • i & p 트릭: 위치 번호 i 의 이진수에 패리티 자리 p 가 켜져 있으면 그 패리티가 감시한다는 뜻.
  • 실제 RAM의 ECC 메모리, QR 코드(리드-솔로몬), 위성·우주선 통신이 모두 이런 오류 정정 코드 위에서 돌아간다.