杜云峰，李 明

(西安電子科技大學(xué) 電子工程研究所，陜西 西安 710071)

隨機(jī)數(shù)是雖然具有一定的統(tǒng)計(jì)學(xué)規(guī)律，但抽樣值不能事先確定的數(shù)。實(shí)際中產(chǎn)生的隨機(jī)數(shù)不是絕對(duì)隨機(jī)數(shù)，而是相對(duì)的，稱(chēng)為“偽隨機(jī)數(shù)”[1]。偽隨機(jī)數(shù)既有隨機(jī)數(shù)所具有的優(yōu)良相關(guān)性，又有隨機(jī)數(shù)所不具備的規(guī)律性。這兩個(gè)特點(diǎn)，使得以偽隨機(jī)數(shù)為基礎(chǔ)的偽隨機(jī)信號(hào)既易于從干擾信號(hào)中被識(shí)別和分離出來(lái)，又可以方便的產(chǎn)生和重復(fù)。因此偽隨機(jī)序列在通訊、雷達(dá)、導(dǎo)航、測(cè)量、密碼、計(jì)算機(jī)、相關(guān)辨識(shí)及故障診斷等許多領(lǐng)域中都有著廣泛的應(yīng)用。

在許多文獻(xiàn)中，涉及的偽隨機(jī)序列產(chǎn)生方法多是基于高級(jí)語(yǔ)言的，較少涉及硬件具體實(shí)現(xiàn)問(wèn)題。已有的一些硬件實(shí)現(xiàn)方法，在FPGA芯片和DSP芯片上都有過(guò)應(yīng)用[1，2]。其中在用DSP芯片實(shí)現(xiàn)時(shí)，如果要求產(chǎn)生任意長(zhǎng)度M(M＞0)的一個(gè)偽隨機(jī)序列并保證在無(wú)重復(fù)數(shù)的前提下該序列包含0～M-1的每一個(gè)數(shù)，傳統(tǒng)做法無(wú)法完成;只有將生成的序列長(zhǎng)度M限制為2n(1≤n≤32)時(shí)，才能滿(mǎn)足要求[3-5]。文中介紹的基于DSP的偽隨機(jī)序列產(chǎn)生方法解決了這樣的問(wèn)題，可以產(chǎn)生任意長(zhǎng)度的偽隨機(jī)序列，對(duì)工程應(yīng)用有一定的現(xiàn)實(shí)意義。

1 線(xiàn)性同余算法的基本原理

線(xiàn)性同余算法[6]的核心公式是Xn+1=(aXn+b)modM，n=0，1，…，M-1。其中，a(0≤a≤M)是乘數(shù)，b(0≤b≤M)是加數(shù)，M(M＞0)是模數(shù)，X0(0≤X0≤M)是初值即種子。模數(shù)M也等于生成的偽隨機(jī)序列的長(zhǎng)度，所有參數(shù)均為整數(shù)。

線(xiàn)性同余算法產(chǎn)生的偽隨機(jī)序列在不更換種子的前提下以M(M=2n)為周期出現(xiàn)循環(huán)，如果M不等于2n，序列將以＜M的周期出現(xiàn)循環(huán)。

例如:當(dāng)M=10，a=b=X0=7時(shí)，生成序列為{6，9，0，7，6，9，…}，周期為4;當(dāng)M=8，a=5，b=1，X0=1時(shí)，生成序列為{6，7，4，5，2，3，0，1，6，7，…}，周期為8;當(dāng)M=16，a=5，b=3，X0=7時(shí)，生成序列為{6，18，11，10，5，12，15，14，9，0，3，2，13，4，7，6，1，…}，周期為16。

由上面的例子可以看出，直接運(yùn)用線(xiàn)性同余算法用硬件產(chǎn)生偽隨機(jī)序列在實(shí)際工程應(yīng)用中并不靈活。比如在雷達(dá)信號(hào)處理中，為了減小外界對(duì)雷達(dá)信號(hào)接收的干擾，會(huì)要求發(fā)射機(jī)和接收機(jī)以一定的時(shí)間間隔隨機(jī)地在一定數(shù)目的頻點(diǎn)上跳頻，在跳頻過(guò)程中不跳完所有規(guī)定的頻點(diǎn)不允許重復(fù)[7，8]。如果一個(gè)頻點(diǎn)用一個(gè)偽隨機(jī)數(shù)來(lái)對(duì)應(yīng)，這就可以等價(jià)為一個(gè)偽隨機(jī)序列問(wèn)題。顯然，不能因?yàn)閭鹘y(tǒng)方法生成的偽隨機(jī)序列長(zhǎng)度必須為2n(1≤n≤32)，而要求發(fā)射機(jī)和接收機(jī)的跳頻點(diǎn)個(gè)數(shù)也設(shè)計(jì)為2n(1≤n≤32)[9]。

