（通信与信息系统专业论文）高速纠错码测试系统的设计与实现.pdf

重庆邮电大学硕士论文摘要 摘要 纠错码做为数字通信系统的重要组成部分，在上世纪末和本世纪初得到了高 速的发展，目前，纠错码正在往低b e r 和低复杂度的方向发展。纠错码测试是纠 错码技术发展不可缺少的环节，随着性能要求的提高，相应的测试数据量也成指 数增加，继续利用传统的软件仿真方式在b e r 为1 0 1 0 的点仿真耗用的时间需要数 十天，而目前对于磁盘存储系统来说，其要求的b e r 已达到了1 0 q 5 ，软件仿真方 法将不可能实现。因此，本文中提出了一种软硬件联合测试的方法，利用软件程 序的直观性和硬件的高速性能相结合，针对b e r 为1 0 4 0 的性能仿真点的测试需求。 软硬件联合测试的一个重要方面是软件和硬件之间数据传输，在本文中，利 用分层思想来设计和实现软硬件之间的数据通道。实现时，利用高速的数据采集 卡做为软硬件之间的物理传输通道，经过两层校验保证软硬件接口适配层之间的 数据无差错到达，其中，在数据链路层通过添加校验位的方法保证帧数据的完整 性，在无差错传输层利用确认重传的方式保证帧无丢失。在接口适配层利用开放 的接口模块与功能模块进行连接，这样可以在被测试的纠错码编译码器吞吐能力 不匹配的情况下，通过并行例化从而使系统的吞吐能力最大。 高性能的噪声源是纠错码正确测试的重要因素，对于低b e r 测试来说，噪声 源必须速率快，随机性能好。本文提供了高斯随机数发生器的f p g a 设计和实现 过程。首先设计实现了m t - 1 9 9 3 7 均匀伪随机数发生器，周期达到2 1 9 9 3 7 ，然后利 用b o xm u l l e r 算法将均匀随机数转换为具有高斯分布的伪随机序列，实现b m 算 法时，通过改进的位宽分配，使输出幅值提高了1 5 6 ，满足b e r 为1 0 。1 5 的仿真的 测试要求。 利用设计的测试系统对码长为1 7 8 4 ，码率为0 4 3 7 的四迸制l d p c 进行测试 后得到的性能曲线，和软件测试相比测试效率大大高于软件测试。 关键字：纠错码，高速，软硬件联合设计，测试系统，高斯随机数发生器 重庆邮电大学硕士论文 a b s t r a c t a b s t r a c t e r r o r - c o r r e c t i n gc o d e ( e c c ) i s a ni m p o r t a n tp a r to ft h ed i g i t a lt r a n s m i s s i o ns y s t e m i td e v e l o p e df a s td u r i n gt h el a s tc e n t u r ya n dt h eb e g i n n i n go ft h i sc e n t u r y n o w a d a y s ， e c c d e s i g na i mf o rl o wb e ra n dl o wc o m p l e x i t y e c c t e s t i n gi sa ni n d i s p e n s a b l ep a r t o ft h ee c cd e v e l o p m e n t a st h e i n c r e a s i n gp e r f o r m a n c er e q u i r e m e n t s ，t h e c o r r e s p o n d i n gt e s td a t av o l u m ei n c r e a s e se x p o n e n t i a l l ys i m u l a t i o np r o c e s sw i l lc o s t s e v e r a ld a y su s i n gt h et r a d i t i o n a ls o t t w a r es i m u l a t i o nm e t h o d sw h e nt h et e s tp o i n t so f t h eb e ri s10 。b u tf o rt h em a g n e t i cr e c o r d i n gs y s t e m s ，t h eb e rr e q u i r e m e n t sh a s r e a c h e d10 - d ，w h i l et h es o f h v a r es i m u l a t i o nm e t h o dw i l lb eu s e l e s s i nt h i sp a p e r ，i t p r o p o s e dah a r d w a r ea n ds o f t w a r ec o d e s i g n e ds y s t e m i tu s e st h ec o m b i n a t i o no ft h e i n t u i t i v es o f t w a r ep r o g r a m sa n dh a r d w a r eh i g h s p e e dp e r f o r m a n c ew a y st os i m u l a t et h e b e ra tlo 。1 0p o i n to ft e s t i n g t h ed a t at r a n s m i s s i o nb e t w e e ns o f t w a r ea n dh a r d w a r ei sa ni m p o r t a n ta s p e c to f h a r d w a r ea n ds o f t w a r ec o - t e s t i n g i nt h i sp a p e r , i tm a k e su s eo fh i e r a r c h i c a lt h e o r yt o d e s i g na n di m p l e m e n tt h ec h a n n e lb e t w e e nh a r d w a r ea n ds o f t w a r e i np r a c t i c e , t h e r ei s a nh i g h - s p e e dd a t aa c q u i s i t i o nc a r db e t w e e nt h eh a r d w a r ea n ds o f t w a r ea st h ep h y s i c a l 仃a n s m i s s i o nc h a n n e l t w o t i e rv e r i f i c a t i o ne n s u r e st h ed a t ae r r o r - f r e ea r r i v a lb e t w e e n t h ei n t e r f a c ea d a p t a t i o nl a y e r so ft h ed i f f e r e n ts u b s y s t e r n s t h ed a t al i n kl a y e re n s u r e s t h ei n t e g r i t yo ft h ef r a m eb ya d d i n gp a r i t yb i t sa n dt h ee r r o r - f l e el a y e ra n du s e st h e m e c h a n i s mo fa n dr e t r a n s m i s s i o nt oe n s u r en ol o s tf a m e s t h ei n t e r f a c ea d a p t a t i o n l a y e ru s e sa no p e ni n t e r f a c em o d u l ec o n n e c t e dw i t ht h ef u n c t i o nm o d u l e s i n t h i sc a s e , w h e nt h et h r o u g h p u ta b i l i t yo ft h et e s t e dc o d e eo fe r r o r - c o r r e c t i n gc o d ed o e sn o tm a t c h e a c ho t h e r , i ts t i l lc a nm a k et h el a r g e s tt h r o u g h p u to fs y s t e mb ya d d i n gl o wt h r o u g h p u t m o d u l e sc o n n e c t e dw i t ho p e ni n t e r f a c e a s i g n i f i a c a n tf a e t o ro f e c c t e s t i n gi sh i g h - p e r f o r m a n c en o i s es o u r c e f a s t e rr a t e a n dh i g h e rr a n d o mp e r f o r m a n c ei sn e c e s s a r yf o rt h el o wb e rt e s t t h i sa r t i c l ep r o v i d e s ad e s i g na n di m p l e m e t a t i o ng a u s s i a nr a n d o mn u m b e rg e n e r a t o ri nf p g a f i r s t l y , d e s i g n sa n di m p l e m e n t su n i f o r mp s e u d o - r a n d o mn u m b e rg e n e r a t o rm t - 19 9 3 7 ，w h i c h p e r i o dr e a c h e s2 1 9 ，9 3 7 ，a n dt h e nu s e sb o x m u l l e ra l g o r i t h mt ot r a n s f o r mt h eu n i f o r m r a n d o mn u m b e rt op s e u d o - r a n d o mn u m b e rw i mt h eg a u s s i a nd i s t r i b u t i o n t h r o u g ha n i m p r o v e db i t - w i d ed i s t r i b u t i o nm a d et h eo u t p u ta m p l i t u d ei n e a s e1 5 8 ，m e c t i n gt h e b e ro f10 1 5s i m u l a t i o no ft h et e s tr e q u i r e m e n t s f i n a l l y ) w eu s et h ed e s i g n e dt e s ts y s t e mt ot e s tt h en o n - b i n a r yl d p c ( 17 8 4 ，2 0 4 8 ) a n do b t a i n st h ep e r f o r m a n c ec u r v e t h ee f f i c i e n c yo ft h es y s t e mi sm u c hh i g h e rt h a n s 0 1 a r et e s t i n g k e yw o r d s ：e r r o r - c o r r e c t i n gc o d e s ，h i g h s p e e d ，h a r d w a r ea n ds o l , r a r ec o d e s i g n , t c s t i n gs y s t e m ，g a u s s i a nr a n d o mn u m b e rg e n e r a t o r i r 重庆邮电大学硕士论文第一章绪论 第一章绪论 本章在简要介绍纠错码的发展历史和现状的基础上，根据目前的纠错码发展 现状和趋势，在有效性和可靠性的要求下，给出了纠错码测试系统的各项指标。 最后给出了本文的研究目的和意义以及本文的主要内容和结构安排。 1 1 纠错码的发展历史与现状 提高信息传输的可靠性和有效性，始终是通信领域研究与追求的目标。在实 际的信道传输数字信号的时候，由于信道传输特性的不理想以及噪声的影响，所 收到的数字信号不可避免的会发生错误，为了在已知信噪比的情况下达到一定的 误码率指标，首先应该合理的设计基带信号，选择调制、解调方式，采用频域均 衡或者时域均衡，使误码率尽可能降低，但如果误码率仍然不能满足要求，则必 须采用信道编码，即纠错码。 1 9 4 8 年，美国贝尔实验室的c l a u d ee s h a n n o n 1 】在贝尔技术杂志上发表了题为 “a m a t h e m a t i c a lt h e o r yo f e o m m u n c a t i o n 的论文，s h a n n o n 在该论文中提出了信 道编码理论，即每个信道具有确定的信道容量c ，对于小于c 的码率r ，存在一 种编码方法，若采用最大似然译码，则随着码长的增加其译码错误概率p 可任意 小。但s h a n n o n 给出的只是一个存在性定理，并没有给出能够达到香农限的码型 的具体构造方法。此后，寻找靠近香农限的好码成为编码科研工作者的主要目标。 2 0 世纪五六十年代，科学家们主要研究的方向是：研究各种有效的编译码方 法，这个时期的主要贡献有：1 9 5 0 年h a m m i n g 发明了一种能纠正一个错误的完备 线性分组码一h a m m i n g 码；b c h 码的编译码方法的出现；卷积码及序列译码方 法的出现等。这个时期是纠错码从无到有迅速发展的时期。 2 0 世纪六七十年代，比较重视的是编码技术在实际应用系统中的应用。这个 时期出现了许多有效的编译码方案，比如门限译码，迭代译码，软判决译码，卷 积码的维特比译码等。尤其是维特比译码的出现为纠错码的实用化前进了一大步。 值得一提的是1 9 6 2 年g a l l a g e r 还提出了一种线性分组码低密度奇偶校验码， 即l d p c 码，他提出了用迭代译码的方法来进行译码，但是由于当时计算机仿真 水平的限制，这种码字的性能没有得到完全的体现。 2 0 世纪七八十年代，计算机硬件技术和电子工艺得到了长足的发展，数字信 重庆邮电大学硕士论文第一章绪论 号处理技术的发展，为编码技术进一步实用化打下了坚实基础。这一时期出现了 性能达到s h a n n o n 信道编码定理中提出的好码g o p p a 码。 2 0 世纪九十年代以来，纠错码理论日趋完善。t u r b o 码的出现，引起了人们对 于迭代译码的关注热情，使各种现代的纠错码理论相继出现，完善了s h a n n o n 编 码理论。而1 9 9 8 年，s y c h u n g ，g d f o m e y 等发现l d p c 码的优越性能：在二进 制加性高斯白噪声信道下，码率为1 2 的不规则l d p c 码的门限值距香农限只有 0 0 0 4 5 d b ，码长为1 0 7 时其仿真结果显示，在误比特率为1 旷的情况下，离香农限 的距离低于o 0 4 d b ，超过了t u r b o 码的性能。 近年来，随着数字通信技术的发展，对数字通信可靠性的要求越来越高，以 磁盘存储【2 】技术为例，要求的误码率达到1 0 1 5 以下，深空通信和w b a n 要求的误 码率也在1 0 d o 以下。因此，纠错码技术在数字通信系统中的地位将会变的尤为突 出，然而，目前的大多数的纠错码都难以达到这种性能，比如基于信度传播的迭 代译码，如l d p c 和t u r b o 码在性能曲线在达到一定点后会出现错误地板，因此， 设计好的码型和解决错误地板是目前纠错码研究的一个热点。随着数字集成技术 的发展，庞大的通信体承载的功能将会越来越多，在保证良好的性能的前提下， 算法的复杂度也是纠错码设计需要重点考虑的方面之一。因此，低复杂度、高性 能是纠错码发展的大势所趋。 1 2 纠错码测试系统的要求 纠错码测试是纠错码研究进程中不可缺少的一个环节，良好的性能结果必须 通过测试系统获得。无误差、高效是任何测试系统必须具备的基本条件，但是， 对于纠错码测试来说，由于纠错码的特殊性，所以其测试系统也必须满足一些特 殊的要求。 1 2 1 高吞吐能力 对于纠错码来说，高性能也就意味着低误码率，根据实际测试时误码率的统 计惯例，错误统计数必须达到1 0 0 以上，这样，误码率要求越低，测试的数据量 就越多。随着计算机处理技术的发展，在一定程度上可以满足纠错码测试的需求， 因此，可以利用各种计算机语言来搭建纠错码测试平台，比如c 、c + + 和m a t l a b 等。但是对于性能要求较高的纠错码就显得捉襟见肘了，以卡耐基梅陇大学提供 的一个在磁盘存储系统中的l d p c 码测试为例，测试要求的误码率是l o 以o ，即仿 2 重庆邮电大学硕士论文第一章绪论 真信源数据量为1 0 1 2 比特。仿真工具采用的是2 0 g h z 的p c 机，仿真程序采用c 语言，考虑在信道中利用状态数为1 6 ，回溯深度为2 5 的s o v a 检测器的情况下， 假如该计算机的所有带宽被全部利用，所需花费的时间也在一个月以上。因此， 传统的软件测试方法已经完全不适用了，设计一个高吞吐能力的测试系统势在必 行。 1 2 2 开放接口模式 由于迭代译码的出现，模块的重复迭代使资源的消耗大大减少了，但是译码 的速度也降低了，直接影响到了译码器的吞吐量指标。传统测试系统【2 h 9 】的数据处 理流程是按照数字通信系统的数据流进行设计的，基本的顺序为信源、编码器、 信道加噪、量化译码、信宿，如若其中的某一个模块速度较慢，则整个测试系统 的运行速度将会为其所困。所以，设计一个开放接口的测试系统，打破基本数据 流操作的方式是非常必要的。 1 2 3 高精度信道模型 大数量的测试，对信道噪声的随机性和精度要求也变的越来越高。实际的数 字设计中不可能生成真正的随机序列，测试中经常使用伪随机序列代替，只要伪 随机序列有足够长的周期，在观测周期内呈现随机性，在测试中就不会影响纠错 码测试的性能。但是，随着测试数据量的增加，伪随机序列的周期数也应该成倍 的增加。以高斯信道为例【l 们，该随机性就体现在产生的随机噪声的最大幅值上， 输出的幅值为96 的概率为2 2 6 x1 0 。1 9 ，输出的噪声幅值为1 06 的概率为1 5 2 x 1 0 - 2 3 ，基本可以满足目前所有通信系统的测试需求。因此，必须设计一个随机周期 长，噪声精确度高的信道模型，以此来满足高性能的大数据量测试。 1 3 论文研究的意义、目的和方法 纠错码是数据通信研究的一个热点领域，从上个世纪八十年代至今一直处于 一个高速发展的状态，各种码型也不断的出现，研究一种码型的性能好坏必须经 过不断的测试和实际的检验方能得到正确的结果，因此，设计一个稳定、可靠、 高效、通用的测试系统对于纠错码的性能测试和不同码型之间的性能比较都具有 非常重要的意义。 3 重庆邮电大学硕士论文第一章绪论 因此，本文的主要目的就是设计一个针对纠错码低误码率要求的测试系统， 该测试系统包括以下几个方面的特点： 1 ) 高速：误码率为1 0 1 0 的性能点能在数小时内完成，也就是系统的吞吐量 达到5 0 0 m 1 g b i t s ，能够满足深空通信、w b a n 和较低要求的磁记录系统的性能 要求。 2 ) 接口：使用统一的接口，对功能模块实行开放式连接，这样，在设计的 编译码器吞吐量不匹配的情况下通过连接多个低吞吐量模块来实现系统吞吐量的 最大化。 3 ) 信道：设计长周期、高精度的伪随机数字噪声信号发生器。 4 ) 系统的稳定性和实用性：数据的调度稳定，使测试性能不受系统异端情 况影响。设计简单的用户接口，方便测试，实用性强。 为了实现上述目的，本文采用的是一种软硬件联合设计方法，软件部分主要 是在p c 平台下利用c 语言实现，硬件平台采用f p g a 实现，软硬件之间通过使 用p c i 接口进行高速的数据采集来进行通信。软件平台可以为用户提供一个简单 的参数平台，具备较强的实用性，观察结果也显得更加方便。f p g a 具备高速运算 的能力，是提高系统吞吐量的主要方法。为了实现系统的稳定性和软硬件之间的 无差错传输，在软硬件平台之间使用了分层传输【l l 】协议。 1 4 论文结构 本文的主要工作包括两个部分：一是测试系统的软硬件之间的分层通信协议 的制定与实现，其中实现包括软件实现和f p g a 实现。二是功能模块的实现，主 要包括信源，信道噪声和信宿，其中的主要工作集中在信道噪声f p g a 设计。软 件系统利用c 语言实现，硬件系统利用m a t l a b 进行算法仿真后利用v e r i l o g 实 现。论文具体内容安排如下： 第一章简要介绍了纠错码的发展历史和现状，分析了纠错码测试系统必须具 体的各项功能和要求，在此基础上提出了本文的目的和实现方法，最后给出了本 文的大致轮廓。 第二章首先介绍了均匀随机数产生的一些方法，然后介绍利用均匀分布的随 机数转化为高斯正态分布的几种转移法，并从几个方面分析各种方法的优劣，甄 选出一种适合f p g a 实现的方法。 第三章主要包括三个部分，第一部分对整个系统的顶层模块进行划分，第二 部介绍了分层模块的设计，以及各分层模块内部的算法。第三部分给出了高斯随 4 重庆邮电大学硕士论文第一章绪论 机数发生器的总体设计架构。 第四章是在第三章的设计规划下，设计具体的实现方法，再通过编写r t l 代 码，仿真和综合之后得到的各个模块的时序关系，综合结构。 第五章首先对高斯随机数发生器的数据分布，资源消耗和最大工作时钟进行 测试。然后介绍了分层通道的各种性能参数，最后利用该系统对多进制l d p c 码1 1 2 】 进行测试，得到性能曲线和消耗时间统计数据。 第六章介绍了本文的结论，并对进一步的研究方向提出建议。 5 重庆邮电大学硕士论文第二章高斯随机数发生器原理与实现方法 第二章高斯随机数发生器原理与实现方法 目前通信系统仿真最常用的是加性噪声信道模型，在这个模型中，发送信号 被加性随机噪声过程恶化。在物理上，加性噪声过程由通信系统接收机中的电子 元器件引起，或者由传输中的干扰引起。如果噪声主要由接收机中的元部件和放 大器引起，那么，它可以表征为热噪声，这种模型的噪声统计地表征为高斯噪声 过程，因此，该信道的数学模型通常称为加性高斯噪声信道。因为这个信道模型 使用于很广的物理通信信道，并且因为它在数学上易于处理，所以是通信系统分 析和设计中所用的最主要的信道模型，比如深空通信，就是用高斯信道模型来逼 近，还有磁记录信道等，都使用高斯随机数发生器作为主要的噪声来源。 2 1 随机信号的产生与处理 在所有具有实际意义的系统中，信息承载信号从信源端到终端用户的传送过 程中，信道噪声、干扰和衰落等随机影响会使它造成损失。要想在波形级精确的 仿真这些系统，首先要对这些随机影响建立准确的模型，因此，需要产生这些随 机影响的算法，其基本构建模块是随机数据发生器。严格来讲，随机数发生器所 产生的并不是真正的随机序列，而是在观察区间上“呈现随机性 的序列，以此 来近似给定仿真程序中的随机过程的样本函数。所谓呈现随机性指的是产生的序 列在仿真区间上具有某种特性，能对具体应用中的随机过程建立准确模型并达到 要求的精度，因此，我们称这种序列为伪随机序列【1 3 1 。具有均匀概率密度分布的 随机变量很容易转换成具有其他所需p d f 的随机变量，实现这种均匀分布随机数的 方法很多，比如线性同余法、非线性同余法、位移寄存法、混沌和组合法等。数 字实现时利用最多的和最易实现是线性同余法和位移寄存法。 2 1 1 线性同余发生器 线性同余发生器( 1 i n e a rc o n g r u e n c eg c n r o a t o r ：l c g ) 定义为如下运算： x m = a x i + c m o d ( m )式( 2 。1 ) 其中，a 和c 分别称为乘子和增量，m 叫做模数。当然，这是一个确定性的序 列算法，能依次产生连续的x 值。x 的初始值即为) 【0 ，称作线性同余发生器的种子 6 重庆邮电大学硕士论文 第二章高斯随机数发生器原理与实现方法 数，l c g 产生的所有数是整数。由于对 a x i + e 进行模m 计算，上式至多可以产生 m 个不同的整数。发生器输出的一个理想特性是它应该具备很长的周期，从而在 序列重复前，输出序列能产生最多数目的整数。对于给定的m 值，当周期最大时， 我们称发生器是全周期的。 混合同余算法 最通用的同余算法就是c o 的混合同余算法。之所以称之为混合算法，是因 为在求解x i + l 的过程中要同时用到乘法和加法。混合线性算法具有下式的形式 x i + l = 【a x l 斗c m o d ( m ) ( c 0 ) 式( 2 2 ) 发生器的最大周期为m 。当且仅当满足以下特性时才能达到这个周期： 1 ) 、增量c 与i 1 1 互质。也就是说1 1 1 与c 没有素公因子。 2 ) 、a - 1 是p 的倍数，这里的p 表示模数m 的任意一个素因子。 3 ) 、如果m 是4 的倍数，则a - l 是4 的倍数。 具有素模数的乘性算法 乘性发生器的定义式为 x i + l = a x i m o d ( m ) ( 萨o )式( 2 3 ) 它是增量c = o 的混合算法，c = o 时，x i 不能为零，因此，全周期是m 1 而不是 m 。若满足以下特性，乘性算法能产生全周期序列： 1 ) 、n l 是素数。 2 ) 、m 为m o d ( m ) 的本原元素。 素数只能被1 和它本身整除，如果除了i - - m 1 外没有更小的i 值，使a 1 1 是m 的倍数，则a 为m o d ( m ) 的本原元素，也就是如果满足 a m - 1 一1 ：七和! 兰k 待l ，2 ，朋一2式( 2 4 ) mm 那么a 为m o d ( m ) 的本原元素，其中k 是一个任意整数。 具有非素模数的乘性算法 模数m 不是素数的同余算法中最重要的情况是m 等于2 的幂，即： x i + l = a x i m o d ( 2 n )式( 2 5 ) 这里的n 为整数。对上式的定义算法，最大周期为2 n 4 = 2 n 2 。如果满足以下条 件，可取得这个周期： 1 ) 乘子a m o d ( 8 ) 结果为3 或者5 2 ) 种子数x 0 为奇数。 由于两个奇数的乘积是奇数，可以推出，若】【0 是奇数，则由上式产生的所有 值都是奇数，也就是说，产生的x i 值都不是偶数，这使周期减少为原来的一半， 产生的奇数分成两组，其中只有一组由给定的种子数产生，这样又使周期减少了 7 重庆邮电大学硕士论文 第二章高斯随机数发生器原理与实现方法 一倍，产生的这组奇数一般跟所选的种子数有关。 采用m = 2 k 的好处是整数溢出能用于m o d ( m ) j 垂算，这样缩短了计算时间，但 所得的程序不易移植。 2 1 2 位移寄存发生器 线性同余发生器产生的均匀随机数具有一些缺点，高维的均匀随机性很差， 而且周期与计算机的字长有关。而移位寄存的方法是通过存储状态值，通过移位 改变状态值的方式来产生伪随机序列，该方法具有周期长，实现简单等优点。 反馈位移寄存器( f s r ) 1 9 6 5 年t a u s w o r t h e 提出了利用寄存器进行位移( 递推) ，直接在存储器单元中 形成随机数的方法。这种方法被称之为反馈位移寄存器( f e e d b a c ks h i f tr e g i s t e r m e t h o d s ) ，其线性反馈递推公式如式2 6 。 a k _ ( c p 虬矿唯l a k 矿l + + c l a k 1 ) ( m o d 2 ) 式( 2 6 ) 对寄存器中的二进制数码敏作递推计算，其中p 是给定正整数，纠，c i = o 或 l ( i = l ，p - 1 ) 为给定常数。 给定初值( a - p + l ，a - x ) ，通过上式产生的0 或1 组成二进制数列 a n ) 。截取 数? 0 a n ) 中连续的l 位构成一个l 位二进制整数：接着截取l 位又形成一个整数， 以此类推，得： x l = ( a l ，a l ，a l ) 2 ， x 2 - - - - ( a l + l ，8 , l + 2 ，a 2 0 2 ， 一般的x n = ( 1 ) l + l ，a ( n - 1 ) l + 2 ，a n d 2 ， r n = x d 2 l , ( n = l ，2 ) ， 则 r n ) 是f s r 发生器产生的均与随机序列。 如果l 与2 p 1 互素，且初值取自0 到2 l - 1 间的任一整数的概率相等；则用f s r 方法产生的随机数列 r n 性质如下： 1 ) 数学期望近似为1 2 ； 2 ) 方差近似为1 1 2 ； 3 ) 自相关系数近似为0 ； 钟当m l 弋 p ，且m l 与2 p 1 互素时，可构成m 维均匀随机数。 不同的p ，c l ，c 2 ，o b e9 c p 值将得到不同的f s r 发生器，当系数q ( j = l ，2 ， p ) 中仅有两个为1 ，其余全为0 的情况下，f s r 发生器不仅变得简单，而且效果 好。递推公式如2 7 。 重庆邮电大学硕士论文第二章高斯随机数发生器原理与实现方法 a k _ ( a 坤+ a k _ 。) ( m o d 2 ) 式( 2 7 ) 其中r ，p 为满足o o 是整数( 常数) ，初始值为( x o 。x o ，硌1 ) ，x n 是二进制表示的行 向量，a 是目w xw 维由( o ，1 ) 元素组成的矩阵，( i “) 表示t 的前w _ r 位和诈q 的后r 位组合而成的行向量。r 称为字符分割点。与经典g f s r 相比较，它在两个 方面有所改进： 1 ) 周期可以达到理论上界2 n w - r - l ( 初始值是0 的情况除外) 。 2 ) n 维的均匀性很好( 线性同余发生器最高只能在5 维分布合理) 。 m e r s e n n et w i s t e r 的名字是起源于周期长度是m e r s e n n e 素数，现在有两类常用 的算法变量，区别是使用的m e r s e n n e 素数的大小。用于3 2 字符长的是m t l 9 9 3 7 ， 6 4 字符长的是m t l 9 9 3 7 6 4 ，当然产生的序列不同。最常用的m t l 9 9 3 7 有如下几 个特点： 1 ) 周期达到2 1 9 9 3 7 ，在实际中，很少会用到周期更大的发生器。 2 ) 序列具有高维均匀性，但是同样要注意不能忽略输出序列连续值的连续相 关性。 3 ) 算法运行快速。 4 ) 通过了包括d i e h a r d 检验包在内的所有统计检验。 5 ) 安全性不好，如果能观察到循环产生的足够多的序列( 在m t l 9 9 3 7 情形下 需要知道6 2 4 个) ，人们就能够预测出以后将产生的序列。 9 重庆邮电大学硕士论文 第二章高斯随机数发生器原理与实现方法 2 2 高斯随机数发生器实现方法 高斯随机数发生器产生的随机数的概率密度必须符合高斯分布的要求，高斯 分布也就是正态分布，标准的正态分布n ( o ，1 ) 表示的函数的意义是其期望为0 ， 方差为1 ，其概率密度函数 d f ) 为： 烈曲2 去p 。2 陀 式( 2 l o ) 分布函数( c d f ) 为 ( x ) = 矽 ) a x = e l + e r f ( 击2 2 ) 式( 2 1 1 ) 1( x ) = i 矽( x = 式( 2 ， 二者的曲线图如图2 1 所示： 图2 1 高斯分布p d f 和c d f 曲线 实现高斯分布的算法有很多，但是都是从p d f 曲线和c d f 曲线和高斯样本值 入手，下面主要介绍几种常见的算法。 2 2 1 均匀变量求和法 中心极限定理( c l t ) 为产生具有高斯p d f 的随机变量提供了一条很好的途径。 c l t 表明，在很好的广义条件下，在当n _ 时，n 个独立随机变量之和的p d f 收 敛为高斯随机变量的p d l 假设有n 个独立的均匀随机变量u i ，i = l ，2 n 。由这n 个均匀随机变量可以 构成如下随机变量： 1 0 重庆邮电大学硕士论文 第二章高斯随机数发生器原理与实现方法 r = b z ( u ；一i 1 ) 式( 2 1 2 ) 其中b 是常量，决定】r 的方差。由c l t 可知，当- - - c o 时，收敛为高斯随机 变量。因为e ) = 1 2 ，所以y 的均值等于： e f t = b ( e 戤) 一i 1 ) = 0 式( 2 1 3 ) 因为珥- 1 2 的方差为： v a t u , 一互1 ) = j - 1 1 ，2 2 x 2 出= 西1 式( 2 1 4 ) 可以由此得到y 的方差。因为假设了各随机变量u 是相互独立的。 嘭= 召2 v a r u , 一书 式( 2 1 5 ) 于是有： 盯：= n b 2 1 2式( 2 1 6 ) 因此，给定值，通过选择合适的召值，就可以将y 的方差设定为所需的任 意值。所以选定时要折中考虑速度与所得p d f 拖尾的精度，通常取1 2 ，因为 这样会给出简单结果b = o r 一 虽然根据中心极限定理产生高斯随机变量的过程简单直接，然而，在试图将 其应用到数字通信的实际问题时，会遇到一些较大的困难。首先，因为一1 2 的 变化范围是从1 2 到1 2 ，由式( 2 1 2 ) 可知y 值在一b n 2 到b n 2 之间变化，因此， 尽管该式可以在均值附近很精确地近似高斯随机变量的p 矽，但是p d f 的拖尾被截 短到+ b n 2 。由式( 2 1 6 ) 可以推出曰的值为： 曰= q 丽 式( 2 1 7 ) 因此，“近似高斯p d f 被截短后，只在以下区间内取非零值 ：t t r , , n 4 1 2 n 2 = _ + t r y 3 n 式( 2 1 8 ) 当n = 1 0 0 时，高斯随机变量在+ 1 7 3 2 t r y 处被截短。对于有些应用来说，在1 7 倍标准偏差处截短，基本满足使用的要求，但是对于实现来说，耗费的存储资源 将非常惊人。 2 2 2b m ( b o xm u l l e r ) b m 1 5 1 算法是一种基于分布转化的方法，设有两个独立的高斯随机变量x 和 】，具有相同的方差盯2 。由于x 和】r 相互独立，联合概率密度函数等于边缘概率 重庆邮电大学硕士论文 第二章高斯随机数发生器原理与实现方法 密度的乘积。 厶( 训= 志e x p ( 一砉) 志e x p ( 一告) = 嘉e x p ( 一可x 2 + y 2 ) 加1 9 ) 令x = r c o s o ，y = s i n o ，则有 夕+ y 2 = 产 式( 2 2 0 ) 0 = t a n 一x )式( 2 2 1 ) 通过以下变换可由厶“y ) 求得联合概率密度函数厶化y ) ： 麓( 毛少) 私胂= 厶伉y ) 出肼 式( 2 2 2 ) 其中拟胂和击分别表示在凡o 平面和x 、】，平面的微分面积，由上式有： 厶( r 9 口) = f x r ( x , y ) 争i 。，嘶口 式( 2 2 3 ) 微分面积之比就是该变换的雅克比行列式，即： 惫= 矧o ( r = 黔d y d r 别d y 抬d o l 妣4 ， ，口) il 、7 化简得： 谢胛一c o s o 一，s i n o i 趔舳l s i n or c o s o i 所以有 厶( ，口) = 寺唧( 一驴t 2 ) ，o ， ，o 9 2 万 式( 2 2 6 ) 现在来考察r 和。的边缘概率密度函数。r 的p d f 为 肭) = r 石赤唧( 一吾瑚= ；唧( 軎) ，o 式( 2 ) 的p d f 为 厶( 臼) = r 2 z l t t 2e x p ( 一驴r 2 ) 办= 芴1 ，o 口 2 石 式( 2 2 8 ) 因此，可以看出r 是一个瑞利随机变量，o 是一个均匀随机变量。由于瑞利 随机变量可由两个正交的高斯随机变量产生，可以推出，瑞利随机变量的正交投 影可以产生一对高斯随机变量。因此，假设r 是瑞利随机变量，o 在( 0 ，2 z ) 上均 匀分布，则通过下面的式子可以产生高斯随机变量x 和y 。 x = r c o s ；y = r s i n o式( 2 2 9 ) x 和y 都是均值为零，方差为仃2 的随机变量。根据它们是高斯变量目不相关， 1 2 重庆邮电大学硕士论文 第二章高斯随机数发生器原理与实现方法 可以推出x 和y 为统计独立的。因此，一对独立的高斯随机变量可由一对均匀的 随机变量u 和通过如下算式产生出来。 肛堕c o s 2 万 式( 2 3 0 ) y = 、- 2 t r 2 l n ( u 1 ) s i n 2 7 t u 2 一、7 2 2 3 逆变换法 逆变换【1 6 1 7 】法可以将一个不相关的均匀分布的随机序列u 变换为一个具有概 率分布函数b ( x ) 的不相关序列x ，如图2 2 所示。 一怔乎 图2 2 逆变换方法 这个变换使用了一个无记忆的非线性器。由于非线性器是无记忆的，在输入 序列不相关时，能保证输出序列也是不相关的。当然，根据维纳辛钦定理，不相 关随机数序列的功率谱密度是常数。逆变换简单设定为： u = 目 式( 2 3 1 ) 并求解x ，得 x = 巧1 ( u ) 式( 2 3 2 ) 使用逆变换方法时要求已知分布函数最( x ) 为闭合形式。 很容易看出，逆变换方法能产生具有所需分布函数的随机变量。分布函数 最( x ) 是自变量x 的一个非减函数，如图2 3 所示。根据分布函数的定义 ，( 工) = p r x z 式( 2 3 3 ) 令x = 巧1 ( u ) ，考虑到目 ) 单调，所以有 ， 尾( 曲= p r f ；1 ( u ) 砖= p r 缈最( 功) = 日( 功 式( 2 3 4 ) 既得要求的结果。 i 。 u 丌 。 耳1 ( u 图2 3 概率分布函数 1 3 重庆邮电大学硕士论文第二章高斯随机数发生器原理与实现方法 然而，高斯反函数缺乏闭合的形式，因此，在实现上只有使用近似的方法。 最常用的方式是将高斯反函数利用级数展开来取来上述分析中的巧1 ( u ) 。 2 2 4 舍弃法 用于产生具有期望或目标p d f 的随机变量的舍弃方法，基本上都涉及到用函数 ( x ) 界定目标p d f , 这里g z ( 工) 表示一个易于产生的随机变量的p d f , m 是一个 满足下式的适当大的常数 m g x ( 功厶( 工) 全部x式( 2 3 5 ) 在简单的形式下，g x ( x ) 均匀分布在( o ，a ) 区间。如果目标p a y 厶 ) 在( o ，a ) 以外 为零，则有 蜊垆 6 _ 鬟砖口 式( 2 3 6 ) 由m g x ( 功界定厶( 曲，在上式中有b = m a m a x f ( 功) 产生高斯分布的舍弃法有z i g g u r a t 1 5 1 和极点法等，其中极点法主要包括四步： 1 ) 产生在( 0 ，1 ) 上均匀分布的u 和。 2 ) 令k = 2 u l - 1 ，砭= 2 u 2 - 1 ，使得k 和屹相互独立，且在区间( 一1 ，1 ) 上为均 匀分布。 3 ) 令s - - 4 v 1 2 + 呼。如果s 一l ，舍弃s 值并跳回第一 步。 4 ) 令a ( s ) = ( _ 2 盯2 l n s ) s 。 5 ) 令x = 么( s ) 矿i ，y = a ( s ) v 2 在第三步中舍弃了s 的一些值，因此，每次调用该函数，产生的随机数少于n 。 2 3g r n g 实现算法比较分析 高斯随机数发生器的实现方法是非常多的，每一种不同的方法也具有不同的 特点，关键就是选择一种适合实际环境的方法。利用f p g a 来实现数字化的高斯 随机数发生器有其自身的特点，主要包括以下四点： 1 ) 尾部精度：从高斯分布的p d f 曲线图2 1 可以看出，主要的概率事件发生在 零点附近，也就是说产生的随机数幅值范围主要集中在零附近，离中心零点越远， 发生的概率值越小，在随机数要求数目不多的情况下，该指标不是很重要，但是 要求产生大量的高斯随机数时，这种小概率事件就非常关键，因此，设计时必须 1 4 重庆邮电大学硕士论文 第二章高斯随机数发生器原理与实现方法 保证一定的尾部精度。 2 ) 资源消耗：影响资源消耗的主要因素是算法的复杂度，所以，必须选择一 种算法复杂度低，并且吞吐能力强的算法以使用于f p g a 设计。 3 ) 灵活性：灵活性主要是包括保证参数化的输出，标准的输入输出接口等。 4 ) 统计准度：输出的结果必须符合统计测试的要求，基本上达到高斯p d f 函 数的概率分布要求。 要完成达到上述要求也是非常困难的，比如要求尾部精度高的情