公开/公告号CN101127575A
专利类型发明专利
公开/公告日2008-02-20
原文格式PDF
申请/专利权人 中兴通讯股份有限公司;
申请/专利号CN200710154108.6
申请日2007-09-12
分类号H04B17/00(20060101);H04Q7/34(20060101);
代理机构11262 北京安信方达知识产权代理有限公司;
代理人龙洪;霍育栋
地址 518057 广东省深圳市南山区高新技术产业园科技南路中兴通讯大厦法律部
入库时间 2023-12-17 19:45:36
法律状态公告日
法律状态信息
法律状态
2017-11-07
未缴年费专利权终止 IPC(主分类):G06F7/58 授权公告日:20100901 终止日期:20160912 申请日:20070912
专利权的终止
2010-09-01
授权
授权
2008-04-16
实质审查的生效
实质审查的生效
2008-02-20
公开
公开
技术领域
本发明涉及信息电子领域，尤其涉及一种均匀分布随机数产生方法及一种均匀分布随机数发生器。
背景技术
随机数广泛应用于信息电子领域。比如在移动通信系统的设计当中，往往需要在实验室对无线信道的各种特性进行模拟，并对通信系统算法在这些信道下的表现或性能进行仿真和评估。用信道模拟的手段来测试通信系统，和在实际通信环境测试相比，可控性和可重复性强，可以节约大量人力物力。
信道模拟技术的实现方法一般可以分为软件仿真和半实物仿真。前者的典型例子是利用Matlab等仿真软件对通信系统进行建模，这种方法实现相对简单，但是无法应用于真实系统的测试，因此仿真真实度不高，且仿真时间往往很长。而半实物仿真技术在实时的环境下运行仿真模型，并实现与实物的连接，这样大大提高了仿真结果的置信度，缩短了仿真时间。
采用半实物仿真来对信道进行模拟，相对软件仿真的难点之一在于需要快速，实时的实现各种信道模拟算法。这些算法在软件仿真中，一般采用浮点运算实现，既不需要考虑其精度，也不需要太多考虑其实时性，但是在半实物仿真中，由于需要和实际系统对接，且其实现的载体往往是FPGA(Field-Programmable Gate Array，现场可编程门阵列)，ASIC(ApplicationSpecific Intergrated Circuits，专用集成电路)或DSP(Digital Signal Processer，数字信号处理器)之类的定点器件，因此，就需要考虑实时性的问题，要求运算尽量简单，便于实现。
以最常见的高斯白噪声模拟为例，其常用的方法为逆变换法，具体步骤如下：
第一步，产生[0，1]区间均匀分布随机变量U；
第二步，记高斯分布变量的累积分布函数为FX(X)，其反函数为FX-1(X)，令
则X为所需的高斯分布随机变量。
上述过程中，第一步需要产生均匀分布随机变量，事实上，均匀分布随机数发生器是生成其他概率分布变量的基础，在其他信道特性的模拟中也广泛使用。譬如，进行信道慢衰落特性的模拟时，需要生成对数正态分布的随机变量，其前提也是先生成均匀分布随机变量。
由此可见，均匀分布随机数发生器是信道模拟中最基本的技术之一。应用最多的均匀分布随机数发生器算法是线性同余法，该算法描述如下：
定义如下递推运算：
xi+1＝(axi+c)(mod M)(i＝0，1，2，…) (2)
其中xi的初值记为x0，称为线性同余发生器的种子数，a和c分别称为乘子和增量，M叫模数，这些均为非负整数，而且，a，c及xi均小于M。上式的xi+1是axi+c被M整除后的余数，称为xi+1与axi+c对模M同余。如果挑选适当的a、c、M，可以使xi满足均匀分布随机变量的各种重要特性，也即xi就是所需产生的均匀分布随机数。
对于式(2)在实时实现时的主要困难在于求余运算。一般来说，如果M不为2的整数次方，那么直接求余将耗费大量时间和资源，且随着M的增大，这个问题尤其突出。而恰恰在很多算法中，M并不是2的整数次方，以最常用的“ran0”随机数发生器为例，该随机数发生器由刘易斯(Lewis)，古德曼(Goodman)和米勒(Miller)于1969年提出，其参数取法如下：
a＝75＝16807，M＝231-1，c＝0 (3)
该随机数发生器经过了大量随机数检验，并被广泛使用在软件仿真中，注意到此时M不是2的整数次方，且M为31位二进制数，对如此大的数求余将非常耗费时间，在FPGA之类的数字器件实现时，还会大量消耗资源，很难满足实时性要求。
综上所述，均匀分布随机数发生器是信息电子领域的重要技术，但在对实时性要求较高的场合，直接采用通用算法不能满足实时性要求。
发明内容
本发明要解决的技术问题是解决现有线性同余法实现均匀分布随机数发生器的时候，计算量太大，无法满足实时性要求的问题，提供一种可以在FPGA或DSP等定点器件里很方便、快速实现的均匀分布随机数产生方法及系统。
为解决上述问题，本发明提出了一种均匀分布随机数发生器，包括初始化模块，选择器，乘加器，以及延迟器，初始化模块产生随机数发生器的种子，输入到所述选择器，所述选择器在初始时选择所述初始化模块输入的数值作为输出，进入正常工作状态，在正常工作状态时所述选择器选择延迟器输入的数值作为输出，选择器的输出输入到所述乘加器，所述乘加器将选择器的输出与a相乘再加c，得到乘加器的输出，其特征在于，还包括第一移位模块，第二移位模块，第一加法器，第三移位模块，第四移位模块，第二加法器，其中，
所述乘加器的输出输入到第一移位模块和第一加法器，第一移位模块对输入的数据进行右移n位，得到第一移位模块的输出，输入到第二移位模块和第一加法器；
第二移位模块对输入的数据左移n位，得到第二移位模块的输出，输入到第一加法器；
第一加法器将第一移位模块和乘加器输出的数值相加，减去第二移位模块输出的数值，再加上1，得到第一加法器的输出值，将其输入到第三移位模块和第二加法器；
第三移位模块对输入值右移n位，输出至第四移位模块和第二加法器；
第四移位模块将输入值左移n位，输出至第二加法器；
第二加法器将第三移位模块和第一加法器的输出的数值相加，减去第四移位模块输出的数值，再减去1，得到第二加法器的输出值，即得到本次输出的随机数，并将其输入延迟器；
延迟器把本次输出的随机数进行延迟，输出到所述选择器。
进一步地，上述发生器还可具有以下特点，所述a＝75＝16807。
进一步地，上述发生器还可具有以下特点，所述c＝0。
进一步地，上述发生器还可具有以下特点，所述n＝31。
为解决上述问题，本发明还提出了一种均匀分布随机数产生方法，包含如下步骤：
步骤一，任意获取数值x0，a与x0相乘再加c得到z，a，c均为非负整数；
步骤二，将z使用移位器右移n位得到z1，z1再使用移位器左移n位得到z2，其中2na+c＜22n；
步骤三，将z和z1相加之和减去z2，其结果为y；
步骤四，将y加上1然后使用移位器右移n位得到y1，y1再使用移位器左移n位得到y2，将y和y1相加之和减去y2得到xi+1，即本次产生的随机数；
步骤五，xi+1延迟，与a相乘再加c得到z，返回步骤二。
进一步地，上述方法还可具有以下特点，参数取法为：a＝75＝16807。
进一步地，上述方法还可具有以下特点，所述c＝0。
进一步地，上述方法还可具有以下特点，所述n＝31。
本发明所述的均匀分布随机数发生器用移位运算和加减运算替代了一般线性同余器所需的求余运算，与一般的线性同余器相比，显著降低了计算量，非常便于FPGA或DSP等嵌入式处理器实现，可以满足各种需要实时生成均匀分布随机数发生器的场合。
附图说明
图1是现有式(2)和(3)描述的均匀分布随机数发生器的结构示意图。
图2是本发明所述的线性同余均匀分布随机数发生器的结构示意图。
图3是本发明线性同余均匀分布随机数产生方法流程图。
具体实施方式
通过本发明的方法，可以把线性同余随机数发生器的求余运算转化为便于硬件实现的乘法运算和移位运算，从而解决求余运算耗时过长的问题。
本发明涉及的快速算法针对背景技术中提到包括ran0方法在内的模数M＝2n-1时的求余方法，该方法可以满足工程中大多数情况下对均匀分布随机数的产生要求，此外，通过类似于本发明的推导过程，可以方便的把这种快速算法推广到其他参数下的线性同余法。
下面介绍本发明的具体推导过程。在n为任意正整数，c为负整数，M＝2n-1，且满足2na+c＜22n的情况下，
式(2)可以等效为
xi+1＝y-(y+1)/2n×(2n-1) (4)
其中
y＝z-z/2n×(2n-1) (5)
z＝axi+c (6)
其中为向下取整符号，即取小于向下取整符号内数值的最大整数。
即利用(4)，(5)，(6)式代替式(2)，具体的推导如下，
假设z/(2n-1)的商为d，余数为e，z/2n的商为f，余数为g，则根据被除数，除数，商和余数的相互关系可以得到下式：
z＝d×(2n-1)+e＝f×2n+g＝f×(2n-1)+f+g (7)
f＝z/2n (8)
由式(5)，式(7)，式(8)，可以得到
y＝z-z/2n×(2n-1)＝f+g (9)
又由推导前提的数值范围以及式(6)，可得
z∈[0，22n] (10)
进一步得到：
y＝(2n-1)×2 (11)
下面分别讨论y＜2n-1以及2n-1＜y＜(2n-1)×2的两个区间内命题是否成立。
对于y＜2n-1，显然
(y+1)/2n＝0 (12)
并且根据式(2)，(7)，(9)，还有
xi+1＝y (13)
结合式(12)和式(13)，可以得到
xi+1＝y-(y+1)/2n×(2n-1)
这就是所需证明的式(4)，可见在y＜231-1式命题成立。
对于2n-1＜y＜(2n-1)×2，显然有
(y+1)/2n＝1 (14)
并且根据式(2)，(7)，(9)，有
xi+1＝y-(2n-1) (15)
结合式(14)和式(15)，可以得到
xi+1＝y-(y+1)/2n×(2n-1)
这就是所需证明的式(4)，可见在231-1≤y＜(231-1)×2命题成立。
因此对于所有y的可能取值范围，本命题成立，证毕。
上面的推导表明，式(2)所描述的随机数发生器可以通过式(4)～(6)等效实现，其中式(4)～(5)可以进一步写成
xi+1＝y-[((y+1)＞＞n)＜＜n]+[(y+1)＞＞n] (16)
y＝z-[(z＞＞n)＜＜n]+[z＞＞n] (17)
这样，式(6)，式(16)以及式(17)就构成了本发明所提出的均匀分布随机数发生器的实现公式，上述＞＞n代表右移n位，＜＜n代表左移n位。
对比式(2)和式(16)，(17)可以看出，本发明所述的均匀分布随机数发生器实现方法用移位运算和加减运算替代了一般线性同余器所需的求余运算，与一般的线性同余器相比，显著降低了计算量，非常便于FPGA或DSP等嵌入式处理器实现，可以满足各种需要实时生成均匀分布随机数发生器的场合。
下面将结合附图及实施例对本发明的技术方案进行更详细的说明。
图1是现有式(2)和(3)描述的均匀分布随机数发生器的结构示意图。图中初始化模块产生随机数发生器的种子，并作为乘加器模块的初始输入，乘加器模块完成z＝axi+c的运算，求余模块完成mod M的运算，延迟器把本次输出的随机数进行延迟，并作为下一次运算中乘加器的输入。
图2是本发明提出的均匀分布随机数发生器结构示意图，和图1的区别在于用一系列移位和加减模块代替了求余模块。该随机数发生器包括初始化模块，乘加器，选择器，延迟器，还包括第一移位模块，第二移位模块，第一加法器，第三移位模块，第四移位模块，第二加法器，
其中，图中初始化模块产生随机数发生器的种子，并作为乘加器模块的初始输入，乘加器模块完成z＝axi+c的运算；
所述选择器在初始时选择所述初始化模块输入的数值作为输出，进入正常工作状态，在正常工作状态时所述选择器选择延迟器输入的数值作为输出，选择器的输出输入到所述乘加器；
乘加器的输出输入到第一移位模块和第一加法器，第一移位模块对输入的数据进行右移n位，第一移位模块的输出输入第二移位模块和第一加法器；
第二移位模块对输入的数据左移n位，得到第二移位模块的输出，输入到第一加法器；
第一加法器将第一移位模块和乘加器的输出相加，减去第二移位模块的输出，再加上1，得到第一加法器的输出值，将其输入到第三移位模块和第二加法器；
第三移位模块对输入值右移n位，输出至第四移位模块和第二加法器；
第四移位模块将输入值左移n位，输出至第二加法器；
第二加法器将第三移位模块和第一加法器的输出相加，减去第四移位模块的输出，再减去1，得到第二加法器的输出值，即得到本次输出的随机数，并将其输入延迟器；
延迟器把本次输出的随机数进行延迟，并作为下一次运算中乘加器的输入。
图3所示为本发明线性同余均匀分布随机数产生方法流程图，具体步骤如下，
步骤310，随机数发生器处于初始状态，产生初值x0，作为随机数发生器的种子；
步骤320，如果随机数发生器处于初始态，x0作为乘加器输入，并计算z＝ax0+c，随后转入正常运行状态；如果处于正常运行状态，xi作为乘加器输入，计算z＝axi+c；
步骤330，计算(z＞＞n)＜＜n；
即对z进行移位运算，首先z使用移位器右移n位得到z1，z1再使用移位器左移n位得到z2。
步骤340，计算y＝z-[(z＞＞n)＜＜n]+[z＞＞n]；
即y＝z-z2+z1；
步骤350，计算xi+1＝y-[((y+1)＞＞n)＜＜n]+[(y+1)＞＞n]
将y+1然后使用移位器右移n位得到y1，y1再使用移位器左移n位得到y2，xi+1＝y-y2+y1。
步骤360，对xi+1延迟得到xi，返回第二步。这里的延迟和现有技术是一样的，如果是软件实现，把值(即xi+1)存储起来，用时取出。对于硬件实现可以用常规的类似D触发器组实现。
对于ran0方法，只要把上述方法和装置中的n设为31，c设为0，a设为16807即可。
通过以上分析可知，本发明提出的均匀分布随机数发生器实现方法，只包含乘法运算，加减运算和移位运算，避免了求余运算，从而解决了实时性的问题，可以非常方便的在各种数字器件(如FPGA，ASIC或DSP)中实现。
当然，本发明还可有其他多种实施例，在不背离本发明精神及其实质的情况下，熟悉本领域的技术人员当可根据本发明作出各种相应的改变和变形，但这些相应的改变和变形都应属于本发明所附的权利要求的保护范围。
机译： 用于产生根据不均匀分布绘制的随机数的装置和方法
机译： 一种生成均匀分布和独立的随机数的方法
机译： 一种构造密钥电流发生器的方法，该发生器用于产生密码应用的伪随机数。
