패리티 비트와 해밍 코드

패리티 비트: Parity Bit

• 정보의 전달 과정에서 오류가 생겼는지를 검사하기 위해 추가된 비트
• 전송하고자 하는 데이터의 끝에 1비트를 더하여 전송하는 방법
• 짝수 패리티라고 0으로 값을 고정하거나 홀수 패리티라고 해서 그 값을 1로 고정하는 건 아니다
• 패리티 비트를 정하고 데이터를 보내면(단위시간당 하나씩) 받는 쪽에서 수신된 데이터의 전체 비트를 계산하고 패리티 비트 또한 다시 계산한다.
• 이때 데이터 오류 발생 여부를 알 수 있찌만 오류 발생 여부만 알 수 있고 오류를 수정할 수 없다.
  
  

1. 짝수(even, 우수)방식

   실제 송신하고자 하는 데이터의 각 비트의 값 중 1의 개수가 짝수가 되도록 패리티 비트를 정한다.
   데이터 비트에서 1의 개수가 홀수이면 패리티 비트를 1로, 그렇지 않으면 0으로 정한다.
   ex) 1001 0101 , 0010 110
   1001 0101 | 0 : 1의 개수 4 → 짝수니까 0
   0010 110 | 1: 1의 개수 3 → 홀수니까 1

2. 홀수(odd, 기수)방식

   실제 송신하고자 하는 데이터의 각 비트의 값 중 1의 개수가 홀수가 되도록 패리티 비트를 정한다.
   데이터 비트에서 1의 개수가 짝수이면 패리티 비트를 0으로, 그렇지 않으면 1로 정한다
   ex) 1001 0101, 0010 110
   1001 0101 | 1: 1의 개수 4 → 짝수니까 1
   0010 110 | 0: 1의 개수 3 → 홀수니까 0

해밍코드: Hamming Code

• 데이터 비트와 에러 검출과 수정을 위한 패리티 비트로 구성되어 있고 전송되는 데이터의 비트 수에 따라 패리티 비트의 수가 달라진다.

1. $2^p$ ≥ $m+p+1$를 만족하는 최소 p 구하기

   p: 추가할 패리티 비트 개수 | m: 원본 데이터의 비트 개수

   • 원본 데이터: 1001 [m=4]

     p = 1, 2 ≥ 6 (X)
     p = 2, 4 ≥ 7 (X)
     p = 3, 8 ≥ 8 (O) → p의 최소
     p =4, 16 ≥ 9 (O)

     
     

2. 패리티 비트 추가: $2^k$ (k= n-1, n≥1)

   Pn은 자기 범위에 대해 짝수/홀수 패리티를 가진다.

   • P1, P2, P3 존재 → 1, 2, 4번지 값에 존재: DDDP DPP: 100P 1PP

     P1(1, 3, 5, 7): P1(P, 1, 0, 1) -XOR→ 1 X 0 X 1 = 0
     P2(2, 3, 6, 7): P2(P, 1, 0, 0) -XOR→ 1 X 0 X 1 = 0
     P3(4, 5, 6, 7): P3(P, 1, 0, 0) -XOR→ 1 X 0 X 0 = 1
     P1, P2, P3 = 0, 0, 1

     • P1에서 1, 3, 5, 7번지를 확인하는 이유
       → 2진수 중에서 그 자리의 수가 1인 곳을 의미한다

       10진수	2진수	P1	P2	P3
       1	0001	1	0	0
       2	0010	0	1	0
       3	0011	1	1	0
       4	0100	0	0	1
       5	0101	1	0	1
       6	0110	0	1	1
       7	01111	1	1	1
       8	1000	0	0	0
       9	1001	1	0	0
       10	1010	0	0	0

       
       

3. 검사 및 수정

   • 해밍코드의 가장 큰 특징은 데이터의 재수신 없이 수신측에서 바로 오류를 검출하고 수정할 수 있다는 점이다.
   • 위의 해밍코드를 수신측의 입장에서 해석하고 원본 데이터를 얻는 방법
   • 정상적으로 수신했을 때: 1001 100 | 단일 비트 오류로 인한: 1011 100 일 때

     P1: 1011 100 → P1 = 1 | E = P’3 P’2 P’1 = P’3 P’2 1
     P2: 1011 100 → P2 = 0 | E = P’3 P’2 P’1 = P’3 0 1
     P3: 1011 100 → P3 = 1 | E = P’3 P’2 P’1 = 1 0 1
     2진수 101을 10진수 5로 바꾼다, 5번째 자리의 값이 오류임을 알 수 있다.