GF(2) 上 4 阶线性反馈移位寄存器输出序列分析

GF(2) 上 4 阶线性反馈移位寄存器输出序列分析

本文将详细分析一个在 GF(2) 上的 4 阶线性反馈移位寄存器，它的初始状态为 S0=(0001)，连接多项式为 g(x)=x4+x+1。我们将计算该寄存器的输出序列，并分析其循环节。

1. 术语解释

• GF(2): GF(2) 代表二元有限域，也称伽罗瓦域，它只包含两个元素：0 和 1。
• 线性反馈移位寄存器 (LFSR): 一种数字电路，由多个存储单元组成，每个单元存储一个二元数 (0 或 1)。LFSR 的工作原理是：
  • 每次移位操作，将寄存器中的所有数字向左移动一位，最左边的数字移出寄存器；
  • 最右边的位置用一个新的数字填充，该数字是根据连接多项式和寄存器中某些数字的线性组合计算得出的。
• 连接多项式: 一个用来定义 LFSR 移位规则的多项式。它的系数只能是 0 或 1。

2. 寄存器输出序列计算

根据题意，我们有：

• 初始状态：S0=(0001)
• 连接多项式：g(x)=x4+x+1

根据连接多项式，我们可以得到 LFSR 的移位规则：

• 左移操作: 将寄存器中的所有数字向左移动一位，最后一位填 0。
• 反馈操作: 将倒数第二位和最后一位进行异或运算，结果作为新的第一位。

下面是逐步计算寄存器输出序列的步骤：

• S0: 0 0 0 1
• S1: 0 0 1 0 (左移 + 反馈: 0 ^ 1 = 1)
• S2: 0 1 0 0 (左移 + 反馈: 1 ^ 0 = 1)
• S3: 1 0 0 1 (左移 + 反馈: 0 ^ 1 = 1)
• S4: 1 1 1 0 (左移 + 反馈: 1 ^ 0 = 1)
• S5: 0 1 1 1 (左移 + 反馈: 1 ^ 1 = 0)
• S6: 1 0 1 1 (左移 + 反馈: 1 ^ 1 = 0)
• S7: 1 1 0 1 (左移 + 反馈: 1 ^ 1 = 0)
• S8: 1 1 1 0 (左移 + 反馈: 0 ^ 1 = 1)
• ...

3. 输出序列的循环节

从上面的计算结果可以看出，输出序列会进入一个循环：

0001 -> 0010 -> 0100 -> 1001 -> 1110 -> 0111 -> 1011 -> 1101

这个循环节的长度为 8。这意味着，一旦 LFSR 的状态进入这个循环，它将不断重复这个循环。

总结

通过以上分析，我们可以得出结论：

• 该 LFSR 的输出序列是一个无限循环的序列，循环节长度为 8。
• 循环节中的每一个状态都是唯一的，并且它们按照特定的顺序循环出现。
• 连接多项式和初始状态共同决定了 LFSR 的输出序列。