跳轉到

6.1 Hamming 碼（1950）#

導言：週末的挫折，劃時代的發明#

1947 年（論文發表於 1950 年），Bell 實驗室的數學家 Richard Hamming 輪值使用公司唯一的打孔卡片機。週末輸入的程式若遇到讀卡錯誤（一位元翻轉），機器就中止並丟棄整批工作，他得等下個週末重來。Hamming 憤而思考：「機器明明知道出錯了，為什麼不能自己改？」——這個怒氣催生了錯誤更正碼（ECC）。

1950 年《Error Detecting and Error Correcting Codes》發表，提出 Hamming 碼：一類能更正一位元錯誤的高效線性碼。它與 Shannon 1948 的存在性理論互補：Shannon 說好碼存在，Hamming 給出第一個可實作的好碼。今日 ECC 無所不在：記憶體（ECC RAM）、硬碟、CD/DVD、衛星、5G——全是 Hamming 思想的後裔。

從奇偶檢驗到 Hamming 碼#

第一步：奇偶檢驗碼（只偵錯）#

在 \(k\) 個資料位元後加一個同位位元，使總數為偶：

\[ p = b_1 \oplus b_2 \oplus \cdots \oplus b_k \]

單一錯誤會破壞偶性 → 可偵測 1 位元錯，但無法更正（不知道錯在哪），也偵測不到雙位元錯。Hamming 的問題：怎麼把「知道有錯」升級為「知道哪裡錯」？

第二步：多個同位，各自覆蓋不同位置#

Hamming 的洞察：安排多組同位，每組覆蓋碼字的不同子集；錯誤位置可由「哪些組報警」唯一推出。經典 \((7,4)\) Hamming 碼：4 個資料位元 \(d_1 d_2 d_3 d_4\) 、3 個同位位元 \(p_1 p_2 p_3\) ，排成碼字 \((p_1, p_2, d_1, p_3, d_2, d_3, d_4)\) ，位置編號 \(1..7\) 。同位規則（用位置號的二進位覆蓋）：

同位 覆蓋位置 二進位判準
\(p_1\) 1, 3, 5, 7 位置號第 1 位元 = 1
\(p_2\) 2, 3, 6, 7 位置號第 2 位元 = 1
\(p_3\) 4, 5, 6, 7 位置號第 3 位元 = 1

（同位位元本身放在 2 的冪次位置：1, 2, 4。）

解碼：症狀碼（syndrome）#

接收後重算三個同位，違反與否組成三位元症狀碼 \(s = (s_1 s_2 s_3)\) ：

\[ s_1 = \bigoplus_{\text{位置覆蓋 } p_1} \text{位元}, \quad s_2 = \bigoplus_{\text{覆蓋 } p_2}, \quad s_3 = \bigoplus_{\text{覆蓋 } p_3} \]

症狀碼直接就是錯誤位置的二進位編號。 \(s = 000\) 無錯； \(s = 101\) （讀作 5）→ 第 5 位元錯，翻轉即得。優雅至極：檢驗矩陣的列就是位置號的二進位表示（見下）。

例題：完整編解碼#

資料 \(d = (1, 0, 1, 1)\) ：

  • \(p_1 = d_1 \oplus d_2 \oplus d_4 = 1 \oplus 0 \oplus 1 = 0\)
  • \(p_2 = d_1 \oplus d_3 \oplus d_4 = 1 \oplus 1 \oplus 1 = 1\)
  • \(p_3 = d_2 \oplus d_3 \oplus d_4 = 0 \oplus 1 \oplus 1 = 0\)

碼字 \(c = (0, 1, 1, 0, 0, 1, 1)\) 。假設第 5 位元在通道中翻轉，接收 \(y = (0, 1, 1, 0, 1, 1, 1)\) ：

  • \(s_1 = y_1 \oplus y_3 \oplus y_5 \oplus y_7 = 0 \oplus 1 \oplus 1 \oplus 1 = 1\)
  • \(s_2 = y_2 \oplus y_3 \oplus y_6 \oplus y_7 = 1 \oplus 1 \oplus 1 \oplus 1 = 0\)
  • \(s_3 = y_4 \oplus y_5 \oplus y_6 \oplus y_7 = 0 \oplus 1 \oplus 1 \oplus 1 = 1\)

\(s = 101_2 = 5\) → 第 5 位元翻回，還原 \(c\) ，取出資料 \((1, 0, 1, 1)\) 。✓

線性碼的正式架構#

Hamming 碼是線性碼的特例（第 6.2 節展開線性碼一般理論）。 \((7,4)\) Hamming 碼：

產生器矩陣（ \(G\) ：資料 → 碼字， \(c = G^T d\) 的行視角；此處以標準形式）：

\[ G = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix}, \qquad H = \begin{pmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{pmatrix} \]

\(H\) 的每一列互不相同且非零——這正是症狀碼能定位錯誤的原因：錯誤向量 \(e_i\) （單位位元）的症狀 \(H e_i^T\) 恰為 \(H\) 的第 \(i\) 列，七列互異故可分辨七種單錯位置。碼滿足

\[ c \in \mathcal{C} \iff H c^T = \mathbf{0} \]

碼空間是 \(\mathbb{F}_2^7\) 中 \(H\) 的核：維度 \(7 - 3 = 4\) ，共 \(2^4 = 16\) 個碼字，率 \(R = 4/7\) 。

Hamming 碼的家族與容量#

一般 Hamming 碼 \([2^r - 1, 2^r - 1 - r, 3]\) ：同位位元 \(r\) 個，碼長 \(n = 2^r - 1\) ，可更正 1 位元錯。

\(r\) \(n\) \(k\) 率 \(R\) 最小距離
2 3 1 0.333 3
3 7 4 0.571 3
4 15 11 0.733 3
5 31 26 0.839 3
6 63 57 0.905 3
7 127 120 0.945 3

