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

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

　　一個(gè)n階的LFSR由n個(gè)觸發(fā)器和若干個(gè)異或門組成。在實(shí)際應(yīng)用當(dāng)中，主要用到兩種類型的LFSR，即異或門外接線性反饋移位寄存器（IE型LFSR，圖1）和異或門內(nèi)接線性反饋移位寄存器（EE型LFSR，圖2）。其中g(shù)0 g1 g2 gn為’0’或’1’， Q1 Q2 Q3 Qn為L(zhǎng)FSR的輸出，M（x）是輸入的碼字多項(xiàng)式，如M（x）=x4+ x1+ 1，表示輸入端的輸入順序?yàn)?1001，同樣，LFSR的結(jié)構(gòu)也可以表示為多項(xiàng)式G（x），稱為生成多項(xiàng)式：

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

　　以EE型LFSR為例來分析LFSR的工作原理以應(yīng)用

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

　　假設(shè)開始的時(shí)候（D2，D1，D0 ） = （0，0，1），那么每過一個(gè)時(shí)鐘周期會(huì)進(jìn)行跳變一次，可以看到具體的跳變?nèi)鐖D4所示：

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

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

　　對(duì)于這個(gè)部分的計(jì)算我開始走進(jìn)了誤區(qū)，因?yàn)殚_始我把這的除法當(dāng)作二進(jìn)制除法來算了，所以一直沒得到正確的結(jié)果，后來我明白了這的除法是模二的除法，在LFSR的結(jié)果中，多項(xiàng)式中的“+”都是模2加，就是異或運(yùn)算，所以是沒有進(jìn)位的概念；同樣，這里的除法秀的也是模2除法，即除法過程中用到的減法是模2減法，是不會(huì)產(chǎn)生加法進(jìn)位和減法借位的運(yùn)算，所以在進(jìn)行模2除法時(shí)，只要部分余數(shù)首位為1，便可上商1，否則上商0，然后按照模2減法求得余數(shù)，當(dāng)被除數(shù)被除完時(shí)，最后得到比除數(shù)少一位的余數(shù)。

　　這里用一個(gè)例子說明一下，比如M（x）=x7時(shí)，R（x）=1;模2的計(jì)算公式如下：

　　所以這里一定要區(qū)別模2和二進(jìn)制數(shù)之間的運(yùn)算的區(qū)別。

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

　　比如M（x）=1時(shí)，R（x）=1，指的就是當(dāng)M（x）輸入一個(gè)1時(shí)，這時(shí)的R（x）為1，即寄存器剩余的數(shù)為001，即Q1=1，Q2=0，Q3=0。

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

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

　　可以看出，當(dāng)?shù)谝粋€(gè)時(shí)鐘時(shí)輸入端輸入一個(gè)1時(shí)，以后保持輸入端為0，則隨著時(shí)鐘的到來，輸入碼字多項(xiàng)式就是按照1，x，x2，x3，x4，x5，x6，x7，…，xn這樣的順序發(fā)展著，觀察前六個(gè)輸入的R（x）分別對(duì)應(yīng)的輸出為：001，010，100，011，101，111，101，111，剛好為除去000的其他七個(gè)狀態(tài)，當(dāng)M（x）為x7時(shí)，輸出又回來001，所以輸出一直這樣循環(huán)下去，因此LFSR可以用來BIST的偽隨機(jī)測(cè)試碼產(chǎn)生器。