1968 Richard Hamming —— 當訊號在噪音中死去#

「電話線上每傳一段話就會錯幾個位元，怎麼可能讓機器通訊？貝爾實驗室的數學家用『冗餘』這個反直覺的答案救了數位時代。」

案件檔案#

1940 年代末，貝爾實驗室的繼電器電腦每週末重跑一次——因為出錯。當時主流觀念：減少錯誤（更好的硬體）。Hamming 的反問： 能否容許錯誤，但自動修正？ 這是從「防禦」到「容錯」的典範轉移。

Shannon 1948 年資訊論（參見 2005 案背景）已證明：只要傳輸率低於通道容量 C，就存在錯誤率任意小的編碼——但 Shannon 只證明存在，沒給出建構方法。Hamming 要找的是可實作的建構性編碼。

定義兩個等長位元串的 Hamming 距離 \(d(x,y)\) = 相異位元數。

最小距離 d_min 與糾錯能力 t 的關係（數學核心）：

  t = ⌊(d_min − 1) / 2⌋

  偵測 e 個錯需 d_min ≥ e + 1
  糾正 t 個錯需 d_min ≥ 2t + 1

直覺：把每個合法碼字畫成球心，半徑 t 的球互不重疊，收到字後落入哪個球，就還原成該球心。

位元編號 p1 p2 d1 p3 d2 d3 d4
p1 = d1⊕d2⊕d4   （覆蓋位置 3,5,6,7）
p2 = d1⊕d3⊕d4
p3 = d2⊕d3⊕d4

最小距離 = 3 → 可糾 1 錯、偵 2 錯

每 4 位元資料只花 3 位元代價——效率驚人。

\[\sum_{i=0}^{t} \binom{n}{i} \le 2^n / M\]

Hamming 碼恰好取等（完美碼），如同把整個空間用不重疊的球精確鋪滿。