免费线性反馈移位寄存器计算器

计算机作为确定性机器，没有外部物理过程就无法生成真正的随机数。线性反馈移位寄存器（LFSR）通过使用简单的XOR运算和移位寄存器结构生成伪随机二进制序列，提供了一种优雅的解决方案。本线性反馈移位寄存器计算器支持斐波那契和伽罗瓦两种配置，让您探索种子和抽头如何影响LFSR的输出，是研究移位寄存器、伪随机数生成器和二进制序列生成的理想工具。

什么是移位寄存器？它们如何构成LFSR？

移位寄存器是由触发器组成的链，每个触发器存储一位。在每个时钟周期，内容向右（或向左）移动一个位置，一端进入新位，最后一位被丢弃或形成输出。如果新输入位是某些当前位的线性函数（XOR或NXOR），则该电路成为线性反馈移位寄存器。参与反馈的位置称为抽头，初始配置称为种子。

XOR门执行模2加法，是LFSR设计中的基本线性操作。其真值表为：

输入 A	输入 B	输出 (A⊕B)
0	0	0
0	1	1
1	0	1
1	1	0

也可以使用NXOR门（它只是XOR的取反）。由于运算是线性的，整个寄存器构成一个在伽罗瓦域GF(2)上的线性系统。

LFSR的输出序列是周期性的，最大周期为$2^n - 1$（其中$n$是寄存器长度），前提是种子不全为零（否则寄存器将锁定在全零平凡状态）。周期很大程度上取决于抽头选择；能产生最大周期的特殊抽头集合称为最大长度抽头，对应于本原多项式的系数。

斐波那契LFSR与伽罗瓦LFSR

线性反馈移位寄存器有两种典型架构：斐波那契和伽罗瓦。它们使用相同的抽头和种子，但反馈应用方式不同。

斐波那契LFSR

在斐波那契LFSR中，所有抽头位进行异或运算形成一个反馈值，成为新的输入位。然后寄存器向右移位，丢弃最右位作为输出。数学上，如果$\vec{X} = (X_1,\dots,X_n)$是当前状态（$X_1$是最左位），$\vec{c} = (c_1,\dots,c_n)$是抽头向量（1表示抽头），则下一状态为：

\begin{aligned} X_i(t+1) &= X_{i+1}(t) \quad\text{for } i = 1,\dots,n-1,\$$2pt] X_1(t+1) &= \bigoplus_{j=1}^{n} \bigl(c_j \cdot X_j(t)\bigr). \end{aligned}

符号$\oplus$表示XOR。LFSR的输出是连续步骤中最右位$X_n(t)$的序列。

伽罗瓦LFSR

在伽罗瓦LFSR中，反馈在移位过程中应用。输出位（当前状态的最右位）直接影响抽头位置。常见的实现可描述为：

\begin{aligned} \text{Let } y &= X_n(t).\$$2pt] X_1(t+1) &= y,\\ X_i(t+1) &= X_{i-1}(t) \oplus \bigl(c_{i-1} \cdot y\bigr),\quad i=2,\dots,n, \end{aligned}

其中$c_i$（对于$i=1,\dots,n-1$）指示从左数第$i$个单元是否为抽头。如果$y=0$，位只是向右移位，不发生抽头翻转；如果$y=1$，抽头位置的位在右移前被取反。

两种类型的关系

对于产生最大长度序列的一组抽头，斐波那契和伽罗瓦LFSR的输出本质上是相同的序列，但一个相对另一个是反转的，并且可能存在相位移动。产生这种对偶行为的抽头向量互为倒数。例如，抽头位置为1、4、6和12的斐波那契LFSR（二进制抽头向量$100100000001$）产生最大长度序列。对应的伽罗瓦LFSR需要抽头位置为1、7、9和12（$100000101001$）才能生成相同的周期（经过反转和对齐后）。

实例：12位LFSR

让我们用一个具体的12位场景来演示：种子 = $100110011001$，抽头 = $110111011101$。

• 斐波那契模式：对抽头向量为1的位进行XOR求和，该和成为新的最左位。每个状态的最右位记录为输出。经过七步后寄存器返回到原始状态，输出流以$10010111\ldots$开始（周期 = 7）。
• 伽罗瓦模式：使用相同的种子和抽头，寄存器遵循伽罗瓦规则。产生的输出以$10100111\ldots$开始。反转此序列并移位几个位置后，恰好得到斐波那契输出，证实了上述对偶性。

此示例还表明周期仅为7，远小于最大可能周期$2^{12}-1 = 4095$。周期短的原因是所选抽头不构成最大长度集合。

LFSR的实际应用

线性反馈移位寄存器在数字系统中无处不在：

• 伪随机数生成器（PRNG），用于仿真、游戏和密码学。
• **内置自测（BIST）**电路，向数字模块施加所有可能的输入模式。
• 加扰器和解扰器，在通信链路中降低信号相关性。
• 流密码，将伪随机密钥流与明文进行XOR运算。
• 噪声生成，用于信号测试和干扰仿真。

由于LFSR在硬件上轻量且能以较小开销产生长周期，它们仍然是数字设计的基石。

如何使用LFSR计算器

此页面上的计算器提供了动手实验LFSR行为的方式：

1. 输入种子和抽头向量，为长度相等的二进制字符串。
2. 选择LFSR类型：斐波那契（默认）或伽罗瓦。
3. 选择输出模式：
   • 输出 – 显示生成的比特序列（以8位块分组）。
   • 步骤 – 显示每个时钟周期的完整寄存器状态。
   • 周期 – 仅返回周期长度。
4. 可选指定生成位数；留空则计算器在一个完整周期后停止。
5. **展开“附加设置”**以：
   • 将线性门从XOR切换为NXOR。
   • 启用“危险计算”，允许超过10,000步的序列（有助于更长的寄存器，例如16位最大周期65,535）。

计算器会自动检测最大长度LFSR（周期 = $2^n-1$）并通知您。如果寄存器变为全零，计算器也会停止，因为这种状态不能用于LFSR操作。

结论

线性反馈移位寄存器是生成伪随机二进制序列的经典数字构建模块。通过斐波那契和伽罗瓦两种架构，几行二进制代码就能产生几乎任意长度的周期。本页面的线性反馈移位寄存器计算器让您轻松探索种子和抽头选择如何影响输出，深入了解移位寄存器、伪随机数生成和二进制序列生成器。尝试不同的配置，看看哪些抽头能产生最长的周期，以及两种LFSR类型之间的相互关系。