FPGA的偽隨機(jī)序列發(fā)生器設(shè)計(jì)

0? 引言

偽隨機(jī)序列現(xiàn)已廣泛應(yīng)用于密碼學(xué)、擴(kuò)頻通訊、導(dǎo)航、集成電路的可測(cè)性設(shè)計(jì)、現(xiàn)代戰(zhàn)爭(zhēng)中的電子對(duì)抗技術(shù)等許多重要領(lǐng)域。偽隨機(jī)序列的偽隨機(jī)性表現(xiàn)在預(yù)先的可確定性、可重復(fù)產(chǎn)生與處理。偽隨機(jī)序列雖然不是真正的隨機(jī)序列，但是當(dāng)偽隨機(jī)序列周期足夠長(zhǎng)時(shí)，它便具有隨機(jī)序列的良好統(tǒng)計(jì)特性。在已有的序列中，m序列的應(yīng)用最為成熟和廣泛，為此，本文給出線性m序列和基于m序列的非線性m子序列的FPGA實(shí)現(xiàn)方法。由于FPGA的內(nèi)部邏輯功能是通過(guò)向內(nèi)部靜態(tài)存儲(chǔ)器單元加載配置數(shù)據(jù)來(lái)實(shí)現(xiàn)的，其配置文件決定了邏輯單元的邏輯功能以及模塊間或與I／O間的連接，故可最終決定FPGA實(shí)現(xiàn)的功能。FPGA的這種結(jié)構(gòu)允許多次編程，并享有快速有效地對(duì)新設(shè)計(jì)進(jìn)行優(yōu)化的靈活性，為此，本文選用了altera的cvclone系列FPGA芯片EPlC12-240PQFP，該芯片內(nèi)部有12060個(gè)邏輯單元、239616 bit RAM、兩個(gè)鎖相環(huán)(PLL)。本文應(yīng)用移位寄存器理論來(lái)產(chǎn)生序列，其算法的關(guān)鍵是找到線性m序列和非線性m子序列移位寄存器的反饋邏輯式。

1 m序列的實(shí)現(xiàn)

1.1 基于FPGA的m序列實(shí)現(xiàn)

利用反饋移位寄存器產(chǎn)生0、1序列時(shí)，其n位反饋移位寄存器的邏輯功能如圖1所示。



圖中，x_i蕾表示寄存器所處的狀態(tài)，通常用0和1來(lái)代表兩個(gè)可能的狀態(tài)，并且把0和1看成是有限域GF(2)的兩個(gè)元素。f(x₀，x₁，…，x_n-1)刻劃了移位寄存器反饋邏輯的功能，它可以看成一個(gè)定義在GF(2)上并且在GF(2)中取值的n元函數(shù)，當(dāng)f(x₀，x₁…，x_n-1)可以表示成一線性齊次函數(shù)時(shí)。即，相應(yīng)的反饋移位寄存器是線性的，而由線性移位寄存器產(chǎn)生的序列就稱為線性移位寄存器序列。m序列就是線性移位寄存器序列。

對(duì)于一個(gè)n級(jí)m序列移位寄存器來(lái)說(shuō)。它在每一時(shí)刻的內(nèi)部狀態(tài)都可以看做有限域GF(2)上的一個(gè)n維向量，而反饋函數(shù)就是刻劃了從每一時(shí)刻的狀態(tài)到下一時(shí)刻狀態(tài)的轉(zhuǎn)移規(guī)律，或者說(shuō)反饋函數(shù)定義了n維向量空間上的一個(gè)線性變換。

通常可以用V_n(F)代表域GF(2)上全體n元數(shù)組構(gòu)成的n維向量空間，a=(a₀a₁a₂…a_n-1…)代表n級(jí)移位寄存器產(chǎn)生的m序列。n級(jí)m序列移位寄存器的狀態(tài)可以看做V_n(F)中的向量。設(shè)f(λ)=λⁿ+c_n-1λ^n-1+…+c₀是多項(xiàng)式環(huán)F[λ]中的一次n多項(xiàng)式，那么，對(duì)于G(f)中的線性移位寄存器序列，從狀態(tài)(a_ka_k+1a_k+n-1)到下一個(gè)狀態(tài)(a_k+1a_k+2…a_k+n)的轉(zhuǎn)移就可以看成是Vn(F)的一個(gè)線性變換。由于a_k+n=a_n-1a_k+n-1+c_n-2a_k+n-2+…+c₀a_k，于是，狀態(tài)轉(zhuǎn)移變換用矩陣寫(xiě)出來(lái)就是：



