基于DSP的任意長度偽隨機序列產生方法

杜云峰，李 明

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

隨機數是雖然具有一定的統計學規律，但抽樣值不能事先確定的數。實際中產生的隨機數不是絕對隨機數，而是相對的，稱為“偽隨機數”[1]。偽隨機數既有隨機數所具有的優良相關性，又有隨機數所不具備的規律性。這兩個特點，使得以偽隨機數為基礎的偽隨機信號既易于從干擾信號中被識別和分離出來，又可以方便的產生和重復。因此偽隨機序列在通訊、雷達、導航、測量、密碼、計算機、相關辨識及故障診斷等許多領域中都有著廣泛的應用。

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

1 線性同余算法的基本原理

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

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

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

由上面的例子可以看出，直接運用線性同余算法用硬件產生偽隨機序列在實際工程應用中并不靈活。比如在雷達信號處理中，為了減小外界對雷達信號接收的干擾，會要求發射機和接收機以一定的時間間隔隨機地在一定數目的頻點上跳頻，在跳頻過程中不跳完所有規定的頻點不允許重復[7，8]。如果一個頻點用一個偽隨機數來對應，這就可以等價為一個偽隨機序列問題。顯然，不能因為傳統方法生成的偽隨機序列長度必須為2n(1≤n≤32)，而要求發射機和接收機的跳頻點個數也設計為2n(1≤n≤32)[9]。

2 任意長度偽隨機序列產生方法及DSP實現

由上面的舉例可以看出，在序列長度M≠2n的時候，生成序列中的數都＜M并且會以＜M的周期出現循環。如果就用這個序列作為輸出肯定是不符合要求的，因為在0～M-1之間有很多數都沒有在結果中出現，換種說法就是輸出的序列沒有對0～M-1這M個數進行遍歷。但是換種思路，如果把這個序列不直接用作輸出，而當作一個偏移地址，就有可能間接地以訪問某個地址的方式輸出一串符合偽隨機序列要求的數。這就是文中介紹的生成任意長度偽隨機序列方法的核心。

下面結合DSP的硬件實現具體闡述各個步驟。

首先，用DSP程序生成一組特定長度為M的數然后放入內存中，這里的M可以等于2n也可以是任意值。也可以事先在外部文件中寫好需要輸出的一組數然后導入DSP的內存中。根據不同的應用場合，放入內存的這組數可以是0～M-1，也可以是沒有任何規律排列的任意M個數。

其次，根據要求給種子、乘數、加數和模數賦值，調用求余子程序根據線性同余算法公式進行運算，得到一個余數。用得到的余數作為偏移地址，加上已放入內存中序列的首地址也就是基地值，就得到了一個訪問地址。因為剛才的求余操作是對M進行，得到的余數即偏移地址一定＜M，所以按照得到的訪問地址進行尋址，得到的數一定是內存中長度為M的已存序列中的某個數，將這個數輸出。

再次，把上一步已輸出數后面的每個數都向前存放一個地址，這樣內存中的序列首地址不變，序列長度減1。把模數M也減1，以對應新的序列長度。再調用求余子程序，根據線性同余算法公式進行運算，得到又一個余數。然后同樣會得到一個新訪問地址，同樣能輸出內存中長度為M-1的序列中的某個數，將其輸出。

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

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

操作流程，如圖1所示。

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

當外部文件中存有1～M依次排列的M個數時，仿真結果舉例如下:

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

由仿真結果可以看出，文中介紹的方法能靈活產生任意長度的偽隨機序列。

3 結束語

圖1 DSP程序流程

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

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

[2] 章瀲，秦會斌.基于FPGA偽隨機碼發生器的實現[J].電子與封裝，2008，8(2):43-45.

[3] 張瑞華，劉慶華，周德新.偽隨機噪聲產生算法及DSP實現[J].聲學與電子工程，2003(2):22-23.

[4] 賈銀潔，趙麗娟，許鵬飛.擴頻系統中偽隨機碼發生器的實現[J].現代計算機，2008(5):72-73.

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

[6] 馬華，張曉清，張鵬鴿.一種基于線性同余算法的偽隨機數產生器[J].純粹數學與應用數學，2005，21(9):206-207.

[7] 茅以海.頻率捷變雷達[M].北京:國防工業出版社，1981.

[8] 韓建輝.雷達抗干擾中隨機數產生技術分析研究[J].雷達與對抗，2006(1):9-11.

[9] 林象平.雷達對抗原理[M].西安:西北電訊工程學院出版社，1985.

[10]劉書明，羅勇江.ADSPTS20XS系列DSP原理與應用設計[M].北京:電子工業出版社，2007.