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

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

1 引言

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

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

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

    2．1 定長序列的綜合

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

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

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

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

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

此時(shí)必須

狀態(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及相應(yīng)的反饋函數(shù)f(x1,x2,…,xn),其算法框圖如圖1所示。

圖3

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

給定周期序列的綜合即尋求產(chǎn)生給定周期序列（a1,a2,…,al,al+1,…）的最短移位寄存器。給定周期序列的綜合被歸結(jié)為尋求使l個(gè)狀態(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 非線性偽隨機(jī)序列的FPGA實(shí)現(xiàn)

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

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

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

（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語言程序計(jì)算移位寄存器反饋函數(shù)為

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

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

圖5

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

以周期15給定周期序列為例，其一個(gè)周期序列為

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

用C評(píng)議程序計(jì)算移位寄存器反饋函數(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é)論

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