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

1. 패리티 비트란?

1-1) 정의

정보 전달 과정에서 오류가 생겼는지 검사하기 위해 추가하는 비트

> 전송하고자 하는 데이터의 "각 문자"에 지정위치에 1 비트를 더하여 전송

> 비트를 더해주는 자리는 미리 약속

   1, 2, 4, 8 ... 2^n 자리수를 패리티 비트 자리로 지정
   데이터는 그 빈자리 사이에 배치

 

전송하고자 하는 대상이 bit으로 변환될 수 있을 것
(string, JSON ....등)

 

■ 패리티 비트 구하는 공식

2^p >= d + p + 1

where

p : 패리티 비트의 수

d : 데이터 비트의 수

 

■ 패리티 비트 추가

1) 패리티 비트 최소 개수를 구함

2) 자리수에 패리티 비트 배치

3) 나머지 자리에 원본 데이터 비트 배치

 

1-2) 패리티 비트 타입

전체 비트에서 (짝수, 홀수)를 맞춰 패리티 비트를 정해주는 과정이 있음

(짝수로 맞출지, 홀수로 맞출지 미리 약속)

1. 짝수
2. 홀수

ex)

짝수 패리티일 때 7bit 데이터가 1010001 라면?

비트 자리	8	7	6	5	4	3	2	1
원본	-	1	0	1	0	0	0	1
짝수 패리티	1	1	0	1	0	0	0	1

원본 1의 개수가 3개이므로
패리티 짝수는 맨 앞자리 1을 배정하여 총 4개로 맞춰줌

 

 

2. 해밍코드

2-1) 정의

데이터 전송 시 1비트의 에러를 정정하는 "자기 오류정정 코드" 방식을 지칭.

패리티비트를 보고, 1비트에 대한 오류를 정정할 비트를 찾아 수정할 수 있음

(패리티 비트는 오류 검출만 하고 수정은 하지 않으므로)

 

2-2) 방법

2의 n승 번째 자리인 1,2,4번째 자릿수가 패리티 비트라는 것으로 부터 시작
이 숫자로부터 시작하는 세개의 패리티 비트가 짝수인지, 홀수인지 기준으로 판별

 

짝수 패리티의 해밍 코드가 0011011일때 오류가 수정된 코드는?

1. 1, 3, 5, 7번째 비트 확인 : 0101로 짝수이므로 '0'
2. 2, 3, 6, 7번째 비트 확인 : 0111로 홀수이므로 '1'
3. 4, 5, 6, 7번째 비트 확인 : 1011로 홀수이므로 '1'

 

역순으로 패리티비트 '110'을 도출했다. 10진법으로 바꾸면 '6'으로, 6번째 비트를 수정하면 된다.

따라서 정답은 00110'0'1이다.

 

---

참조

https://gyoogle.dev/blog/computer-science/computer-architecture/%ED%8C%A8%EB%A6%AC%ED%8B%B0%20%EB%B9%84%ED%8A%B8%20&%20%ED%95%B4%EB%B0%8D%20%EC%BD%94%EB%93%9C.html

패리티 비트 & 해밍 코드 | 👨🏻‍💻 Tech Interview