基于FPGA的高速高斯隨機(jī)數(shù)發(fā)生器

陸興平，許　拔

（國(guó)防科學(xué)技術(shù)大學(xué) 電子科學(xué)與工程學(xué)院湖南 長(zhǎng)沙410073）

　　摘　要：設(shè)計(jì)了一個(gè)基于FPGA的高速、高性能的高斯隨機(jī)數(shù)發(fā)生器。首先簡(jiǎn)要介紹了以前的一些算法并指出其不足之處。然后闡明了本文的算法：對(duì)均勻隨機(jī)數(shù)進(jìn)行高效的變換以生成非常接近高斯分布的隨機(jī)數(shù)，再依據(jù)中心極限定理把兩個(gè)上述隨機(jī)數(shù)相加得到高斯隨機(jī)數(shù)。算法所需的運(yùn)算只有RAM的讀操作與乘法、加法運(yùn)算。分析了算法的性能并與其他算法做了對(duì)比，證明了本文算法的高效性。最后給出了FPGA實(shí)現(xiàn)的系統(tǒng)結(jié)構(gòu)，并分析了所需的硬件資源。
　　關(guān)鍵詞：正態(tài)分布；隨機(jī)數(shù)發(fā)生器；FPGA；RAM

Highspeed Gaussian Random Number Generator Impl emented with FPGA

LU Xingping，XU Ba

(College of Electronic Science and Engineering, National University of Defense
Technology, Changsha, 410073, China)

　　Abstract：A highspeed gaussian random number generator implemented with FPGA is pr esented in this paperSeveral algorithms are briefly introduced and their sh ortcomings are pointed outThen algorithm is presented: firstly,uniformly distributed random numbers are effectively transformed to "GaussianLike" numbers,secondly,based on central limit theorem,each two of such "Gau ssianLike"numbers are added together to generate a gaussian sampleA ll the operations needed are addition,multiplication and RAM readingThe perfo rmance of the generator is excellent compared with othersFinally the system s tructure in FPGA is given
　　Keywords：norm distribution;random number generator;FPGA;RAM

　　高速地產(chǎn)生高斯隨機(jī)數(shù)在仿真領(lǐng)域具有重要意義。通常研究方差為1均值為0的標(biāo)準(zhǔn)正態(tài)隨 機(jī)數(shù)的產(chǎn)生方法，其他的正態(tài)分布可由標(biāo)準(zhǔn)正態(tài)分布經(jīng)線性變換輕易得到，故“正態(tài)分 布”若無(wú)特殊聲明皆指標(biāo)準(zhǔn)正態(tài)分布。已有的大多數(shù)高斯隨機(jī)數(shù)產(chǎn)生算法一般適合用高 級(jí)語(yǔ)言編制程序?qū)崿F(xiàn)，難以運(yùn)用于硬件制作。本文提出一種高速算法，用FPGA實(shí)現(xiàn)只需少 量硬件資源。所設(shè)計(jì)的高斯隨機(jī)數(shù)發(fā)生器周期長(zhǎng)（大于2⁶⁰），精度高（小 數(shù)部分大于10 b），所得的概率密度函數(shù)與理想正態(tài)分布相比具有非常小的相對(duì)誤差（4倍 標(biāo)準(zhǔn)差時(shí)為1%，3.5倍標(biāo)準(zhǔn)差時(shí)為0.1%）。

1已有的算法
　　Brien等的方法［1］基于逆變換法。令F(x)為正態(tài)分布的累積分布函數(shù)，F^{- 1}(x)為F(x)的反函數(shù)。首先，產(chǎn)生［0,1］上的均勻隨機(jī)數(shù)U,則X=F^-1(U)為正態(tài)隨機(jī)數(shù)［1］。Brien等把［0,1］區(qū)間用N b均勻量化，計(jì)算離散化后的F^-1(x)，如圖1所示。把2N個(gè)函數(shù)值存于RAM中。用線性反饋移存器產(chǎn)生N b的 RAM地址作為均勻隨機(jī)數(shù)U。此法只需RAM的讀操作，特別簡(jiǎn)單。硬件資源只需1塊RAM，1個(gè)控制方差的乘法器（這是高斯隨機(jī)數(shù)發(fā)生器必需的），1個(gè)線性反饋移存器。輸出速度主要決定于乘法器。缺點(diǎn)是由于采用均勻量化，大隨機(jī)數(shù)（|X|≥3）不易得到（除非大幅度地提高量化精度，從而指數(shù)地增加RAM容量）。而大的隨機(jī)數(shù) 在仿真中雖然出現(xiàn)的概率很小但往往很重要。

