引言

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

該電路具有以下特點:

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

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

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

斐波那契LFSR與伽羅瓦LFSR

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

與此相反，伽羅瓦LFSR為一到多型LFSR，即一個觸發(fā)器的輸出通過異或邏輯驅動多個觸發(fā)器的輸入。這兩種電路都產生（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的輸出與其前級輸出異或的結果；
• x2的輸人由x1的輸出與x3的輸出通過異或運算得到。

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

LFSR反饋多項式

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

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

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

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

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

LFSR的用法

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

LFSR計數器

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

擾碼器/解擾器

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

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

擴展：m序列

m Sequence (MLS : Maximum Length Sequence)

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

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

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

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

來源：OpenFPGA版權歸原作者所有，如有侵權，請聯系刪除。