PE Notes · 네트워크
해밍 코드
2의 거듭제곱 자리에 패리티를 두어 한 비트 위치를 찾아 뒤집는 해밍 코드를 신드롬, SEC/DED, CRC·리드솔로몬과 비교합니다.
한 비트가 뒤집혀도 위치를 알면 다시 뒤집으면 됩니다. 해밍 코드는 패리티를 1, 2, 4, 8… 자리에 두고, 각 패리티가 담당 비트를 짝·홀로 맞춥니다. 의 고전이며, 재전송이 어려운 메모리와 우주 링크에 남았습니다.
자리를 정하면 주소가 나온다
는 데이터 4비트에 패리티 3비트를 붙여 7자리를 만듭니다. 일반식은 2^r ≥ k + r + 1입니다. k=4이면 r=3이 최소입니다. 코드율은 4/7입니다.
짝수 패리티라면, P1은 1·3·5·7, P2는 2·3·6·7, P4는 4·5·6·7을 0으로 맞춥니다. 확장하면 전체 짝 한 비트를 더해 두 비트 오류를 검출합니다(SECDED).
| 기호 | 의미 |
|---|---|
| k | 데이터 비트 |
| r | 패리티 비트 |
| n = k+r | 코드워드 길이 |
| SEC | 한 비트 정정 |
| DED | 두 비트 검출, 정정은 못 함 |
을 해시가 ‘바뀌었는가’로 본다면, 해밍은 ‘몇 번 비트가 바뀌었는가’를 답합니다. 이나 서명과는 층이 다릅니다.
신드롬이 위치다
수신은 같은 패리티를 다시 계산합니다. 깨진 검사들의 번호를 이진수로 읽으면 그 자리가 오류입니다. 그 비트를 반전하면 끝입니다. 모두 맞으면 은 0입니다.
두 비트 오류를 한 비트로 오인해 더 망가뜨릴 수 있어, 서버 메모리는 전체 패리티를 더한 SECDED를 씁니다. 이 그 상자입니다. 암호학의 타원곡선 ECC와 약어만 같습니다.
| 비교축 | 해밍 SEC | SECDED |
|---|---|---|
| 정정 | 1비트 | 1비트 |
| 검출 | 2비트는 위험 | 2비트 검출 |
| 오버헤드 | r | r+1 |
| 자리 | 수업·간단 링크 | 서버 메모리 |
거리와 이웃 코드
해밍 거리는 두 워드가 다른 비트 수입니다. 최소 거리 d면 검출은 d−1, 정정은 ⌊(d−1)/2⌋입니다. (7,4)는 d=3이라 1비트 정정입니다.
는 검출에 강하고 정정은 없습니다. 오버헤드는 짧습니다. 해밍은 단일 비트에 강하고 버스트에 약합니다. 와 리드솔로몬은 여러 심벌을 고칩니다. 는 희소 검사 행렬로 5G·SSD에 가깝습니다.
| 비교축 | 해밍 | CRC | 리드솔로몬 |
|---|---|---|---|
| 목적 | 정정 | 검출 | 다중 심벌 정정 |
| 버스트 | 약함 | 강함(검출) | 강함 |
| 오버헤드 | log₂ n 부근 | 16~32비트 | 가변 |
| 자리 | ECC 메모리 | 이더넷 | 디스크·QR |
오류제어 토픽이 재전송을 다루면, 여기서는 한 장의 계산만 적습니다.