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

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

一、基本概念

• GF(2)：GF(2) 是一个有限域，它仅包含两个元素：0 和 1。在该问题中，我们使用 GF(2) 中的元素来表示二进制位。
• 线性移位寄存器：线性移位寄存器是一种特殊的移位寄存器，其输出序列是输入序列的线性变换。

二、移位寄存器结构和连接多项式

该移位寄存器有 4 个位，可以表示 16 种不同的状态。连接多项式 g(x) = x^4 + x + 1 描述了移位寄存器的反馈路径，即每个位如何影响下一个位的值。在这个问题中，反馈路径是将第 1 位的值与第 4 位异或，将第 4 位的值与第 2 位异或，以及将第 4 位的值与第 1 位异或。这个过程可以表示为：

S4 = S3 ⊕ S0 S3 = S2 S2 = S1 S1 = S0

其中，S0-S4 表示移位寄存器的状态，⊕ 表示异或运算。

三、输出序列计算

初始状态为 S0 = (0001)，第一个输出位是 S0 的最低位，即 1。接下来，我们使用反馈路径计算下一个状态：

S1 = S0 = (0001) S2 = S1 = (0001) S3 = S2 = (0001) S4 = S3 ⊕ S0 = (0001) ⊕ (0001) = 0000

现在，我们得到一个新的状态 S4，它的最低位为 0，作为第二个输出位。接下来，我们继续使用反馈路径计算下一个状态：

S1 = S0 = (0001) S2 = S1 = (0001) S3 = S2 = (0001) S4 = S3 ⊕ S0 = (0001) ⊕ (0001) = 0000

我们发现，这个状态与前一个状态完全相同，即移位寄存器进入了一个循环。因此，输出序列也会重复，即 1 0 0 0 1 0 0 0 1 0 0 0 ...。

四、总结

GF(2) 上的 4 阶线性移位寄存器，初始状态为 (0001)，连接多项式为 g(x) = x^4 + x + 1，其输出序列为 1 0 0 0 1 0 0 0 1 0 0 0 ...。这个序列是周期性的，因为移位寄存器最终会进入一个循环状态。