벨 연구소, 1947년
리처드 해밍은 1946년에 벨 전화 연구소에 입사했다. 그곳의 릴레이 컴퓨터는 기술자들이 오류 후에 다시 시작할 수 있는 평일에만 실행되었다. 주말에는 무언가 문제가 생기면 기계가 멈췄고, 작업들은 월요일까지 대기했다.
해밍은 격분했다. '기계가 오류를 감지할 수 있다면, 왜 그것을 위치시키고 정정할 수 없는가?'라고 생각했다. 이 좌절감은 이진 산술과 패리티 검사에 대한 깊은 친숙함과 함께, 무대를 마련했다.
첫 번째 통찰: 직사각형 부호
해밍의 첫 아이디어: 메시지 비트를 m×n 직사각형으로 배열하고, 모든 행과 모든 열에 패리티 검사를 추가한다. 단일 오류는 정확히 하나의 실패한 행 검사와 하나의 실패한 열 검사를 생성한다. 그 교점이 오류의 위치를 지칭한다.
중복도 비율: (m+1)(n+1) / mn. 미적분학은 고정된 메시지 크기에 대해 정사각형이 이를 최소화함을 보여준다. 그러나 m과 n이 커질수록, 이중 오류가 더 가능성이 높아진다 — 보편적 답변이 없는 공학적 판단이다.
직사각형 중복도 최소화
4×4 직사각형은 16개의 메시지 비트를 4개의 행 검사와 4개의 열 검사 그리고 1개의 모서리 패리티 비트 = 16개 메시지 비트에 대해 9개 검사 비트로 전달한다.
중복도 비율: (m+1)(n+1) / mn = 25/16 ≈ 1.56.
10×10 직사각형의 경우: 100개 메시지 비트, 121개 총 비트, 중복도 ≈ 1.21.
이진 수로서의 신드롬
직사각형 부호 통찰로부터 몇 주 후, 해밍은 뉴저지 농경지를 지나 뉴욕 방향으로 가고 있었고, 정신적으로 자신의 성공을 검토하고 있었다. 삼각형 부호가 그에게 떠올랐다 — 더 나은 중복도. 그 다음 입방체. 그 다음 4차원, 5차원...
각 추가 차원은 중복도를 개선했다. n차원의 변 길이가 2인 초입방체는 2^n개 꼭짓점에 대해 n+1개의 패리티 검사만 사용한다. 그러나 이것이 최적인가?
세기 논증
n+1개의 패리티 비트는 신드롬을 생성한다: (n+1)-비트 이진 수. 그 신드롬은 2^n + 1개의 서로 다른 결과를 식별해야 한다: 2^n개의 오류 위치 각각에 더해, 특별한 '오류 없음' 결과.
2^(n+1) = 2·2^n — 거의 충분하다. 비율 2 만큼 부족하다. 해밍은 문제를 미뤘다.
핵심 통찰
나중에, 해밍은 새로운 아이디어를 가지고 돌아왔다: 신드롬 자체를 오류 위치를 이름 붙이는 이진 수로 사용하자. 위치 1 = 이진 001, 위치 2 = 이진 010, 위치 3 = 이진 011 등. 모든 0은 '오류 없음'을 위해 예약한다.
이는 신드롬을 패리티 검사의 결과에서 주소로 변환한다. 패리티 검사는 단일 비트가 뒤집힐 때 정확히 올바른 주소를 생성하도록 설계된다.
(7,4) 부호 설계
7-비트 부호 (3개 패리티 비트, 4개 메시지 비트)의 경우, 위치 1부터 7까지의 이진은: 001, 010, 011, 100, 101, 110, 111이다.
패리티 검사 1은 비트 0 = 1인 위치들을 포함한다: 위치 1, 3, 5, 7.
패리티 검사 2는 비트 1 = 1인 위치들을 포함한다: 위치 2, 3, 6, 7.
패리티 검사 3은 비트 2 = 1인 위치들을 포함한다: 위치 4, 5, 6, 7.
패리티 비트는 2의 거듭제곱 위치에 위치한다: 1, 2, 4. 메시지 비트는 나머지를 점유한다: 3, 5, 6, 7.
비트 6이 뒤집히면, 패리티 검사 2와 3이 실패한다 (이진 110 = 6). 신드롬이 110 = 6을 읽는다. 위치 6을 뒤집는다. 완료.
단일 오류 정정, 이중 오류 감지
(7,4) 해밍 부호는 단일 오류를 정정한다. 그러나 두 비트가 뒤집히면? 추가 보호가 없으면, 복호기는 신드롬 규칙을 적용하고 코드워드를 잘못된 메시지로 '정정'한다 — 침묵의 오정정이다.
SECDED: 하나의 추가 패리티 비트
전체 코드워드(모든 7비트)를 포함하는 단일 패리티 비트 p₀를 추가한다. 이제 신드롬은 4개의 항목을 가진다: 원래의 3개 검사 플러스 p₀.
``
기존 신드롬 새로운 p₀ 의미
000 0 정정
000 1 p₀에만 오류
xxx 1 단일 오류, 기존 신드롬이 이름 붙인다
xxx 0 이중 오류 — 표시한다
``
네 가지 경우는 완전하다. 이중 오류는 두 비트를 뒤집는다: 기존 신드롬은 000을 읽지 않을 것이다 (두 비트 모두가 함께 신드롬의 두 개를 손상시킨다), 그러나 p₀는 두 번 뒤집혀 0으로 돌아온다. xxx + 0 패턴은 구분 불가능하다.
SECDED가 작동하는 이유
SECDED 규칙은 패리티의 모듈로 구조를 악용한다. 짝수 패리티의 경우, 단일 뒤집기는 p₀를 변경한다. 이중 뒤집기는 p₀를 변경하지 않는다. 그래서 p₀는 모듈로 2 오류를 센다.
기하학적 그림
해밍은 다른 방향에서 같은 곳에 도착했다: 해석 기하학. 각 n-비트 문자열을 n차원 초입방체의 꼭짓점으로 나타낸다. 단일 비트 뒤집기는 점을 한 축을 따라 한 모서리 길이 이동한다. 두 번의 뒤집기: 두 모서리. 메트릭은 해밍 거리이다.
해밍 거리 t인 코드워드 c 주위의 해밍 공을 정의한다: c의 t-비트 뒤집기 이내의 모든 점. 단일 오류 정정의 경우, t = 1.
단일 오류 정정을 위한 조건: 서로 다른 코드워드 쌍 주위의 반경 1인 공은 겹쳐서는 안 된다. 겹치면, 겹침에서 수신된 단어는 두 코드워드 중 어느 것에든 속할 수 있고 복호기가 실패한다.
이는 직접 최소 거리로 변환된다: 반경 1인 두 개의 공은 코드워드가 최소 3만큼 떨어져 있을 경우에만 겹치지 않는다 (d_min ≥ 3).
(7,4) 부호는 d_min = 3을 달성한다. 해밍의 한계: 2^7 / (1 + 7) = 16 = 2^4. 정확히 16개의 코드워드. 완전 부호: 반경 1인 16개의 공이 겹침이나 간격 없이 {0,1}^7을 채운다.
공학적 판단
해밍은 명확했다: 오류 정정 부호는 공학적 판단을 포함하고, 순수 수학이 아니다.
메시지 길이: 더 긴 메시지는 더 효율적인 코딩을 허용한다 (n개 메시지 비트에 대해 log n 패리티 비트). 그러나 더 긴 메시지는 또한 더 많은 노이즈를 축적하고, 거짓 단일 정정으로 미끄러지는 이중 오류의 위험을 증가시킨다.
정정 대 감지 수준: 한 오류 정정을 두 개의 추가 오류 감지로 거래한다. 최적 분할은 채널의 노이즈 특성에 따라 달라진다.
현장 유지보수 값: 장비가 더 복잡해지면서, 현장 기술자는 첫 원칙에서 모든 결함을 진단할 수 없다. 자가 진단하는 시스템은 유지보수에 필요한 기술을 극적으로 감소시킨다. 해밍은 이를 가장 중요한 이점 중 하나로 불렀고, 종종 순수 신뢰성 증가보다 더 중요하다.
스타일: 행운은 준비된 마음을 돕는다
해밍은 12장을 직접적인 도전으로 마쳤다. 그는 발견을 주로 벨 연구소에서 자신의 주요 의무를 수행하면서 이상한 시간에 3~6개월의 작업으로 설명했다.
그는 이를 가능하게 한 세 가지를 식별했다:
1. 준비: 문제가 나타나기 전에 패리티 검사, 이진 산술 & 군론에 대한 깊은 친숙함.
2. 성공 검토: 과거 해결책을 습관적으로 재생하여 그들의 스타일을 내재화한다. 삼각형 부호가 그에게 통근하는 동안 직사각형 부호를 정신적으로 검토하면서 떠올랐다.
3. '괜찮은 것 같다'로 정착하지 않기: 겉보기 최적을 받아들임으로써 한 번 화상을 입었다. 그는 부호가 최적임을 증명할 수 있을 때까지 계속 밀었다.