线性反馈移位寄存器

线性反馈移位寄存器（英語：Linear feedback shift register，LFSR）是指给定前一状态的输出，将该输出的线性函数再用作输入的移位寄存器。异或运算是最常见的单比特线性函数：对寄存器的某些位进行异或操作后作为输入，再对寄存器中的各比特进行整体移位。

赋给寄存器的初始值叫做“种子”，因为线性反馈移位寄存器的运算是确定性的，所以，由寄存器所生成的数据流完全决定于寄存器当时或者之前的状态。而且，由于寄存器的状态是有限的，它最终肯定会是一个重复的循环。然而，通过本原多项式，线性反馈移位寄存器可以生成看起来是随机的且循环周期非常长的序列。

线性反馈移位寄存器的应用包括生成伪随机数，伪随机噪声序列，快速数字计数器，还有扰频器。线性反馈移位寄存器在硬件和软件方面的应用都非常得普遍。

循环冗余校验中用于快速校验传输错误的数学原理，就与线性反馈移位寄存器密切相关。

Fibonacci LFSRs

 

一个 16-位 Fibonacci LFSR. 图中黑色数字为抽头，与表中本原多项式相对应，则寄存器的循环周期为最大，65535（不包括全零状态）。图中的状态为 0xACE1 (十六进制) 下一个状态是 0x5670.

影响下一个状态的比特位叫做抽头。图中，抽头序列为[16,14,13,11]。LFSR最右端的比特为输出比特。抽头依次与输出比特进行异或运算，然后反馈回最左端的位。最右端位置所生成的序列被称为输出流。

• 影响LFSR下一个状态的比特位叫做抽头（图中黑色数字）
• 最大长度的LFSR生成一个M序列（例如，只有与有一定抽序列的LFSR才能通过所有 2ⁿ − 1 个内部状态，不包括全零状态），除非它本身为全零，亦即状态永不改变
• 作为基于异或运算的LFSR的替换，LFSR也可以给予同或运算。与使用异或门的LFSR全零状态下为无效状态相应的，使用同或门的LFSR在全“1”状态下也是无效的。

有LFSR或者基于同或门的LFSR生成的序列可以被认为是同格雷码或者自然二进制码同样有效的二进制序列。

在LFSR中，抽头的设定可以用有限域算数中模2的多项式来表示。这就意味着，多项式中的所有系数必须是“1”或者“0”。这个多项式被称作回授多项式或特征多项式。例如图中的抽头为在第16，14，13，11个比特，则相应的特征多项式为：

${\displaystyle x^{16}+x^{14}+x^{13}+x^{11}+1.\,}$ 

多项式中常数“1”并不代表某一个抽头，它所指的是一个比特位的输入（例如 x⁰,等效为 1 ）。多项式中的指数代表从左至右的抽头位。第一个和最后一个比特一般相应的是输入和输出位。

当且仅当相应的回授多项式是本原多项式时，LFSR才能达到最大长度。这表示以下条件是必须的：

• 抽头的数量必须为偶数。
• 抽头之间不能成对出现，必须是互质的。

生成最长LFSRs的本原多项式表可通过下部的链接找到。 这类型LFSR也被成为标准，多对一或外部异或门的LFSR。下一节将会介绍Galois型的LFSR。

Galois LFSRs

 

A 16-bit Galois LFSR. The register numbers in white correspond to the same primitive polynomial as the Fibonacci example but are counted in reverse to the shifting direction. This register also cycles through the maximal number of 65535 states excluding the all-zeroes state. The state ACE1 hex shown will be followed by E270 hex.

以法国数学家埃瓦里斯特·伽罗瓦命名，是LFSRs的Galois型结构。

參見

• 梅森旋轉演算法
• M-sequence

外部連結

• LFSR Reference （页面存档备份，存于互联网档案馆） LFSR theory and implementation, maximal length sequences, and comprehensive feedback tables for lengths from 7 to 16,777,215 (3 to 24 stages), and partial tables for lengths up to 4,294,967,295 (25 to 32 stages).
• International Telecommunications Union Recommendation O.151 （页面存档备份，存于互联网档案馆） (August 1992)
• Maximal Length LFSR table （页面存档备份，存于互联网档案馆） with length from 2 to 67. (Error detected: period are (2^n)-1 not 2^n)
• Pseudo-Random Number Generation Routine （页面存档备份，存于互联网档案馆）
• http://www.ece.ualberta.ca/~elliott/ee552/studentAppNotes/1999f/Drivers_Ed/lfsr.html （页面存档备份，存于互联网档案馆）
• http://www.quadibloc.com/crypto/co040801.htm （页面存档备份，存于互联网档案馆）
• Feedback terms （页面存档备份，存于互联网档案馆）
• An implementation of LFSR in VHDL. （页面存档备份，存于互联网档案馆）
• Simple VHDL coding for Galois and Fibonacci LFSR. （页面存档备份，存于互联网档案馆）