第 13 讲：线性反馈移位寄存器与本原多项式

课件最后把有限域多项式落到线性反馈移位寄存器（LFSR）。在 $\mathbb F_2$ 上，序列 $(a_k)$ 若满足

$$a_{k+n}=c_{n-1}a_{k+n-1}+\cdots+c_1a_{k+1}+c_0a_k,$$

其中加法就是异或，则由最初 $n$ 位可以不断产生后续位。对应的连接多项式可写为

$$f(x)=x^n+c_{n-1}x^{n-1}+\cdots+c_1x+c_0.$$

不同电路图可能把寄存器从左到右或从右到左编号，连接多项式也会相应写成倒数多项式。不要只看抽头位置硬背符号；最稳妥的是先从电路写出一条明确递推式，再按课程约定读出多项式。

把连续 $n$ 项组成状态

$$s_k=(a_k,a_{k+1},\ldots,a_{k+n-1}),$$

递推每做一步，就把状态左移并补入一个线性反馈位。因为状态空间有限，序列最终必然进入循环；若常数项 $c_0=1$，状态更新可逆，非零初态从一开始就在某个纯周期上。

周期从哪里来

寄存器状态是 $n$ 位向量，共有 $2^n$ 个。全零状态一旦进入就永远为零，所以非零状态的周期至多 $2^n-1$。当连接多项式是 $n$ 次本原多项式时，任意非零初态都会遍历全部 $2^n-1$ 个非零状态，得到最大长度序列，也称 m 序列。

例如递推 $a_{k+2}=a_{k+1}+a_k$ 对应 $x^2+x+1$。从非零初态 $(0,1)$ 出发得到 $0,1,1,0,1,1,\ldots$，周期为 3，恰是 $2^2-1$。

再看三阶例子

$$a_{k+3}=a_{k+1}+a_k,$$

对应 $f(x)=x^3+x+1$。从 $(1,0,0)$ 出发得到周期块

$$1,0,0,1,0,1,1.$$

连续三位状态依次为

$$100,001,010,101,011,111,110,$$

恰好遍历全部七个非零状态，然后回到 $100$。因此周期为 $7=2^3-1$。

多项式与序列的互译

左移算子 $L$ 定义为 $(La)_k=a_{k+1}$。递推关系就是 $f(L)a=0$。能湮灭序列的多项式构成 $\mathbb F_2[x]$ 的一个理想，其首一生成元称为序列的最小多项式。序列的线性复杂度就是该最小多项式的次数。

这解释了课件中的编码应用：多项式除法提供了快速的余数计算；LFSR 可以低成本地产生长周期伪随机序列；错误图样是否被生成多项式整除，决定循环码能否检测到它。

课件中的 $15$ 位单错纠正循环码

取本原多项式

$$g(x)=x^4+x+1\in\mathbb F_2[x].$$

它的周期是 $2^4-1=15$。把一个 $15$ 位向量 $(a_1,\ldots,a_{15})$ 对应成次数不超过 $14$ 的多项式

$$f(x)=a_1x^{14}+a_2x^{13}+\cdots+a_{15}.$$

选取所有能被 $g(x)$ 整除的 $f(x)$ 作为码字：

$$\mathcal C =\{f(x):\deg f\leq14,\ g(x)\mid f(x)\} =\{g(x)h(x):\deg h\leq10\}.$$

因为 $h$ 有 $11$ 个二进制系数，$\mathcal C$ 是维数为 $11$ 的线性码，共有 $2^{11}$ 个码字；一组基可取

$$g(x),xg(x),\ldots,x^{10}g(x).$$

发送码字 $f(x)$ 后，若第 $i$ 位翻转，接收多项式就是

$$f_1(x)=f(x)+x^{15-i}.$$

对 $g(x)$ 取余，码字部分余数为零，所以综合（syndrome）只剩

$$r_i(x)=x^{15-i}\bmod g(x).$$

由于 $g(x)$ 本原，$x$ 在 $\mathbb F_2[x]/(g)$ 的非零元乘法群中阶为 $15$。因此 $x^0,x^1,\ldots,x^{14}$ 的余式恰好是 $15$ 个互不相同的非零元，每个综合都唯一对应一个错误位置：

错误位 $i$	$x^{15-i}\bmod g(x)$	错误位 $i$	$x^{15-i}\bmod g(x)$
1	$x^3+1$	9	$x^3+x^2$
2	$x^3+x^2+1$	10	$x^2+x$
3	$x^3+x^2+x+1$	11	$x+1$
4	$x^3+x^2+x$	12	$x^3$
5	$x^2+x+1$	13	$x^2$
6	$x^3+x$	14	$x$
7	$x^2+1$	15	$1$
8	$x^3+x+1$

解码时先算 $f_1(x)$ 除以 $g(x)$ 的余式：余式为零，便没有检测到错误；余式等于表中的 $r_i(x)$，就在第 $i$ 位再异或一次 $1$，即加上 $x^{15-i}$，把该位纠正回来。

这个码没有重量为 $1$ 的非零码字；也没有重量为 $2$ 的非零码字，否则 $g(x)$ 会整除 $x^a+x^b=x^b(x^{a-b}+1)$，迫使 $x$ 的阶小于 $15$。所以它的最小距离至少为 $3$，确实能纠正一个比特错误。这就是课件构造的二元 $(15,11)$ 单错纠正循环码。

m 序列的几个可核对性质

对 $n$ 阶本原连接多项式产生的最大长度序列：

• 周期为 $2^n-1$；
• 一个周期内，$1$ 的个数为 $2^{n-1}$，$0$ 的个数为 $2^{n-1}-1$；
• 每个非零 $n$ 位状态恰好出现一次；
• 任意非零初态只会改变周期序列的起始相位，不会改变周期长度。

这些性质可以用来反查手算。若声称得到 m 序列，却出现全零状态、周期没有整除 $2^n-1$，或一个周期没有遍历所有非零状态，计算一定有问题。

题目常见的三个方向

由递推求周期

从指定初态逐步列状态，直到第一次回到初态。只盯输出位容易误判；比较完整的 $n$ 位状态才可靠。

由多项式判断最大周期

先判不可约，再检查根的阶是否为 $2^n-1$。只证明不可约还不够，因为不可约多项式的周期可能只是 $2^n-1$ 的真因子。

由序列反求关系

设一个可能的线性递推，把已知连续项代入，在 $\mathbb F_2$ 上解系数。能湮灭序列的最低次数首一多项式才是最小多项式；人为选得更长的递推也可能成立，但会高估线性复杂度。