trustintruth · 2020年10月21日

线性反馈移位寄存器(LFSR)及伪随机序列

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

同余伪随机序列

生成伪随机序列通常有两种方法,第一种是采用复现关系实现:
9a245fb9bcdb41ce37dc0fc6dc49097.png
当B=0是为倍增同余,当B 0时称为混合同余。但是很显而易见的是,这个伪随机序列具有很强的周期性,并不能符合均匀分布的随机序列特性。

在这种序列下,第 位数字的周期为 (在经过 个数之后会遇到相同的数),在序列中
85f458dc0e043f706eb426cdfecc088.png
可以看出伪随机序列都具有周期性,而且不能被消除。因此倍增的方法是不可以采用的

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

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

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

对于反馈移位寄存器和异或门构成的电路,可以按下面的关系式生成序列
5d852eee3cb672da0fc3e692157dd30.png
对于m位的线性反馈移位寄存器,最多可以产生 个不同状态。如果一个序列发生器正好生产这 个不同状态之后才重复此序列,那么该序列发生器称为最大长度序列发生器。

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

图一

图二

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

LFSR的数学基础

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

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

M序列的特性f8b047f4fb89984743c44511a4fc4b0.png

本文转自作者知乎:https://zhuanlan.zhihu.com/p/166022257
作者:Trustintruth

相关文章

更多IC设计相关技术干货请关注IC设计专栏。
2 阅读 240
推荐阅读
0 条评论
关注数
1792
内容数
258
主要交流IC以及SoC设计流程相关的技术和知识
目录
极术微信服务号
关注极术微信号
实时接收点赞提醒和评论通知
Arm中国学堂公众号
关注Arm中国学堂
实时获取免费 Arm 教学资源信息
Arm中国招聘公众号
关注Arm中国招聘
实时获取 Arm 中国职位信息