基本介紹
- 中文名：多項式碼
- 外文名：polynomial code
定義,例子,編碼,解碼,多項式碼的性質,特定多項式碼,
定義
對於整數
，令g(x) 為 m 階多項式，稱為生成多項式。由 g(x) 生成的多項式碼其碼字都是階數低於 n，並且可以被g(x) 整除（沒有餘式）的多項式。
例子
考慮
上， n=5、m=2、生成多項式為
的多項式碼。此碼由下列碼字組成：
或直接寫成：
等價地，用二進制位的序列表示，這些碼字就是：
注意到如所有多項式碼一樣，這個碼確實是一個線性碼，即碼字的線性組合還是碼字。在域為 GF(2) 的情形，可以通過對二進制形式的兩個碼字取XOR（如00111 XOR 10010 = 10101）得到其線性組合。
編碼
在
上長度為 n、生成多項式為 m 階多項式g(x) 的多項式碼中，會有
個碼字。事實上，根據定義，若且唯若一個碼字形式為
（其中q(x) 的階小於n-m）時， p(x) 才是一個碼元。因為會有
個商，所以也會有相同數量的碼字。 未編碼的數據字長度應為n-m。
一些作者，如（Lidl & Pilz, 1999），僅討論了從數據字到碼字賦值的映射
。但在數據字不是碼字的一部分時會存在缺陷。
相反，常用下面的方法來建立系統碼：給定長度為n-m 的數據字
，先把
乘以
，這樣的效果就是將
向左移 m 位。
一般不能被g(x) 整除，也就不是一個有效的碼字。不過，調整
的最右面 m 個符號可以得到一個確定的碼字。 要求它，需要計算
除以g(x) 的餘式：
其中 r(x)的階數小於 m。於是對應於數據字d(x)的碼字定義為
注意以下性質：
1.
可以被 g(x) 整除。特別地，p(x) 是一個有效碼字。
2.由於 r(x)的階數小於 m，p(x) 最左面的 n-m 個符號與
中對應符號相同。換句話說，碼字的前 n-m 個符號與原數據字相同。剩下的 m 個符號稱為校驗位。
例如：
對於 n=5、m=2、生成多項式為 
的上述碼，我們的帶下列從數據字到碼字的賦值：
- 000 ↦ 00000
- 001 ↦ 00111
- 010 ↦ 01001
- 011 ↦ 01110
- 100 ↦ 10010
- 101 ↦ 10101
- 110 ↦ 11011
- 111 ↦ 11100
解碼
錯誤訊息可以直接通過多項式除以生成多項式得到非零餘式而檢測出來。假設碼字沒有差錯，系統碼可以通過剝離 m 個檢驗位解碼。如果存在差錯，則應在解碼前糾錯。有些多項式碼（如BCH碼）會有高效的解碼算法。
多項式碼的性質
對於所有數字碼來說，多項式碼的誤差檢測與校正能力取決於該碼的最小漢明距離。由於多項式碼是線性碼，最小漢明距離等於任何非零碼字的最小重量。在上面的例子中，最小漢明距離是2，因為01001是一個碼字，並且沒有非零碼字只有一位是1的。
多項式碼更具體的性質往往取決於它的生成多項式的特定的代數性質。這裡有此類性質的一些例子：
一個多項式碼若且唯若生成多項式能夠整除
時為循環碼。
如果生成多項式是本原多項式，若 
，則得到的碼的漢明距離最小為3。
在BCH碼中，生成多項式在擴展域中有能夠得到很大漢明距離的特定的根。
巧妙選取生成多項式的多項式碼的代數性質可以用來尋找有效的誤差校正算法。BCH碼就屬於這種情況。
特定多項式碼
- 循環碼；所有循環碼都是多項式碼；如CRC碼。
- BCH碼；一類漢明距離很大、有代數糾錯算法的循環碼。
- 里德-所羅門碼；BCH碼的一個重要子集，有特別高效的結構。
