线性反馈移位寄存器(LFSR)概念和M序列

时间:2024-03-19 07:13:01

LFSR的概念

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

线性反馈移位寄存器(LFSR)概念和M序列

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序列:

线性反馈移位寄存器(LFSR)概念和M序列