Tausworthe 非相關(guān)均勻隨機(jī)數(shù)的簡單生成方法*

張志軍，王衛(wèi)鋒，呂豐東，段新濤

(1.河南師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 新鄉(xiāng) 453007;2.智慧商務(wù)與物聯(lián)網(wǎng)技術(shù)河南省工程實(shí)驗(yàn)室，河南 新鄉(xiāng) 453007;3.新鄉(xiāng)學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，河南 新鄉(xiāng) 453000;4.河南師范大學(xué) 物理與信息工程學(xué)院，河南 新鄉(xiāng) 453007)

1 引言

均勻隨機(jī)數(shù)是產(chǎn)生其他分布隨機(jī)數(shù)的基礎(chǔ)，例如兩個相互獨(dú)立、取值于(0，1)區(qū)間的均勻隨機(jī)數(shù)對，經(jīng)Box－Muller 變換［1－2］可得到一對相互獨(dú)立的正態(tài)分布隨機(jī)數(shù)。Tausworthe 均勻隨機(jī)數(shù)(Tausworthe Uniform Random Numbers，TURN)序列亦稱為線性反饋移位寄存器(Linear Feedback Shift Register，LFSR)序列，由于其硬件易實(shí)現(xiàn)且所需硬件資源最少，被廣泛用于硬件實(shí)現(xiàn)正態(tài)分布隨機(jī)數(shù)［3－4］的通信系統(tǒng)蒙特卡洛仿真實(shí)驗(yàn)中。

應(yīng)用于高速通信系統(tǒng)性能硬件蒙特卡洛仿真實(shí)驗(yàn)中的TURN 序列生成器，采用的均為和同步脈沖速度一致的并行輸出結(jié)構(gòu)［3－4］。針對并行輸出相繼TURN 間強(qiáng)相關(guān)性的問題，研究人員提出了組合Tausworthe 結(jié)構(gòu)［5－6］和一步多跳算法［7－8］等改進(jìn)算法，這些改進(jìn)方法均以犧牲硬件資源為代價，并且均未考慮同步產(chǎn)生相互獨(dú)立均勻隨機(jī)數(shù)對的問題。

本文提出了一個利用不同輸出樣式以消除相繼TURN 間強(qiáng)相關(guān)性的方法，在不增添寄存器個數(shù)情形下，同時采取不同的、經(jīng)優(yōu)化的輸出生成矩陣，可并行輸出與時鐘脈沖速度一致的、能滿足蒙特卡洛實(shí)驗(yàn)質(zhì)量要求的非相關(guān)TURN 序列對。

2 TURN 序列并行輸出結(jié)構(gòu)

TURN 序列生成器基于本原多項(xiàng)式與模2 運(yùn)算(記為⊕)，例如本原多項(xiàng)式為

則對應(yīng)的LFSR 序列發(fā)生器為

式中，系數(shù)ck∈{0，1}(k=n－1，n－2，…，0)被稱為反饋抽頭系數(shù)，［cn－1，cn－2，…，c0］是一組不全為0的n 維向量，ck為1 表示LFSR 中第k個寄存器的輸出參與反饋有鏈接，否則無鏈接。Tausworthe 指出［9］，若將上述相繼m個隨機(jī)數(shù)作為m 位二進(jìn)制小數(shù)0.XiXi+1… Xi+m－1，則此數(shù)可看成區(qū)間(0，1)上的均勻隨機(jī)數(shù)，故將此序列稱為TURN 序列。顯然，經(jīng)典串行輸出TURN 序列的生成速度為LFSR 同步時鐘脈沖的1/m。

并行輸出結(jié)構(gòu)可提高TURN 的生成速度，其結(jié)構(gòu)如圖1 虛線所圍部分。設(shè)Xt=為兩個相繼TURN 的m 位量化并行輸出序列，顯然，隨機(jī)數(shù)Xt+1序列的和隨機(jī)數(shù)Xt序列的是完全一致的，因此，并行輸出時，相繼TURN 序列間有較強(qiáng)的相關(guān)性。圖2 給出了生成本原多項(xiàng)式為X52+X3+1［10］，并行輸出16 量化比特TURN 序列的樣本協(xié)方差與功率譜密度曲線。理想均勻隨機(jī)數(shù)序列的協(xié)方差函數(shù)是δ 函數(shù)，與之相比，TURN 序列至少有±6 位位移延伸。同時，該均勻隨機(jī)數(shù)序列的功率譜密度中出現(xiàn)不期望的低通特性。

圖1 TURN 序列m 比特量化的并行輸出結(jié)構(gòu)框圖Fig.1 Block diagram of TURN with parallel output structure

