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

线性移位寄存器的特征多项式可以通过其连接的存储单元数和反馈连接的方式来确定。设线性移位寄存器有n个存储单元，反馈连接的方式为f(x)，则其特征多项式P(x)为：

P(x) = 1 + f(x) * x + f(x) * x^2 + ... + f(x) * x^(n-1)

反馈函数f(x)可以通过以下步骤来求得：
1. 假设线性移位寄存器的输出为y0, y1, y2, ..., yn-1，其中y0为最后一个存储单元的输出。
2. 假设反馈连接的存储单元为第k个存储单元，则f(x)的系数为1当且仅当k与n之间存在一个1的循环移位关系。
3. 可以通过试错法来找到f(x)。从k = 1开始，逐个尝试反馈连接的存储单元，看是否满足上述条件。如果找到符合条件的k，则将f(x)的系数相应位置置为1，否则为0。

举个例子，假设一个线性移位寄存器有4个存储单元，反馈连接的方式为y1 ⊕ y3，则其特征多项式为：

P(x) = 1 + x^2 + x^3

反馈函数为f(x) = x^1 + x^3。

相关问题

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

线性移位寄存器（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。

已知某线性反馈移位寄存器的反馈函数对应的特征多项式是p(x)=x^4+x^2+1，求 (1) 写出该线性反馈移位寄存器的反馈函数并画出结构图: (40分) (2) 设初始状态是 (0，0，1，0) ，求此线性反馈移位寄存器产生的序列及其周期 (写出具体过程) (40分)。

(1) 根据所给特征多项式，可以写出其对应的线性反馈移位寄存器的反馈函数为 $f(x)=x^4+x^2+1$，其结构图为：

         +----> D ----+
         |            |
         v            |
1 -->[D]--->[D]--->[D]--->[D]--->[+]-->  输出
         ^     |    |
         |     |    |
         +-----+----+
           ^^^
           ||| 
           f(x)

其中，$[D]$ 表示数据存储器，$+$ 表示异或运算。

(2) 根据初始状态 (0,0,1,0) 可以得到初始状态下，寄存器中各位的值为 $s_0=(0,0,1,0)$。为了求出该线性反馈移位寄存器产生的序列，需要对初始状态进行迭代计算。

首先将反馈函数 $f(x)=x^4+x^2+1$ 转化为二进制形式 $f(x)=11001$，并将初始状态 $s_0=(0,0,1,0)$ 转化为二进制形式 $s_0=0010$。

接下来，按照以下步骤进行迭代计算：

1. 将寄存器中各位的值从左到右依次写出，得到 $s_1=0100$；
2. 计算 $s_1$ 和 $f(x)$ 的乘积，并对结果取模，得到 $r_1=s_1\cdot f(x)\mod 2=1001$；
3. 将 $r_1$ 的各位依次从右到左写入寄存器中，得到 $s_2=1001$；
4. 重复上述步骤，直到得到重复的状态。具体计算过程如下表所示：

| 迭代次数 | 寄存器状态 | 乘积 $s_i\cdot f(x)$ | 取模 $r_i$ | 下一状态 |
| -------- | ---------- | -------------------- | ---------- | -------- |
| 0 | 0010 | | | |
| 1 | 0100 | 110010 | 1001 | 1001 |
| 2 | 1001 | 111110010 | 1011 | 0111 |
| 3 | 0111 | 111111011110 | 0100 | 0010 |

因此，该线性反馈移位寄存器产生的序列为 $0010, 0100, 1001, 0111$，其周期为 3。