parity bit?

• 데이터를 주고 받을 때에 오류가 생겼는지 확인하는 방법 중 하나.
• 송신 데이터의 끝에 parity bit을 추가해서 이를 알게 해 준다.

Parity bit 구성 방법

예를 들어, 1011001의 7비트 데이터를 전송한다고 해 보자.

이에 추가해서 제일 뒤에 0비트를 하나 덧붙인다. (0인 이유 : parity bit을 포함해서 전체 전송 bit의 1bit 개수가 짝수개가 되게 parity bit 값을 설정한다.)

그러면 전송 비트는 10110010이 된다.

만약 오류가 발생해서 비트값이 잘못 전달이 되었다?

-> parity bit와 전체 bit가 일치하지 않으면, 오류 발생.

ex) 10110010이 아닌, 00110010이 전달되었을 경우, parity bit은 0인데 1bit는 3개로 맞지 않게 된다. -> 오류 탐지 가능!!

• 한계
  • 오직 하나의 bit 오류만 탐지 가능하다.
  • 오류의 수정이 불가능함. (어느부분에서 오류가 발생했는지 모름)
• parity bit가 오류가 발생할 수도 있지 않나?
  • 뇌피셜이긴 하지만, 어차피 parity bit에 오류가 생기게 되어도 마찬가지로 parity가 맞지 않게 됨 -> 오류임은 똑같이 탐지가 된다.

Parity의 종류?

• 짝수 parity
  • 위에서 사용한 parity로, parity bit를 포함해 전체 비트에서 1bit의 개수가 짝수가 되도록 한다.
• 홀수 parity
  • 전체 비트에서 1bit의 개수가 홀수가 되도록 한다.

애초에 짝수개인지 홀수개인지의 판별은 XOR 연산을 통해 이루어진다.

Hamming Code

• parity bit를 이용한 방법.
• 오류 탐지 뿐만 아니라 오류 수정또한 가능하다.
• 최대 2bit의 오류 탐지, 1bit의 오류 수정 가능.

기본 원리

ex) 1011의 데이터를 보낸다고 가정.

그러면 실제로 xx1x011의 데이터를 보내게 된다.

각각의 x들은 어떻게 결정되냐하면,, (짝수 parity 가정)

1. 첫 번째 x (1, 3, 5, 7)
   1, 3, 5, 7번째 비트들의 parity bit에 해당.
   즉, 0비트가 된다.
2. 두 번째 x (2, 3, 6, 7)
   2, 3, 6, 7번째 비트들의 parity bit에 해당.
   즉, 1비트가 된다.
3. 세 번째 x (4, 5, 6, 7)
   4, 5, 6, 7번째 비트들의 parity bit에 해당.
   즉, 0비트가 된다.

결국, 최종으로 전달되는 비트는 0110011이 된다.

오류 감지 방법

• 앞에서의 방법과 동일하다. 만약 비트값이 오류로 인해 변경되었다면, 각 parity bit에 의해 오류가 감지된다.
• 최대 2비트까지 감지할 수 있다.

위의 예제로 돌아가자.

만약 0110101이라는 비트가 수신되었다면,

각 parity에 대해서 계산을 해 본다.

1. 첫 번째 x (1, 3, 5, 7)
   1이 3개 -> 오류!
2. 두 번째 x (2, 3, 6, 7)
   1이 3개 -> 오류!
3. 세 번째 x (4, 5, 6, 7)
   1이 2개 -> 정상!

몇 번째 비트에 오류가 발생했는지는 모르지만, 확실한 건 오류가 발생했다는 것은 감지할 수 있다.
(위의 parity bit 내용과 비교했을 때 2bit까지 감지 가능하다고 한 건, parity bit이 하나만 있는 경우에는 두 bit가 오류가 발생하면 전체 짝/홀에는 영향을 끼치지 않으므로 감지가 안 되지만, 이 경우에는 parity bit이 여러 개이기 때문에 감지를 할 수 있다.)

오류 수정 방법

위의 예제로 돌아가자.

만약 0110111이라는 비트가 수신되었다면,

각 parity에 대해서 계산을 해 본다.

1. 첫 번째 x (1, 3, 5, 7)
   1이 3개 -> 오류! -> $2^0$을 '1'으로 설정
2. 두 번째 x (2, 3, 6, 7)
   1이 4개 -> 정상! -> $2^1$을 '0'으로 설정
3. 세 번째 x (4, 5, 6, 7)
   1이 3개 -> 오류! -> $2^2$을 '1'으로 설정

-> 101(2) 번째 비트에 오류가 발생 -> 0110011로 바꾸면 된다!!

사실 이렇게 계산 안 하더라도, 복구할 수 있다.
2번에 의해 2, 3, 6, 7에서는 정상비트만 존재.
1번에 의해 1, 5번이 의심됨.
3번에 의해 4, 5번이 의심됨.

-> 공통 의심비트는 5번 -> 5번 비트만 고치면 된다!

특징

• parity bit는 1, 2, 4, 8, ..., $2^n$번째에 위치한다.
• Hamming code 변환 시 추가할 비트 수 계산
  • d : 전송할 데이터 bit 수
  • p : 필요한 parity bit 수
  • $2^p \ge d + p + 1$를 만족해야 한다.

정도면 될듯.. 사실 RAID보다가 이 부분에서 막혀서 잠깐 공부한거라 직접 증명해보고 할 시간은 없다..

참고 자료

• https://wooono.tistory.com/400