圖2 容量為107并行輸出TUＲN序列的樣本協(xié)方差曲線和功率譜密度圖Fig.2 Covariance curve and power spectral density charts for 107 parallel quantified output TURNs

3 TRUN 序列并行輸出生成矩陣及其優(yōu)化

TURN 序列生成器中反饋電路由生成本原多項(xiàng)式完全決定，所生成序列的周期為2n－1，n 為LFSR的階數(shù)。在應(yīng)用TURN 序列時，希望其周期趨于無窮大，也就是說，LFSR 的階數(shù)n 遠(yuǎn)大于并行量化比特位數(shù)m。因此，每一量化比特ri可由多個寄存器的狀態(tài)共同決定，這一關(guān)系可用輸出生成向量gi表示:

上述加法是模2 加，gi，j∈{0，1}(j=n－1，n－2，…，0)稱為生成抽頭系數(shù)，生成向量gi=［gi，n－1gi，n－2… gi，0］中的gi，j不全為零。設(shè)向量重量函數(shù)w(gi)表示向量gi中1 的個數(shù)。由于gi，j取值為二進(jìn)制數(shù)，在下面描述中向量gi用八進(jìn)制數(shù)表示，例如gi=(15)，則該生成向量為［1 1 0 1］，w(gi)=4。改進(jìn)后的TURN 序列并行量化輸出結(jié)構(gòu)的位置在圖1中以線性輸出電路G 示意出。

對于m 位量化輸出構(gòu)成的向量r=［rm－1rm－2…r0］，可由生成向量所構(gòu)成輸出生成矩陣表示:

經(jīng)典TURN 序列m 比特位并行輸出時，所對應(yīng)的輸出生成矩陣是稀疏的，其輸出生成矩陣為

式中，Im×m為m 階單位矩陣，當(dāng)量化輸出比特位數(shù)m等于LFSR 的階數(shù)n 時，G'退化為n 階單位矩陣。顯然，不同生成矩陣G 生成不同的TURN 序列，因此，非相關(guān)TURN 序列并行輸出電路結(jié)構(gòu)的設(shè)計(jì)優(yōu)化問題可轉(zhuǎn)化成對輸出生成矩陣G 的優(yōu)化問題。

硬件資源的高效利用是TURN 序列生成器設(shè)計(jì)優(yōu)化的目標(biāo)之一，即在隨機(jī)數(shù)質(zhì)量不下降前提下，以生成矩陣G 中1 的個數(shù)盡可能少為優(yōu)化目標(biāo)，即

對式(4)中的生成矩陣G 采用差分進(jìn)化算法［11］進(jìn)行優(yōu)化。表1 給出了兩組生成矩陣G 的優(yōu)化參數(shù)，其生成本原多項(xiàng)式為X52+X3+1，TURN 序列16 量化位。

表1 生成矩陣G 的兩組優(yōu)化參數(shù)Table 1 Optimized parameters of two generator matrices

4 實(shí)驗(yàn)結(jié)果分析與隨機(jī)數(shù)質(zhì)量檢驗(yàn)

圖3 給出了生成矩陣為G1、容量為107改進(jìn)TURN 序列的樣本協(xié)方差曲線和功率譜密度。與圖2 對比可得，利用本文所提生成方法，采用優(yōu)化的生成矩陣所生成的TURN 序列相繼值間呈現(xiàn)非常理想的低相關(guān)性，同時功率譜的低通效應(yīng)也隨即消失。

圖3 生成矩陣G1所生成的容量為107改進(jìn)的TURN 樣本協(xié)方差曲線和功率譜密度圖Fig.3 Covariance curve and power spectral density charts for 107 TURNs with optimized output generator matrix G1

4.1 χ2 擬合優(yōu)度檢驗(yàn)

擬合優(yōu)度檢驗(yàn)是一種檢驗(yàn)樣本數(shù)據(jù)是否服從某一分布的方法。隨機(jī)數(shù)質(zhì)量檢驗(yàn)中，χ2擬合優(yōu)度檢驗(yàn)［11］是最常用的方法，其檢驗(yàn)統(tǒng)計(jì)量為

檢驗(yàn)時，樣本被分割成k個區(qū)間，Xi為樣本數(shù)據(jù)落入?yún)^(qū)間((i－1)/k，i/k)內(nèi)的觀測個數(shù)，i=1，2，…，k;Ei為落入該區(qū)間待檢驗(yàn)分布的期望觀測值，對于容量為N 的樣本，該值為Npi，pi為待檢驗(yàn)變量落入?yún)^(qū)間((i－1)/k，i/k)內(nèi)的概率，對于均勻分布假設(shè)，pi=1/k。

