Hamming Code
Summary
Hamming Code는 전송 중 한 비트가 틀렸을 때, 어디가 틀렸는지 찾아 고칠 수 있는 오류정정 코드다.
핵심 insight
메시지에 여분의 검사 비트(parity bit)를 붙이면, 받은 쪽에서 “어느 위치가 이상한지” 추적할 수 있다.
Hamming distance
두 bit string이 몇 자리에서 다른지 세는 값을 Hamming distance라고 한다.
예:
1011
1001
두 번째 자리만 다르므로 Hamming distance는 1이다.
Hamming(7,4)
대표적인 Hamming code는 4비트 데이터를 7비트로 바꾼다.
- data bits: 4개
- parity bits: 3개
- total: 7개
보통 parity bit는 1, 2, 4번 위치처럼 2의 거듭제곱 위치에 둔다.
위치: 1 2 3 4 5 6 7
종류: p p d p d d d
각 parity bit는 정해진 위치 묶음을 검사한다. 오류가 생기면 어떤 parity check들이 실패했는지를 보고, 틀린 위치 번호를 알아낸다.
예시
받은 7비트 중 parity check 결과가 101이라고 하자. 이 값을 이진수 위치로 읽으면 5다. 즉 5번 비트가 틀렸다는 뜻이다.
그러면 5번 비트를 뒤집어 고친다.
한계
- 한 비트 오류는 고칠 수 있다.
- 두 비트 오류는 감지할 수는 있어도 기본 Hamming code만으로는 정확히 고치기 어렵다.