查看“︁线性反馈移位寄存器”︁的源代码

{{expand|time=2013-04-16T14:35:24+00:00}}

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

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

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

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

==Fibonacci LFSRs==
[[Image:LFSR-F16.gif|thumb|right|351 px|一个 16-位 Fibonacci LFSR. 图中黑色数字为抽头，与表中本原多项式相对应，则寄存器的循环周期为最大，65535（不包括全零状态）。图中的状态为 0xACE1 ([[十六进制]]) 下一个状态是 0x5670. ]]
影响下一个状态的比特位叫做抽头。图中，抽头序列为[16,14,13,11]。LFSR最右端的比特为输出比特。抽头依次与输出比特进行异或运算，然后反馈回最左端的位。最右端位置所生成的序列被称为输出流。

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

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

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

:<math>x^{16} + x^{14} + x^{13} + x^{11} + 1.\,</math>

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

当且仅当相应的回授多项式是本原多项式时，LFSR才能达到最大长度。这表示以下条件是必须的：
* 抽头的数量必须为偶数。
* 抽头之间不能成对出现，必须是互质的。
生成最长LFSRs的本原多项式表可通过下部的链接找到。
这类型LFSR也被成为'''标准'''，'''多对一'''或'''外部异或门'''的LFSR。下一节将会介绍Galois型的LFSR。

==Galois LFSRs==
[[Image:LFSR-G16.gif|thumb|right|393 px|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.]]
以法国数学家[[Évariste Galois|埃瓦里斯特·伽罗瓦]]命名，是LFSRs的Galois型结构。
== 參見 ==
* [[梅森旋轉演算法]]
* [[M-sequence]]

== 外部連結 ==
* [http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm LFSR Reference] {{Wayback|url=http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm |date=20181001062252 }} 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).
* [http://www.itu.int/rec/T-REC-O.151-199210-I/en International Telecommunications Union Recommendation O.151] {{Wayback|url=http://www.itu.int/rec/T-REC-O.151-199210-I/en |date=20210429131953 }} (August 1992)
* [http://spreadsheets.google.com/ccc?key=0AvYtZsho-JTldFRYZnJLRFFaSWtUcVNXc1Y3M2VWd1E&hl=en Maximal Length LFSR table] {{Wayback|url=http://spreadsheets.google.com/ccc?key=0AvYtZsho-JTldFRYZnJLRFFaSWtUcVNXc1Y3M2VWd1E&hl=en |date=20131111191408 }} with length from 2 to 67. (Error detected: period are (2^n)-1 not 2^n)
* [http://www.maxim-ic.com/appnotes.cfm?appnote_number=1743&CMP=WP-9 Pseudo-Random Number Generation Routine] {{Wayback|url=http://www.maxim-ic.com/appnotes.cfm?appnote_number=1743&CMP=WP-9 |date=20081225073609 }}
* http://www.ece.ualberta.ca/~elliott/ee552/studentAppNotes/1999f/Drivers_Ed/lfsr.html {{Wayback|url=http://www.ece.ualberta.ca/~elliott/ee552/studentAppNotes/1999f/Drivers_Ed/lfsr.html |date=20210228164643 }}
* http://www.quadibloc.com/crypto/co040801.htm {{Wayback|url=http://www.quadibloc.com/crypto/co040801.htm |date=20210224163740 }}
* [https://web.archive.org/web/20060315203220/http://www.yikes.com/~ptolemy/lfsr_web/index.htm Simple explanation of LFSRs for Engineers]
* [http://www.ece.cmu.edu/~koopman/lfsr/index.html Feedback terms] {{Wayback|url=http://www.ece.cmu.edu/~koopman/lfsr/index.html |date=20130304161428 }}
* [https://web.archive.org/web/20010605005727/http://homepage.mac.com/afj/lfsr.html General LFSR Theory]
* [http://opencores.org/project,lfsr_randgen An implementation of LFSR in VHDL.] {{Wayback|url=http://opencores.org/project,lfsr_randgen |date=20171022151434 }}
* [http://emmanuel.pouly.free.fr Simple VHDL coding for Galois and Fibonacci LFSR.] {{Wayback|url=http://emmanuel.pouly.free.fr/ |date=20210301150412 }}

{{Cryptography stream}}

[[Category:二进制算术]]
[[Category:數位寄存器]]
[[Category:密码算法]]
[[Category:伪随机数生成器]]