任意級數的快速m序列發生器的設計

鄒學玉 (長江大學電子信息學院,湖北荊州434023)

m序列是一種偽隨機序列,具有優良的自相關函數,容易產生和復制,在數字基帶信號的加擾、擴頻通信、雷達、通信系統的測量、石油地震勘探等領域都有著廣泛的應用,因而m序列的產生一直是國內外信息領域的研究熱點[1～4]。近年來,隨著可編程邏輯器件FPGA/CPLD的不斷發展,在很多高速設計和高速測試的場合,都希望能夠在FPGA中直接實現不同級數的m序列發生器。傳統的大數乘法產生偽隨機數方法受到時鐘頻率不能太高的限制,并且需要消耗FPGA/CPLD內大量的資源[4],因而要找到一種合適的邏輯結構來高速產生任意級數的m序列并運行于較高的工作頻率。基于Fabonacci結構的FPGA設計一種任意級數和初始相位均可調的m序列發生器,因Fabonacci結構的反饋網絡較大延時隨級數的增加而增加,制約了m序列產生速度的提升[5]。基于Galois結構的m序列發生器,其反饋網絡簡單,其運算延時基本不隨級數的變化而變化,這有利于以相同的高速產生不同級數的m序列。由于Galois結構與Fabonacci結構的反饋系數不同,因而需要從 Fabonacci結構的反饋系數中導出Galois結構的反饋系數[6]。為此,筆者基于Galois結構的反饋系數表設計出快速m序列發生器。

1 Galois結構的m序列發生器原理

m序列信號發生器是在n級線性移位寄存器[6～8]的基礎上,加上反饋邏輯電路構成的。m序列信號發生器有2種結構,即Fabonacci型和Galois型[4,6～8]。筆者采用Galois型移位寄存器產生m序列。該結構的特點是只有第n位觸發器的狀態作為反饋,而且其反饋網絡延時小,但移位寄存器的反饋抽頭位置與本原多項式不一致,需要經過某種變換才能得到Galois結構,其結構如圖1所示。

圖1 n級 Galois結構模型

圖1表示一個有限狀態機,其中D為延時環節,該狀態機的轉換方程和輸出方程分別為:

若從最后一級輸出m序列,則C可簡化為:

A與n級線性移位寄存器構成的偽隨機序列的本原多項式有關,反饋系數g0,g1,…,gn-2將決定m序列發生器的結構。因此,只要初態s0≠0和任意級數n的反饋系數已知,就可以設計出相應的Galois型m序列發生器。該設計主要基于二元有限域GF(2)上的n級反饋系數g0,g1,…,gn-2表來實現GF(2)上的m序列發生器。

2 任意級數m序列發生器模塊設計與實現

根據上述分析,設計任意級數m序列發生器的總體框圖,如圖2所示。

圖2 任意可變級數n的Galois型m序列發生器框圖

圖3 Galois型反饋系數表存儲器結構圖

以Altera公司的EPM1270T144C5芯片為例,在級數n值在3～29時系統中2個最為關鍵的模塊設計具體內容如下。

1)Galois型反饋系數表存儲器設計 設計Galois型反饋系數表存儲器結構如圖3所示。該結構由FPGA中內嵌的E2PROM構成,只要給定n,經過級數調整模塊運算得到其相應地址addr,即可從E2PROM的輸出端feedfactor輸出其相應的反饋系數。故存儲器中要存儲27組反饋系數值,若設計級數的最小級數為ns,最大級數為ne,則E2PROM的地址空間范圍是從0至ne-ns。將這27組反饋系數值做成一個ROM表,則需要一個5位二進制數字作為地址輸入來提取與之相應的反饋系數值。該模塊的VHDL程序如下:

2)Galois型移位存儲器設計 為實現級數n值在3～29可調的m序列,先生成一個29級的Galois型移位寄存器,該結構的第29位D觸發器的輸出是否反饋取決于級數n。可用一個信號X來表征相應級數的Galois型結構中的反饋特征,X在移位寄存器狀態輸出(S(1),…,S(28))中取值。通過輸入5位二進制信號addr[4,…,0]來確定末位反饋信號X的取值。如當輸入addr[4,…,0]為00000時,反饋信號X＜=S(1),這樣就生成了一個3級的m序列發生器;當輸入addr[4,…,0]為00001時,反饋信號X＜=S(2),這樣就生成了一個4級的m序列發生器;依此類推。該模塊的VHDL程序如下:

該模塊有4個輸入 (clk,rst,addr[4,…,0],G[0,…,27])、1個輸出 (Q)和1個緩沖口(S[n-1,…,0])。clk為器件的工作時鐘;rst為器件的控制信號,為 “1”時器件工作;G[0,…,27]是位于地址addr[4,…,0]的反饋系數表存儲器中輸出的反饋系數;Q為n級的m序列信號的輸出。

3 結果分析

筆者在QuartusⅡ上對級數n分別為3～29的m序列發生器進行了仿真,給出了級數n分別為3和29的m序列發生器的仿真結果 (見圖4),并對系統的延時進行分析。

為便于分析,筆者對系統中各寄存器的初始狀態都設定為 “1”,所以m序列的輸出應該從 “1”開始。由圖4可知,m序列的每一位的寬度均為一個時鐘周期;m序列輸出的起始位置為rst置 “1”后的第一個時鐘上升沿是在35ns處。圖4(a)中m序列在57.599ns開始輸出,系統延時22.599ns;圖4(b)中m序列在57.472ns開始輸出,系統延時22.472ns。由此可見,系統延時受級數n的影響較小。

4 結 語

用VHDL語言描述復雜的數字系統設計效率顯著提高,對于任意級數的m序列發生器,充分利用FPGA芯片內置的ROM構建任意級數的Galois型反饋系數表,極大地簡化了快速m序列發生器的實現過程。由于其產生的速率快,且基本不受級數n的影響,因而該m序列產生方法具有較強的適應性和較廣的應用范圍,尤其適用于級數n可變的應用場合。

圖4 m序列發生器的仿真結果

[1]Zeng Kencheng,Yang Chung-Huang,Wei Dah-Yea,et al.Pseudorandom Bit Generators in Stream-Cipher Cryptograph[J].Computer,1991,24(2):8～17.

[2]Ali Kanso.Clock-controlled shrinking generator of feedback shift registers[A].8th Australasian Conference on Information Security and Privacy-ACISP[C].2003.

[3]蒲海,陳自力,胡玫榮.基于CP LD的高速m序列碼發生器的設計[J].微計算機信息,2005,21(4):172～173.

[4]束禮寶,宋克柱.偽隨機數發生器的FPGA實現與研究[J].電路與系統學報,2003,8(3):121～124.

[5]鄒學玉,易國華.一類基于FPGA的m序列發生器的設計 [J].長江大學學報 (自然科學版),2006,3(3):84～86.

[6]Zepernick H J,Finger A.Pseudo Random Signal Processing:Theory and Application[M].Chichester:John Wiley&Sons,2005.

[7]林可祥,汪一飛.偽隨機碼的原理與應用[M].北京:人民郵電出版社,1998.

[8]梅文華,楊義先.跳頻通信地址編碼理論[M].北京:國防工業出版社,1996.