[Network] 패리티 비트와 해밍 코드

패리티 비트란?

• 송신 컴퓨터에서 수신 컴퓨터로 데이터를 전송할 때,

• 데이터는, 컴퓨터에 연결된 전선을 타고, 이진수의 전기 신호로 전달됩니다.

• 하지만, 전달하는 과정에서 데이터에 오류가 생길 수도 있습니다.

• 따라서, 송신 컴퓨터는, 수신 컴퓨터에서 해당 데이터의 오류를 확인할 수 있도록

• 이진수 데이터의 끝에, 0 또는 1 의 패리티 비티를 붙여 보냅니다.

  

• 따라서, 수신 컴퓨터는, 수신 받은 데이터의 끝에 붙은 패리티 비트를 보고,

• 해당 데이터에 오류가 있는지 확인하여, 오류가 있다면 송신 컴퓨터에게 데이터 재송신을 부탁하게 됩니다.

패리티 비트의 종류

• 패리티 비트는 '짝수 패리티' 와 '홀수 패리티' 가 존재합니다.

• 송신자는, 사용하는 패리티 종류에 따라 데이터에 다른 bit 를 추가하게 됩니다.

  • 짝수 패리티(Even Parity)

    

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

  • 홀수 패리티(Odd Parity)

    

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

• 수신자는 송신자로부터, 어떤 패리티 비트 규칙을 사용했는지 공유 받게 됩니다.

• 따라서, 수신자는 수신 받은 데이터가 공유 받은 패리티 비트 규칙을 만족하는지 확인함으로써, 오류를 검출하고

• 오류가 있다면, 송신 컴퓨터에게 데이터 재송신을 부탁하게 됩니다.

해밍 코드란?

• 패리티 비트 사용 시, 수신자는 오류 검출 및 데이터 재송신 요청만 가능했습니다.
• 하지만, 해밍 코드를 사용한다면, 수신자는 오류 검출 뿐만 아니라 오류 수정까지 가능해집니다.

해밍 코드의 특징

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 이 됩니다.

추가

• 해밍 코드 변환 시, 추가할 패리티 비트 개수는 아래 공식을 만족해야합니다.
  • 2^p ≥ d + p + 1 (ex, 2^3 ≥ 4 + 3 + 1 )
    • d = 데이터 비트 수
    • p = 패리티 비트 수

참고

• https://www.youtube.com/watch?v=me9__tpMbpQ
• https://www.youtube.com/watch?v=nwWZPG-5b5k