패리티 비트 & 해밍 코드

패리티 비트

정보 전달 과정에서 오류가 생겼는 지 검사하기 위해 추가하는 비트를 말한다.
전송하고자 하는 데이터의 각 문자에 1비트를 더하여 전송한다.

종류 : 짝수 패리티(Even Parity), 홀수 패리티(Odd Parity)

 

패리티 예시

7비트 데이터	짝수	홀수
0000000 (0)	00000000	10000000
1010001 (3)	11010001	01010001
1101001 (4)	01101101	11101001
1111111  (7)	11111111	01111111

 

짝수 패리티

• 전체 비트에서 1의 개수가 짝수가 되도록 패리티 비트를 정하는 것이다.
• Ex.) 데이터 비트에서 1의 개수가 홀수면 패리티 비트를 1로 정한다.

 

홀수 패리티

• 전체 비트에서 1의 개수가 홀수가 되도록 패리티 비트를 정하는 것이다.

 

해밍 코드

데이터 전송 시 1비트의 에러를 정정할 수 있는 자기 오류정정 코드를 말한다.
패리티비트를 보고, 1비트에 대한 오류를 정정할 곳을 찾아 수정할 수 있다. (패리티 비트는 오류를 검출하기만 할 뿐 수정하지는 않기 때문에 해밍 코드를 활용)

• (n, k) 선형블록부호 및 순회부호에 속한다.
  • 선형블록부호 : 블록부호에 선형성이 추가된다.
  • 순회부호 : 블록부호에 선형성 및 순회성이 추가적으로 부가된다.

 

패리티 비트 체크 범위 확인 및 패리티 비트의 값 결정

n번째 패리티 비트는 n번째에서 시작하고, n비트 만큼을 포함하고 n비트씩 건너뛴 비트들을 대상으로 패리티 비트 범위를 지정하고 각 패리티 비트를 결정한다.

 

• P1의 영역 = D3 + D5 + D7 + D9 + D11
• P2의 영역 = D3 + D6 + D7 + D10  + D11
• P4의 영역 = D5 + D6 + D7 + D12
• P8의 영역 = D9 + D10 + D11 + D12

Ex.) 전송할 데이터 비트가 01011011(91)이고 짝수 패리티 비트 사용시 생성된 해밍 코드는 다음과 같다.

• P1의 영역 = D3 + D5 + D7 + D9 + D11 = 0 + 1 + 1 + 1 + 1 = 0
• P2의 영역 = D3 + D6 + D7 + D10  + D11 = 0 + 0 + 1 + 0 + 1 = 0
• P4의 영역 = D5 + D6 + D7 + D12 = 1 + 0 + 1 + 1 = 1
• P8의 영역 = D9 + D10 + D11 + D12 = 1 + 0 + 1 + 1 = 1

 

 

해밍 조건

   2 ^(n-k)  ≥  n + 1                       

• k : 정보 비트 수
• n-k : 최소 잉여 비트 수
• 결국, 최소로 필요한, 패리티 비트 수 n-k 는, 위 관계식에 의해 결정된다.

 

 

출처 : 

https://velog.io/@octo__/%ED%95%B4%EB%B0%8D-%EC%BD%94%EB%93%9C-Hamming-Code

http://www.ktword.co.kr/test/view/view.php?m_temp1=1212

https://gyoogle.dev/blog/computer-science/computer-architecture/%ED%8C%A8%EB%A6%AC%ED%8B%B0%20%EB%B9%84%ED%8A%B8%20&%20%ED%95%B4%EB%B0%8D%20%EC%BD%94%EB%93%9C.html