稱為線性移位寄存器的狀態(tài)轉(zhuǎn)移矩陣，顯然，狀態(tài)轉(zhuǎn)移矩陣T和初始狀態(tài)完全刻畫(huà)了線性移位寄存器所產(chǎn)生的序列。它在此建立起了反饋函數(shù)，即，和狀態(tài)轉(zhuǎn)移矩陣T之間的對(duì)應(yīng)關(guān)系。

設(shè)F(λ)=λⁿ+c_n-1λ^n-1+…+c₀是線性遞推序列的極小多項(xiàng)式，那么，一個(gè)周期序列的周期就等于它的極小多項(xiàng)式的周期，因此，一個(gè)n級(jí)m序列的極小多項(xiàng)式f(λ)的周期就是2ⁿ-1。在代數(shù)中，這樣的多項(xiàng)式稱為n次本原多項(xiàng)式。由于矩陣T是有理塊，它的特征多項(xiàng)式∣ΛI(xiàn)-T∣=f(λ)就是它的極小多項(xiàng)式。找到了m序列本原多項(xiàng)式與狀態(tài)轉(zhuǎn)移矩陣T之間的關(guān)系，就可進(jìn)一步獲得m序列本原多項(xiàng)式與反饋函數(shù)，即=之間的關(guān)系，這樣就可以直接從m序列本原多項(xiàng)式出發(fā)，在FPGA中實(shí)現(xiàn)m序列移位寄存器結(jié)構(gòu)并產(chǎn)生m序列。




圖2所示是該序列在QuartusⅡ開(kāi)發(fā)平臺(tái)中的仿真波形。



仿真時(shí)，1個(gè)CLK周期設(shè)置10ns，外加復(fù)位信號(hào)RD所占用的時(shí)間，周期為29-1的m序列仿真時(shí)間需要5.16 μs。所產(chǎn)生的序列如下：



其中，斜體0、1代碼表示序列又一周期的開(kāi)始，周而復(fù)始。

1.2 序列偽隨機(jī)性分析


根據(jù)SEL[0．．2]端子可選擇不同周期的序列，m序列發(fā)生器中R序列周期可選2⁶-1，2⁹-1，2¹⁵-1，2²⁸-1，2³⁶-1；m子序列發(fā)生器中的序列周期可選2⁵-1，2⁶-1，2⁷-1，2⁸-1，2⁹-1。若N_L_SEL端子取1，則選擇非線性偽隨機(jī)序列發(fā)生器，SEL[0．．2]端子取101，則選擇周期是2⁹-1的m子序列。圖4所示是序列發(fā)生器模塊的仿真波形圖。

比較周期是2⁹-1的某一m子序列與同一周期的m序列可知，其兩者具有相同的周期、平衡性、相近的自相關(guān)性以及不同的局部游程和不同的線性復(fù)雜度。QUARTUS中的仿真報(bào)告表明，L_prsg模塊將耗費(fèi)96個(gè)Logic Elements，NL_prsg模塊則耗費(fèi)35個(gè)Logic Elements。

3? 結(jié)束語(yǔ)

偽隨機(jī)序列在通信、密碼學(xué)、雷達(dá)、導(dǎo)航、芯片內(nèi)建自測(cè)試方面具有廣泛的應(yīng)用，本文給出了線性m序列和基于m序列的m子序列的FPGA實(shí)現(xiàn)方法。本方法應(yīng)用移位寄存器理論，從m序列的本原多項(xiàng)式出發(fā)，其算法核心是找到m序列本原多項(xiàng)式與線性m序列和m子序列移位寄存器反饋邏輯式之間的關(guān)系，然后采用VHDL語(yǔ)言編程，并借助Quart usⅡ開(kāi)發(fā)平臺(tái)實(shí)現(xiàn)序列。

文中通過(guò)對(duì)偽隨機(jī)性分析表明：其所產(chǎn)生的序列符合m序列的統(tǒng)計(jì)特性，m子序列也具有優(yōu)良的偽隨機(jī)特性，從而驗(yàn)證了該算法的正確性。