圖4 給出了生成矩陣G1所生成容量為106和107改進(jìn)TURN 序列的樣本直方圖，其中k=50，在顯著水平α 為0.05 和0.01 下的拒絕域分別為［66.34，+∞)和［74.90，+∞)。

圖4 生成矩陣G1所生成容量為106和107的改進(jìn)TURN樣本直方圖，檢驗(yàn)P－值分別為0.913 5 和0.643 6Fig.4 Sample histograms with P－value 0.913 5 and 0.643 6 for 106 and 107 TURNs with optimized output generator matrix G1

表2 給出了生成矩陣G1和G2在不同容量下樣本檢驗(yàn)統(tǒng)計(jì)量t 值及檢驗(yàn)的P－值［11］。從表2 可以看出，生成矩陣為G1和G2、容量分別為106和107改進(jìn)TURN 序列樣本檢驗(yàn)統(tǒng)計(jì)量t 值均未落入拒絕域，表明均通過χ2擬合優(yōu)度檢驗(yàn)，即生成矩陣G1和G2所生成的樣本均可認(rèn)為是(0，1)區(qū)間內(nèi)的均勻隨機(jī)數(shù)。表2 同時給出了Matlab 軟件和ANSI C 標(biāo)準(zhǔn)中，常用均勻隨機(jī)函數(shù)rand()所生成同容量下均勻隨機(jī)數(shù)的統(tǒng)計(jì)量t 值和對應(yīng)的P－值，對比可得，利用優(yōu)化輸出生成矩陣所生成的改進(jìn)TURN 序列完全可以取代上述兩個軟件應(yīng)用于通信系統(tǒng)性能的硬件蒙特卡洛仿真實(shí)驗(yàn)中。

表2 均勻隨機(jī)數(shù)的樣本檢驗(yàn)統(tǒng)計(jì)量t 值和對應(yīng)P－值Table 2 Test statistic and P－ values for different samples

4.2 獨(dú)立性檢驗(yàn)

滿足Box－Muller 變換服從(0，1)區(qū)間上的均勻隨機(jī)數(shù)對必須不相關(guān)，因此，需對所提方案中由不同生成矩陣生成的TURN 序列對進(jìn)行相關(guān)性檢測。本文采用樣本相關(guān)系數(shù)進(jìn)行度量檢測，其定義為［11］

相關(guān)系數(shù)值越小表明隨機(jī)數(shù)對越不相關(guān)。從表3 可得，與常用軟件生成的均勻隨機(jī)數(shù)對相比，優(yōu)化的生成矩陣G1和G2所生成的均勻隨機(jī)數(shù)對間完全可以滿足非相關(guān)性的要求。

表3 不同容量下各算法生成均勻隨機(jī)數(shù)對的相關(guān)系數(shù)Table 3 Correlation coefficients for pairs of uniform random numbers generated by different algorithms

利用組合Tausworthe 結(jié)構(gòu)和一步多跳算法生成相互獨(dú)立的TURN 序列對時，是基于多個同結(jié)構(gòu)、不同初始寄存器狀態(tài)的TURN 序列生成器并行輸出的。與之相比，表3 中改進(jìn)的TURN 序列對是在不增添寄存器個數(shù)前提下，通過配置不同優(yōu)化的輸出生成矩陣所生成的。表4 給出了上述3 種優(yōu)化算法生成2個相互獨(dú)立的Tausworthe 均勻隨機(jī)數(shù)時，對應(yīng)的隨機(jī)數(shù)生成器在Altera Cyclone FPGA 上硬件結(jié)果，生成的本原多項(xiàng)式為X52+X3+1，并行16 比特量化位。從表4 可得，利用本文不同優(yōu)化輸出矩陣生成均勻隨機(jī)數(shù)對時，所需的硬件資源僅為組合Tausworthe 結(jié)構(gòu)和一步多跳算法的27.4% 和48.8%，硬件資源的利用效率大大提高，該優(yōu)勢隨著輸出非相關(guān)TURN 序列個數(shù)的增多而更趨顯著。

表4 各優(yōu)化算法生成2個非相關(guān)TURN 序列所需硬件資源類型(EP1C6Q240)Table 4 Resources to generate two uncorrelated TURNs for different algorithms

5 結(jié)束語

