패리티비트와 해밍코드

패리티비트

목적

• 오류 검출이 목적 (detEction).
• 데이터 비트들의 합(1의 개수)을 기준으로 짝수 또는 홀수가 되도록 맞춘다.

방법 (짝수/홀수 패리티)

• 데이터 비트들의 1의 개수를 세서 짝수(또는 홀수)가 되도록 패리티 비트를 1개 붙임.
• 짝수 패리티: 전체(데이터+패리티)의 1의 개수가 짝수가 되게 함
• 홀수 패리티: 전체 1의 개수가 홀수가 되게 함

예) 데이터 1011 (1의 개수=3, 홀수)

• 짝수 패리티 → 패리티 비트 1을 붙여 1011|1 (전체 1의 개수=4, 짝수)
• 홀수 패리티 → 패리티 비트 0을 붙여 1011|0 (전체 1의 개수=3, 홀수 유지)

오류 검출 원리

• 전송/저장 후 전체 1의 개수를 다시 세서, 약속(짝수/홀수)과 다르면 오류 발생으로 판단.

한계점

• 단일 비트 오류(1개 flip)는 탐지 가능
• 하지만 2개 이상의 오류는 탐지 못함
• 오류의 위치는 알 수 없어서 수정은 불가능

그래서 더 고급 기법이 나온 것이 해밍 코드.

---

해밍코드

목적

• 단일 비트 오류 정정(Single Error Correction = SEC) + 이중 비트 오류 검출(Double Error Detection = DED).
• 즉, 어디가 틀렸는지 위치까지 계산해서 고칠 수 있음.

방법

• 데이터 비트들 사이사이에 여러 개의 패리티 비트(검사 비트)를 배치.
• 각 패리티 비트는 서로 다른 비트 집합을 “감시”하고, 이상이 생기면 값이 뒤집혀 오류 위치를 이진수로 가리킴

대표 형식: Hamming(7,4)

• 4비트 데이터 → 3개의 패리티 비트를 추가해 총 7비트 전송(저장).
• 비트 위치 번호를 1부터 매기고, 2의 제곱수 위치(2^0부터)를 패리티 비트 자리로 사용:
  • 위치 1 → p1
  • 위치 2 → p2
  • 위치 4 → p3
• 나머지 자리(3,5,6,7)에 데이터 비트 d1,d2,d3,d4 배치.

배치 예

위치:  1   2   3   4   5   6   7
비트:  p1  p2  d1  p3  d2  d3  d4

패리티 계산 규칙(짝수 패리티 가정)

• p1은 1이 들어간 위치들(1,3,5,7)의 비트 합이 짝수가 되게
• p2는 2가 들어간 위치들(2,3,6,7)의 비트 합이 짝수가 되게
• p3는 4가 들어간 위치들(4,5,6,7)의 비트 합이 짝수가 되게

k=2^(n-1)일 때, n번째 패리티비트는 k번째 수부터 k개 그 후 k개를 건너뛴 뒤 k개의 비트 합이 짝수가 되게 한다. 즉, 각 p는 자신이 커버하는 위치 집합의 XOR이 0(짝수)이 되도록 정해짐(1과 0의 갯수가 각 짝수).

인코딩

데이터 d1 d2 d3 d4 = 1 0 1 0

배치:

pos:   1   2   3   4   5   6   7
bits:  p1  p2  d1  p3  d2  d3  d4
val:   ?   ?   1   ?   0   1   0

짝수 패리티 계산:

• p1 → (pos 1,3,5,7) = (p1, d1=1, d2=0, d4=0) → p1 ⊕ 1 ⊕ 0 ⊕ 0 = 0 ⇒ p1=1
• p2 → (pos 2,3,6,7) = (p2, d1=1, d3=1, d4=0) → p2 ⊕ 1 ⊕ 1 ⊕ 0 = 0 ⇒ p2=0
• p3 → (pos 4,5,6,7) = (p3, d2=0, d3=1, d4=0) → p3 ⊕ 0 ⊕ 1 ⊕ 0 = 0 ⇒ p3=1

완성된 7비트:

[1, 0, 1, 1, 0, 1, 0]  =  p1 p2 d1 p3 d2 d3 d4

디코딩(오류 1비트 발생)

전송 후 수신한 비트가 1011010인데, pos 5가 1로 뒤집혔다고 가정(원래 pos5=0 → 1):

1. 수신값으로 각 패리티를 다시 검사(짝수여야 함):

• s1 = (1,3,5,7) XOR = 1 ⊕ 1 ⊕ 1 ⊕ 0 = 1
• s2 = (2,3,6,7) XOR = 0 ⊕ 1 ⊕ 1 ⊕ 0 = 0
• s3 = (4,5,6,7) XOR = 1 ⊕ 1 ⊕ 1 ⊕ 0 = 1

1. 신드롬(syndrome) = s3 s2 s1 = 1 0 1 (이진수) = 5
2. → 오류 위치가 5번임을 지적.
3. pos 5의 비트를 뒤집어 원본 복원.
4. → 단일 비트 오류를 자동 정정.

해밍 + 전체 패리티(확장형)

• 위 7비트에 추가로 전체 패리티 비트(1개)를 더하면 Hamming(8,4)처럼 확장 가능.
• 이렇게 하면 단일 오류 정정 + 이중 오류 검출(SECDED)이 가능해져,

  ---

• 2비트 오류가 생겼을 때 “정정은 못 해도 오류임은 확실히 알 수 있음”.

3) 패리티 vs 해밍

항목 패리티(1비트) 해밍(다비트)

목적	오류 검출만	오류 위치 파악 + 단일 오류 정정
검출 범위	홀수 개수 오류만	단일 오류 확정 검출, (확장 시) 이중 오류 검출
정정	불가	가능(단일 비트)
계산 비용	매우 낮음	낮음~보통(여러 패리티 집합 계산)
사용 예	간단 전송, 일부 프로토콜	ECC 메모리, RAID 2(역사적), 통신/저장 ECC