[筆記] 網路通訊原理:頻道編碼與錯誤控制 (二)

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:

位置 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) 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),可用來診斷與更正錯誤。

Exit mobile version