코드 (3) - 패리티 비트 & 해밍 코드

1. 패리티비트

1) 패리티 비트 : 1의 개수가 홀수인지 짝수인지 체크하기 위해 추가되는 비트. 1Bit로 오류 검출 가능. 그러나 여러비트에서 동시에 오류가 발생하면 검출 불가능

 

---

e.g. 짝수 패리티
(반드시 1의 개수가 짝수여야함)

 

110100010 = 1이므로 오류 발생

011011000 = 0이므로 오류 없음

 

---

 

2. 해밍코드

0) 해밍코드란? :

데이터비트에 여러개의 패리티비트를 추가하여 오류를 검출하고 정정할 수 있는 코드.

 

1) 최소 패리티 비트 수 결정 :

$2^{Parity} \leq Parity + Data + 1$의 공식을 성립해야함. 4개의 데이터 비트가 있다면 $2^3 = 8 = 3 + 4 + 1$로 3개의 패리티비트가 필요함. 등호가 아닌 부등호이기 때문에 4개 이상 써도 되지만 작을수록 좋음.

 

2) 패리티 비트의 위치 결정 :

n번째 패리티비트가 $2^{n-1}$의 위치에 들어감 (1, 2, 4, 8, 16, ...)

 

3) 패리티 비트 결정 :

패리티 범위 원소들의 XOR연산으로 결정. 아래 표에서 1로 표시된 원소들이 n번째 패리티비트의 패리티 범위임.

구분	3번째 P비트	2번째 P비트	1번째 P비트
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

 

만약 데이터가 1001이라면 3개의 P비트를 (1, 2, 4)에 추가해서 100P1PP가 됨. 

 

1번 P비트 = (1, 3, 5, 7) = (P, 1, 0, 1) = 1 X 0 X 1 = 0

2번 P비트 = (2, 3, 6, 7) = (P, 1, 0, 1) = 1 X 0 X 1 = 0

3번 P비트 = (4, 5, 6, 7) = (P, 0, 0, 1) = 0 X 0 X 1 = 1

 

짝수패리티는 각 패리티범위의 모든 원소들 중 1의 개수가 짝수가 되어야함 (0101/0101/1001). 홀수패리티는 반대로 홀수가 되어야함. 따라서 최종결과는 100P1PP → 1001100이 됨.

 

4) 패리티 비트 검증

패리티 범위 (e.g. 1번 P비트 = 1, 3, 5, 7)값들의 XOR값이 모두 0이면 오류가 없는 것이고 만약 1이 나온다면 에러가 발생한것. 3개의 P비트 범위에서 검출된 2진값을 10진수로 변경하여 해당 자리수 수정 (홀수패리티의 경우 모두 1이면 오류가 없는 것이고 0이 나오면 에러가 발생한 것)

 

 

---

1001100

 

1번째 패리티비트 범위 (1, 3, 5, 7) = (0, 1, 0, 1)이다.

0 XOR 1 XOR 0 XOR 1 = 1 XOR 1 = 0이다.

 

2번째 패리티비트 범위 (2, 3, 6, 7) = (0, 1, 0, 1)이다.

0 XOR 1 XOR 0 XOR 1 = 1 XOR 1 = 0이다.

 

3번째 패리티비트 범위 (4, 5, 6, 7) = (1, 0, 0, 1)이다.

1 XOR 0 XOR 0 XOR 1 = 1 XOR 1 = 0이다.

 

000 : 오류없음

 

---

1101101

 

1번째 패리티비트 범위 (1, 3, 5, 7) = (1, 1, 0, 1)이다.

1 XOR 1 XOR 0 XOR 1 = 0 XOR 1 = 1이다.

 

2번째 패리티비트 범위 (2, 3, 6, 7) = (0, 1, 1, 1)이다.

0 XOR 1 XOR 1 XOR 1 = 1 XOR 0 = 1이다.

 

3번째 패리티비트 범위 (4, 5, 6, 7) = (1, 1, 0, 1)이다. 

1 XOR 1 XOR 0 XOR 1 = 0 XOR 1 = 1이다.

 

111 : 7번 비트 수정해야함

→ 0101101로 수정됨.

 

---

 

3. Reference

해밍 부호, 해밍 코드(Hamming code)