线性反馈移位寄存器(LFSR)：通常由移位寄存器和异或门逻辑组成。其主要应用在：伪随机数，伪噪声序列，计数器，BIST，数据的加密和CRC校验等。
线性反馈移位寄存器(LFSR)主要包括两大类
- 伽罗瓦(内部LFSR)，又称one-to-many
- 斐波那契(外部LFSR)，又称many-to-one
- 其中，gn为反馈系数，取值只能为0或1，取为0时表明不存在该反馈之路，取为1时表明存在该反馈之路；这里的反馈系数决定了产生随机数的算法的不同。用反馈函数表示成
y = a0x^0 + a1x + a2x^2…，反馈函数为线性的叫线性移位反馈序列，否则叫非线性反馈移位序列。- Q1、Q2、Q3、Qn为LFSR的输出，M(x)是输入的码字多项式，如M(x)=x^4+ x^1+ 1，表示输入端的输入顺序为11001，同样，LFSR的结构也可以表示为多项式G(x)，称为生成多项式：
G(x) = gn*x^n+ …+g1*x^1+ g0；
抽头选择与状态个数最大
- 影响线性反馈寄存器下一个状态的比特位叫做抽头，选取的“某些位”构成的序列叫做抽头序列，理论表明，要使LFSR得到最长的周期，这个抽头序列构成的多项式加1必须是一个本原多项式（所有系数的最大公因数为1的多项式），也就是说这个多项式不可约，如：
f(x) = x^4 + x + 1 - n个D触发器最多可以提供2^(n-1)个状态(不包括全0的状态)，为了保证这些状态没有重复，gn的选择必须满足一定的条件。下面以n=3，g0=1，g1=1，g2=0，g3=1为例，说明LFSR的特性，具有该参数的LFSR结构如下图：
- 抽头的位置会影响LSFR的最大输出状态的个数,例如：3bit的抽头为【3,2】会产生7个状态（多项式对应为：x3+x2+1)，若抽头为【3,1】会产生2个状态（多项式对应为：x^3+x+1)。
当N bits下，抽头的设定产生的最大输出序列长度为2^N-1时，此时对应的模2多项式为本原多项式。下表为不同的bits下，抽头的设定（对应不同的本原多项式）和最大的输出状态个数关系表。
参考文章：
LFSR的工作原理以及LFSR在CRC上的应用；
线性反馈移位寄存器（LFSR）-非线性反馈移位寄存器的verilog实现（产生伪随机数）；
线性反馈移位寄存器原理
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/212074.html原文链接：https://javaforall.net
