檢視線性回饋移位暫存器的原始碼

'''線性反饋移位暫存器'''（英語：Linear feedback shift register，LFSR）是講予定前一狀態的輸出，將該輸出的線性函數才閣用作輸入的移位暫存器。異或者是上捷看著的單比特線性函數：對暫存器的某一寡位進行異或者是操作了後作為輸入，閣對暫存器內底的各比特進行整體移位。

共暫存器的初初值號做「種子」，因為線性反饋移位暫存器的運算是確定性的，所以乎，由暫存器所生成的數據流完全決定佇暫存器彼當陣抑是進前的狀態。而且，因為暫存器的狀態是有限的，終其尾伊肯定會是一个重複的循環。毋過，通過本原濟項式，線性反饋移位暫存器會當生看起來是隨機的而且循環周期非常長的序列。

線性反饋移位暫存器的應用包括生造假隨機數，偽隨機噪聲序列，快速數字計數器，閣擾頻器。線性反饋移位暫存器佇硬體佮軟體方面的應用攏真普遍。

循環趁食校驗內底用佇咧快速校驗傳輸錯誤的數學原理，就和線性反饋移位暫存器密切相關。

==Fibonacci LFSRs==

影響後一个狀態的比特位叫做抽頭。圖當中，抽頭序列做 [十六 , 十四 , 十三 , 十一]。LFSR 上正爿的比特為輸出比特。抽頭殼依次佮輸出比特進行異或者是運算，然後反饋回上倒爿的位。上正爿位置所生成的序列被稱做輸出流。

* 影響 LFSR 後一个狀態的比特位叫做抽頭（圖中烏色數字）
* 上大長度的 LFSR 成做一个 M 序列（比如講，干焦佮一定抽序列的 LFSR 才會當通過所有的二 n−  一个內部的狀態，無包括全零狀態）， 除非伊本身為全零，亦即狀態永不改變
* 作為是異或者是運算的 LFSR 的替換，LFSR 嘛會當予同抑是運算。佮使用異抑是門的 LFSR 全零狀態下為無效狀態相應的，使用同抑是門的 LFSR 佇全「一」狀態之下嘛是無效的。

有 LFSR 抑是講仝抑是門的 LFSR 生做的序列會當被認為是同格雷碼或者是自然二進位碼仝款有效的二進位序列。

佇咧 LFSR 中，抽頭的設定會當用有限域算數中模二的濟項式來表示。這就意味對，多項式內底的所有的係數必須是「一」抑是講「零」。 這个多項式予人號做回授多項式抑是特徵多項式。譬如講圖內底的抽頭為啥物佇第十六，十四，十三，十一个比特，則相應的特徵多項式為：


: $ x ^ { 十六 } + x ^ { 十四 } + x ^ { 十三 } + x ^ { 十一 } + 一 . \ , $

多項式當中常數「一」並無代表某一个抽頭，伊所指的是一个比特位的輸入（比如講 _ x 零 _ , 等效為一）。 多項式當中的指數代表對左至右的抽頭位。頭一个佮上尾一个比並特別相應的是輸入佮輸出位。

若是唯若相應的回授多項式是本原多項的時陣，LFSR 伊才會當達到上大的長度。這表示以下的條件是必須的：

* 抽頭的數量著愛濫偶數。
* 抽頭之間袂當成對出現，著愛互質的。

生成上長 LFSRs 的本本底有足濟項式通過下部的連結揣著。
這味的 LFSR 嘛予人成做'''標準'''，'''加嘿一'''抑是'''外部異抑是門'''的 LFSR。後一節將會介紹 Galois 型的啦 LFSR。

==Galois LFSRs==

以法國數學家埃瓦里斯特 ・ 伽羅瓦號名，是 LFSRs 的 Galois 型結構。

==參見==

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

==外部連結==

* LFSR Reference LFSR theory and implementation , maximal length sequences , and comprehensive feedback tables for lengths from 七 to 十六 , 七仔七十七 , 兩百十五 ( 三 to 二十四 stages ) , and partial tables for lengths up to 四 , 兩百九十四 , 九百六十七喔 , 兩百九十五 ( 二十五 to 三十二 stages ) .
* International Telecommunications Union Recommendation O . 百五一 ( August 一千九百九十二 )
* Maximal Length LFSR table with length from 二 to 六十七 . ( Error detected : period are ( 二 ^ n ) 影一 not 二 ^ n )
* Pseudo-Random Number Generation Routine
* http : / / www . ece . ualberta . ca / ~ elliott / ee 五仔五十二 / studentAppNotes / 一千九百九十九 f / Drivers \ _ Ed / lfsr . html
* http : / / www . quadibloc . com / crypto / co 四配空八百空一 . htm
* Simple explanation of LFSRs for Engineers
* Feedback terms
* General LFSR Theory
* An implementation of LFSR in VHDL .
* Simple VHDL coding for Galois and Fibonacci LFSR .

[[分類: 待校正]]