線性反饋移位寄存器

線性反饋移位寄存器（英語：Linear feedback shift register，LFSR）是指給定前一狀態的輸出，將該輸出的線性函數再用作輸入的移位寄存器。異或運算是最常見的單比特線性函數：對寄存器的某些位進行異或操作後作為輸入，再對寄存器中的各比特進行整體移位。

賦給寄存器的初始值叫做「種子」，因為線性反饋移位寄存器的運算是確定性的，所以，由寄存器所生成的數據流完全決定於寄存器當時或者之前的狀態。而且，由於寄存器的狀態是有限的，它最終肯定會是一個重複的循環。然而，通過本原多項式，線性反饋移位寄存器可以生成看起來是隨機的且循環周期非常長的序列。

線性反饋移位寄存器的應用包括生成偽隨機數，偽隨機噪聲序列，快速數字計數器，還有擾頻器。線性反饋移位寄存器在硬件和軟件方面的應用都非常得普遍。

循環冗餘校驗中用於快速校驗傳輸錯誤的數學原理，就與線性反饋移位寄存器密切相關。

Fibonacci LFSRs

影響下一個狀態的比特位叫做抽頭。圖中，抽頭序列為[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個比特，則相應的特徵多項式為：

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

多項式中常數「1」並不代表某一個抽頭，它所指的是一個比特位的輸入（例如 x⁰,等效為 1 ）。多項式中的指數代表從左至右的抽頭位。第一個和最後一個比特一般相應的是輸入和輸出位。

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

生成最長LFSRs的本原多項式表可通過下部的連結找到。這類型LFSR也被成為標準，多對一或外部異或門的LFSR。下一節將會介紹Galois型的LFSR。

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