2 任意長(zhǎng)度偽隨機(jī)序列產(chǎn)生方法及DSP實(shí)現(xiàn)

由上面的舉例可以看出，在序列長(zhǎng)度M≠2n的時(shí)候，生成序列中的數(shù)都＜M并且會(huì)以＜M的周期出現(xiàn)循環(huán)。如果就用這個(gè)序列作為輸出肯定是不符合要求的，因?yàn)樵?～M-1之間有很多數(shù)都沒(méi)有在結(jié)果中出現(xiàn)，換種說(shuō)法就是輸出的序列沒(méi)有對(duì)0～M-1這M個(gè)數(shù)進(jìn)行遍歷。但是換種思路，如果把這個(gè)序列不直接用作輸出，而當(dāng)作一個(gè)偏移地址，就有可能間接地以訪(fǎng)問(wèn)某個(gè)地址的方式輸出一串符合偽隨機(jī)序列要求的數(shù)。這就是文中介紹的生成任意長(zhǎng)度偽隨機(jī)序列方法的核心。

下面結(jié)合DSP的硬件實(shí)現(xiàn)具體闡述各個(gè)步驟。

首先，用DSP程序生成一組特定長(zhǎng)度為M的數(shù)然后放入內(nèi)存中，這里的M可以等于2n也可以是任意值。也可以事先在外部文件中寫(xiě)好需要輸出的一組數(shù)然后導(dǎo)入DSP的內(nèi)存中。根據(jù)不同的應(yīng)用場(chǎng)合，放入內(nèi)存的這組數(shù)可以是0～M-1，也可以是沒(méi)有任何規(guī)律排列的任意M個(gè)數(shù)。

其次，根據(jù)要求給種子、乘數(shù)、加數(shù)和模數(shù)賦值，調(diào)用求余子程序根據(jù)線(xiàn)性同余算法公式進(jìn)行運(yùn)算，得到一個(gè)余數(shù)。用得到的余數(shù)作為偏移地址，加上已放入內(nèi)存中序列的首地址也就是基地值，就得到了一個(gè)訪(fǎng)問(wèn)地址。因?yàn)閯偛诺那笥嗖僮魇菍?duì)M進(jìn)行，得到的余數(shù)即偏移地址一定＜M，所以按照得到的訪(fǎng)問(wèn)地址進(jìn)行尋址，得到的數(shù)一定是內(nèi)存中長(zhǎng)度為M的已存序列中的某個(gè)數(shù)，將這個(gè)數(shù)輸出。

再次，把上一步已輸出數(shù)后面的每個(gè)數(shù)都向前存放一個(gè)地址，這樣內(nèi)存中的序列首地址不變，序列長(zhǎng)度減1。把模數(shù)M也減1，以對(duì)應(yīng)新的序列長(zhǎng)度。再調(diào)用求余子程序，根據(jù)線(xiàn)性同余算法公式進(jìn)行運(yùn)算，得到又一個(gè)余數(shù)。然后同樣會(huì)得到一個(gè)新訪(fǎng)問(wèn)地址，同樣能輸出內(nèi)存中長(zhǎng)度為M-1的序列中的某個(gè)數(shù)，將其輸出。

隨后，把上一步已輸出數(shù)后面的每個(gè)數(shù)再都向前存放一個(gè)地址，這樣內(nèi)存中的序列首地址還不變，序列長(zhǎng)度再減1，把模數(shù)M也再減1。按照剛才闡述的操作步驟重復(fù)進(jìn)行，直至模數(shù)被減為1，就會(huì)輸出一個(gè)符合要求的長(zhǎng)度為的偽隨機(jī)序列。此時(shí)的序列就是任意長(zhǎng)度的偽隨機(jī)序列。

最后，如果內(nèi)存中的數(shù)都被輸出完，重新導(dǎo)入長(zhǎng)度為M的序列，并更換種子[8]，乘數(shù)和加數(shù)可以更換也可以不更換。然后進(jìn)入新一輪的偽隨機(jī)數(shù)生成，新生成序列中的M個(gè)數(shù)和已生成序列中的M個(gè)數(shù)相比較順序已經(jīng)被完全打亂。這樣一直重復(fù)操作下去，每輸出M個(gè)數(shù)更換一次種子，就可以生成含有M個(gè)元素的長(zhǎng)度為n×M(n為正整數(shù))的偽隨機(jī)序列。

