에러 검출 코드

: 에러 위치 검출과 정정 모두 가능

해밍코드(hamming code)

단일 비트 에러의 검출 및 위치 지정(정정)

데이터 비트 수를 d, 패리티 비트 수를 p라 할 때, 만족해야 할 조건:

• 왼쪽 식은 최소 데이터 비트 수
• 오른쪽 식은 최대 데이터 비트 수

ex. d=8개의 데이터 비트를 전송하려면

식을 만족하는 p는 4 (범위 5…11)에만 해당하므로
⇒ 패리티 비트 4개가 필요

해밍 코드에서 패리티 비트 위치 결정과 검사 영역

해밍 코드에서는 짝수 패리티(even parity) 사용

패리티 비트 위치

전체 전송 비트열에서, 2의 거듭제곱 위치에 패리티 비트를 둠.
나머지 위치는 데이터 비트($D_{3},\,D_{5},\,D_{6},\,D_{7},\,D_{9},\,\dots$) 가 채워짐

각 패리티 비트의 검사 영역

$P_k$ 는 비트 번호의 이진수 에서 k번째 비트가 1인 모든 비트를 검사

패리티	영역에 속한 비트 위치 (체크 대상)
P₁ (1)	1, 3, 5, 7, 9, 11, …
P₂ (2)	2, 3, 6, 7, 10, 11, …
P₄ (4)	4, 5, 6, 7, 12, 13, 14, 15, …
P₈ (8)	8, 9, 10, 11, 12, 13, 14, 15, …

오류 검출 · 정정

1. 수신된 각 $P_k$ 영역 내에서 1의 개수를 세어 짝수여야 하는지 확인
2. 규칙 위반이 발생한 $P_k$ 들의 번호(1,2,4,8…)를 이진수의 가중치로 합산
3. 그 합이 오류가 발생한 비트 위치
   ex. $P_1, P_4$ 오류 → 1+4=5 → 5번째 비트 오류