GF(2) 上的 4 阶移位寄存器输出序列分析

本文将分析一个在 GF(2) 上的 4 阶移位寄存器，其初始状态为 S0=(0001)，连接多项式为 g(x)=x4+x+1，并写出其输出序列。

一、基本概念

• GF(2)： 代表二元有限域，即在模 2 的意义下进行运算，只能取 0 或 1 两个值。
• 移位寄存器： 是一种电子电路，通常用于在数字电子系统中存储和移动数据，由一组触发器和逻辑门组成。
• 连接多项式： 用于控制移位寄存器的反馈逻辑，决定新的数据位的生成方式。

二、移位寄存器工作原理

在这个 4 阶移位寄存器中，有 4 个触发器，每个触发器的输出都连接到下一个触发器的输入，最后一个触发器的输出又回到第一个触发器的输入，这种连接方式被称为环形连接。输出序列由寄存器中的当前状态决定。每个时钟脉冲都会使寄存器中的数据向左移动一位，新的数据位由连接多项式 g(x) 生成，通过将 g(x) 与移位寄存器中最右侧的数据位进行异或运算得到。

三、输出序列计算

1. 初始状态： S0=(0001)
2. S1： 数据向左移动一位得到 S1=(0010)。新的数据位通过 g(1) = 1 XOR 1 = 0 计算得到，所以 S1=(0010)。
3. S2： 数据向左移动一位得到 S2=(0100)。新的数据位通过 g(0) = 0 XOR 1 = 1 计算得到，所以 S2=(0100)。
4. S3： 数据向左移动一位得到 S3=(1001)。新的数据位通过 g(1) = 1 XOR 1 = 0 计算得到，所以 S3=(1001)。
5. S4： 数据向左移动一位得到 S4=(0011)。新的数据位通过 g(1) = 1 XOR 1 = 0 计算得到，所以 S4=(0011)。

四、输出序列

因此，这个 4 阶移位寄存器的输出序列是：(0001) -> (0010) -> (0100) -> (1001) -> (0011) -> ...

五、总结

这个移位寄存器的输出序列是线性的，这意味着任何给定的状态的输出都可以由初始状态和连接多项式计算出来。这种性质在密码学中非常有用，因为可以用它来生成伪随机数序列。