패리티 비트와 해밍 코드

패리티비트 (Parity Bit)

• 송신 컴퓨터에서 수신 컴퓨터로 데이터를 전송할 때, 데이터는 컴퓨터에 연결된 전선을 타고, 이진수의 전기 신호로 전달된다. 수신 컴퓨터에서 데이터의 오류를 검출하기 위한 일종의 장치 중 하나이다.
• 정보 전달 과정에서 오류가 생겼는지 검사하기 위해 추가하는 비트이다.
• 이진수 데이터의 끝에, 0 또는 1 의 패리티 비트를 붙여 보낸다.

종류

짝수 패리티(Even Parity)

• 데이터 비트와 패리티 비트를 포함한 전체 비트에서, 1의 개수가 짝수가 되도록 패리티 비트를 정한다.

홀수 패리티(Odd Parity)

• 데이터 비트와 패리티 비트를 포함한 전체 비트에서, 1의 개수가 홀수가 되도록 패리티 비트를 정한다.
• 수신자는 송신자로부터, 어떤 패리티 비트 규칙을 사용했는지 공유 받게 된다.
• 따라서, 수신자는 수신 받은 데이터가 공유 받은 패리티 비트 규칙을 만족하는지 확인함으로써, 오류를 검출하고 오류가 있다면, 송신 컴퓨터에게 데이터 재송신을 부탁하게 된다.

특징

• 2bit의 데이터가 손실되면 알아차릴 수 없다.
• 오류 검출만 할 뿐 수정하지는 않는다.

해밍 코드 (Hamming code)

• 수신자가 오류 검출 뿐만 아니라 오류 수정까지 가능한 자기 오류정정 코드

특징

1. 2Bit 의 오류를 검출할 수 있고, 1Bit 의 오류를 교정할 수 있다.
2. 데이터 비트 외에 오류 검출 및 교정을 위한 잉여 비트가 많이 필요하다.
3. 해밍 코드 중 1, 2, 4, 8, 16 , ... , 2^n 번째 비트는, 오류 검출을 위한 패리티 비트이다.
4. 패리티 규칙(짝수 or 홀수) 이 정해졌다면, n번째 패리티 비트는 n 번째 비트에서 시작하여, n 비트 만큼을 포함하고, n 비트씩 건너뛴 비트들을 대상으로, 패리티 비트를 결정할 수 있다.

해밍 코드 예제

1. '1 0 1 1 0 0 1 1' 의 해밍 코드를 받았다고 가정

   • 해밍 코드 특징 3번에 의하여, 오류 검출을 위한 패리티 비트는 2^n 번째 위치하므로, 해밍 코드 내의 패리티 비트는 '1 0 1 1 0 0 1 1' 이다. 
     • 1(2^0) 0(2^1) 1 1(2^2) 0 0 1 1(2^3)

   전체 비트에서 패리티 비트를 제거해보면, 원본 데이터는 '1 0 0 1' 임을 알 수 있다.

2. 정보 비트 '1 0 1 1' 에 홀수 패리티 비트를 적용하여 해밍 코드로 변환한다고 가정

   • 우선, 패리티 비트는 2^n 에 위치해야므로, 해밍코드는 '? ? 1 ? 0 1 1' 의 형태로 만들 수 있을 것이다.
     • ?(2^0) ?(2^1) 1 ?(2^2) 0 0 1
   • 해밍 코드 특징 4번에 의하여, 패리티 규칙이 홀수로 정해졌으므로, 각 자리의 패리티 비트를 결정할 수 있다.
     • 1(2^0) 번째 패리티 비트는, 1 번째 비트에서 시작하여, 1 비트 만큼을 포함하고, 1 비트씩 건너뛴 비트들을 대상으로, 패리티 비트를 결정한다.
       • 즉, 1 번째 패리티 비트는 1, 3, 5, 7 번째 비트들을 대상으로 패리티 비트를 결정하게 되며,
       • 해당 위치의 값은 '? 1 0 1' 이므로, ? 는 홀수 패리티 비티를 만족하기 위해 1 이 된다.
     • 2(2^1) 번째 패리티 비트는, 2 번째 비트에서 시작하여, 2 비트 만큼을 포함하고, 2 비트씩 건너뛴 비트들을 대상으로, 패리티 비트를 결정한다.
       • 즉, 2 번째 패리티 비트는 2, 3, 6, 7 번째 비트들을 대상으로 패리티 비트를 결정하게 되며,
       • 해당 위치의 값은 '? 1 1 1' 이므로, ? 는 홀수 패리티 비티를 만족하기 위해 0 이 된다.
     • 4(2^2) 번째 패리티 비트는, 4 번째 비트에서 시작하여, 4 비트 만큼을 포함하고, 4 비트씩 건너뛴 비트들을 대상으로, 패리티 비트를 결정한다.
       • 즉, 4 번째 패리티 비트는 4, 5, 6, 7 번째 비트들을 대상으로 패리티 비트를 결정하게 되며,
       • 해당 위치의 값은 '? 0 1 1' 이므로, ? 는 홀수 패리티 비티를 만족하기 위해 1 이 된다.

   따라서, 변환된 해밍 코드는 '1 0 1 1 0 1 1' 이다.

3. 짝수 패리티 비트를 적용한 해밍 코드가 '0 0 1 1 0 1 1' 일 때, 오류를 수정한다고 가정

   • 1, 3, 5, 7 번째 비트 확인
     • '0 1 0 1' 로, 1 의 합이 짝수이며,
     • 짝수 패리티 비트와 일치하므로 '0'
   • 2, 3, 6, 7 번째 비트 확인
     • '0 1 1 1' 로, 1 의 합이 홀수이며,
     • 짝수 패리티 비트와 일치하지 않으므로 '1'
   • 4, 5, 6, 7 번째 비트 확인
     • '1 0 1 1' 로, 1의 합이 홀수이며,
     • 짝수 패리티 비트와 일치하지 않으므로 '1'

   역순으로 패리티비트 '110' 을 도출할 수 있다.
   이후, 2진법 '110' 을 10진법 '6' 으로 바꾼 뒤, 6 번째 비트를 수정하면 된다.
   따라서, 오류를 수정한 답은 0 0 1 1 0 '0' 1 이 된다.

출처
https://dos-soles.tistory.com/20
https://wooono.tistory.com/400