数字IC知识点总结（10）-线性反馈移位寄存器（LFSR）

在我们之前的文章中，我们讲过了扰码器电路。在串行扰码器电路中，主要应用的就是线性反馈移位寄存器。今天我们就从伪随机序列的角度，说一说线性反馈移位寄存器。

同余伪随机序列

生成伪随机序列通常有两种方法，第一种是采用复现关系实现：

当B=0是为倍增同余，当B  0时称为混合同余。但是很显而易见的是，这个伪随机序列具有很强的周期性，并不能符合均匀分布的随机序列特性。

在这种序列下，第  位数字的周期为  （在经过  个数之后会遇到相同的数），在序列中

可以看出伪随机序列都具有周期性，而且不能被消除。因此倍增的方法是不可以采用的

另一种实现方法就是无输入的线性反馈移位寄存器构成伪随机序列生成电路。

反馈移位寄存器与异或门构成的伪随机序列生成电路

无输入的线性反馈移位寄存器构成的伪随机序列生成电路，生成的序列至于寄存器初始状态和反馈方式有关，从实质上讲这种数字序列还是伪随机的。因为每一个向量生成的概率是相等的。

对于反馈移位寄存器和异或门构成的电路，可以按下面的关系式生成序列

对于m位的线性反馈移位寄存器，最多可以产生  个不同状态。如果一个序列发生器正好生产这  个不同状态之后才重复此序列，那么该序列发生器称为最大长度序列发生器。

如何使序列发生器生成最大长度的序列呢？首先线性反馈移位寄存器反馈分为两种，一种是IE型的LFSR（如图一），即异或门内接的线性反馈移位寄存器。另一种是异或门外接的线性反馈移位寄存器，简称EE型LFSR（如图二）。

公式中的常数项表示接不接入反馈，常数项为1即为接入，否则不接入。

LFSR的数学基础

对于任意一个m阶的线性反馈移位寄存器，根据本原多项式，连接电路都可以产生最大长度为  的序列，称之为M序列。对于每一个m，总会存在项数最少的而且每项系数为1的多项式，这样的多项式称之为本原多项式。基于本原多项式所实现的电路最简单。

本原多项式具有这样的特性：本原多项式的反也是本原多项式，根据本原多项式的反也可以生成最大序列。比如  互为反，它们都是本原多项式

M序列的特性

1. M序列的周期是 
2. 对于给定的多项式，他们可以生成L个不同的M序列，且他们的相移不同
3. 对于任意一个M序列的第k位，出现0或1的概率为 
4. 一个M序列中0和1出现的概率接近于随机序列中的概率。
5. 对于任意自然数k，存在另一个自然数r，使得  (移位加)
6. m>4的多项式，原多项式的反所对应的伪随机序列的顺序也与原多项式的顺序相反
7. 对于任意一个长度为  的M序列中，都会有一组长度为m的“1”和一组长度为m-1的“0”