二元給定序列非線性移位寄存器的綜合與產生
加入技術交流群
關鍵詞：非線性偽隨機序列 非線性移位寄存器 現場可編程門陣列
1 引言
偽隨機序列具有良好的隨機性，在偽碼測距、導航、遙控和遙測、擴頻通信、多址通信、分離多徑、數據加亂、信號同步、誤碼測試、線性系統測量、天線方向測量和各種噪聲源等方面得以廣泛的應用。偽隨機序列的產生可以通過線性移位寄存器即m序列來實現，也可以通過非線性移位寄存器來實現。非線性移位寄存器比起線性移位寄存器具有許多優越性，非線性移位寄存器的總線比線性反饋移位寄存器的總數要多得多，給實際應用提供了充分的選擇余地。但是非線性反饋移位寄存器一般比線性反饋移位寄存器在邏輯上要復雜得多，因而也在設備上帶來了相應的復雜性。本文從非線性移位寄存器的綜合問題發出，討論給定序列的綜合問題，并在大規模可編程邏輯器件上實現這種非線性偽隨機序列發生器。
2 非線性移位寄存器的綜合
關于非線性移位寄存器的綜合問題可以有很多種提法，這里討論產生定長非周期序列和給定周期序列的最短移位寄存器的方法。
2．1 定長序列的綜合
定長序列的綜合尋求長為l給定二元序列（a1,a2,3,…al, …）的最短移位寄存器。產生上述定長二元序列的n(nl)級反饋移位寄存器，其反饋函數為f(x1,x2,…，xn)，則序列的前項所形成的狀態序列為S1，S2，…，Sl-n,Si=(ai+ai+1,…,ai+n+1)（i=1,2,…,l-n）必須具備下列條件之一：
（1）狀態序列中諸頂點彼此互異；
（2）狀態序列諸頂點中有相重者。
滿足條件（1）時，則反饋函數為
滿足條件（2）時，若n0為最小正整數（n1≤l-n），使Snl與它前面的一個狀態Sn0相重(1≤n0≤n1≤l-n):Snl=Sn0
此時必須
狀態Sl,S2,…，Sn0Sn0+1,…,Sl-n必須彼此互異，于是反饋函數可寫成
尋求長為l給定序列的最短移位寄存器可歸結為尋求滿足條件（1）或（2）的最小自然數n(n1)的問題，滿足上述條件的最小自然數n(nl-1)一定存在。
因此，尋求該序列之最短移位寄存器可以采用從n=1開始逐步搜索的方法來求得滿足條件（1）或（2）的最小自然數n及相應的反饋函數f(x1,x2,…,xn),其算法框圖如圖1所示。
圖3
給定周期序列的綜合即尋求產生給定周期序列（a1,a2,…,al,al+1,…）的最短移位寄存器。給定周期序列的綜合被歸結為尋求使l個狀態Si=(ai,ai+1,…,ai+n-1)，i=1,2,A,l彼波互異的最小自然數n(n≤l)的問題。狀態序列S1,S2,…，Sl,其中Si=(ai,ai+1,…,ain+1),1≤i≤l兩兩不同，則產生給定周期序列的移位寄存器的反饋函數為
其算法流程如圖2所示。
圖4
3 非線性偽隨機序列的FPGA實現
FPGA為現場可編程門陣列邏輯器件，是倍受現代數字系統設計工程師歡迎的最新一代系統設計積木塊。FPGA為邏輯門級編程，其芯片中有被互連網絡包圍的邏輯單元，芯片四周為可編程的輸入/輸出單元陣列，其互連模式亦是可編程的，用戶可以通過現場編程決定每個單元的功能及它們的互連關系。FPGA具有集成度高，編程靈活，陣列引腳數多，功耗低，設計編程速度快等特點。Altera公司的FLEX10K系列中的EPF10K10LC84-4型FPGA，基于SRAM的在系統可編程結構，該FPGA可利用Altera公司的MAX+PlusII軟件進行編程。MAX+PlusII軟件有原理圖輸入法和硬件語言輸入法，本設計采用原理圖輸入法，經過編譯、時序仿真優化后，下載至EPF10K10LC84-4中。
3．1 定長序列的實現
以長為28序列為說明設計過程，給定序列為
（0,1,1,1,0,1,01,1,0,0,01,1,1,1,1,0,0,1,1,0,1,1,1,0） (1)
f(x)=x1x2x3x6+x2x3x4x5+x1x2x3x5+x2x4x6(x3+x1x5)+x1x3x4x6+x1x3x5x2x4+x1x5x6x2x3x4+x4x5x6(x3+x1)+x1x2x6+x1x2x4x5
用原理圖輸入法構成圖3所示的電路。其中cp端為時鐘，start端為起始狀態輸入端，x28為序列輸出端，其仿真波形如圖4所示。
圖5
以周期15給定周期序列為例，其一個周期序列為
（0，1，1，1，，0，1，01，01，1，0，0，0，1） （2）
用C評議程序計算移位寄存器反饋函數為
f(x)=x1x2x3x4+x1x2x5(x4+x6)+(x2x4+x1x2x4)x3x5x4x6x2x3+x4x5x6x1x2+x1x3x6(x2+x4+x5)+(x4+x2)x1x3x5x6
用原理圖輸入法構成的電路如圖5所示，仿真波形見圖6。
將圖3和圖5電路下載到EPF10K10LC84-4中，用Tektronix TDS3052型示波器觀察波形，其波形如圖7所示。
圖6、7
4 結論
本文從非線性偽隨機序列的綜合出發，對尋找給定序列非線性反饋移位寄存器反饋函數的算法進行了討論，用C語言和Mathematica編程計算定長序列和給定周期序列的反饋函數。利用MAX+PlusII軟件設計了定長有限序列和給定周期序列發生器，并在EPF10K10LC84-4中實現了該非線性偽隨機序列發生器并進行驗證。非線性偽隨機序列發生器產生序列數多，給實際應用帶來更多的選擇。
評論