什麼是 Hamming Code（漢明碼）？
什麼是 Hamming Code（漢明碼）？
歡迎你點入本篇文章，會促成我想做這篇的原因，主要是因為在上計概時，突然浮現很多靈感，跟一大堆的問題（教授，為什麼要講的這麼淺白呢？我想知道更多啊啊！），為了一次解決我所有的困惑，於是製作本篇文章。
若文章有任何疑點及錯誤的地方歡迎提出。
為什麼需要這個東東？
在資料傳輸或儲存的過程中，位元（bit）可能因雜訊、干擾或硬體錯誤而被翻轉（做補數 0 -> 1, 1-> 0），導致資料錯誤。為了解決這個問題，1950 年代美國數學家 Richard Wesley Hamming 發明了 Hamming Code（漢明碼）。
Hamming Code 是一種錯誤偵測與單一錯誤修正（Single Error Correction, SEC）的編碼機制，在傳輸資料時會加入一些額外的同位元（parity bits），使接收端能判斷是否發生錯誤，並自動修正錯誤的位元。
若結合奇偶校驗位（overall parity bit），還可以達到 SECDED：Single Error Correction, Double Error Detection。
另外這個 Hamming Code 也廣泛應用到當今熟知的記憶體上面，如 ECC 校驗。
Hamming Code 的運算步驟
有關 Hamming Code 的詳細數學原理，推薦這篇給大家：最简单易懂的汉明码Hamming Code原理！-CSDN博客
1. 決定需要多少個 Parity Bits
假設有 $m$ 個資料位元（data bits），需要多少個 parity bits $r$ 才能偵測與修正錯誤？公式： $2^r \ge m + r + 1$
若資料長度為 7，則可找到最小的 $r$ 使得 $2^r \ge 7 + r + 1$ 。
經過數學窮舉的結果，最終可得到 r = 4，因此會有 4 bits 用來給 parity bits 糾錯。
2. 配置 Parity Bits 跟 Data Bits
Parity Bits 以代號 P 表示；Data Bits 以代號 D 表示。
而 Parity Bits 擺放在位元位置的 $2$ 次方上（ $1(2^0), 2(2^1), 4(2^2), 8(2^3)\cdots$ ）
如有 7 個 Data bits，4 個 Parity Bits，共 11 個 Bits：
| 位元位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 內容 | $P_1$ | $P_2$ | $D_1$ | $P_4$ | $D_2$ | $D_3$ | $D_4$ | $P_8$ | $D_5$ | $D_6$ | $D_7$ |
可看見上表在位元位置 1、2、4、8 中存放了這 4 個 Parity Bits，其他都是 Data bits。
3. 計算 Parity Bits
首先以下是看 Parity Bits 要算的規則：
- $P_1$ ：從 2 的 0 次方變來的，所以凡是「位元位置」（非常重要，是位元的位置！！）二進位數字最右邊有 1 的都要被它檢查。
- $P_2$ ：同理，它是從 2 的 1 次方變來的，凡位元位置的二進位數字最右邊數過來第二位有 1 的都要被它檢查。
- $P_4$ 、 $P_8$ 以此類推。
然後根據每個 $P$ 不同檢查奇偶校驗（看題目要問你奇還是偶校驗去決定）。
把上面的表抄下來，D 改成實際的位元（假設 D 完整的位元是 1001101，從左到右分別為 $D_1$ 到 $D_7$）：
| 位元位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 內容 | $P_1$ | $P_2$ | 1 | $P_4$ | 0 | 0 | 1 | $P_8$ | 1 | 0 | 1 |
那 $P_1$ 要檢查的位元位置有第 1、3（ $11_2$ ）、5（ $101_2$ ）、7（ $111_2$ ）、9（ $1001_2$ ）、11 位元。
看到這裡，你會發現如果先寫好所有位元位置的二進位數的話，會比較好找，因此先寫吧：
- 1 : $0001_2$
- 2 : $0010_2$
- 3 : $0011_2$
- 4 : $0100_2$
- 5 : $0101_2$
- 6 : $0110_2$
- 7 : $0111_2$
- 8 : $1000_2$
- 9 : $1001_2$
- 10 : $1010_2$
- 11 : $1011_2$
所以 $P_2$ 要檢查的有第 2、3、6、7、10、11。
$P_4$ 為 4、5、6、7。
$P_8$ 為 8、9、10、11。
那這邊要先看的是 Data bits，確定它們 1 的個數是否為奇數或偶數時，就可以依據 parity bits 去做調整，看是要將 parity bits 調 0 還是調 1。
所有的動作完成後，這 11 位元就是 Hamming Code 了。
4. 接收方糾錯方法
若得到 Hamming Code = 11101011011，收到的資料為：11101011111
假設 $P_1$ 與 $P_4$ 錯誤（其餘正確），則錯誤位元位置 = 1 + 4 = 5，表示第 5 位出錯。
接收端翻轉該位元即可修正。
Hamming Code 的簡單小範例
假設 4 個資料位元為 $D_1D_2D_3D_4 = 1011$ ，以 even parity 的方式求出 Hamming Code。
拿公式對一下要拿幾個 parity bit： $2^r \ge 4 + r + 1$ ，窮舉一下會發現 r 最小等於 3，所以有 $P_1, P_2, P_4$
然後畫表配置一下（4 位資料位元 + 3 位 Parity Bit = 7 位）：
| 位元位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 內容 | $P_1$ | $P_2$ | 1 | $P_4$ | 0 | 1 | 1 |
位元位置的二進位表示如下：
- 1 : $001_2$
- 2 : $010_2$
- 3 : $011_2$
- 4 : $100_2$
- 5 : $101_2$
- 6 : $110_2$
- 7 : $111_2$
然後以下是每個 Parity Bit 要檢查的位元位置：
- $P_1 = 1, 3, 5, 7$
- $P_2 = 2, 3, 6, 7$
- $P_4 = 4, 5, 6, 7$
首先檢查 $P_1$ ，其他位置 3, 5, 7 的 1 的個數剛好是偶數，所以 $P_1$ 位元為 0。
再來是 $P_2$ ，其他位置 3, 6, 7 的 1 的個數是奇數，因此 $P_2$ 的位元 = 1。
最後是 $P_3$ ，其他位置 5, 6, 7 的 1 的個數是偶數，所以 $P_4$ 的位元 = 0。
最後求得 Hamming Code = $(0110011)_2$ 。
從 Hamming Code 糾錯
要從 Hamming Code 糾錯，首先要做一件事情就是錯誤症候群（Error Symptom），什麼意思呢？就是對每一個 P1、P2、P4… 去檢查，如果有錯，那一個位置就會是 1，否則為 0 表示沒錯，最後由下往上拼湊起來的二進位數字，轉成十進位去對比第幾個位置就知道哪裡有錯了。
以 Given a 7-bit Hamming codeword $(1011001)_2$ with odd parity, extract the data bits, determine bit error if any, and if so, correct it. 這道題目來舉例。
首先列出這樣的表格：
| position | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| Type | $P_1$ | $P_2$ | D | $P_4$ | D | D | D |
| Bits | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
然後對 $P_1, P_2, P_4$ 做檢查：
- $P_1 = 1 + 1 + 0 + 1 = 3$ ，沒有錯，所以錯誤症候群 $S_1 = 0$ 。
- $P_2 = 0 + 1 + 0 + 1 = 2$ ，有錯，所以錯誤症候群 $S_2 = 1$ 。
- $P_4 = 1 + 0 + 0 + 1 = 2$ ，有錯，所以錯誤症候群 $S_3 = 1$ 。
由下到上組合起來得到二進位數字 $(110)2$ ，轉換成十進位是 $6{10}$ ，那錯誤的地方就是位置 6 了，這時候將位置 6 的位元反轉就可以完成糾錯。
最後得到正確的 Hamming Code 為： $(1011011)_2$ 。
參考資料
