Hamming Code 漢明碼

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

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

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

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

位置ABCD
1000
2000
30011
4000
50101
60000
70111
8000
90000
原始
加總
0001

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

位置ABCD
10001
20000
30011
40000
50101
60000
70111
80000
90000
原始
加總
0001

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

101010100

Hamming Code 的錯誤校正範例

以「101110100」為例,首先畫出位置表:

位置ABCD
10001
20000
30011
40100
50101
60000
70111
80000
90000

 

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

0100

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

Cyclic Code 循環碼

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

循環碼的表示方式

c (x) = m (x) xn-k + cp(x)

cp(x) 為檢查多項式 (check polynomial),等於 m(x) xn-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),可用來診斷與更正錯誤。

  • 有疑問的人

    請問一下漢明碼不是確定是 等號嗎?? 怎麼可以用線性分區碼的定義去做 >= 去做??

    • Jyun Ming Huang

      漢明碼本身就是線性區段碼的一種,範例可另外參見 Wikipedia 上 http://zh.wikipedia.org/wiki/%E6%B1%89%E6%98%8E%E7%A0%81 將 11000010 編碼成 101110010010 的過程。

      該範例中,原始資料長 K = 8,R = 4,滿足 2^R ≧ K + R + 1 (16 ≧ 8 + 4 + 1 = 13)

  • Steve Zhen

    不是縱列全部加起來是0就代表沒錯
    因為兩個1做XOR計算也會是0
    事實上0可能代表的是兩個以上的錯誤
    用你的例子來說101110100這個code
    有可能錯的是編號1 4 8 9 正確的也許是001010111