Hamming Distance - Error 검출/정정 능력 관계
1. 개요
o 채널의 오류율 특성에 따라 채널 코드에 요구되는 오류 제어 능력을 결정한다.
o 주어진 코드는 오류 검출 능력과 오류 정정 능력에 의하여 특징 지어지고,
코드의 오류 검출/정정 능력은 코드의 최소 해밍 거리에 의해 좌우된다.
o 해밍 거리는 수신된 단어와 송신한 단어 사이에 일치하지 않는 비트의 개수를 세어서 측정함
2. 최소 해밍 거리 (dmin)
o 코드의 최소 해밍 거리는 잉여비트 수 (r)과 관계가 있다.
dmin ≤r + 1 (Singleton 경계)
o 복호화 규칙은 수신된 단어로부터 최소 해밍 거리에 놓인 코드워드를
전송 단어로 간주하는 것을 기반으로 함
o 모든 코드워드 (Codeword)쌍에 대해 0 이 아닌 해밍거리를 계산할 수 있고,
여기에는 해밍거리가 최소인 적어도 하나의 코드워드 쌍이 존재함
<예>
(1) k개 비트로 구성된 2k개의 2진 메시지 집합
예를 들면 (0, 0, .., 0) 과 (1, 0, .., 0) 이 존재하고, 모든 메시지는 고유함
dmin = 1 , (잉여비트 r = 0)
(2) 위에 패리티 비트가 하나 추가된 경우
두 메시지가 최소거리 1을 갖을 때 패리티 비트가 추가된 두 코드워드 간의
최소거리는 2이다.
dmin = 2 ( = r + 1 )
(3) 패리티 비트 대신 메시지 첫 번째 비트를 검사 비트로 사용할 경우
dmin = 1 ( < r + 1 )
(4) 반복 코드의 경우 : 0 -> 000, 1 -> 111
dmin = 3 ( = r + 1 )
3. 오류 검출/정정 능력 관계
o dmin ≥t + 1 일 때
t 개까지의 오류를 검출할 수 있으며 그 역도 성립함
o dmin ≥2t + 1 일 때
t 개까지의 오류를 정정할 수 있으며 그 역도 성립함
o dmin ≥2tc + 1 이고, dmin ≥tc + td + 1 이면
tc 까지 오류를 정정할 수 있고, td ( > tc ) 개의 오류까지 검출할 수
있으며 그 역도 성립함
이상