　　Jeanluc Danger等改善了Brien等的方法，其方法基于如下BoxMuller法［3］：產(chǎn)生［0,1］上的均勻隨機(jī)數(shù)U1,U2；再做如下變換：
　　
X即服從正態(tài)分布。利用g的對(duì)稱性，計(jì)算g在［0,025］上的均勻采樣存于RAM中。把U1非均 勻量化，f的各點(diǎn)采樣存于RAM中。對(duì)U1的量化方法如下：把［0,1］首先均勻分為S（S=16）段；再把第一段［0,1/16］均分為S段；如此共進(jìn)行K次分割，如圖2所示（為簡(jiǎn)化S=4）。



　　此法得到了大的隨機(jī)數(shù)，但量化仍比較粗糙。所以Jean-luc Danger等依據(jù)中心極 限定理把 4個(gè)這樣產(chǎn)生的“類似高斯”的隨機(jī)數(shù)相加產(chǎn)生1個(gè)高斯數(shù)。產(chǎn)生的高斯數(shù)性能良好。此法 產(chǎn)生一個(gè)“類高斯數(shù)”需要較多塊數(shù)的RAM（6塊），1個(gè)乘法器，1個(gè)方差變換乘法器。如 要產(chǎn)生并行4路的“類高斯數(shù)”，則所需資源相當(dāng)可觀（低門數(shù)的FPGA提供不了如此多塊的 Block RAM）。如僅產(chǎn)生1路的“類高斯數(shù)”，再用累加器累積4個(gè)串行“類高斯數(shù)”，則 輸出速度將降為1/4。不管何種情況，非均勻量化導(dǎo)致RAM尋址困難，這將制約速度的進(jìn)一步 提高。
　　Byungyang Ahn的方法基于中心極限定理［4］。通常多個(gè)［0,1］上的獨(dú)立均勻數(shù) 疊加可近 似正態(tài)分布。由于均勻分布“不太像”高斯分布，故大量的均勻數(shù)疊加才能較好地近似正態(tài) 分布，尤其是對(duì)正態(tài)分布尾部的近似要求較高時(shí)［3］。為減少所需均勻數(shù)的個(gè)數(shù)， 先把均勻數(shù) 通過(guò)簡(jiǎn)單PDF變換，得到比較接近正態(tài)分布的隨機(jī)數(shù)，再把數(shù)個(gè)變換后的隨機(jī)數(shù)疊加以接近 高斯分布。其PDF變換如圖3所示，硬件實(shí)現(xiàn)非常容易。此法需八路獨(dú)立的均勻數(shù)，多個(gè)加法 器、功率變換的乘法器。當(dāng)偽均勻數(shù)有高的量化精度和長(zhǎng)的周期時(shí)，此法將耗費(fèi)大量的FPGA 的CLB資源用于產(chǎn)生均勻數(shù)。  

2本文的算法
　　本文的思想也是先進(jìn)行PDF的變換，再疊加產(chǎn)生高斯數(shù)。為最大限度地減少所需均勻數(shù)的 個(gè)數(shù)，把均勻數(shù)變得非常接近高斯分布。采用圖4所示的變換方法，先把正態(tài)密度函數(shù)曲 線下方的面積（為1）等分為K份，每份面積是1/K（圖中均分為4份）。從而每份都是一 個(gè)曲邊梯形。對(duì)每個(gè)曲邊梯形，再用一個(gè)面積與之相等（1/K）、高與之相等的矩形近似他。

　　則正態(tài)分布可表為：
　　
其中：V_i(x)是形狀為曲邊梯形的概率密度。
　　此矩形函數(shù)的和構(gòu)成的階梯函數(shù)也是一個(gè)概率密度，他是不同區(qū)間上的均勻PDF的疊加，即：
　　
其中：ai是相應(yīng)矩形的端點(diǎn)。
　　顯然當(dāng)K足夠大時(shí)，階梯的概率密度G(x)將十分接近正態(tài)密度。從圖5可見，這樣的PDF變換把A區(qū)間對(duì)應(yīng)的隨機(jī)點(diǎn)轉(zhuǎn)為與其非常接近的B區(qū)間內(nèi)的點(diǎn)。通常情況下，A區(qū)間中的點(diǎn)與B區(qū)間中的點(diǎn)并無(wú)多少區(qū)別，因?yàn)樗麄兊闹担ǚ龋┫嗖顭o(wú)幾。尤其是大幅度時(shí)，不管X＝5σ還是X＝6σ，只要隨機(jī)數(shù)發(fā)生器能按概率P=P(X>4σ)產(chǎn)生［4σ，∞］中的一些數(shù)即可。由于這樣的PDF變換保持了大隨機(jī)數(shù)的產(chǎn)生概率，故他對(duì)近似正態(tài)分布的尾部是有利的。而依據(jù)中心極限定理疊加均勻數(shù)的做法不能保證按概率P= P(X>4σ)產(chǎn)生［4σ，∞］中的大隨機(jī)數(shù)。
　　上述的分割近似過(guò)程用Matlab進(jìn)行。預(yù)先準(zhǔn)備完成后，產(chǎn)生服從G(x)分布的隨機(jī)數(shù)很方便 ：

