# 什麼是 Hamming Code（漢明碼）？

[TOC]

歡迎你點入本篇文章，會促成我想做這篇的原因，主要是因為在上計概時，突然浮現很多靈感，跟一大堆的問題（~~教授，為什麼要講的這麼淺白呢？我想知道更多啊啊！~~），為了一次解決我所有的困惑，於是製作本篇文章。

若文章有任何疑點及錯誤的地方歡迎提出。

## 為什麼需要這個東東？

在資料傳輸或儲存的過程中，位元（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博客](https://blog.csdn.net/qq_44143499/article/details/126457676)

### 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$ 。

## 參考資料

[Hamming Code - GeeksforGeeks](https://www.geeksforgeeks.org/computer-networks/hamming-code-in-computer-network/)

[Calculating the Hamming Code](https://users.cs.fiu.edu/~downeyt/cop3402/hamming.html)

[Hamming code - Wikipedia](https://en.wikipedia.org/wiki/Hamming_code)

[最简单易懂的汉明码Hamming Code原理！-CSDN博客](https://blog.csdn.net/qq_44143499/article/details/126457676)