引言

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

該電路具有以下特點(diǎn):

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

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

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

斐波那契LFSR與伽羅瓦LFSR

斐波那契LFSR也可稱(chēng)為多到一型LFSR，即多個(gè)觸發(fā)器的輸出通過(guò)異或邏輯來(lái)驅(qū)動(dòng)一個(gè)觸發(fā)器的輸入。

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

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

• 觸發(fā)器xl的輸入通常來(lái)自于觸發(fā)器x2的輸出；
• x3(最高項(xiàng)）的輸入通常來(lái)自于xl的輸出；
• 此多項(xiàng)式中剩余觸發(fā)器的輸入是xl的輸出與其前級(jí)輸出異或的結(jié)果；
• x2的輸人由x1的輸出與x3的輸出通過(guò)異或運(yùn)算得到。

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

LFSR反饋多項(xiàng)式

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

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

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

//上圖中，原作者可能存在一個(gè)錯(cuò)誤，應(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)用， 下面對(duì)其中的一些典型應(yīng)用進(jìn)行介紹。

LFSR計(jì)數(shù)器

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

擾碼器/解擾器

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

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

擴(kuò)展：m序列

m Sequence (MLS : Maximum Length Sequence)

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

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

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

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

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