操作流程，如圖1所示。

DSP主要匯編程序[10]。程序中以j19寄存器中所放值為基地值、長(zhǎng)度為M(M為任意值)的一組數(shù)就是得到的長(zhǎng)度為M(M為任意值)的偽隨機(jī)序列，想要得到含有M個(gè)元素的長(zhǎng)度為n×M(n為正整數(shù))的偽隨機(jī)序列，只要每隔M個(gè)數(shù)更換種子重新運(yùn)行程序就可以得到。

當(dāng)外部文件中存有1～M依次排列的M個(gè)數(shù)時(shí)，仿真結(jié)果舉例如下:

當(dāng)M=8，a=b=X0=7時(shí)，生成序列為{1，2，5，4，3，8，6，7，12，…}，周期為8;當(dāng)M=10，a=b=X0=7時(shí)，生成序列為(7，3，1，2，6，5，4，10，8，9，7，3，…)，周期為10;當(dāng)M=11，a=5，b=3，X0=4時(shí)，生成序列為{2，5，8，11，4，10，7，9，6，3，1，2，5，…}，周期為11;當(dāng)M=12，a=5，b=3，X0=4時(shí)，生成序列為{12，2，5，8，11，4，10，7，9，6，3，1，12，2，…}，周期為12。

由仿真結(jié)果可以看出，文中介紹的方法能靈活產(chǎn)生任意長(zhǎng)度的偽隨機(jī)序列。

3 結(jié)束語(yǔ)

圖1 DSP程序流程

偽隨機(jī)序列有著廣泛的應(yīng)用前景，在通信傳輸和雷達(dá)抗干擾方面尤為重要，序列長(zhǎng)度是影響其應(yīng)用的關(guān)鍵因素。文中討論了偽隨機(jī)序列長(zhǎng)度和遍歷性的矛盾，提出了基于DSP芯片具有遍歷性的任意長(zhǎng)度偽隨機(jī)序列的工程實(shí)現(xiàn)方法。給出了對(duì)該實(shí)現(xiàn)方法具體步驟的分析，DSP程序的仿真結(jié)果顯示了該實(shí)現(xiàn)方法的正確性和有效性。在應(yīng)用中可方便地修改程序中各參數(shù)，以滿(mǎn)足各種場(chǎng)合不同的需求。

[1] 束禮寶，宋克柱，王硯方.偽隨機(jī)數(shù)發(fā)生器的FPGA實(shí)現(xiàn)與研究[J].電路與系統(tǒng)學(xué)報(bào)，2003，8(3):121.

[2] 章瀲，秦會(huì)斌.基于FPGA偽隨機(jī)碼發(fā)生器的實(shí)現(xiàn)[J].電子與封裝，2008，8(2):43-45.

[3] 張瑞華，劉慶華，周德新.偽隨機(jī)噪聲產(chǎn)生算法及DSP實(shí)現(xiàn)[J].聲學(xué)與電子工程，2003(2):22-23.

[4] 賈銀潔，趙麗娟，許鵬飛.擴(kuò)頻系統(tǒng)中偽隨機(jī)碼發(fā)生器的實(shí)現(xiàn)[J].現(xiàn)代計(jì)算機(jī)，2008(5):72-73.

[5] 吳浩，郝燕玲，徐定杰.DSP在偽隨機(jī)序列發(fā)生器中的應(yīng)用[J].應(yīng)用科技，2002，29(8):43-44.

[6] 馬華，張曉清，張鵬鴿.一種基于線(xiàn)性同余算法的偽隨機(jī)數(shù)產(chǎn)生器[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2005，21(9):206-207.

[7] 茅以海.頻率捷變雷達(dá)[M].北京:國(guó)防工業(yè)出版社，1981.

[8] 韓建輝.雷達(dá)抗干擾中隨機(jī)數(shù)產(chǎn)生技術(shù)分析研究[J].雷達(dá)與對(duì)抗，2006(1):9-11.

[9] 林象平.雷達(dá)對(duì)抗原理[M].西安:西北電訊工程學(xué)院出版社，1985.

[10]劉書(shū)明，羅勇江.ADSPTS20XS系列DSP原理與應(yīng)用設(shè)計(jì)[M].北京:電子工業(yè)出版社，2007.