[CE] Parity Check and Hamming Code - Parity Bit

Parity Check

초기 컴퓨터 및 통신 시스템에서 널리 사용되던 패리티 검사(Parity Check)는

• 데이터에 하나의 추가 비트(parity bit라고 불림)를 더해 전체 1의 개수를 홀수 또는 짝수로 맞춤으로써
• 단일 비트 오류를 감지할 수 있음

하지만, 오류의 위치를 특정하거나 교정할 수는 없는 간단한 오류 검출 기법임.

패리티 비트(Parity Bit) 는
데이터 저장 및 전송 시 오류를 검출하기 위해 사용되는 추가적인 비트를 가리킴.

 

"Parity"의 원래 단어 뜻은 "동등함(equality)" 또는 "대등함(equivalence)"이지만,
수학에서는 "홀수 또는 짝수의 성질"을 나타내는 의미로도 사용됨: parity bit는 홀짝 여부에 따라 결정이 됨.

---

Hamming Code

Parity Check의 한계를 극복하기 위해

1940년대 말 Bell 연구소의 리처드 해밍(Richard Wesley Hamming, 1915-1998)이 제안한 기법

• 단일 비트의 오류를 자동으로 검출하고,
• 이의 위치를 찾아 교정까지 가능함.

리처드 해밍은 두 word 사이의 차이를 측정하는 방법으로 서로 다른 심볼의 수를 세는 Hamming Distance도 개발함.

https://dsaint31.me/mkdocs_site/DIP/cv2/etc/dip_metrics/?h=hamming+distance#hamming-distance

BME

---

 

Hamming Code의 작성방법은 다음과 같음:

• 원래 데이터의 bit크기에 따라 크기가 결정되는 여러 parity bit를 사용하고,
  • $n$bit 의 데이터에 최소한 필요한 parity bit의 수 $r$:
  • $r = \lceil \log_2 (n+r+1) \rceil$
  • $\lceil x \rceil$은 ceiling function으로 $x$ 이상의 가장 작은 정수를 반환함.
• 이 parity bits들을 각각 $2^{i-1}$의 위치에 배치함.
• 이 $i$ 번째 parity bit의 값은 이진수 표현에서 (오른쪽에서)$i$번째 비트가 모두 1인 위치의 데이터 bit들을 xor하여 구함.
  • $i=1$인 parity bit는 이진수 표현에서 맨 오른쪽 비트가 1인 $1,3,5, \dots$의 데이터 bit들을 xor함.

이렇게 만들어진 Hamming Code 에서 오류 발생여부는 Syndrome을 계산하여 확인.

• Syndrome은 Hamming Code에서 parity bits를 다시 계산한 값으로, 그 값이 곧 오류가 발생한 위치를 나타내는 이진수임
  • Syndrome이 0이면 오류가 없음.
  • Synfrome이 0이 아닌 경우, 해당 이진수에 해당하는 위치에 오류가 발생함을 의미함.

Syndrome의 계산은 다음과 같음:

• Hamming Code의 각 parity bit를 구하는데 사용된 데이터 bit와 해당 parity bit를 다시 xor수행.
• 모든 parity bit에 대해 위의 계산을 처리하고 이들을 $i$ 순으로 배치한 이진수가 Syndrome임.

"Syndrome"의 원래 단어 뜻은 의학에서 유래한 "증후군" 또는 "여러 증상의 집합"을 의미

그리스어 "syn(함께)"과 "dromos(달리다)"에서 비롯된 이 단어는 "함께 나타나는 특징적인 패턴"을 뜻함. 

 

Hamming Code에서 Syndrome이란 다음의 의미를 가진 이름이라고 볼 수 있음

 

• 의학에서 증후군(syndrome)이 여러 증상의 패턴을 통해 질병을 진단하는 것처럼
• 해밍 코드에서 신드롬(syndrome)은 여러 패리티 비트의 검사 결과 패턴을 통해 오류를 진단

---

 

