摘要：依據(jù)非線性移位寄存器的原理，文中討論二元給定序列非線性反饋移位寄存器的綜合算法，用C語言編程，找到了產(chǎn)生該序列的非線性移位寄存器。借助EDA技術(shù)，以FPGA為硬件基礎(chǔ)，經(jīng)過設(shè)計優(yōu)化構(gòu)成定長序列和給定周期序列的偽隨機序列發(fā)生器，并進行了仿直實驗，用硬件實驗證實了設(shè)計的合理性。

    關(guān)鍵詞：非線性偽隨機序列 非線性移位寄存器 現(xiàn)場可編程門陣列

1 引言

偽隨機序列具有良好的隨機性，在偽碼測距、導航、遙控和遙測、擴頻通信、多址通信、分離多徑、數(shù)據(jù)加亂、信號同步、誤碼測試、線性系統(tǒng)測量、天線方向測量和各種噪聲源等方面得以廣泛的應用。偽隨機序列的產(chǎn)生可以通過線性移位寄存器即m序列來實現(xiàn)，也可以通過非線性移位寄存器來實現(xiàn)。非線性移位寄存器比起線性移位寄存器具有許多優(yōu)越性，非線性移位寄存器的總線比線性反饋移位寄存器的總數(shù)要多得多，給實際應用提供了充分的選擇余地。但是非線性反饋移位寄存器一般比線性反饋移位寄存器在邏輯上要復雜得多，因而也在設(shè)備上帶來了相應的復雜性。本文從非線性移位寄存器的綜合問題發(fā)出，討論給定序列的綜合問題，并在大規(guī)?？删幊踢壿嬈骷蠈崿F(xiàn)這種非線性偽隨機序列發(fā)生器。

2 非線性移位寄存器的綜合

關(guān)于非線性移位寄存器的綜合問題可以有很多種提法，這里討論產(chǎn)生定長非周期序列和給定周期序列的最短移位寄存器的方法。

    2．1 定長序列的綜合

定長序列的綜合尋求長為l給定二元序列（a1,a2,3,…al, …）的最短移位寄存器。產(chǎn)生上述定長二元序列的n(n<l)級反饋移位寄存器，其反饋函數(shù)為f(x1,x2,…，xn)，則序列的前項所形成的狀態(tài)序列為S1，S2，…，Sl-n,Si=(ai+ai+1,…,ai+n+1)（i=1,2,…,l-n）必須具備下列條件之一：

（1）狀態(tài)序列中諸頂點彼此互異；

（2）狀態(tài)序列諸頂點中有相重者。

滿足條件（1）時，則反饋函數(shù)為

滿足條件（2）時，若n0為最小正整數(shù)（n1≤l-n），使Snl與它前面的一個狀態(tài)Sn0相重(1≤n0≤n1≤l-n):Snl=Sn0

此時必須

狀態(tài)Sl,S2,…，Sn0Sn0+1,…,Sl-n必須彼此互異，于是反饋函數(shù)可寫成

尋求長為l給定序列的最短移位寄存器可歸結(jié)為尋求滿足條件（1）或（2）的最小自然數(shù)n(n<1)的問題，滿足上述條件的最小自然數(shù)n(n<l-1)一定存在。

因此，尋求該序列之最短移位寄存器可以采用從n=1開始逐步搜索的方法來求得滿足條件（1）或（2）的最小自然數(shù)n及相應的反饋函數(shù)f(x1,x2,…,xn),其算法框圖如圖1所示。

圖3

    2．2 給定周期序列的綜合

給定周期序列的綜合即尋求產(chǎn)生給定周期序列（a1,a2,…,al,al+1,…）的最短移位寄存器。給定周期序列的綜合被歸結(jié)為尋求使l個狀態(tài)Si=(ai,ai+1,…,ai+n-1)，i=1,2,A,l彼波互異的最小自然數(shù)n(n≤l)的問題。狀態(tài)序列S1,S2,…，Sl,其中Si=(ai,ai+1,…,ain+1),1≤i≤l兩兩不同，則產(chǎn)生給定周期序列的移位寄存器的反饋函數(shù)為

其算法流程如圖2所示。

圖4

3 非線性偽隨機序列的FPGA實現(xiàn)

FPGA為現(xiàn)場可編程門陣列邏輯器件，是倍受現(xiàn)代數(shù)字系統(tǒng)設(shè)計工程師歡迎的最新一代系統(tǒng)設(shè)計積木塊。FPGA為邏輯門級編程，其芯片中有被互連網(wǎng)絡包圍的邏輯單元，芯片四周為可編程的輸入/輸出單元陣列，其互連模式亦是可編程的，用戶可以通過現(xiàn)場編程決定每個單元的功能及它們的互連關(guān)系。FPGA具有集成度高，編程靈活，陣列引腳數(shù)多，功耗低，設(shè)計編程速度快等特點。Altera公司的FLEX10K系列中的EPF10K10LC84-4型FPGA，基于SRAM的在系統(tǒng)可編程結(jié)構(gòu)，該FPGA可利用Altera公司的MAX+PlusII軟件進行編程。MAX+PlusII軟件有原理圖輸入法和硬件語言輸入法，本設(shè)計采用原理圖輸入法，經(jīng)過編譯、時序仿真優(yōu)化后，下載至EPF10K10LC84-4中。

3．1 定長序列的實現(xiàn)

以長為28序列為說明設(shè)計過程，給定序列為

（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)


    輸入l=28和（1）序列，C語言程序計算移位寄存器反饋函數(shù)為

f(x)=x1x2x3x6+x2x3x4x5+x1x2x3x5+x2x4x6(x3+x1x5)+x1x3x4x6+x1x3x5x2x4+x1x5x6x2x3x4+x4x5x6(x3+x1)+x1x2x6+x1x2x4x5

用原理圖輸入法構(gòu)成圖3所示的電路。其中cp端為時鐘，start端為起始狀態(tài)輸入端，x28為序列輸出端，其仿真波形如圖4所示。

圖5

    3．2 給定周期序列的實現(xiàn)

以周期15給定周期序列為例，其一個周期序列為

（0，1，1，1，，0，1，01，01，1，0，0，0，1） （2）

用C評議程序計算移位寄存器反饋函數(shù)為

f(x)=x1x2x3x4+x1x2x5(x4+x6)+(x2x4+x1x2x4)x3x5x4x6x2x3+x4x5x6x1x2+x1x3x6(x2+x4+x5)+(x4+x2)x1x3x5x6

用原理圖輸入法構(gòu)成的電路如圖5所示，仿真波形見圖6。

將圖3和圖5電路下載到EPF10K10LC84-4中，用Tektronix TDS3052型示波器觀察波形，其波形如圖7所示。

圖6、7

4 結(jié)論

本文從非線性偽隨機序列的綜合出發(fā)，對尋找給定序列非線性反饋移位寄存器反饋函數(shù)的算法進行了討論，用C語言和Mathematica編程計算定長序列和給定周期序列的反饋函數(shù)。利用MAX+PlusII軟件設(shè)計了定長有限序列和給定周期序列發(fā)生器，并在EPF10K10LC84-4中實現(xiàn)了該非線性偽隨機序列發(fā)生器并進行驗證。非線性偽隨機序列發(fā)生器產(chǎn)生序列數(shù)多，給實際應用帶來更多的選擇。