多项式码

在编码理论中，多项式码（英语：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.