Hamming Code 漢明碼

Hamming Code 屬於一種線性分組碼，在漢明碼系統中，若 Parity Check Bits 的數量為 R，原始資料長度為 K，總資料長度為 N，則 2^R ≧ K + R + 1，此外 R 必須大於 3。

漢明碼和先前所提的分組碼主要的差異在於漢明碼會將 Parity Check Bits 與原始資料混雜擺放，漢明碼的檢查碼會落在 1、2、4、8、16 等 2^H 位置。

假設現在有一數據為「11010」，要將其加入 Hamming Code 的話，首先進行 Parity Check Bits 數量的判斷，代入 K = 5，2^R ≧ 6 + R 可以得到 R = 4，因此我們可以知道第 1、2、4、8 位是要拿來做為 Hamming Code 使用的，同時在完成之後新的數列串會有 9 個 bits，原始資料將被依序塞入剩下的第 3、5、6、7、9 位中。

接下來將位置表畫出來 (各列的數字填上該位置編號的二進位值)，並且將原有資料所在欄位若本來為「0」者，將整列改填 0，再將要作為 Hamming Code 的欄位暫時留空，之後再將各欄的總值加總，若為偶數填 0，否則填 1：

位置	A	B	C	D
1	0	0	0
2	0	0		0
3	0	0	1	1
4	0		0	0
5	0	1	0	1
6	0	0	0	0
7	0	1	1	1
8		0	0	0
9	0	0	0	0
原始 加總	0	0	0	1

Hamming Code 的規則要求每列的 1 必須有偶數個，因此可以很快反推出剛剛留空的部分：

位置	A	B	C	D
1	0	0	0	1
2	0	0	0	0
3	0	0	1	1
4	0	0	0	0
5	0	1	0	1
6	0	0	0	0
7	0	1	1	1
8	0	0	0	0
9	0	0	0	0
原始 加總	0	0	0	1

接下來就可以視各列的值是否為 0 或位置本身來決定對應欄位要填入 1 或是 0：

1

0

1

0

1

0

1

0

0

Hamming Code 的錯誤校正範例

以「101110100」為例，首先畫出位置表：

位置	A	B	C	D
1	0	0	0	1
2	0	0	0	0
3	0	0	1	1
4	0	1	0	0
5	0	1	0	1
6	0	0	0	0
7	0	1	1	1
8	0	0	0	0
9	0	0	0	0

 

接下來把每一欄由上到下看一遍，如果該欄有奇數個 1，就在對應的欄位上填 1，若有偶數個 1 則填入 0，以上面這個例子而言最後會得到：

0

1

0

0

而二進制的 0100 就是十進制中的「4」，由此可得知是第四位發生錯誤，將發生錯誤的地方 0、1 互換即可得到 101010100 的正確結果。

Cyclic Code 循環碼

循環碼也是一種線性分組碼，最明顯的特色在於不論左移或右移循環幾位，所得到的結果永遠都是合法的，例如 abcdefg => bcdefga => cdefghab => …. 都是合法的，因為其編碼與解碼較為容易，因此被大量採用於 FEC 系統所使用的分組碼中。

循環碼的表示方式

c (x) = m (x) x^n-k + c_p(x)

c_p(x) 為檢查多項式 (check polynomial)，等於 m(x) x^n-k 除以 g(x) 所得的餘式。 (※ n-k 次方是為了平衡加上檢查碼之後偏移的位數)

s(x) 則為症狀方程式 (syndrome polynomial)，接收方會接收到 r(x) + e(x) (Error Polynomial，錯誤多項式)，而若 e(x) 不存在 (也就是沒有發生任何錯誤)，則 r(x) + s(x) 應該能被 g(x) 整除，若沒有整除的話則餘數就稱為 s(x)，可用來診斷與更正錯誤。