基于FPGA的高速高斯随机数发生器

陆兴平，许　拔
（国防科学技术大学 电子科学与工程学院湖南 长沙410073）
摘　要：设计了一个基于FPGA的高速、高性能的高斯随机数发生器。首先简要介绍了以前的一些算法并指出其不足之处。然后阐明了本文的算法：对均匀随机数进行高效的变换以生成非常接近高斯分布的随机数，再依据中心极限定理把两个上述随机数相加得到高斯随机数。算法所需的运算只有RAM的读操作与乘法、加法运算。分析了算法的性能并与其他算法做了对比，证明了本文算法的高效性。最后给出了FPGA实现的系统结构，并分析了所需的硬件资源。
关键词：正态分布；随机数发生器；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
高速地产生高斯随机数在仿真领域具有重要意义。通常研究方差为1均值为0的标准正态随 机数的产生方法，其他的正态分布可由标准正态分布经线性变换轻易得到，故“正态分 布”若无特殊声明皆指标准正态分布。已有的大多数高斯随机数产生算法一般适合用高 级语言编制程序实现，难以运用于硬件制作。本文提出一种高速算法，用FPGA实现只需少 量硬件资源。所设计的高斯随机数发生器周期长（大于260），精度高（小 数部分大于10 b），所得的概率密度函数与理想正态分布相比具有非常小的相对误差（4倍 标准差时为1%，3.5倍标准差时为0.1%）。
1已有的算法
Brien等的方法［1］基于逆变换法。令F(x)为正态分布的累积分布函数，F- 1(x)为F(x)的反函数。首先，产生［0,1］上的均匀随机数U,则X=F-1(U)为正态随机数［1］。Brien等把［0,1］区间用N b均匀量化，计算离散化后的F-1(x)，如图1所示。把2N个函数值存于RAM中。用线性反馈移存器产生N b的 RAM地址作为均匀随机数U。此法只需RAM的读操作，特别简单。硬件资源只需1块RAM，1个控制方差的乘法器（这是高斯随机数发生器必需的），1个线性反馈移存器。输出速度主要决定于乘法器。缺点是由于采用均匀量化，大随机数（|X|≥3）不易得到（除非大幅度地提高量化精度，从而指数地增加RAM容量）。而大的随机数 在仿真中虽然出现的概率很小但往往很重要。

Jeanluc Danger等改善了Brien等的方法，其方法基于如下BoxMuller法［3］：产生［0,1］上的均匀随机数U1,U2；再做如下变换：

X即服从正态分布。利用g的对称性，计算g在［0,025］上的均匀采样存于RAM中。把U1非均 匀量化，f的各点采样存于RAM中。对U1的量化方法如下：把［0,1］首先均匀分为S（S=16）段；再把第一段［0,1/16］均分为S段；如此共进行K次分割，如图2所示（为简化S=4）。

此法得到了大的随机数，但量化仍比较粗糙。所以Jean-luc Danger等依据中心极 限定理把 4个这样产生的“类似高斯”的随机数相加产生1个高斯数。产生的高斯数性能良好。此法 产生一个“类高斯数”需要较多块数的RAM（6块），1个乘法器，1个方差变换乘法器。如 要产生并行4路的“类高斯数”，则所需资源相当可观（低门数的FPGA提供不了如此多块的 Block RAM）。如仅产生1路的“类高斯数”，再用累加器累积4个串行“类高斯数”，则 输出速度将降为1/4。不管何种情况，非均匀量化导致RAM寻址困难，这将制约速度的进一步 提高。
Byungyang Ahn的方法基于中心极限定理［4］。通常多个［0,1］上的独立均匀数 叠加可近 似正态分布。由于均匀分布“不太像”高斯分布，故大量的均匀数叠加才能较好地近似正态 分布，尤其是对正态分布尾部的近似要求较高时［3］。为减少所需均匀数的个数， 先把均匀数 通过简单PDF变换，得到比较接近正态分布的随机数，再把数个变换后的随机数叠加以接近 高斯分布。其PDF变换如图3所示，硬件实现非常容易。此法需八路独立的均匀数，多个加法 器、功率变换的乘法器。当伪均匀数有高的量化精度和长的周期时，此法将耗费大量的FPGA 的CLB资源用于产生均匀数。

