引言

LFSR(線性反饋移位寄存器）用于產(chǎn)生可重復(fù)的偽隨機序列PRBS，該電路由n級觸發(fā)器和一些異或門組成。在每個時鐘周期內(nèi)，新的輸入值會被反饋到LFSR內(nèi)部各個觸發(fā)器的輸入端，輸人值中的一部分來源于LFSR的輸出端，另一部分由LFSR各輸出端進行異或運算得到。

該電路具有以下特點:

• 如果初始狀態(tài)相同，則最終會得到相同的輸出序列(即輸出序列是確定的)；
• 輸出序列趨向于隨機序列(偽隨機)；
• 經(jīng)過一定次數(shù)的迭代后，你將得到與初始狀態(tài)相同的狀態(tài)值；(最大重復(fù)間隔可由(2^n- 1)計算，其中n為移位寄存器的數(shù)目)

由于上述特性，LFSR主要用于生成PN序列(偽噪聲序列)。

LFSR的初始值被稱為偽隨機序列的種子，其最后一個觸發(fā)器輸出的就是一個周期性重復(fù)的偽隨機序列。由n個觸發(fā)器構(gòu)成的LFSR電路可以產(chǎn)生一個周期為2^n-1的序列。以3比特LFSR為例，觸發(fā)器依次重復(fù)出現(xiàn)111，101，100,010,001，110及011這7種組合，最后一個觸發(fā)器輸出的就是一個周期為7的偽隨機序列。目前有兩類常用的LFSR電路：斐波那契LFSR與伽羅瓦LFSR下面分別進行介紹。

斐波那契LFSR與伽羅瓦LFSR

斐波那契LFSR也可稱為多到一型LFSR，即多個觸發(fā)器的輸出通過異或邏輯來驅(qū)動一個觸發(fā)器的輸入。

與此相反，伽羅瓦LFSR為一到多型LFSR，即一個觸發(fā)器的輸出通過異或邏輯驅(qū)動多個觸發(fā)器的輸入。這兩種電路都產(chǎn)生（2^n-1)序列，但是一到多型LFSR具有更高的速度，因為它的兩個觸發(fā)器之間僅使用一個異或門。圖6.1至圖6.3是3比特和4比特LFSR的具體電路。

伽羅瓦LFSR(反饋多項式為x^3 x^2 1):

• 觸發(fā)器xl的輸入通常來自于觸發(fā)器x2的輸出；
• x3(最高項）的輸入通常來自于xl的輸出；
• 此多項式中剩余觸發(fā)器的輸入是xl的輸出與其前級輸出異或的結(jié)果；
• x2的輸人由x1的輸出與x3的輸出通過異或運算得到。

LFSR電路可用于構(gòu)建高速計數(shù)器，LFSR計數(shù)器與二進制計數(shù)器有何不同呢？二進制計數(shù)器產(chǎn)生重復(fù)且規(guī)整的輸出序列，而LFSR計數(shù)器產(chǎn)生的序列是近似隨機的。我們是否可以從LFSR鏈中任意位置取值并且通過異或邏輯產(chǎn)生偽隨機序列呢？答案是肯定的，這樣可以產(chǎn)生偽隨機序列，但此時序列的長度可能不是最長的。換言之，對于由n個觸發(fā)器構(gòu)成的LFSR而言，選擇合適的反饋多項式不僅可以產(chǎn)生偽隨機序列，而且可以產(chǎn)生最大長度的偽隨機序列。

LFSR反饋多項式

本電路中每次迭代的狀態(tài)轉(zhuǎn)換如下表所示，在這個表中，你會發(fā)現(xiàn)到上面列出的所有屬性。

產(chǎn)生最大長度偽隨機序列的反饋多項式如下表所示。表中給出了n取不同值時產(chǎn)生最大長度偽隨機序列的反饋多項式。需要注意的是，對于任意給定的移位寄存器長度n，可能存在不止一個產(chǎn)生最大長度偽隨機序列的反饋多項式。

在上面表述中這個電路被表示為一個多項式，但是你會發(fā)現(xiàn)很難把真實的電路和生成的多項式聯(lián)系起來，下面的插圖將幫助你理解生成的多項式的含義。

//上圖中，原作者可能存在一個錯誤，應(yīng)該是1X^1, 而不是0X^1

//理解：反饋路徑存在，取1；反之，取0。x^4 、x和x^0存在，x^3和x^2不存在，所以是【1 0 0 1 1】

LFSR的用法

LFSR具有廣泛的應(yīng)用， 下面對其中的一些典型應(yīng)用進行介紹。

LFSR計數(shù)器

LFSR可用于構(gòu)建通過隨機序列狀態(tài)進行計數(shù)的計數(shù)器。與常見的計數(shù)器相比， LFSR計數(shù)器具有速度快 、 消耗邏輯門少的特點。

擾碼器/解擾器

LFSR可用作擾碼器來產(chǎn)生重復(fù)的比特圖案。當(dāng)重復(fù)間隔較大時， 該比特圖案看上去就像一個隨機的比特序列。用戶數(shù)據(jù)發(fā)送前和擾碼器生成的序列進行異或， 然后發(fā)出， 此時發(fā)送的數(shù)據(jù)就是經(jīng)過擾碼的數(shù)據(jù)。接收電路與發(fā)送電路采用相同的多項式， 這樣， 解擾器就可以將發(fā)送端原始的用戶數(shù)據(jù)恢復(fù)出來。

LFSR還可應(yīng)用于其他領(lǐng)域， 如密碼系統(tǒng) 、 BIST ( 內(nèi)建自測試 ）、 快速以太網(wǎng)及吉比特以太網(wǎng)等。

擴展：m序列

m Sequence (MLS : Maximum Length Sequence)

m序列是一類特殊的LFSR序列，為了更好的理解m序列，首先你需要理解LFSR序列的概念。

與典型的LFSR相比，m序列有什么特別之處?

如果使用LFSR生成一個序列，輸出最終會重復(fù)它自己，但是在大多數(shù)應(yīng)用程序中，其目的是使用給定數(shù)目的移位寄存器(后續(xù)用taps表示這些寄存器)生成盡可能長的非重復(fù)序列。m-Squence 是一種特殊類型的LFSR，它為每個給定的taps提供了最長的非重復(fù)序列。

下表顯示了各種taps的已知m序列:

來源：OpenFPGA版權(quán)歸原作者所有，如有侵權(quán)，請聯(lián)系刪除。