數(shù)字通信系統(tǒng)性能仿真實(shí)驗(yàn)時，均勻隨機(jī)數(shù)序列常用于模擬數(shù)字信號源和噪聲。加性高斯白噪聲信道中服從高斯分布的噪聲，通常由獨(dú)立的均勻隨機(jī)數(shù)序列對經(jīng)變換得到。本文針對經(jīng)典TURN 序列并行輸出時相繼值間呈現(xiàn)較大相關(guān)性問題，在應(yīng)用高周期的TURN 序列生成器中寄存器個數(shù)大大增加情形下，提出了一種新的非相關(guān)TURN 序列生成方法。該方法中每位輸出量化比特均由多個寄存器的狀態(tài)共同決定，從而將生成TURN 序列問題等價為輸出生成矩陣的優(yōu)化問題。在需要同時輸出多個TURN 序列的硬件仿真實(shí)驗(yàn)中，與組合Tausworthe結(jié)構(gòu)和一步多跳優(yōu)化方法基于多個同結(jié)構(gòu)、不同初始寄存器狀態(tài)的TURN 序列生成器并行輸出相比，采用本文所提方法可以根據(jù)優(yōu)化的輸出生成矩陣快速配置輸出完成，不需要對電路中的反饋電路等其他結(jié)構(gòu)部分進(jìn)行重新設(shè)計(jì)，相應(yīng)的電路僅需增加輸出所需的連線和模2 加電路，大大提高了硬件資源的利用率，這是區(qū)別于其他TURN 序列優(yōu)化方法最主要的地方。將本文改進(jìn)的TURN 序列應(yīng)用于高斯信道、衰落信道等場景下通信系統(tǒng)性能硬件蒙特卡洛實(shí)驗(yàn)中，是后續(xù)需要進(jìn)一步研究的內(nèi)容。

［1］Malik J S，Hemani A，Malik J N，et al.Revisiting Central Limit Theorem:Accurate Gaussian Random Number Generation in VLSI［J］.IEEE Transactions on VLSI Systems，2014，23(5):842－855.

［2］張志軍，劉行兵，段新濤.高斯隨機(jī)數(shù)生成算法對比研究［J］.河南科技學(xué)院學(xué)報(自科版)，2014，42(3):56－59.ZHANG Zhijun，LIU Xingbing，DUAN Xintao.Algorithm comparison on Gaussian random number generators［J］.Journal of Henan Institute of Science and Technology(Natural Sciences Edition)，2014，42 (3):56－ 59.(in Chinese)

［3］Alimohammad A，F(xiàn)ard S F.FPGA－based bit error rate performance measurement of wireless systems［J］.IEEE Transactions on VLSI Systems，2014，22(7):1583－1592.

［4］Yen S W，Hung S Y，Chen C L，et al.A 5.79－Gb/s energy－efficient multirate LDPC codec chip for IEEE 802.15.3c applications［J］.IEEE Journal of Solid－State Circuits，2012，47(9):2246－2257.

［5］L'ecuyer P.Maximally equidistributed combined Tausworthe generators［J］.Mathematics of Computation of the American Mathematical Society，1996，65(213):203－213.

［6］谷曉忱，張民選.多輸出LFSR 結(jié)構(gòu)均勻分布偽隨機(jī)數(shù)生成器的硬件設(shè)計(jì)優(yōu)化［J］.武漢大學(xué)學(xué)報(信息科學(xué)版)，2010，35(5):566－ 569.GU Xiaochen，ZHANG Minxuan.Mult－ ioutput LFSR Based Uniform Pseudo Random Number Generator［J］.Geomatics and Information Science of Wuhan University，2010，35(5):566－ 569.(in Chinese)

［7］Li Y，Chow P，Jiang J，et al.Software/Hardware Parallel Long－ Period Random Number Generation Framework Based on the WELL Method［J］.IEEE Transactions on VLSI Systems，2014，22(5):1054－1059.

［8］Lu Q，F(xiàn)an J，Sham C，et al.A high throughput Gaussian noise generator［C］// Proceedings of 2014 IEEE Asia Pacific Conference on Circuits and Systems.Ishigaki:IEEE，2014:117－120.

［9］Tausworthe R C.Random numbers generated by linear recurrence modulo two［J］.Mathematics of Computation，1965，19(90):201－209.

［10］劉玉君.信道編碼［M］.修訂版.鄭州:河南科學(xué)技術(shù)出版社，2001:30－31.LIU Yujun.Channel Coding［M］.revised ed.Zhengzhou:Henan Science and Technology Press，2001:30－31.(in Chinese)

［11］Kroese D P，Taimre T，Botev Z I.Handbook of Monte Carlo Methods［M］.New York:John Wiley ＆ Sons，2013:301－345.