1. 해밍 부호 (Hamming Code)
ㅇ 데이타 전송시 1 비트의 에러를 정정할 수 있는 자기 오류정정부호의 일종
ㅇ (n,k) 선형블록부호, 순회부호의 특성을 갖음
* 미국의 Bell 연구소의 Hamming에 의해 고안된 간단한 블록부호 (1950년)
2. (7,4) 해밍부호 例
ㅇ 부호화 (1 비트 오류정정을 위한 3개의 패리티비트 첨가)
- 부호표
- 패리티검사비트 생성규칙 (짝수 패리티 비트)
. 여기서,
는 Modulo-2 덧셈 연산 (0+0=0, 0+1=1, 1+0=1, 1+1=0)
- 부호어 생성을 위한 행렬표현 ☞ 생성행렬 참조
ㅇ 복호화 (Syndrome Decoding - 오염된 부호의 오류정정)
- 신드롬표
- 신드롬 생성규칙
- 신드롬 생성 행렬표현
3. (7,4) 해밍부호 특징
ㅇ 유효 부호어 개수 : 16개
- 2k = 24 = 16개
ㅇ 닫힘 성질
- 두 부호어의 합이 다시 또다른 부호어가 됨
ㅇ 최소 해밍거리 : 3
- 임의의 두 부호어 쌍 간에 항상 3 비트 만 상이함
ㅇ 신드롬 수 : 8개
- 1개 : 오류 없음
- 7개 : 1 비트 오류 징후(error pattern)
ㅇ 오류검출능력 : td ≥ dmin - 1 = 3 - 1 = 2
- dmin - 1 보다 작거나 같은 모든 오류 패턴을 검출할 수 있음
ㅇ 오류정정능력 : tc ≥ (dmin - 1)/2 ≥ (3-1)/2 = 1
- 잉여 패리티검사비트가 (n-k)인 3개 비트가 추가되므로,
dmin의 상한이 3 이 되면서 오류정정능력 비트수는 1 비트가 됨
. 각 부호의 해밍거리가 3 이상의 부호어로하는 부호계에서,
. 각 부호어의 거리가 3 이상이므로 하나의 부호어가 1 비트 잘못된 부호는,
. 다른 부호어와 명확하게 구별할 수 있으므로,
. 원리적으로 1 비트 에러를 정정할 수 있음.
ㅇ 패리티 비트를 필요한 수 만큼 정해진 위치에 두어서,
- 에러가 발생했을 때 에러 발생 비트를 알아내어 정정이 가능하도록 함.
4. 해밍조건
ㅇ 2 p >= m + p + 1
- m : 정보 비트 수, p : 최소잉여 비트 수
- 결국, 패리티 비트 수 p 는 위 관계식에 의해 결정