패리티비트 & 해밍코드

패리티 비트

패리티 비트는 정보의 전달 과정에서 오류가 생겼는지 검사하기 위해 추가된 비트이다. 문자열 내 1비트의 모든 숫자가 짝수 또는 홀수인지를 보증하기 위해 전송하고자 하는 데이터의 각 문자에 1 비트를 더하여 전송하는 방법으로[1] 2가지 종류의 패리티 비트(홀수, 짝수)가 있다. 패리티 비트는 오류 검출 부호에서 가장 간단한 형태로 쓰인다. (위키백과)

• 짝수 패리티
  데이터의 모든 1의 개수를 짝수로
• 홀수 패리티
  데이터의 모든 1의 개수를 홀수로

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

Q)짝수 패리티일 때 7비트 데이터가 1010001라면?

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

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

해밍코드

데이터 전송 시, 1비트의 에러를 정정할 수 있는 자기 오류정정 코드
패리티 비트를 참고하여 1비트에 대한 오류를 정정할 곳을 찾아 수정할 수 있다.

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

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

1, 3, 5, 7번째 비트 확인 : 0101로 짝수이므로 '0'

2, 3, 6, 7번째 비트 확인 : 0111로 홀수이므로 '1'

4, 5, 6, 7번째 비트 확인 : 1011로 홀수이므로 '1'

역순으로 패리티비트 '110'을 도출했다. 10진법으로 바꾸면 '6'으로, 6번째 비트를 수정하면 된다.

따라서 정답은 00110'0'1이다.

예제 출처
해밍 코드 예제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 이 됩니다.