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

本文分析了 GF(2) 上的 4 阶线性移位寄存器，其初始状态为 S0=(0001)，连接多项式为 g(x)=x4+x+1。

专业名词解释：

• GF(2)：伽罗瓦域 GF(2) 是一个包含两个元素 (0 和 1) 的有限域，其运算遵循模 2 运算规则。在 GF(2) 上，加法和减法是一样的，即 1+1=0，0+0=0，1+0=1，0+1=1。
• 4 阶移位寄存器：指一个包含 4 个存储单元的寄存器，每个存储单元只能存储 0 或 1 的二进制数。
• 连接多项式：表示移位寄存器的运算规则，它是一个多项式，其系数对应着移位寄存器中每个存储单元的反馈连接方式。
• 初始状态：表示移位寄存器开始工作时，各个存储单元的值。
• 输出序列：指移位寄存器在每一次运算后得到的输出值，通常以二进制形式表示。

移位寄存器工作原理：

移位寄存器的运算分为两步：移位和反馈。

1. 移位：将寄存器中的每个存储单元的值向左移动一位，最高位丢弃，最低位补 0。
2. 反馈：将移位后的状态和连接多项式做异或运算，得到一个新的存储单元的值，将其存储到寄存器的最低位。

分析过程：

1. 初始状态 S0 = (0001)。
2. 移位 得到 S1 = (0010)。
3. 反馈 将 S1 和连接多项式 g(x)=10011 做异或运算，得到 1，将 1 存储到寄存器的最低位，得到 S2 = (1000)。
4. 继续移位和反馈，得到以下输出序列：
   • S0 = (0001) 输出 0001
   • S1 = (0010) 输出 0010
   • S2 = (1000) 输出 0100
   • S3 = (0001) 输出 1001
   • S4 = (0011) 输出 0011
   • S5 = (0110) 输出 0110
   • S6 = (1101) 输出 1101
   • S7 = (1011) 输出 1011
   • S8 = (0111) 输出 0111
   • S9 = (1110) 输出 1110
   • S10 = (1100) 输出 1100
   • S11 = (1000) 输出 1000
   • S12 = (0001) 输出 0001 ...

结论：

该移位寄存器的输出序列为：0001，0010，0100，1001，0011，0110，1101，1011，0111，1110，1100，1000，0001，…，该序列具有周期性，循环节为 12。