　　(1）產(chǎn)生一個(gè)小于等于K的均勻分布的隨機(jī)自然數(shù)I。
　　(2）產(chǎn)生一個(gè)［-1,1］上的均勻數(shù)U。
　　(3）X=a_IU，則X服從G分布。
　　由于G分布的不連續(xù)，考慮把M個(gè)服從G分布的獨(dú)立隨機(jī)數(shù)疊加，對(duì)G進(jìn)行卷積平滑以取得 性能更好的高斯隨機(jī)數(shù)。K與M的取值需綜合考慮算法的近似性能與硬件結(jié)構(gòu)特性。希望 M＝2，因?yàn)樵黾?/span>K僅僅增加了單塊RAM的存入字?jǐn)?shù)，但增加M卻增加了所需Block RAM的塊數(shù)與乘法器的數(shù)目（這將浪費(fèi)FPGA的資源）。
　　最終輸出的PDF為：
　　

3算法的性能
　　首先分析不同K時(shí)G(x)對(duì)正態(tài)分布的逼近效果。采用Byungyang Ahn文中定義的性能參 數(shù)概率密度函數(shù)的均方差：
　　
計(jì)算了K=2ⁱ(i=1，2，…，10) 的近似效果。如圖6所示?？梢?/span>K=2¹⁰時(shí)的性能已經(jīng)優(yōu)于Byungyang Ahn的最終結(jié)果（8個(gè)“類高斯數(shù)”疊加）。
　　由于均方差不能反映對(duì)正態(tài)分布各點(diǎn)的近似效果，再采用Jeanluc Dange的指標(biāo) 來(lái)計(jì)算概率密度的相對(duì)誤差：
　　
　　在K=2¹⁰時(shí)計(jì)算了上述指標(biāo)函數(shù)，如圖7所示。性能已經(jīng)優(yōu)于Jeanlu c Danger把二個(gè)“類高斯數(shù)”相加得到的高斯數(shù)的性能。

　　在要求較低的場(chǎng)合，G的性能已經(jīng)可以了。當(dāng)然還可以增加K取得更好的效果。這里從另一途徑提高性能：把2個(gè)G分布的類高斯數(shù)相加。這樣G與自身卷積得到了平滑的H。最終H的近似性能如圖8所示。



　　圖中還做出了K等于其他值（M=2）時(shí)的性能曲線?？梢娫黾?/span>K具有非常好的逼近效果。

4算法的FPGA實(shí)現(xiàn)
　　選用Xilinx公司Virtex2 FPGA系列的xc2v404芯片。FPGA內(nèi)部布局如圖9所示。

　　2塊Block RAM內(nèi)容相同，都存有1 024個(gè)18 b矩形端點(diǎn)；2路隨機(jī)自然數(shù)皆為10 b，各用一個(gè)32級(jí)的特征多項(xiàng)式為本原多項(xiàng)式的不同線性反饋移存器產(chǎn)生，故其周期都是2³² -1；一路［-1,1］上的均勻數(shù)采用18 b量化，用31級(jí)的特征多項(xiàng)式為本原多項(xiàng)式的線性反饋移存器產(chǎn)生，其周期為2³¹-1是一素?cái)?shù)(本應(yīng)產(chǎn)生2路獨(dú)立均勻數(shù)，但由于2路地址是獨(dú)立的，故即便共用一路均勻數(shù)，2路“類高斯數(shù)”也是獨(dú)立的)。乘法器使用FPGA內(nèi)部自帶的硬核乘法器。加法器由IPcore生成。功率控制字從外部輸入，為18 b。加乘運(yùn)算都是有符號(hào)數(shù)的運(yùn)算。
　　最終輸出的高斯數(shù)為18 b，周期為（2³¹-1）×（2³²-1）。輸出速率主要由硬核乘法器的速度決定。單路串行的輸出可達(dá)95 MHz。如降低量化精度或并行多路，速度還能提高。

5結(jié)語(yǔ)
　　本文提出的算法能產(chǎn)生性能優(yōu)良的高斯隨機(jī)數(shù)，非常適合硬件實(shí)現(xiàn)，占用硬件資源很少。達(dá)到了很高的高斯隨機(jī)數(shù)輸出速度。

參考文獻(xiàn)

［1］Brien.A High Speed Digital Noise GeneratorSoutheastcon′81［M］.Conference Proceedings1981.
［2］［美］艾弗列爾.模擬系統(tǒng)的建模與分析［M］.惠益民.譯.北京：清華大學(xué)出版社，1 987.
［3］Jeanluc DangerEfficient FPGA Implementation of　 Gaussian Noise Generat or for Communication Channel Emulation 2000［J］.The 7th IEEE Internatio nal Conference on Electronics,Circuits and Systems，2000，12：17-20.
［4］Byungyang AhnA Study on a Highspeed Gaussian Random Number Generator［J］.IEEE Asia Pacific Conference on Circuits and Systems，1996，11：18-21.

現(xiàn)代電子技術(shù)