해밍 거리
IT 위키
- Hamming Distance; 해밍 거리
- 같은 길이의 두 부호(비트열)에서 서로 다른 자리의 개수
- 1011101 과 1011001 → 해밍 거리 1
- 1001 과 0011 → 해밍 거리 2
비트열에서는 두 값을 XOR 한 뒤 1의 개수를 세면 된다.
부호 집합에 속한 모든 부호쌍의 해밍 거리 중 가장 작은 값을 최소 해밍 거리 d 라 한다. 부호의 오류 검출·정정 능력이 여기서 결정된다.
| 능력 | 조건 |
|---|---|
| t 비트 오류 검출 | d ≥ t + 1 |
| t 비트 오류 정정 | d ≥ 2t + 1 |
- d = 2 → 1비트 오류를 검출만 할 수 있다 (패리티 비트)
- d = 3 → 1비트 오류를 정정하고 2비트 오류를 검출한다 (해밍 코드)
- d = 4 → 1비트 정정 + 2비트 검출 (SECDED)
- 오류 검출·정정 부호 설계 (해밍 코드, CRC)
- 문자열 비교, 철자 교정
- 생물정보학의 서열 비교
- 기계학습의 범주형 거리 척도
- 편집 거리(Levenshtein) : 삽입·삭제까지 허용해 길이가 달라도 잰다. 해밍 거리는 길이가 같아야 정의된다
- 자카드 거리 : 집합의 겹침 정도
