在實際應用中, 直接利用DSP產生任意長度偽隨機序列的方法, 可以為系統(tǒng)設計和測試帶來便利。文中
基于線性同余算法, 結合Analo Gdevices公司DSP芯片TigerSHARC20XS的運算結構, 設計出一種利用尋址遞減長度序列, 從而產生具有遍歷性的任意長度偽隨機序列的方法。通過對比, 說明此方法成功解決了傳統(tǒng)方法中, 利用DSP的反饋位移寄存器只能產生2n (1≤n≤32)長度偽隨機序列的問題, 在生成序列的任意長度方面具有一定創(chuàng)新性, 對通信傳輸和雷達變頻抗干擾具有一定的參考價值。
關鍵詞 線性同余算法; 偽隨機數(shù); 任意長度序列; DSP
Genera tion Method about Pseudo Random Sequence of Optiona l Cycle Ba sed on DSP
Abstract In many p rojects, it is a great advantage for designing and debugging systems to generate the p seudo random sequence by DSP. Based on the analysis of the linear congruential generator and TigerSHARC20XS of ANALOGDEV ICES, this paper p resents a method for generating the p seudo random sequence in op tional cycle by ad2 dressing the sequence of descending length. Compared with traditionalmethods, the new method, which is innova2 tive in op tional cycle, solves the p roblem that the p seudo random sequence can only be in a fixed cycle of 2n ( 1≤n≤32) using DSP in traditional methods and is of value in the transmission of communication and anti2jamming of the frequency hopp ing radar.
Keywords LCG; p seudo random number; op tional cycle sequence; DSP
隨機數(shù)是雖然具有一定的統(tǒng)計學規(guī)律, 但抽樣值不能事先確定的數(shù)。實際中產生的隨機數(shù)不是絕對隨機數(shù), 而是相對的, 稱為“偽隨機數(shù)” 。偽隨機數(shù)既有隨機數(shù)所具有的優(yōu)良相關性, 又有隨機數(shù)所不具備的規(guī)律性。這兩個特點, 使得以偽隨機數(shù)為基礎的偽隨機信號既易于從干擾信號中被識別和分離出來,又可以方便的產生和重復。因此偽隨機序列在通訊、雷達、導航、測量、密碼、計算機、相關辨識及故障診斷等許多領域中都有著廣泛的應用。
在許多文獻中, 涉及的偽隨機序列產生方法多是基于高級語言的, 較少涉及硬件具體實現(xiàn)問題。已有的一些硬件實現(xiàn)方法, 在FPGA芯片和DSP芯片上都有過應用 。其中在用DSP芯片實現(xiàn)時, 如果要求產生任意長度M (M > 0)的一個偽隨機序列并保證在無重復數(shù)的前提下該序列包含0～M - 1的每一個數(shù),傳統(tǒng)做法無法完成; 只有將生成的序列長度M 限制為2n (1≤n ≤32)時, 才能滿足要求。文中介紹的基于DSP的偽隨機序列產生方法解決了這樣的問題, 可以產生任意長度的偽隨機序列, 對工程應用有一定的現(xiàn)實意義。
1 線性同余算法的基本原理
線性同余算法[ 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 也等于生成的 偽隨機序列的長度, 所有參數(shù)均為整數(shù)。 線性同余算法產生的偽隨機序列在不更換種子的 前提下以M (M = 2n )為周期出現(xiàn)循環(huán), 如果M 不等于 2n , 序列將以
由上面的例子可以看出, 直接運用線性同余算法用硬件產生偽隨機序列在實際工程應用中并不靈活。比如在雷達信號處理中, 為了減小外界對雷達信號接收的干擾, 會要求發(fā)射機和接收機以一定的時間間隔隨機地在一定數(shù)目的頻點上跳頻, 在跳頻過程中不跳完所有規(guī)定的頻點不允許重復。如果一個頻點用一個偽隨機數(shù)來對應, 這就可以等價為一個偽隨機序列問題。顯然, 不能因為傳統(tǒng)方法生成的偽隨機序列長度必須為2n ( 1≤n ≤32) , 而要求發(fā)射機和接收機的跳頻點個數(shù)也設計為2n (1≤n≤32) 。
2 任意長度偽隨機序列產生方法及DSP實現(xiàn)
由上面的舉例可以看出, 在序列長度M ≠2n 的時候, 生成序列中的數(shù)都
下面結合DSP的硬件實現(xiàn)具體闡述各個步驟。首先, 用DSP程序生成一組特定長度為M 的數(shù)然后放入內存中, 這里的M 可以等于2n 也可以是任意值。也可以事先在外部文件中寫好需要輸出的一組數(shù)然后導入DSP的內存中。根據(jù)不同的應用場合,放入內存的這組數(shù)可以是0～M - 1, 也可以是沒有任何規(guī)律排列的任意M 個數(shù)。
其次, 根據(jù)要求給種子、乘數(shù)、加數(shù)和模數(shù)賦值, 調用求余子程序根據(jù)線性同余算法公式進行運算, 得到一個余數(shù)。用得到的余數(shù)作為偏移地址, 加上已放入內存中序列的首地址也就是基地值, 就得到了一個訪問地址。因為剛才的求余操作是對M 進行,得到的余數(shù)即偏移地址一定
再次, 把上一步已輸出數(shù)后面的每個數(shù)都向前存放一個地址, 這樣內存中的序列首地址不變, 序列長度減1。把模數(shù)M 也減1, 以對應新的序列長度。再調用求余子程序, 根據(jù)線性同余算法公式進行運算,得到又一個余數(shù)。然后同樣會得到一個新訪問地址,同樣能輸出內存中長度為M - 1的序列中的某個數(shù),將其輸出。
隨后, 把上一步已輸出數(shù)后面的每個數(shù)再都向前存放一個地址, 這樣內存中的序列首地址還不變, 序列長度再減1, 把模數(shù)M 也再減1。按照剛才闡述的操作步驟重復進行, 直至模數(shù)被減為1, 就會輸出一個符合要求的長度為的偽隨機序列。此時的序列就是任意長度的偽隨機序列。
最后, 如果內存中的數(shù)都被輸出完, 重新導入長度為M 的序列, 并更換種子 , 乘數(shù)和加數(shù)可以更換也可以不更換。然后進入新一輪的偽隨機數(shù)生成,新生成序列中的M 個數(shù)和已生成序列中的M 個數(shù)相比較順序已經被完全打亂。這樣一直重復操作下去,每輸出M 個數(shù)更換一次種子, 就可以生成含有M 個元素的長度為n ×M ( n為正整數(shù))的偽隨機序列。
操作流程, 如圖1所示。
DSP主要匯編程序 。程序中以j19寄存器中所放值為基地值、長度為M (M 為任意值)的一組數(shù)就是得到的長度為M (M 為任意值)的偽隨機序列, 想要得到含有M 個元素的長度為n ×M ( n為正整數(shù))的
偽隨機序列, 只要每隔M 個數(shù)更換種子重新運行程序就可以得到。
當外部文件中存有1～M 依次排列的M 個數(shù)時,仿真結果舉例如下:
當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 結束語
偽隨機序列有著廣泛的應用前景, 在通信傳輸和雷達抗干擾方面尤為重要, 序列長度是影響其應用的關鍵因素。文中討論了偽隨機序列長度和遍歷性的矛盾, 提出了基于DSP芯片具有遍歷性的任意長度偽隨機序列的工程實現(xiàn)方法。給出了對該實現(xiàn)方法具體步驟的分析, DSP程序的仿真結果顯示了該實現(xiàn)方法的正確性和有效性。在應用中可方便地修改程序中各參數(shù), 以滿足各種場合不同的需求。