2本文的算法
本文的思想也是先进行PDF的变换，再叠加产生高斯数。为最大限度地减少所需均匀数的 个数，把均匀数变得非常接近高斯分布。采用图4所示的变换方法，先把正态密度函数曲 线下方的面积（为1）等分为K份，每份面积是1/K（图中均分为4份）。从而每份都是一 个曲边梯形。对每个曲边梯形，再用一个面积与之相等（1/K）、高与之相等的矩形近似他。

则正态分布可表为：

其中：Vi(x)是形状为曲边梯形的概率密度。
此矩形函数的和构成的阶梯函数也是一个概率密度，他是不同区间上的均匀PDF的叠加，即：

其中：ai是相应矩形的端点。
显然当K足够大时，阶梯的概率密度G(x)将十分接近正态密度。从图5可见，这样的PDF变换把A区间对应的随机点转为与其非常接近的B区间内的点。通常情况下，A区间中的点与B区间中的点并无多少区别，因为他们的值（幅度）相差无几。尤其是大幅度时，不管X＝5σ还是X＝6σ，只要随机数发生器能按概率P=P(X>4σ)产生［4σ，∞］中的一些数即可。由于这样的PDF变换保持了大随机数的产生概率，故他对近似正态分布的尾部是有利的。而依据中心极限定理叠加均匀数的做法不能保证按概率P= P(X>4σ)产生［4σ，∞］中的大随机数。
上述的分割近似过程用Matlab进行。预先准备完成后，产生服从G(x)分布的随机数很方便 ：

(1）产生一个小于等于K的均匀分布的随机自然数I。
(2）产生一个［-1,1］上的均匀数U。
(3）X=aIU，则X服从G分布。
由于G分布的不连续，考虑把M个服从G分布的独立随机数叠加，对G进行卷积平滑以取得 性能更好的高斯随机数。K与M的取值需综合考虑算法的近似性能与硬件结构特性。希望 M＝2，因为增加K仅仅增加了单块RAM的存入字数，但增加M却增加了所需Block RAM的块数与乘法器的数目（这将浪费FPGA的资源）。
最终输出的PDF为：

3算法的性能
首先分析不同K时G(x)对正态分布的逼近效果。采用Byungyang Ahn文中定义的性能参 数概率密度函数的均方差：

计算了K=2i(i=1，2，…，10) 的近似效果。如图6所示。可见K=210时的性能已经优于Byungyang Ahn的最终结果（8个“类高斯数”叠加）。
由于均方差不能反映对正态分布各点的近似效果，再采用Jeanluc Dange的指标 来计算概率密度的相对误差：

在K=210时计算了上述指标函数，如图7所示。性能已经优于Jeanlu c Danger把二个“类高斯数”相加得到的高斯数的性能。


在要求较低的场合，G的性能已经可以了。当然还可以增加K取得更好的效果。这里从另一途径提高性能：把2个G分布的类高斯数相加。这样G与自身卷积得到了平滑的H。最终H的近似性能如图8所示。

图中还做出了K等于其他值（M=2）时的性能曲线。可见增加K具有非常好的逼近效果。
4算法的FPGA实现
选用Xilinx公司Virtex2 FPGA系列的xc2v404芯片。FPGA内部布局如图9所示。

2块Block RAM内容相同，都存有1 024个18 b矩形端点；2路随机自然数皆为10 b，各用一个32级的特征多项式为本原多项式的不同线性反馈移存器产生，故其周期都是232 -1；一路［-1,1］上的均匀数采用18 b量化，用31级的特征多项式为本原多项式的线性反馈移存器产生，其周期为231-1是一素数(本应产生2路独立均匀数，但由于2路地址是独立的，故即便共用一路均匀数，2路“类高斯数”也是独立的)。乘法器使用FPGA内部自带的硬核乘法器。加法器由IPcore生成。功率控制字从外部输入，为18 b。加乘运算都是有符号数的运算。
最终输出的高斯数为18 b，周期为（231-1）×（232-1）。输出速率主要由硬核乘法器的速度决定。单路串行的输出可达95 MHz。如降低量化精度或并行多路，速度还能提高。
5结语
本文提出的算法能产生性能优良的高斯随机数，非常适合硬件实现，占用硬件资源很少。达到了很高的高斯随机数输出速度。
参考文献
［1］Brien.A High Speed Digital Noise GeneratorSoutheastcon′81［M］.Conference Proceedings1981.
［2］［美］艾弗列尔.模拟系统的建模与分析［M］.惠益民.译.北京：清华大学出版社，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.
现代电子技术