線性反饋移位寄存器(LFSR)：通常由移位寄存器和異或門邏輯組成。其主要應(yīng)用在：偽隨機(jī)數(shù)，偽噪聲序列，計(jì)數(shù)器，BIST，數(shù)據(jù)的加密和CRC校驗(yàn)等。

Part.1

線性反饋移位寄存器(LFSR)主要包括兩大類：斐波那契(外部LFSR),又稱many-to-one；伽羅瓦(內(nèi)部LFSR),又稱one-to-many。

如下圖(模2的多項(xiàng)式：x^8+x^6+x^4+1)：

Part.2

抽頭(tap)：影響線性反饋寄存器下一個(gè)狀態(tài)的比特位叫做抽頭，抽頭的設(shè)定會(huì)決定線性反饋寄存器最大的輸出序列長(zhǎng)度，抽頭通常用有限域算數(shù)中模2的多項(xiàng)式來(lái)表示（例如模2的多項(xiàng)式為：x^8+x^6+x^4+1）。

通常N bits的線性反饋寄存器能產(chǎn)生最長(zhǎng)的不重復(fù)序列為2^N-1。因?yàn)楫?dāng)所有寄存器的輸出為全零狀態(tài)時(shí)，線性反饋寄存器陷入死循環(huán)，故Nbit的線性反饋寄存器的輸出狀態(tài)有2^N-1。

抽頭的位置會(huì)影響LSFR的最大輸出狀態(tài)的個(gè)數(shù),例如：3bit的抽頭為【3,2】會(huì)產(chǎn)生7個(gè)狀態(tài)（多項(xiàng)式對(duì)應(yīng)為：x^3+x^2+1)，若抽頭為【3,1】會(huì)產(chǎn)生2個(gè)狀態(tài)（多項(xiàng)式對(duì)應(yīng)為：x^3+x+1)。

當(dāng)N bits下，抽頭的設(shè)定產(chǎn)生的最大輸出序列長(zhǎng)度為2^N-1時(shí)，此時(shí)對(duì)應(yīng)的模2多項(xiàng)式為本原多項(xiàng)式。下表為不同的bits下，抽頭的設(shè)定（對(duì)應(yīng)不同的本原多項(xiàng)式）和最大的輸出狀態(tài)個(gè)數(shù)關(guān)系表。

Part.3

上面提到N bits的LFSR能產(chǎn)生最大輸出狀態(tài)的個(gè)數(shù)為2^N-1，如果輸出狀態(tài)包括全零的狀態(tài)，最大輸出狀態(tài)的個(gè)數(shù)可達(dá)到2^N，那么通過(guò)對(duì)LFSR做如下圖的修改，即如果檢測(cè)到Q[7]-Q[0]輸出狀態(tài)為全零時(shí)，經(jīng)過(guò)~|Q[6:0]^Q[7]邏輯運(yùn)算后輸出的結(jié)果為1，進(jìn)而保證線性反饋寄存器不會(huì)陷入死循環(huán)中。

Part.4

在實(shí)際的應(yīng)用中，例如crc的校驗(yàn)，會(huì)用到模2的多項(xiàng)式的運(yùn)算，遵循如下的計(jì)算原則：

寫在最后

這里只是介紹了線性反饋移位寄存器的原理，后面會(huì)寫到RTL的具體實(shí)現(xiàn)。

參考資料： 1.https://en.wikipedia.org/wiki/Linear-feedback_shift_register 2.HDL Chip Design. A Practical Guide for Designing, Synthesizing and Simulating ASICs and FPGAs Using VHDL or Verilog

審核編輯 ：李倩