LFSR的概念

Linear Feedback Shift Register - 线性反馈移位寄存器

LFSR 是一种移位寄存器电路，其中两个或多个中间步骤的输出线性组合并反馈到输入值。该电路有以下特点：

• 如果初始状态相同，则最终会得到相同的输出序列(即输出序列是确定的)；
• 输出序列趋向于随机序列(伪随机)；
• 经过一定次数的迭代后，你将得到与初始状态相同的状态值(最大重复间隔可由( 2 n 2^n 2n-1)计算，其中n为移位寄存器的数目)。

LFSR的初始值称为伪随机序列的种子。
该电路常表示为一个多项式。例如图中的电路可以表示为y= x 4 x^4 x4+ x 1 x^1 x1+1。
其中，多项式的最大阶数为4，即图中i=4，x(0)与x(1)需要异或，异或的结果作为x(4)。

M序列

M Sequence (MLS : Maximum Length Sequence)
最大重复间隔为 2 n 2^n 2n-1的LFSR序列。
下表为一些已知的M序列: