패리티 비트 & 해밍 코드

2021. 8. 21. 19:56

패리티 비트(Parity bit)

정보의 전달 과정에서 오류가 생겼는지 검사하기 위해 추가된 비트로, 전송하고자 하는 데이터에 1 비트를 더하여 전송하는 방법

전송 데이터 비트에서 1의 개수가 홀수 혹은 짝수인지 체크하여 패리티 비트를 추가하고, 수신된 데이터의 전체 비트를 계산하여 패리티 비트를 다시 계산함으로써 데이터 오류 발생 여부를 체크
패리티 비트는 오류 발생 여부만 알 수 있지 오류 수정 불가
다수의 비트에서 오류 발생 시 오류 검출 불가능할 수 있음(짝수 개의 비트에서 오류 발생 시)
패리티 비트는 짝수, 홀수 두 가지 방법이 있음
1. 짝수 패리티 비트
  - 전체 비트에서 1의 개수가 짝수가 되도록 패리티 비트를 정하는 것
2. 홀수 패리티 비트
  - 전체 비트에서 1의 개수가 홀수가 되도록 패리티 비트를 정하는 것

데이터 비트에 여러 개의 체크비트(패리티 비트)가 추가된 코드

1. 필요한 체크 비트의 개수 계산

예를 들어 데이터 비트의 길이가 8일 때, 위 수식을 만족하는 p의 최소값이 4이므로 최소 4개의 패리티 비트가 필요하다.

2. 전송 비트 중 2^n 번째 자리 비트에 패리티 비트를 위치시키고 데이터 비트를 삽입

위 그림은 Little Endian 기준 데이터 비트 길이가 8일 경우의 예시이며, P는 패리티 비트, D는 데이터 비트, 숫자는 각 비트의 자리 번호를 의미한다.

3. 패리티 비트 체크 범위를 확인하여 패리티 비트의 값 결정

n번째 패리티 비트는 n번째에서 시작하며, n비트 만큼을 포함하고 n비트씩 건너뛴 비트들을 대상으로 패리티 비트를 결정각각의 데이터 비트 자리에 데이터 비트를 나열하고, 결정된 패리티 비트들을 삽입하여 해밍 코드 생성

패리티 비트 체크 범위는 다음과 같은 규칙을 따른다.

각각의 데이터 비트 자리에 데이터 비트를 나열하고, 결정된 패리티 비트들을 삽입하여 해밍 코드 생성

4. 오류 검출 및 오류 비트 수정

수신된 데이터로 다시 1 ~ 3 작업을 수행하여 패리티 비트를 계산하여 수신된 체크 비트열과 비교하여 오류 검출 가능
수신측에서 계산한 체크 비트열과 수신된 체크 비트열을 XOR 연산하여 오류 비트 검출 및 수정 작업 수행
ex) 수신 데이터로 계산한 체크 비트열이 1001, 수신된 체크 비트열이 0011인 경우, 두 체크 비트열을 XOR 연산하여 1010을 얻고, 이를 10진수 변환 시 10이므로 10번째 비트 값을 수정하여 오류 수정 가능