LFSR简介
LFSR(Linear-feedback shift register)是一种特殊的的移位寄存器，他的输入取决于其先前状态。
LFSR的使用异常广泛，可以说涉及到方方面面，以下是Wikipedia列举的一些应用
INTELSAT business service (IBS)Intermediate data rate (IDR)SDI (Serial Digital Interface transmission)Data transfer over PSTN (according to the ITU-T V-series recommendations)CDMA(Code Division Multiple Access码分多址) cellular telephony100BASE-T2 “fast” Ethernet scrambles bits using an LFSR1000BASE-T Ethernet, the most common form of Gigabit Ethernet, scrambles - bits using an LFSRPCI Express 3.0SATASerial attached SCSI (SAS/SPL)USB 3.0IEEE 802.11ascrambles bits using an LFSRBluetoothLow Energy Link Layer is making use of LFSR (referred to as whitening)Satellite navigation systems such asGPS and GLONASS
事实上LFSR在上述系统中更广为人知的应用是伪随机数的生成与CRC计算。
以下来自Wikipedia的动图展示了LFSR的一个有趣的应用。
这是一个使用LSFR构建的31位伪随机数发生器，LED充当了其输出。原作者使用了4块74HC565（这个IC查不到，应该是作者看错了）和一块74HC86（异或门）。
对于一个LFSR，其可以看作一个FSM。这个LFSR最多状态数为
2n−12^n -12n−1
那么对于上面那个31位的LFSR，有多达2,147,483,6487个状态，假如一个状态持续0.2秒，那么需要长达13.61925年这个状态机才能重新回到初始状态！
LFSR的实现
LFSR可以使用若干个寄存器和异或门组成，其结构也不同，这里列举其中两个。
Galois型
Fibonacci型
当然这两种无论哪一种都是比较方便用HDL语言或者其他语言实现的。
我们以一个简单的3位Galois型LFSR为例。
注意这里g0=1g_0 = 1g0=1，g1=0g_1 = 0g1=0，g2=1g_2 = 1g2=1，g3=1g_3 = 1g3=1。
请注意，无论是何种LFSR，g0g_0g0 与gng_ngn都是不可能为0的。
我们可以写出这样一段C语言代码描述这个3位的LFSR
void lfsr3(){unsigned int temp0, temp1, temp2;temp0 = ff0; //拷贝ff0temp1 = ff1; //拷贝ff1temp2 = ff2; //拷贝ff2ff0 = temp2;ff1 = temp0 ^ (0 * temp2);ff2 = temp1 ^ (1 * temp2);}
现在我们令三个ff的初值为ff0=1ff_0 = 1ff0=1、ff1=0ff_1 = 0ff1=0、ff2=0ff_2 = 0ff2=0，运行这段代码20次可以得到如下结果：
// ff2 ff1 ff0[1]: 0 0 1[2]: 0 1 0[3]: 1 0 0[4]: 1 0 1[5]: 1 1 1[6]: 0 1 1[7]: 1 1 0[8]: 0 0 1[9]: 0 1 0[10]: 1 0 0[11]: 1 0 1[12]: 1 1 1[13]: 0 1 1[14]: 1 1 0[15]: 0 0 1[16]: 0 1 0[17]: 1 0 0[18]: 1 0 1[19]: 1 1 1[20]: 0 1 1
很明显可以看到每7次一个循环，我们看到这个LFSR恰好达到了最多的状态数。至于为什么且看下面的分析。
LFSR的行为
LFSR的行为是比较难于分析的。事实上这是一个伽罗华域（Galois Field）上的除法运算。这里同样以上面的那个3位的LFSR为例。
图中的3位数按照从高到低的顺序，即(ff2,ff1,ff0ff_2 ,ff_1 ,ff_0ff2,ff1,ff0)的顺序。
我们将每一个ff的值看作一个多项式中某一项，例如
100=(1×x0)+(0×x1)+(0×x2)=x0100 = (1\times x^0)+(0\times x^1)+(0\times x^2)=x^0100=(1×x0)+(0×x1)+(0×x2)=x0
于是这个状态转移图可以描述为一个多项式结果的转换，特别地，这里x=2
这样做有什么意义呢？
前面说到，这样一个LFSR的行为可以视作一个伽罗华域的除法。对于伽罗华域而言，其四则运算封闭，则结果必然是这个域中的一个元素。这个域我们记作GF(23)GF(2^3)GF(23)。
这里R(x)R(x)R(x)是ff的值，M(x)M(x)M(x)是输入多项式，G(x)G(x)G(x)是抽头多项式。
注意这个是在伽罗华域中的除法运算，本质上是一个模二除法。
这里给出M(x)M(x)M(x)的值，列出下表(当G(x)=x3+x2+x0G(x)=x^3+x^2+x^0G(x)=x3+x2+x0时)
对照上面的状态转移图，我们可以看到实际上这个LFSR的行为就是一个模二除法的输出，除法表达式受抽头表达式的控制。
对于一个nnn位的LFSR，可用的抽头至少有nnn个（第0个抽头是必须的，不算数）
虽然一个nnn位的LFSR可以有很多种不同的抽头配置，但不是所有抽头都能使其达到最长输出序列。下表给出一些能够使LFSR达到最长反馈的抽头配置
这里抽头对应的多项式G(x)G(x)G(x)均为GF(2n)GF(2^n)GF(2n)域上的本原多项式。
需要注意的是一个确定域上的本原多项式可能不止一个，例如GF(23)GF(2^3)GF(23)上的本原多项式除了x3+x+1x^3+x+1x3+x+1还有x3+x2+1x^3+x^2+1x3+x2+1，这个大家可以验证以下，这俩多项式构造的LFSR序列长度都是7。
本原多项式可以通过查表获得，也可以通过特定算法生成，这些生成算法在某些领域非常有用。
LFSR应用
PRBS（随机序列）发生器
在通信系统经常会用到一些PRBS，这些发生器可以使用一定长度的LFSR构建。由上面的结论可知，当抽头表达式恰好为本原多项式时，LFSR由最长PRBS输出。即使抽头表达式不为本原多项式，足够位数的LFSR产生的PRBS长度依然非常可观！
我们可以使用一些经典的分立器件构造LFSR，例如D触发器74HC574。
需要注意的是，如果使用移位寄存器构造LFSR，则要使用斐波那契型的LFSR。
值得关注的是Fibonacci型提高工作频率的时候容易出现误码（可以观察反馈抽头和移位寄存器），因此Galois型设计可以有更高的码率。
利用HDL在CPLD或FPGA上实现LFSR也是非常方便的。
这个就是一个32位的LFSR，抽头表达式为x32+x22+x2+x+1x^{32 }+ x^ {22} + x^ 2 + x + 1x32+x22+x2+x+1，是一个本原多项式。
白噪声发生器
白噪声是在其频率范围内频谱平坦的噪声，功率谱密度和每单位带宽的功率在噪声带宽上是恒定的。
假若将PRBS发生器输出接入一个权电阻网络，就可以构成一个速度还不错的DAC，DAC的输出经过低通滤波，可以在一定带宽内得到不错的白噪声。
图片来源：Digi-Key
补充：另外几种低成本的白噪声产生方法
1.利用电阻的约翰逊噪声产生白噪声
这个方法比较简单，噪声电压密度为
VNOISE=4kBTRV_{NOISE} = \sqrt{4k_{B}TR}VNOISE=4kBTR
其中kBk_BkB为玻尔兹曼常数。
2.利用PN结的齐纳击穿
可以使用二极管或者BJT或者JFET有PN结的东西产生白噪声，这个容易在版图上实现。目前intel CPU内部的真随机数发生器是这个原理。
PRBS设计白噪声发生器的缺点
滤波器难以设计 带宽受限
**传说白噪声煲耳机不错，博主改天得弄个玩玩😀 传说白噪声能安神助眠，放松身体（尚无更多科学依据支撑）**
CRC计算
CRC计算实际是一个GF(2n)GF(2^n)GF(2n)上的除法，又叫做模二除法。加入能够注意到这幅图，CRC的计算就迎刃而解。
CRC多项式对应了G(x)G(x)G(x)，现在只需要依次输入M(x)M(x)M(x)即可，微调以下LFSR的结构，加一个异或门，变成这个亚子
关于CRC与LFSR，在另一篇文章中介绍。
RS编码
这个目前博主没有研究，留一个坑等以后填。
