多項式碼

在編碼理論中，多項式碼（英語：polynomial code）是有效碼字集合是由多項式（通常是固定長度的多項式）可以被特定多項式（長度較短，稱為生成多項式）整除的一種線性碼。

定義

對於有限域 $GF(q)$，其元素我們稱作碼元。為了建立多項式碼，我們要確定一個 $n$ 個碼元的序列 $a_{n-1}\ldots a_{0}$ 其多項式為

$a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}.\,$

對於整數 $m\leq n$，令 $g(x)$ 為 $m$ 階多項式，稱為生成多項式。由 $g(x)$ 生成的多項式碼其碼字都是階數低於 $n$，並且可以被 $g(x)$ 整除（沒有餘式）的多項式。

例子

考慮 $GF(2)=\{0,1\}$ 上，$n=5$、$m=2$、生成多項式為 $g(x)=x^{2}+x+1$ 的多項式碼。此碼由下列碼字組成：

$0\cdot g(x),\quad 1\cdot g(x),\quad x\cdot g(x),\quad (x+1)\cdot g(x),$

$x^{2}\cdot g(x),\quad (x^{2}+1)\cdot g(x),\quad (x^{2}+x)\cdot g(x),\quad (x^{2}+x+1)\cdot g(x).$

或直接寫成：

$0,\quad x^{2}+x+1,\quad x^{3}+x^{2}+x,\quad x^{3}+2x^{2}+2x+1,$

$x^{4}+x^{3}+x^{2},\quad x^{4}+x^{3}+2x^{2}+x+1,\quad x^{4}+2x^{3}+2x^{2}+x,\quad x^{4}+2x^{3}+3x^{2}+2x+1.$

由於多項式碼定義在二元伽羅華域 $GF(2)=\{0,1\}$ 中，多項式元素用模q求和表示，於是最終多項式為：

$0,\quad x^{2}+x+1,\quad x^{3}+x^{2}+x,\quad x^{3}+1,$

$x^{4}+x^{3}+x^{2},\quad x^{4}+x^{3}+x+1,\quad x^{4}+x,\quad x^{4}+x^{2}+1.$

等價地，用二進制位的序列表示，這些碼字就是：

$00000,\quad 00111,\quad 01110,\quad 01001,$

$11100,\quad 11011,\quad 10010,\quad 10101.$

注意到如所有多項式碼一樣，這個碼確實是一個線性碼，即碼字的線性組合還是碼字。在域為 GF(2) 的情形，可以通過對二進制形式的兩個碼字取XOR（如00111 XOR 10010 = 10101）得到其線性組合。

編碼

在 $GF(q)$ 上長度為 $n$、生成多項式為 $m$ 階多項式 $g(x)$ 的多項式碼中，會有 $q^{n-m}$ 個碼字。事實上，根據定義，若且唯若一個碼字形式為 $p(x)=g(x)\cdot q(x)$（其中 $q(x)$ 的階小於 $n-m$）時，$p(x)$ 才是一個碼元。因為會有 $q^{n-m}$ 個商，所以也會有相同數量的碼字。 未編碼的數據字長度應為 $n-m$。

一些作者，如（Lidl & Pilz, 1999），僅討論了從數據字到碼字賦值的映射 $q(x)\mapsto g(x)\cdot q(x)$。但在數據字不是碼字的一部分時會存在缺陷。

相反，常用下面的方法來建立系統碼：給定長度為 $n-m$ 的數據字 $d(x)$，先把 $d(x)$ 乘以 $x^{m}$，這樣的效果就是將 $d(x)$ 向左移 $m$ 位。$x^{m}d(x)$ 一般不能被 $g(x)$ 整除，也就不是一個有效的碼字。不過，調整 $x^{m}d(x)$ 的最右面 $m$ 個符號可以得到唯一的碼字。 要求它，需要計算 $x^{m}d(x)$ 除以 $g(x)$ 的餘式：

$x^{m}d(x)=g(x)\cdot q(x)+r(x),\,$

其中 $r(x)$ 的階數小於 $m$。於是對應於數據字 $d(x)$ 的碼字定義為

$p(x):=x^{m}d(x)-r(x),\,$

注意以下性質：

1. $p(x)=g(x)\cdot q(x)$ 可以被 $g(x)$ 整除。特別地，$p(x)$ 是一個有效碼字。
2. 由於 $r(x)$ 的階數小於 $m$，$p(x)$ 最左面的 $n-m$ 個符號與 $x^{m}d(x)$ 中對應符號相同。換句話說，碼字的前 $n-m$ 個符號與原數據字相同。剩下的 $m$ 個符號稱為校驗位。

例子

對於 $n=5$、$m=2$、生成多項式為 $g(x)=x^{2}+x+1$ 的上述碼，我們的帶下列從數據字到碼字的賦值：

• 000 ↦ 00000
• 001 ↦ 00111
• 010 ↦ 01001
• 011 ↦ 01110
• 100 ↦ 10010
• 101 ↦ 10101
• 110 ↦ 11011
• 111 ↦ 11100

譯碼

錯誤消息可以直接通過多項式除以生成多項式得到非零餘式而檢測出來。

假設碼字沒有差錯，系統碼可以通過剝離 $m$ 個檢驗位譯碼。

如果存在差錯，則應在譯碼前糾錯。有些多項式碼（如BCH碼）會有高效的譯碼算法。

多項式碼的性質

對於所有數字碼來說，多項式碼的誤差檢測與校正能力取決於該碼的最小漢明距離。由於多項式碼是線性碼，最小漢明距離等於任何非零碼字的最小重量。在上面的例子中，最小漢明距離是2，因為01001是一個碼字，並且沒有非零碼字只有一位是1的。

多項式碼更具體的性質往往取決於它的生成多項式的特定的代數性質。這裏有此類性質的一些例子：

• 一個多項式碼若且唯若生成多項式能夠整除 $x^{n}-1$ 時為循環碼。
• 如果生成多項式是本原多項式，若 $n\leq 2^{m}-1$，則得到的碼的漢明距離最小為3。
• 在BCH碼中，生成多項式在擴展域中有能夠得到很大漢明距離的特定的根。

巧妙選取生成多項式的多項式碼的代數性質可以用來尋找有效的誤差校正算法。BCH碼就屬於這種情況。

特定多項式碼

• 循環碼；所有循環碼都是多項式碼；如CRC碼。
• BCH碼；一類漢明距離很大、有代數糾錯算法的循環碼。
• 里德-所羅門碼；BCH碼的一個重要子集，有特別高效的結構。

參考文獻

• W.J. Gilbert and W.K. Nicholson: Modern Algebra with Applications, 2nd edition, Wiley, 2004.
• R. Lidl and G. Pilz. Applied Abstract Algebra, 2nd edition. Wiley, 1999.