线性反馈移位寄存器的反馈函数_线性反馈移位寄存器(LFSR)

线性反馈移位寄存器(LFSR):通常由移位寄存器和异或门逻辑组成。主要用于：伪随机数、伪噪声序列、计数器、BIST、数据加密和CRC校验。

第一部分

线性反馈移位寄存器(LFSR)主要包括两大类：斐波那契(外部LFSR)，又称多对一；伽罗瓦(内部LFSR)，又称一对多。

如下图(模2的多项式：x^8 x^6 x^4 1):

第二部分

Tap:影响线性反馈寄存器下一状态的位称为tap。抽头的设置将决定线性反馈寄存器的最大输出序列长度。抽头在有限域算术中通常用模2的多项式表示(例如模2的多项式为：x^8 x^6 x^4 1)。通常，N比特的线性反馈寄存器可以产生2 n-1的最长不重复序列。因为当所有寄存器的输出都是零时，线性反馈寄存器陷入无限循环，所以Nbit的线性反馈寄存器的输出状态有2 n-1。抽头的位置会影响LSFR的最大输出状态数。例如，3位[3，2]的抽头将产生7个状态(多项式对应于：x ^ 3 x ^ 21)，而[3，1]的抽头将产生2个状态(多项式对应于：x^3 x ^ 1)。当通过设置抽头产生的最大输出序列长度是N比特下的2 n-1时，对应的模2多项式是原始多项式。下表给出了不同比特下，抽头设置(对应不同的本原多项式)与最大输出状态数的关系。

第三部分

上述N位LFSR可以产生的最大输出状态数为2 n-1。如果输出状态包含全零状态，最大输出状态数可以达到2 n，那么，LFSR修改如下图所示，即如果检测到Q[7]-Q[0]的输出状态都是全零，在~ | q [6: 0] q [7]之后。

第四部分

在实际应用中，比如crc校验，会用到模2的多项式运算，并遵循以下计算原则：

写在最后

本文只介绍线性反馈移位寄存器的原理，后面会写RTL的具体实现。

参考资料：1.https://en.wikipedia.org/wiki/Linear-feedback_shift_register 2。HDL芯片设计。使用VHDL或verilog设计、合成和模拟ASICs和fpgas的实用指南。

审核编辑：李倩