高斯随机数发生器的研究与设计

论文摘要

高斯随机数序列广泛地运用于通信系统、金融建模、经济学仿真和分子动力学等领域。在通信系统中,经常碰到的噪声之一就是高斯白噪声。通过采用高斯随机数序列对高斯白噪声进行建模,就可以通过仿真来研究通信信道的性能。基于软件实现的高斯随机数发生器的研究已经有悠久的历史,但是基于硬件实现的高斯白噪声发生器的研究比较少。近年来,随着可编程逻辑器件的发展以及硬件仿真工具性能的提高,使得基于硬件实现的高斯随机数发生器有了很好的研究平台。现有基于硬件实现的高斯随机数序列发生器大部分都是基于线性反馈移位寄存器及其简单变形所产生的均匀随机数序列的。可是早在1981年的时候,有学者就指出了线性反馈移位寄存器是最糟糕的均匀随机数发生器,但是大多数人都贪图其实现结构简单,都忽略了这一缺点。本文采用细胞自动机来实现高斯随机数发生器。与线性反馈移位寄存器等其它方法相比,细胞自动机最大优势在于其特有的适合VLSI实现之组成单元的简单规则性、单元之间的局部互连性和信息处理的高度并行性等。实验证明,基于细胞自动机产生的均匀随机数序列在周期相等情况下其硬件实现的性能明显优于基于线性反馈移位寄存器产生的均匀随机数序列。本文先采用细胞自动机代替传统的线性反馈移位寄存器产生高斯随机数序列,然后再结合经典的Box-Muller算法、中心极限定理,产生出较为理想的高斯随机数序列。Matlab仿真表明,其样本均值为0.00421,方差为1.00046。不仅如此,其所产生的高斯随机数序列对于高斯分布尾部的那些序列的产生也是很好的,可以达到7.8σ以上的效果,已接近8.2σ的理论值。本文还进一步改进了细胞自动机的结构,设计实现了基于32单元的可编程细胞自动机以产生高斯随机数序列。通过MATLAB仿真,测得其性能可以达到样本均值为0.02456,方差为1.08941。虽然与理想值还是有一定的差距,但是也比基于LFSR产生的高斯随机序列的性能好。另外,本文基于Wallace算法,提出一种新的有利于Wallace算法实现的硬件结构来产生高斯随机数,此种算法没有涉及到复杂的运算,更有利于硬件的实现。而且试验仿真数据表明,基于Wallace算法实现的高斯随机数发生器所产生的高斯随机数序列不仅所占有的硬件资源是最少的,而且其性能也为最优（与本文提出的基于细胞自动机的高斯随机数发生器相比）,其样本均值为-0.00181,方差为1.0007,已经很接近理想的高斯随机数的统计特性。而本文提出的硬件结构的实现,更优化了Wallace算法关联性较强的内在的缺陷。最后,分别以Xilinx公司的Virtex-2 XC2V4000-6为目标器件,比较了文中的两种高斯随机数发生器的方案的硬件占用资源,相比之下,Wallace算法是最适宜于硬件实现的方法。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 课题研究背景及意义
• 1.2 高斯白噪声发生器的国内外研究现状
• 1.3 本文的研究内容
• 1.4 本文的组织结构
• 第二章 高斯白噪声发生器的算法分析
• 2.1 通信系统中的噪声
• 2.1.1 白噪声
• 2.1.2 高斯型噪声
• 2.1.3 高斯型白噪声
• 2.2 高斯随机数发生器的算法
• 2.2.1 基于累积分布函数的反变换法
• 2.2.2 变换法
• 2.2.2.1 三角分布的分段近似算法
• 2.2.2.2 Monty Python 算法
• 2.2.3 基于拒绝-接收的算法
• 2.2.3.1 Polar 算法
• 2.2.3.2 Marsaglia-Bray Rejection 算法
• 2.2.3.3 Ratio of Uniforms 算法
• 2.2.3.4 Ahrens-Dieter Table-Free 算法
• 2.2.3.5 GRAND 算法
• 2.2.3.6 Ziggurat 算法
• 2.2.4 递归算法
• 2.3 均匀随机序列发生器的建模
• 2.4 本章小结
• 第三章 细胞自动机的理论与研究
• 3.1 细胞自动机的概念
• 3.2 细胞自动机的类型
• 3.2.1 加性细胞自动机
• 3.2.2 线性与非线性细胞自动机
• 3.2.3 循环和非循环细胞自动机
• 3.2.4 单一细胞自动机和混合细胞自动机
• 3.2.5 可编程细胞自动机
• 3.3 90/150 线性细胞自动机
• 3.4 可编程细胞自动机的分析
• 3.5 细胞自动机的综合
• 3.5.1 利用欧几里德最大公约数的算法综合细胞自动机
• 3.5.1.1 除法定理的运用
• 3.5.1.2 细胞自动机的二次方程式
• 3.5.1.3 90/150 细胞自动机的综合算法
• 3.6 细胞自动机的VLSI 实现
• 3.7 细胞自动机生成均匀随机数发生器
• 3.7.1 周期特性
• 3.7.2 随机统计特性
• 3.7.2.1 单比特测试
• 3.7.2.2 扑克测试（Poker）
• 3.7.2.3 游程测试（Run）
• 3.7.2.4 自相关测试
• 3.7.3 线性复杂度
• 3.8 细胞自动机和线性反馈移位寄存器的FPGA 实现比较
• 3.8.1 细胞自动机的 FPGA 实现
• 3.8.1.1 功能仿真
• 3.8.1.2 综合仿真
• 3.8.2 线性反馈移位寄存器的 FPGA 实现
• 3.9 本章小结
• 第四章 基于细胞自动机的高斯随机数序列发生器设计
• 4.1 Box-Muller 算法
• 4.2 中心极限定理
• 4.3 基于细胞自动机的高斯白噪声发生器的设计方案
• 4.3.1 均匀随机数生成模块
• 4.3.2 Box-Muller 算法实现模块
• 4.3.3 中心极限定理实现模块
• 4.4 算法优化设计
• 4.4.1 输出的最小比特宽度分析
• 4.4.2 sin/cos的算法优化
• 4.4.2.1 sin/cos的最小比特宽度优化
• 4.4.2.2 sin/cos的分段折线多项式拟合
• 4.4.3 平方根的算法优化
• 4.4.3.1 平方根的最小比特宽度优化
• 4.4.3.2 平方根的分段折线多项式拟合
• 4.4.4 自然对数的算法优化
• 4.4.4.1 自然对数的最小比特宽度优化
• 4.4.4.2 自然对数的分段折线拟合
• 4.5 基于细胞自动机的高斯随机数发生器的实现以及仿真结果
• 4.5.1 Matlab 仿真以及实验结果
• 4.5.2 Modelsim 仿真以及实验结果
• 4.5.3 Xilinx ISE Foundation 仿真以及实验结果
• 4.6 本章小结
• 第五章 基于 Wallace 算法的高斯随机数发生器的设计实现
• 5.1 Wallace 算法的原理
• 5.2 基于Wallace 算法的高斯随机数发生器实现方案设计
• 5.2.1 均匀随机数发生模块
• 5.2.2 地址产生模块
• 5.2.3 高斯随机数发生模块
• 5.2.3.1 ROM 以及双口RAM 模块
• 5.2.3.2 正交转换模块
• 5.2.4 平方和修正模块
• 5.3 实验仿真结果以及分析
• 5.3.1 Matlab 仿真以及实验结果
• 5.3.2 Modelsim 仿真以及实验结果
• 5.3.3 Xinlinx ISE Foundation 仿真以及实验结果
• 5.4 高斯随机数的统计测试
• 2 检验'>5.4.1 χ²检验
• 5.4.1.1 χ2 检验的原理
• 5.4.1.2 卡方检验步骤
• 2检验'>5.4.1.3 基于Wallace 算法的高斯随机数序列的x²检验
• 5.4.2 A-D 检验
• 5.4.2.1 A-D 检验定义
• 5.4.2.2 基于Wallace 算法的高斯随机数序列的A-D 检验
• 5.5 本章小结
• 第六章 结论与展望
• 致谢
• 参考文献
• 个人简历及硕士期间发表的论文