패리티 비트 & 해밍 코드

Dayon·2023년 1월 28일
0

CS공부

목록 보기
12/18

🚘 패리티 비트

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

🔹 종류

수신자는 송신자로부터, 어떤 패리티 비트 규칙을 사용했는지 공유를 받고, 수신자는 수신받은 데이터가 공유받은 패리티 비트 규칙을 만족하는지 확인해 오류 검출

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

🔹 예제

짝수 패리티일 때 7비트 데이터가 1010001 이다.

1이 총 3개이므로, 짝수로 맞춰주기 위해 1을 더해야 함

답 : 11010001 (규칙 : 맨앞이 패리티비트)



✍🏻 해밍코드

  • 데이터 전송시, 1비트의 에러를 정정할 수 있는 자기 오류 정정 코드

  • 패리티 비트 사용 시, 수신자는 오류 검출 및 데이터 재송신만 가능한 단점 존재

  • 해밍코드 사용시, 수신자는 오류 검출 + 오류 수정 가능


🔸 특징

  • 2 bit 오류를 검출할 수 있고, 1 bit의 오류를 수정 가능

  • 데이터 비트 외에 오류 검출 및 교정을 위한 잉여 비트 필요

  • 해밍 코드 중에서 1,2,4,8,16, … ,2n2^n 번째 비트는 오류 검출을 위한 패리티 비트

  • 패리티 규칙이 정해진 후 → n번째 패리티 비트는 n번째 비트에서 시작하여 n비트 만큼을 포함하고, n비트씩 건너뛴 비트들을 대상으로, 패리티 비트를 결정할 수 있다.


🔸 예제

짝수 패리티의 해밍 코드가 0011011일때 오류가 수정된 코드는?

  1. 1, 3, 5, 7번째 비트 확인 : 0101로 짝수이므로 '0'
  2. 2, 3, 6, 7번째 비트 확인 : 0111로 홀수이므로 '1'
  3. 4, 5, 6, 7번째 비트 확인 : 1011로 홀수이므로 '1'

역순으로 ‘110’ 도출했다. 110(2진법) = 6(10진법), 6번째 비트를 수정하여 0011001 이 정답이다.


🔸 공식

해밍 코드 변환 시, 추가할 패리티 비트 개수

2pd+p+12^p ≥ d + p + 1

(d = 데이터 비트 수, p = 패리티 비트 수 ) ex, 234+3+12^3 ≥ 4 + 3 + 1



🔗 참조한 사이트

https://wooono.tistory.com/400

https://dos-soles.tistory.com/20

profile
success is within reach, allow yourself time

0개의 댓글