線性反饋移位寄存器原理與實現

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

　　線性反饋移位寄存器（LFSR）是一個產生二進制位序列的機制。這個寄存器由一個初始化矢量設置的一系列信元組成，最常見的是，密鑰。這個寄存器的行為被一個時鐘調節。在每個定時時刻，這個寄存器信元的內容被移動到一個正確的位置，這個排外的或這個信元子集內的內容被放在最左邊的信元中。輸出的一個位通常來自整個更新程序。LFSRs的應用包括產生偽隨機數字，偽噪聲序列，快速數字計算器和灰數序列。LFSRs軟件和硬件的執行是相同的。

　　一個n階的LFSR由n個觸發器和若干個異或門組成。在實際應用當中，主要用到兩種類型的LFSR，即異或門外接線性反饋移位寄存器（IE型LFSR，圖1）和異或門內接線性反饋移位寄存器（EE型LFSR，圖2）。其中g0 g1 g2 gn為’0’或’1’， Q1 Q2 Q3 Qn為LFSR的輸出，M（x）是輸入的碼字多項式，如M（x）=x4+ x1+ 1，表示輸入端的輸入順序為11001，同樣，LFSR的結構也可以表示為多項式G（x），稱為生成多項式：

　　G（x）= gn*xn+ …+g1*x1+ g0；

　　以EE型LFSR為例來分析LFSR的工作原理以應用

　　以n = 3 來做個例子，具體的電路圖如圖3所示：

　　假設開始的時候（D2，D1，D0 ） = （0，0，1），那么每過一個時鐘周期會進行跳變一次，可以看到具體的跳變如圖4所示：

　　然后我們可以看到這個計數器循環起來了，無論進入那樣一個狀態除了0之外，都可以循環著回來，其實這里就相當于了一個3bit的偽隨機數，很有意思，不是所有的多項式都有這個特性，我們現在在從數學上面來看看這個問題，其實最上面的電路是可以看成是一個除法電路，在Galois域的一個除法電路?，F在假設的是R（x）是寄存器中剩余的數據，M（x）是輸入的碼字多項式，然后數學公式可以表示成：

　　然后分別計算出了Ｍ（ｘ）的各種情況，

　　對于這個部分的計算我開始走進了誤區，因為開始我把這的除法當作二進制除法來算了，所以一直沒得到正確的結果，后來我明白了這的除法是模二的除法，在LFSR的結果中，多項式中的“+”都是模2加，就是異或運算，所以是沒有進位的概念；同樣，這里的除法秀的也是模2除法，即除法過程中用到的減法是模2減法，是不會產生加法進位和減法借位的運算，所以在進行模2除法時，只要部分余數首位為1，便可上商1，否則上商0，然后按照模2減法求得余數，當被除數被除完時，最后得到比除數少一位的余數。

　　這里用一個例子說明一下，比如M（x）=x7時，R（x）=1;模2的計算公式如下：

　　所以這里一定要區別模2和二進制數之間的運算的區別。

　　M（x）和R（x）到底是什么意義呢？

　　比如M（x）=1時，R（x）=1，指的就是當M（x）輸入一個1時，這時的R（x）為1，即寄存器剩余的數為001，即Q1=1，Q2=0，Q3=0。

　　又M（x）=x時，R（x）=x，指的就是當M（x）順序輸入1，0時，這時的R（x）為x，即寄存器剩余的數為010，即Q1=0，Q2=1，Q3=0。

　　同理，可以知道，當M（x）=x6時，R（x）=x2+1，指的就是當M（x）順序輸入1，0，0，0，0，0，0時，這時的R（x）為x2+1，即寄存器剩余的數為010，即Q1=1，Q2=0，Q3=1。

　　可以看出，當第一個時鐘時輸入端輸入一個1時，以后保持輸入端為0，則隨著時鐘的到來，輸入碼字多項式就是按照1，x，x2，x3，x4，x5，x6，x7，…，xn這樣的順序發展著，觀察前六個輸入的R（x）分別對應的輸出為：001，010，100，011，101，111，101，111，剛好為除去000的其他七個狀態，當M（x）為x7時，輸出又回來001，所以輸出一直這樣循環下去，因此LFSR可以用來BIST的偽隨機測試碼產生器。