[Study - CS > Computer Architecture] 패리티 비트와 해밍코드 (Parity bit and Hamming code)
패리티 비트 (Parity bit)
정보 전달 과정에서 오류가 생겼는지를 검사하기 위해 추가하는 bit를 말한다.
전송하고자 하는 데이터의 각 문자에 1bit를 더하여 전송한다.
종류는 짝수 parity와 홀수 parity가 있고, 전체 bit에서 (짝수, 홀수)에 맞도록 bit를 정한다.
- parity bit를 짝수 parity로 정했을 경우, 각 비트의 값 중에서 1의 개수가 짝수가 되도록 맞춰준다.
- parity bit를 홀수 parity로 정했을 경우, 각 비트의 값 중에서 1의 개수가 홀수가 되도록 맞춰준다.
패리티 비트를 추가하는 이유
데이터를 송수신하는 과정에서 각 bit를 단위 시간당 하나씩 보내게 되어있다.
이때 오류에 의해서 bit의 값이 틀어져서 1에서 0으로 바뀌거나, 0에서 1로 바뀌었을 때 parity bit를 이용해서 확인할 수 있다.
해밍 코드 (Hamming code)
데이터 전송 시 1bit의 에러를 정정할 수 있는 자기 오류 정정 코드를 말한다.
parity bit를 이용하여 오류 검출과 수정을 할 수 있다.
parity bit는 오류를 검출하기만 할 뿐 수정은 하지 않기 때문에 hamming code를 활용한다.
전송 bit 중 2^n 번째를 오류 검출하기 위한 parity bit로 사용한다.
오류 검출 및 교정을 위한 잉여 비트가 많이 필요하다.
해밍 코드 원리
필요한 체크 bit의 개수 계산
2^p >= d + p + 1 (d:데이터 비트, p:패리티 비트)
예를 들어, 데이터 비트의 길이가 8일 때, 위 수식을 만족하는 p의 최솟값이 (2^p >= 8+p+1) -> 4 이므로, 최소 4개의 parity bit가 필요하다.전송 비트 중 2^n 번째 자리 bit에 parity bit를 위치시키고 데이터 bit를 삽입
위 그림은 Little Endian 기준 데이터 bit 길이가 8일 경우의 예시이며, P는 parity bit, D는 data bit, 숫자는 각 bit의 자리 번호를 의미한다.
Little Endian : 낮은 주소에 데이터의 낮은 바이트(LSB, Least Significant Bit)부터 저장하는 방식
parity bit 체크 범위를 확인하여 parity bit의 값 결정
n번째 parity bit는 n번째에서 시작하며, n bit 만큼을 포함하고, n bit씩 건너뛴 bit들을 대상으로 parity bit를 결정한다.
각각의 data bit 자리에 data bit를 나열하고, 결정된 parity bit들을 삽입하여 hamming code를 생성한다.오류 검출 및 오류 비트 수정
- 수신된 데이터로 다시 1~3 작업을 수행하여 parity bit를 계산해서 수신된 체크 비트열과 비교한 후, 오류 검출 가능
- 수신측에서 계산한 체크 비트열과 수신된 체크 비트열을 XOR 연산하여 오류 비트 검출 및 수정 작업 수행
예를 들어, 수신 데이터로 계산한 체크 비트열이 1001, 수신된 체크 비트열이 0011인 경우
두 체크 비트열을 XOR 연산하여 1010을 얻고, 이를 10진수 변환 시 10이므로,
10번째 비트 값을 수정하여 오류 수정 가능