Hamming Code는 단일 비트 오류 수정이 가능하지만, 2개 이상의 비트에서 오류가 발생할 경우에는 정확한 수정이 불가능함.

 

다중 비트 오류 검출 및 정정기법으로는 Reed-Solomon Code나 BCH Code 등이 있음

---

Example: 4비트 데이터 에서 Hamming Code 계산

1. 필요한 parity bit 계산

4비트 데이터에는 3개의 parity bits가 필요:

• 데이터 비트 : $n = 4$
• 패리티 비트 : $r = \lceil \log_2(n+r+1) \rceil = \lceil \log_2(8)\rceil = 3$

---

2. 코드 구조 (총 7비트)

위치(i):   7   6   5   4   3   2   1
이진표현:  111 110 101 100 011 001 000
내용   :   D4  D3  D2  P3  D1  P2  P1

---

3. 데이터 인코딩 예시

원본 데이터: 1011

• $D1=1, D2=1, D3=0, D4=1$

패리티 비트 계산 (xor):

• $P1 = D1\oplus D2\oplus D4 = 1 \oplus 1 \oplus 1 = 1$ : 011, 101, 110, 111
• $P2 = D1\oplus D3\oplus D4 = 1 \oplus 0 \oplus 1 = 0$ : 011, 101, 110, 111
• $P3 = D2\oplus D3\oplus D4 = 1 \oplus 0 \oplus 1 = 0$ : 011, 101, 110, 111

인코딩된 코드워드: 1010101

---

4. 오류 검출 및 정정 예시

오류 없는 경우 (1010101)

Syndrome 계산:

• $S1 = \color{blue}{1} \oplus 1 \oplus 1 \oplus 1 = 0$
• $S2 = \color{blue}{0} \oplus 1 \oplus 0 \oplus 1 = 0$
• $S3 = \color{blue}{0} \oplus 1 \oplus 0 \oplus 1 = 0$
• Syndrome = S3 S2 S1 = 000 = 0 이므로 오류 없음!

---

오류 발생 (위치 5의 D2가 변경됨)

변경된 코드워드: 1000101 (D2가 1에서 0로 변경)

Syndrome 계산:

• $S1 = P1 \oplus D1 \oplus \color{red}{D2} \oplus D4 =  \color{blue}{1} \oplus 1 \oplus \color{red}{0} \oplus 1 = 1$
• $S2 = P2 \oplus D1 \oplus D3 \oplus D4 = \color{blue}{0} \oplus 1 \oplus 0 \oplus 1 = 0$
• $S3 = P3 \oplus \color{red}{D2} \oplus D3 \oplus D4 =  \color{blue}{0} \oplus \color{red}{0} \oplus 0 \oplus 1 = 1$
• Syndrome = S3 S2 S1 =  101 = 5 이므로 위치 5에 오류!

오류 정정: 위치 5의 비트 반전 → 1010101 (정상 복원)

---

오류 발생 (위치 3의 D1이 변경됨)

변경된 코드워드: 1010001 (D1이 1에서 0로 변경)

Syndrome 계산:

• $S1 = P1 \oplus \color{red}{D1} \oplus D2 \oplus D4 =  \color{blue}{1} \oplus \color{red}{0} \oplus 1 \oplus 1 = 1$
• $S2 = P2 \oplus \color{red}{D1} \oplus D3 \oplus D4 = \color{blue}{0} \oplus \color{red}{0} \oplus 0 \oplus 1 = 1$
• $S3 = P3 \oplus D2 \oplus D3 \oplus D4 =  \color{blue}{0} \oplus 1 \oplus 0 \oplus 1 = 0$
• Syndrome = S3 S2 S1 =  011 = 3 이므로 위치 3에 오류!

오류 정정: 위치 3의 비트 반전 → 1010101 (정상 복원)

---

같이보면 좋은 자료들

https://dsaint31.me/mkdocs_site/CE/ch03_seq/ce03_04_ecc_memory/?h=ecc

BME

https://blog.naver.com/leapforfly/90169128293

해밍코드(Hamming Code)