摘要：討論了應(yīng)用移位寄存器在Ahera的FPGA芯片中實(shí)現(xiàn)線性和非線性偽隨機(jī)序列的方法，該算法基于m序列本原多項式來獲得線性m序列和非線性m子序列移位寄存器的反饋邏輯式。文中給出了以Altera的QuartusⅡ?yàn)殚_發(fā)平臺，并用VHDL語言實(shí)現(xiàn)的m序列的仿真波形。
關(guān)鍵詞：偽隨機(jī)序列；m序列；m子序列；移位寄存器；VHDL語言編程

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

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

    圖中，xi表示寄存器所處的狀態(tài)，通常用0和1來代表兩個可能的狀態(tài)，并且把0和1看成是有限域GF(2)的兩個元素。f(x0，x1，…，xn-1)刻劃了移位寄存器反饋邏輯的功能，它可以看成一個定義在GF(2)上并且在GF(2)中取值的n元函數(shù)，當(dāng)f(x0，x1，…，xn-1)可以表示成一線性齊次函數(shù)時，即GF(2)，相應(yīng)的反饋移位寄存器是線性的，而由線性移位寄存器產(chǎn)生的序列就稱為線性移位寄存器序列。m序列就是線性移位寄存器序列。
    對于一個n級m序列移位寄存器來說，它在每一時刻的內(nèi)部狀態(tài)都可以看做有限域GF(2)上的一個n維向量，而反饋函數(shù)就是刻劃了從每一時刻的狀態(tài)到下一時刻狀態(tài)的轉(zhuǎn)移規(guī)律，或者說反饋函數(shù)定義了n維向量空間上的一個線性變換。
    通?？梢杂肰n(F)代表域GF(2)上全體n元數(shù)組構(gòu)成的n維向量空間，a=(a0a1a2…an-1…)代表n級移位寄存器產(chǎn)生的m序列。n級m序列移位寄存器的狀態(tài)可以看做Vn(F)中的向量。設(shè)f(λ)=λn+Cn-1λn-1+…+C0是多項式環(huán)F[λ]中的一次n多項式，那么，對于G(f)中的線性移位寄存器序列，從狀態(tài)(akak+1…ak+n-1)到下一個狀態(tài)(ak+1ak+2…ak+n)的轉(zhuǎn)移就可以看成是Vn(F)的一個線性變換。由于ak+n=cn-1ak+n-1+cn-2ak+n-2+…+coak，于是，狀態(tài)轉(zhuǎn)移變換用矩陣寫出來就是：

 稱為線性移位寄存器的狀態(tài)轉(zhuǎn)移矩陣，顯然，狀態(tài)轉(zhuǎn)移矩陣T和初始狀態(tài)完全刻畫了線性移位寄存器所產(chǎn)生的序列。它在此建立起了反饋
    =GF(2)之間的關(guān)系，這樣就可以直接從m序列本原多項式出發(fā)，在FPGA中實(shí)現(xiàn)m序列移位寄存器結(jié)構(gòu)并產(chǎn)生m序列。

    若本原多項式的m序列移位寄存器反饋邏輯為，則本原多項式的m序列的VHDL語言實(shí)現(xiàn)代碼如下：

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

    
    其中，斜體0、1代碼表示序列又一周期的開始，周而復(fù)始。
1．2序列偽隨機(jī)性分析
    對本原多項式是的m序列偽隨機(jī)性進(jìn)行分析時，主要是分析其平衡性和游程特性。首先是平衡性。通常在一個周期中，m序列的l出現(xiàn)的次數(shù)為2n-1次；0出現(xiàn)的次數(shù)2n-1-1次。其次是游程特性。即對于O<k≤n-2，其長度為k的0游程出現(xiàn)2n-k-2次；長度為k的l游程也出現(xiàn)2n-k-2次；長度為n-1的0游程出現(xiàn)1次；長度為n的l游程出現(xiàn)1次。以上就是其中出現(xiàn)的全部游程。
    平衡性和游程特性分析表明該序列符合m序列的統(tǒng)計特性。

2 非線性m子序列實(shí)現(xiàn)
    m子序列是與m序列具有同周期、相同平衡性和不同局部游程的序列，m子序列移位寄存器的反饋多項式與m序列移位寄存器的反饋多項式的關(guān)系，可以根據(jù)m子序列的構(gòu)造思想來計算，其中交換一對共軛狀態(tài)的后繼意味著反饋函數(shù)f(x)在共軛狀態(tài)處取補(bǔ)，其中s=(s0s1…sn-1)，，即f(x)’=f(x)+1。其它狀態(tài)處反饋函數(shù)不變，即f(x)’=f(x)+0。因此，可由布爾函數(shù)理論推知：

    
    現(xiàn)以本原多項式所對應(yīng)的移位寄存器為出發(fā)點(diǎn)，以周期29-1的某一m子序列為例，給移位寄存器賦以初始值{000000001}，并在此交換兩對共軛狀態(tài)的后繼，其中；
那么，由布爾函數(shù)理論及式(1)和式(2)有：m子序列移位寄存器反饋邏輯為：
，
若將線性m序列和非線性m子序列整合在一起，那么，在Quartus中生成的序列發(fā)生器模塊如圖3所示。

    圖3中，L_prsg模塊是線性偽隨機(jī)序列發(fā)生器(m序列發(fā)生器)，NL_prsg模塊是非線性偽隨機(jī)序列發(fā)生器(m子序列發(fā)生器)。時鐘clk選用2 MHz。根據(jù)SEL[0．．2]端子可選擇不同周期的序列，m序列發(fā)生器中R序列周期可選；m子序列發(fā)生器中的序列周期可選。若N_L_SEL端子取1，則選擇非線性偽隨機(jī)序列發(fā)生器，SEL[0. .2]端子取101，則選擇周期是29-1的m子序列。圖4所示是序列發(fā)生器模塊的仿真波形圖。

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

3 結(jié)束語
    偽隨機(jī)序列在通信、密碼學(xué)、雷達(dá)、導(dǎo)航、芯片內(nèi)建自測試方面具有廣泛的應(yīng)用，本文給出了線性m序列和基于m序列的m子序列的FPGA實(shí)
現(xiàn)方法。本方法應(yīng)用移位寄存器理論。從m序列的本原多項式出發(fā)，其算法核心是找到m序列本原多項式與線性m序列和m子序列移位寄存器反
饋邏輯式之間的關(guān)系，然后采用VHDL語言編程，并借助Qualt usⅡ開發(fā)平臺實(shí)現(xiàn)序列。
    文中通過對偽隨機(jī)性分析表明：其所產(chǎn)生的序列符合m序列的統(tǒng)計特性。m子序列也具有優(yōu)良的偽隨機(jī)特性，從而驗(yàn)證了該算法的正確性。