在設計線性反饋移位暫存器（LFSR）以達到最大長度時，對於抽頭的個數和排列方式有以下要求：

1. **抽頭的數量必須為偶數**：這是因為只有偶數個抽頭才能保證生成的序列是最大長度序列。

2. **抽頭之間不能成對出現，必須是互質的**：這是指任意兩個抽頭位之間的距離必須互質，這樣可以確保生成的序列具有良好的擴散性和隨機性，以達到最大長度。

符合這些條件的LFSR能夠生成一個M序列，並且在其狀態空間內達到全部可能的狀態（除了全零狀態）。
在設計 LFSR 時，抽頭的個數和排列方式有哪些要求，才能使其達到最大長度？
**線性反饋移位暫存器**（英語：Linear feedback shift register，LFSR）是指給定前一狀態的輸出，將該輸出的線性函數再用作輸入的移位暫存器。異或運算是最常見的單比特線性函數：對暫存器的某些位進行異或操作後作為輸入，再對暫存器中的各比特進行整體移位。

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

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

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

## Fibonacci LFSRs

影響下一個狀態的比特位叫做抽頭。圖中，抽頭序列為 [16,14,13,11]。LFSR 最右端的比特為輸出比特。抽頭依次與輸出比特進行異或運算，然後反饋回最左端的位。最右端位置所生成的序列被稱為輸出流。

* 影響 LFSR 下一個狀態的比特位叫做抽頭（圖中黑色數字）
* 最大長度的 LFSR 生成一個 M 序列（例如，只有與有一定抽序列的 LFSR 才能通過所有 2n− 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」並不代表某一個抽頭，它所指的是一個比特位的輸入（例如 _x0_, 等效為 1 ）。多項式中的指數代表從左至右的抽頭位。第一個和最後一個比特一般相應的是輸入和輸出位。

若且唯若相應的回授多項式是本原多項式時，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 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 （頁面存檔備份，存於網際網路檔案館）
* 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. （頁面存檔備份，存於網際網路檔案館）
**M-sequence**（Maximum length sequence、MLS、最大長度序列）是在基本的通訊電路設計中，所經常被利用到的一個偽隨機數位訊號（Pseudo Random Sequence），其主要的方式是利用第一位與其他位暫存器的輸出值做互斥或來設計其第一位暫存器的輸入值。

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

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

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

循環冗餘校驗中用於快速校驗傳輸錯誤的數學原理，就與線性反饋移位暫存器密切相關。 **時滯斐波那契生成器（Lagged Fibonacci generator，LFG 或 LFib）** ，是一類偽隨機數生成器。用於改進標準的線性同餘生成器。

用遞推關係表示序列的生成：

　
: $S_{n}\equiv S_{n-j}\star S_{n-k}{\pmod {m}},0<j<k$

其中，新項由兩個老項計算生成。_m_ 通常是 2 的冪 (_m_ = 2M), 經常 232 或 264。其中 $\star $ 算符表示一般的二元運算符，這可以是加法、減法、乘法或者位運算異或。相應地稱作_加法時滯斐波那契生成器_（ALFG）、_乘法時滯斐波那契生成器_（MLFG）、 _雙抽頭廣義反饋移位暫存器_（GFSR）。梅森旋轉算法是 GFSR 的變種。GFSR 與線性反饋移位暫存器有關。

使用 _k_ 個狀態字的生成器，稱作 ' 記住 ' 了過去 _k_ 個值。

時滯斐波那契生成器的理論相當複雜，理論也不夠充分到能指導如何選擇 j 與 k。生成器的初始化也非常敏感。 ## Fibonacci LFSRs

影響下一個狀態的比特位叫做抽頭。圖中，抽頭序列為 [16,14,13,11]。LFSR 最右端的比特為輸出比特。抽頭依次與輸出比特進行異或運算，然後反饋回最左端的位。最右端位置所生成的序列被稱為輸出流。

* 影響 LFSR 下一個狀態的比特位叫做抽頭（圖中黑色數字）
* 最大長度的 LFSR 生成一個 M 序列（例如，只有與有一定抽序列的 LFSR 才能通過所有 2n− 1 個內部狀態，不包括全零狀態），除非它本身為全零，亦即狀態永不改變
* 作為基於異或運算的 LFSR 的替換，LFSR 也可以給予同或運算。與使用異或門的 LFSR 全零狀態下為無效狀態相應的，使用同或門的 LFSR 在全「1」狀態下也是無效的。

有 LFSR 或者基於同或門的 LFSR 生成的序列可以被認為是同格雷碼或者自然二進位碼同樣有效的二進位序列。

在 LFSR 中，抽頭的設定可以用有限域算數中模 2 的多項式來表示。這就意味著，多項式中的所有係數必須是「1」或者「0」。這個多項式被稱作回授多項式或特徵多項式。例如圖中的抽頭為在第 16，14，13，11 個比特，則相應的特徵多項式為：