線性反饋移位寄存器(LFSR):通常由移位寄存器和異或門邏輯組成。其主要應(yīng)用在:偽隨機數(shù),偽噪聲序列,計數(shù)器,BIST,數(shù)據(jù)的加密和CRC校驗等。
Part.1
線性反饋移位寄存器(LFSR)主要包括兩大類:斐波那契(外部LFSR),又稱many-to-one;伽羅瓦(內(nèi)部LFSR),又稱one-to-many。
如下圖(模2的多項式:x^8+x^6+x^4+1):
Part.2
抽頭(tap):影響線性反饋寄存器下一個狀態(tài)的比特位叫做抽頭,抽頭的設(shè)定會決定線性反饋寄存器最大的輸出序列長度,抽頭通常用有限域算數(shù)中模2的多項式來表示(例如模2的多項式為:x^8+x^6+x^4+1)。
通常N bits的線性反饋寄存器能產(chǎn)生最長的不重復序列為2^N-1。因為當所有寄存器的輸出為全零狀態(tài)時,線性反饋寄存器陷入死循環(huán),故Nbit的線性反饋寄存器的輸出狀態(tài)有2^N-1。
抽頭的位置會影響LSFR的最大輸出狀態(tài)的個數(shù),例如:3bit的抽頭為【3,2】會產(chǎn)生7個狀態(tài)(多項式對應(yīng)為:x^3+x^2+1),若抽頭為【3,1】會產(chǎn)生2個狀態(tài)(多項式對應(yīng)為:x^3+x+1)。
當N bits下,抽頭的設(shè)定產(chǎn)生的最大輸出序列長度為2^N-1時,此時對應(yīng)的模2多項式為本原多項式。下表為不同的bits下,抽頭的設(shè)定(對應(yīng)不同的本原多項式)和最大的輸出狀態(tài)個數(shù)關(guān)系表。
Part.3
上面提到N bits的LFSR能產(chǎn)生最大輸出狀態(tài)的個數(shù)為2^N-1,如果輸出狀態(tài)包括全零的狀態(tài),最大輸出狀態(tài)的個數(shù)可達到2^N,那么通過對LFSR做如下圖的修改,即如果檢測到Q[7]-Q[0]輸出狀態(tài)為全零時,經(jīng)過~|Q[6:0]^Q[7]邏輯運算后輸出的結(jié)果為1,進而保證線性反饋寄存器不會陷入死循環(huán)中。
Part.4
在實際的應(yīng)用中,例如crc的校驗,會用到模2的多項式的運算,遵循如下的計算原則:
寫在最后
這里只是介紹了線性反饋移位寄存器的原理,后面會寫到RTL的具體實現(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
審核編輯 :李倩
-
寄存器
+關(guān)注
關(guān)注
31文章
5336瀏覽量
120232 -
線性
+關(guān)注
關(guān)注
0文章
198瀏覽量
25145
原文標題:線性反饋移位寄存器原理
文章出處:【微信號:zhuyandz,微信公眾號:FPGA之家】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
相關(guān)推薦
評論