线性移位寄存器怎么用特征多项式求反馈函数

线性移位寄存器（Linear Feedback Shift Register，LFSR）是一种常见的硬件实现方式，可以用于产生伪随机数序列、加密算法等领域。其反馈函数决定了其输出序列的特性，通过特征多项式可以求出反馈函数。

一个n位的LFSR可以表示为：

x[n] = x[n-1]⊕x[n-2]⊕...⊕x[n-m]

其中，x[n]表示第n个时刻的输出，x[n-1]、x[n-2]、...、x[n-m]表示当前时刻（n）和前m个时刻的输入信号。 ⊕表示异或运算。

特征多项式是一个二进制多项式，可以通过如下方式求出：

1. 假设LFSR的反馈函数为f(x)，那么可以构造一个初始状态为1，长度为n的序列，依次输入到LFSR中，得到一个长度为2^n-1的序列S。

2. 将S的末尾n位取出，得到一个n位的二进制数。

3. 这个二进制数就是LFSR的特征多项式，可以表示为f(x) = xn + a1xn-1 + a2xn-2 + ... + an-1x + an，其中ai为0或1。

例如，对于一个3位LFSR，反馈函数为f(x) = x3 + x2 + 1，可以构造一个初始状态为1，长度为3的序列输入到LFSR中，得到如下输出序列：

1 1 1 0 1 0 1

取出末尾3位得到101，这就是LFSR的特征多项式。

反馈函数可以根据特征多项式求出，方法如下：

1. 将特征多项式转换为反馈系数a1~an，其中a1~an-1表示LFSR中各阶反馈的系数。

2. 构造一个长度为n的序列，初始状态为任意值（通常是全0），依次输入到LFSR中，得到一个长度为2^n-1的序列S。

3. 对于S中每一个元素，计算其对应的反馈系数和输入信号的乘积，然后进行异或运算，得到反馈函数。

例如，对于特征多项式f(x) = x3 + x2 + 1，反馈系数为a1=1，a2=1，a3=0。构造一个初始状态为000的序列，输入到LFSR中，得到如下输出序列：

000 001 011 110 101 010 100

对于每一个时刻，根据反馈系数和输入信号的乘积计算反馈函数，得到如下表格：

| 时刻 | 输出 | 输入信号 | a1*a2 | a1*a3 | a2*a3 | a1*a2*a3 | 反馈函数 |
|------|------|----------|-------|-------|-------|----------|----------|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
| 3 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
| 4 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| 5 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 6 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |

因此，反馈函数为f(x) = x2 + x + 1。