率隨 \(r\) 增大趨近 1，但錯誤更正能力固定在 1 位元。在 BSC 上直接套用（更正 1 錯）的等效錯誤率為

\[ P_{\text{block}} = 1 - (1-p)^n - n p (1-p)^{n-1} \approx \binom{n}{2} p^2 \]

例題：效能估算#

\(p = 0.01\) 、 \((7,4)\) 碼：未更正塊錯誤率 \(1 - 0.99^7 - 7(0.01)(0.99^6) \approx 1 - 0.9321 - 0.0659 = 0.0020\) ，即約 \(2 \times 10^{-3}\) ；除以 4 個資料位元，位元錯誤率約 \(5 \times 10^{-4}\) ，比裸傳（ \(10^{-2}\) ）改善 20 倍，代價是率降到 \(4/7\) 。但 \(n = 127\) 時同樣 \(p\) ：雙錯事件約 \(\binom{127}{2} p^2 \approx 0.079\) ——長 Hamming 碼在 BSC 上並不逼近香農極限，這是 6.3 節「編碼增益」與第 10 章 Turbo/LDPC 登場的理由。

歷史前因後果#

誰、何時、為什麼#

  • 1948 Shannon：證明好碼存在（存在性，非建構）。
  • 1947–1950 Hamming：第一個建構性 ECC；同時定義了 Hamming 距離與 Hamming 界（6.2 節）。
  • 1950 Golay：同時期發現兩個完美碼 \([23,12,7]\) 與 \([11,6,5]\) （二元與三元）——完美碼極為罕見（Tietäväinen 1973 證明僅此幾族）。
  • 1960 Bose–Chaudhuri–Hocquenghem（BCH）：把 Hamming 推廣到多位元更正（7.2 節）。

Hamming 在 Bell 實驗室與 Shannon 是同事；他自述在聽了 Shannon 1948 的內部演講後深受震撼，決定找出實際的碼。理論（Shannon）與工程（Hamming）在兩年內相繼落地，這是資訊科學史上最漂亮的接力。

解決了什麼問題#

  1. 可靠儲存與傳輸：記憶體、磁帶、電話線的單錯自動更正。
  2. 偵錯到除錯的躍升：症狀碼把「有錯」升級為「錯在哪」。
  3. 線性代數的登場： \(G\) 、 \(H\) 矩陣架構成為之後所有代數碼的模板。

引發什麼新問題#

  1. 多位元錯誤：Hamming 只更正 1 錯，實際通道常有多錯與突發——BCH/RS 碼（7.2 節）。
  2. 距離的極限：碼的距離能多大？——Hamming 界、Plotkin 界、Gilbert–Varshamov 界（6.2 節）。
  3. 接近香農極限：Hamming 碼率受 1 錯限制，遠不及 \(C\) ——長碼 + 軟解碼，等待 Turbo/LDPC（第 10 章）。
  4. 計算複雜度： syndrome 解碼是 \(O(n)\) ，但一般線性碼的 ML 解碼是 NP-hard（Berlekamp–McEliece–van Tilborg, 1978）——複雜度理論介入編碼（9.3 節以 NP-hard 性做公鑰密碼）。

與其他領域的關聯#

線性代數#

\(G\) 與 \(H\) 是 \(\mathbb{F}_2\) 上的矩陣，碼是線性空間的核/列空間；症狀解碼是解線性方程組；對偶碼（ \(H\) 的列空間）是線性代數的正交補觀念。第 9.1 節的有限體將把 \(\mathbb{F}_2\) 推廣到 \(\mathbb{F}_q\) 。

群論與組合#

線性碼是加法群 \(\mathbb{F}_2^n\) 的子群，陪集（coset）分解給出標準陣列解碼表——群論直接進入解碼。

圖論#

\((7,4)\) Hamming 碼的奇偶檢驗矩陣對應Tanner 圖（9.2 節）：3 個檢驗節點、7 個變數節點的稀疏連接圖。把它放大、隨機化，就是 LDPC 碼（10.2 節）——Hamming 碼是 LDPC 的祖先。

數位電路#

Hamming 碼的 XOR 陣列在硬體上是幾個異或閘與查找表；ECC 記憶體控制器今日每秒執行數十億次症狀計算。

小結與思考題#

Hamming 碼用「多組同位 + 症狀定位」實現單錯更正；其線性結構（ \(G\) 、 \(H\) 、症狀）成為代數編碼的通用語言；但它受 1 錯限制，逼近香農極限的任務留給後世。本章接下來將系統化「距離—能力」理論（6.2）與編碼增益的真相（6.3）。

思考題

  1. 對資料 \(d = (0, 1, 1, 0)\) 計算 \((7,4)\) Hamming 碼字；若接收時第 3 位元翻轉，症狀碼為何？
  2. 證明： \((7,4)\) Hamming 碼的 16 個碼字中，任意兩碼字的 Hamming 距離 \(\ge 3\) （提示：線性碼的最小距離 = 最小非零碼字重量）。
  3. 為什麼同位位元要放在 2 的冪次位置？若放在其他位置，症狀碼還能直接讀出錯誤位置嗎？
  4. \(r = 4\) 的 \([15, 11]\) Hamming 碼，率與 \((7,4)\) 相比如何？對 \(p = 0.01\) 的 BSC，兩者的塊錯誤率誰更好？
  5. Hamming 碼在 \(n \to \infty\) 時率 \(\to 1\) ，為何仍遠離香農極限？（提示：1 錯限制 ⇒ 雙錯機率 \(\binom{n}{2}p^2\) 發散條件。）

下一節：最小距離與錯誤更正能力——把「能修幾個錯」變成幾何。