（物理电子学专业论文）turbo码的算法及实用化研究.pdf

t u r b o 码，简介是法国人b e r r o u 等在1 9 9 3 年i c c 上提出的一种采用重复迭代译码的并行级联码。模拟结果表明，如果采用大小为6 5 5 3 6的随机交织器，进行1 8 次迭代，则在e b n 0 _ 0 7 d b ，码率为1 2 的t u r b o码在a w g n 信道上的误码率p e 无穷3 、译码采用最佳的最大后验译码6 0 年代后期，g m l a g e r 和f o m e y 分别给出误码率的指数界。对于分组码，g m l a g e r 在采用随机码及最佳最大后验译码的前提下，给出下列指数界f 6 ：p 。e h 5 - 。( 1 2 1 )其中：l l 为分组码的编译码长度，e l ( r ) o 为可靠性函数，取决于不同的编译码方式。对于串接级联码f o m e y 在采用准最佳的广义最小距离译码前提下，提出了类似的下列指数界 6 】：p 。e 一2 岛脚( 1 2 2 )其中l 2 为串接级联码长，e 2 ( r ) o 为非随机级联码可靠性函数。上述两式中e l ( r ) l l 。对于卷积码，v i t e r b i 等也指出它具有类似的指数界【6 ：p 。e 一。，b ( 8 )( 1 2 3 )其中e i ( r ) e 3 ( r ) 。在高斯白噪声信道时，信道容量c - w l o g ： 1 + 去】( 6 州s )( 1 2 4 )上式为著名的s h a n n o n 公式，式中w 是信道所能提供的带宽，p 。= e j t 是信号概率，e 。是信号能量，t 是分组码信号的持续时间即信号宽度，p j w 是单位频带的信号功率，n o 是单位频带的噪声功率，p g ( w l q o 是信噪比。e ( r ) 与信道容量c 之间的关系可见参考文献 1 】上1 3 页图1 1 5 。由该图可知，e ( r ) 随信道容量c 的增大而增加，随码率r 的增加而减小。由上面几式可知，为了满足一定误码率的要求，可以由以下两类方法实现：一是增加信道容量c ，从而使e ( r ) 增加，由1 2 4 式可知，增加c 的方法可以采用诸如加大系统带宽或增加信噪比的方法达到。当噪声功率n 。趋向0时，信道容量趋于无穷，即无干扰信道容量为无穷大；增加信道带宽w 并不能无限制的使信道容量增加。增加发射机功率；应用高增益天线：采用分集接收及低噪声器件等通信中常用的方法都是通过增加信道容量c ，从而使e ( r ) 增加，以减小误码率。另外一种方法是在r 一定下，增加分组码长n ( 也就是增加分组码信号持续的时间t ) ，可使p 随n 的增加呈指数下降。但由于码长n 的增加，当r 保持一定时，可能使发送的码字指数增加，从而增加了译码的复杂度。这就是通过纠错码。信道编码就是通过增加分组码长来降低误码率。应用信道编码后，若仍要求传输信息的速率不变，则必须增加信道带宽，因此信道编码主要应用于功率受限而带宽不受限的信道中。s 1 4 纠错码简论。e 节中s h a n n o n 第二定理包含了两方面的含义：一是s h a n n o n 用随机编码方式证明了当r c 时，若n o o 则使p o 的好码是存在的，由此也给出了对给定信道通过编码方式在理论上所能达到的编码增益的上限，或传输每一信息位所需信噪比的下限；另一意思是为了达到这些理论限，应该利用最大似然译码a 五十年以来，纠错码理论的发展正是沿着这二条基本路线：一是构造码长n o o 好码；另一个是在人们所能接收的译码复杂性范围内，如何实现最大似然译码。1 4 1 线性分组码在s h a n n o n 提出通信系统的理论限的时候，h a m m i n g 和g o l a y 正致力于提出了第一种实用的编码理论，r i c h a r dh a m m i n g 发明了第一种纠错码- - h a m m i n g码( 汉明码) 。汉明码需要三位检验位来对应四位数据位，能够纠正一个错误。汉明码的提出是一个重大的发现，但是它的效率较低，且只能纠一位错误。m a r c e lg o l a y 通过研究汉明码的结构，g o l a y 发明了两种效果显著的编码方法，一是b i n a r yg o l a y 码，它由十二位数据位和十一位检验位组成，可以纠三位错；二是t e r n a r yg o l a y 码，它由六位t e r n a r y 数据位和五位t e r n a r y 检验位组成，可以纠两位错。汉明码和g o l a y 码都归属于线性分组码，线性分组码中的分组是指编、译码过程是按分组进行的，一般是按每k 个信息位一组，进行编译码；而线性是指分组码的编码特别是监督位是按线性方程生成的，其n k 位监督位是由k 个信息位的线性组合产生的。在线性分组码中，有一种重要的码称为循环码。它是在严密的代数理论基础上建立起来的。循环码除了具有线性码的一般特性外，还具有循环性，即循环码中任意码组循环一位( 将最右端的码元移至最左端，或反之) 以后，还是该码中的一个码组。b c h 码也是一类重要的循环码，它由发明这种码的三个人的名字”b o s e c h a u d h u r i h o c g u e n g h e m ”来命名的，它能纠正多个随机错误。r s ( r e e d s o l o m o n )码是一种具有很强纠错能力的多进制b c h 码。1 4 2 卷积码卷积码，或称连环码，是由e e l i s 于1 9 9 5 年提出的一种非分组码。卷积码编码中，本组的1 1 0 一k 0 个检验元不仅与本组l 【0 个信息元，而且与前面m 组信息元有关。同时，在卷积码译码过程中，不仅从此时刻收到的码组中提取译码信息，而且还要利用以前或以后各时刻收到的码组中提取有关信息。由于卷积码在编码过程中，充分利用了各组之间的相关性，因此，在与分组码同样的码率r 和设备复杂度的条件下，无论从理论上还是从实际上均已证明卷积码的性能至少不比分组码差，而且实现最佳和准最佳译码也较分组码容易【1 。但由于卷积码各组相关，因此，卷积码的分析比较困难，现在往往借助计算机的搜索来寻找好码。卷积码常用的三种较好的译码方法为：( 1 ) 1 9 6 3 年由梅西( m a s s e y ) 提出的门限译码，这是利用码代数结构的代数译码，类似于分组码中的大数逻辑译码；( 2 )1 9 6 1 年w o z e n c r a f t 提出，有f a n o 改进的序列译码，这是基于码树图结构上的一种准最佳的概率译码；( 3 ) 1 9 6 7 年由v i t e r b i 提出的v i t e r b i 算法，这是基于码的网( t r e l l i s ) 图基础上的一种最大似然译码算法，是一种最佳的概率译码方法。1 4 3 级联码长期以来，由于译码的复杂度高，构造信道编码的重点放在短码上，即寻找简单可译码的短码结构，并使其具有尽可能大的最小距离，如分组码和卷积码等。1 9 6 6 年，f o r n e y 首先提出利用两个短码串接构成的串行级联码。其典型类型是内码采用较简单的卷积码，外码采用较复杂的r s 码，纠错能力亦为两者串联乘积。传统级联码的实现框图如图1 3 所示：图1 3 级联码实现框图1 4 4t c m在二十世纪七十年代中期以前，纠错码编解码和调制解调都被认为是两个独立的部分。1 9 7 4 年梅西根据香农的信息理论最早证明了将编码与调制作为一个整体考虑时的最佳设计可以大大改善系统性能。u n g e r b o c k 等人在七十年代后期进行了这方面的研究，并与1 9 8 2 年提出了利用码率n ( n + 1 ) 的格状( t r e l l i s ) 码，并将每一码段映射为有2 一个调制信号集中的一个信号，在接收端信号解调器后经过反映射交换为卷积码的码序列，并送入维特比译码器译码的一种调制与编码相结合的方法，在不增加带宽和相同的信息速率下可获得3 - - 5 d b 的功率增益。由于调制信号和卷积码都可看成为网格码，因此这种体制就称为格码或网格码调制( t k l l i sc o d e dm o d u l a t i o n ) ，简称t c m1 4 5t u r b o 码香农定理证明，随机码是好码，但是它的译码却太过复杂。因此，许多年来随机编码理论一直是作为分析和证明编码定理的主要方法，而如何在构造码上发挥作用却并未引起人们的足够重视。直到1 9 9 3 年，t u r b o 码的发现，才较好的解决了这一问题，为s h a n n o n 随机定理理论的应用研究奠定了基础。t u r b o 码，又称并行级联卷积码( p c c c ) ，是法国人b e r r o u 在i c c 上提出的 5 7 。它巧妙的将卷积码和随机交织器结合起来，实现了随机编码的思想：同时采用软输出迭代译码来逼近最大似然译码。模拟结果表明，如果采用大小为6 5 5 3 6 的随机交织器，并且进行1 8 次迭代，则在e d n a 0 7 d b ，码率为1 2 的t u r b o码在a w g n 信道上的误码率p b _ l0 - 5 , 达到了近s h a n n o n 限( 对于二进制调制，普遍认为l 2 码率的s h a n n o n 限是e c n o = 0 d b ，p b o( 2 _ 2 5 甸【0扩 ( d k ) 0( 2 2 5 b )为了计算，引入三个概率函数：口：( m ) = 9 1 l 二铲p d 。= f ，& = m r ? ) ( 2 2 6 )i l k ( m ) = 鬻一( 月 ，脚，1 ) = 只 巩= f ，r 女，s i = m s = m )( 2 2 7 )( 2 2 8 )坝蝴馘( 郴) 2 等= 警拥得连接粹枷k 盟铲墨! 丝! 垡三! ：墨三竺：壁!p r t r 0 l r ：j( 2 2 9 )考虑到k 时刻以后的事件在状态值s k 已知的情况下，不受观察值群和d k 的影响，则有：只 r 。d ，= f ，s 女= m ，r ) = 只 d * 2 f ，s t因此连接概率的公式可改写为：以( 朋) = 口：( m ) 风( 聊)由附录1 可以得到：口；( 聊) =反( 埘) = m r ? 只 r 晶s = 卅) ( 2 2 - l o )y ，( r t ，m ，m ) 口f _ 1 ( m 。)m 。l = 0j = o ( r 。+ 。，m ，删) ，( m 。)。j = 0一( 2 2 1 1 )( 2 2 1 2 )( 2 2 1 3 )z z z z r ，( r k + l 聊，m ) 口f ( 埘)mmi = oj = oy ，( 墨，m ，朋) 由离散无记忆高斯信道的传输概率和编码网格图的传输概率决定：”( r i ，m ，珊) = p ( r d t = f ，s t = m ，s i 一1 = m 1 ) 留( d i = i s = m ，s 1 = m ) 石( s t = m s 女一l = m )( 2 21 4 )改善的b a h l 的算法步骤为：1 、假设口；( 州) 和风) 都初始化为下面关系式：口j ( o ) = 1a 0 ( m ) = 0 q m 0 ，i = 0 ，1芦0 ( o ) = 1风( 聊) = 0v m 0 编码器状态归零风( 0 ) = 1 m瓜( m ) = 0v m 编码器状态不归零2 、对于每一个观察值r k ，口：沏) 和”( r ，聊+ ，埘) 都能计算出来3 、当序列r l 已经完全接收时，尾( 埘) 也能计算出来，最后计算出五( m ) ，每个译码位也能因此计算出来。对于一( 毋，m 。，m ) 的计算，c b e r r o u 5 7 帛t lr o b e r t s o n 3 9 有不同的计算方法：a 、c b e r r o u 译码器c b e r r o u 认为外信息服从高斯分布，且与接收信道相互独立时，并假定输入信息比特具有( 0 ，1 ) 等概率出现的特征。上式中，p ( r k 破= f ，咒= m ，& 一。= m 。)为离散无记忆高斯信道的传输概率，由于x k 和y k 是两个不相关的高斯变量，因m一酬一嘲一川一竺。童j。生此：p ( 月 d = f ，s = 埘，s 一1 = 埘) = p ( 靠d = j ，s i = 埘，s = 珊) p ( y d = f ，s = 肌，s = 州)( 2 2 1 5 ) ；g ( 以：f 瓯= m ，s 。= m ) 为转移概率，当存在此转移路径时为1 ，否则取0 ；因为输入概率p r d k = 1 ) = n 以= 0 ) = 1 2 ，因为对于任意传输过程编码网格图的传输概率万( 最= m s k 一，= m 。) 均由输入概率决定，所以：万( 瓯= m s k l = m 。) = 1 2 ；( 2 2 1 6 )b 、r o b e r t s o n 译码器在这种译码器中，外信息被直接转换为先验概率，反映到公式：万( s k 刊* m ) = 等飘d k = o s k = m , s k _ l = m ) _ 1 ( 2 2 1 7 )，r ( s k = m s n = m ) = 南当g ( 以= 1 瓯= 州州s k= 聊) = l( 2 。2 1 8 )r o b e r t s o n 译码器其他计算与c b e = o u 译码器相同。2 2 3t u r b o 码的其他译码算法一、l o g m a p 算法对于m a p 算法，如果在对数域中进行计算，则称为l o c r - - m a p 算法。利甲i n -用兀t = p 7，可以得到：l o g a k ( 川) ：上d g ( 圭。c ”n ( 墨一川+ z * 一( m ) 一三昭一一ie l o g r , ( r k , m , m ) + l * 一( m 1 )f = 0mm t * 0( 2 2 1 9 )三o g p 女( 埘) ：三0 9 ( 1e ( ，m 。川+ l 鹕“m 。) - l o g 一一1e ( + ( m )r a + j 1 0m 。i m of 2 2 2 0 )二、m a x l o g m a p 算法令：瓦( m ) = l o g c t 女( 研)( 2 2 2 1 )反沏) = l o g l i ( m )( 2 2 2 2 )万( r t ，m + ，) = l o g ，( 胄i ，m ，m ) ( 2 2 2 3 )采用近似公式：上d g ( p 4 + p 如+ - + p 如) = f ；l m ，2 a x 匹i 2 l 、2 、3 n ( 2 2 2 4 )1 4所以上述三式近似表示为瓦( m ) m 。a x i ( - 触，珊。，m ) + 瓦( m ) ) _ m m ，a x ，膨啪。，珊) + 一o k - i ( m 。) ) ( 2 2 2 5 ) f nm z肌，l瓦 ) 。m 誓( 万( r 。，m ，m 。) + 万i 。) )m 、zm a x ( 万( r 。，坍，聊) + 瓦( 历+ ) ) ( 2 2 2 6 )研，m ，l懈) = 。m a 埘x ( - - 扎( r k ，m m ) + 瓦( m 。) + 万( 研) ) _ 川m ，a ，聊x ( - - ( 枷+ ，川) + 一c q _ 1 ( m ) + 万( 脚) )m mf h ，t hr 2 2 2 7 )r e a s o n 译码器的表达式表示为：l o g ? ， s = 州，s k l = m ) = z ( d 女) 一m a x ( o ，z ( d i ) ) 当g ( d k = o s 女= m ，s 一l = m ) = 1f 2 2 2 8 )l o g ? , s k = m ，s k l = m 。) = 一m a x ( o ，z ( d k ) ) 当g ( d k = 1 s k = m ，s k l = m ) = 1f 2 2 2 9 )这种算法称为m a x l o g m a p 算法三、t u r b o 码的其他译码算法t u r b o 码的其他译码算法：包括s o v a 、s w - b c j r 、m - b c j r 、t - b c 佩、m a x l o g m a p 、o s a 、h r - s o v a 、b r s o v a 算法等。s o v a 算法的全称是：软输出v i t e r b i 算法( s o f t - o u t p u t v i t e r b i m g o r i t h m ) ，它是由h a g e n a u e r 于1 9 8 9 年提出来的，它是v i t e r b i 算法的改进类型( v i t e r b i 算法是一种最大似然译码算法，它的译码过程是在接收序列r 的控制下，在码的网格图上重复编码器编码过的路径) 。其他译码算法也一般是从b c j r 算法和s o v a 算法演变而来的，这些算法可参见参考文献 1 】附录a 。2 2 4 主要算法的性能比较图2 7 主要算法的性能比较图如图所示：l o g m a p 算法远优于s o v a 算法。6 2 3t u r b o 码的研究进展2 3 1t u r b o 码的缺点l 、计算量大，要得到好的编译码性能，需要很长的码长和很多的迭代次数，在文 2 3 1 中的优异性能，是在码长为6 5 5 3 6 ，迭代次数为1 8 次的情况下取得的，这就增加了译码复杂性，而较短的交织器不可能达到好的性能，因此往往要根据实际需要来确定性能和计算复杂性之间的平衡来设计相应的t u r b o 码。2 、由交织和交织译码造成的时延使t u r b o 码在某些对时延要求高的通信系统中的应用受到限制。3 、理论分析困难。至今尚未有对t u r b o 码译码复杂性，比特误差概率完整的理论分析和估计。一般是通过数值模拟与单个卷积码、乘积码，级联码比较或不同译法之间作性能比较。文【6 、7 、8 】分析了t u r b o 码的性能，文 9 讨论了t u r b o码的有效自由距离，文 1 0 给出t u r b o 码的距离谱，文【1 1 】讨论t u r b o 码在随机或非随机置换下的重量分布，文 1 2 1 讨论t u r b o 码的重量分布，文 1 3 讨论了t u r b o 码的差错概率限。2 3 2t u r b o 码的主要研究方向1 、对总体t u r b o 码构造的改进研究最初的t u r b o 码是由二个卷积码并行级联而成，属于并行( p a r a l l e l ) 级联码的一种。最近又提出了串行( s e r i a l ) 和混合( h y b r i d ) 级联【1 4 2 0 ，据认为串行( s e r i a l )和混合( h y b r i d ) 级联码比并行级联码有着更好的性能。( a ) 并行级联交错码【1 和1 5 1复一编码器卜开接关器交织器l + |编码器zl +堇一兀图2 8 并行级联交错码结构图并行级联码由两路或多路编码器组成，输入信息一路直接输入编码器1 中，另外一路通过交织器交织后，输入编码器2 中进行编码。输入信息和多路编码器输出通过开关电路和复接器，可以改变得到不同码率的输出码元。( b ) 串行级联交织码1 6 1 8 1r r 1r _ 1输入1 外码编码器h 交织器h内码编码器r + 输出信息l 一l 一jl 一码元图2 9 串行级联交织码结构图串行级联码其编码器包括一个# b ! f - n j ( o u t e rc o d e ) ，一个交织器和一个内码( i n n e re o d e ) 事联而成，交织器将编码后的外码码字交织后作为内码的输入，为了得到高的编码收益，交织器必须很大，这时m l 译法就不适用，而改用一个次优的译码方案，即用二个软判决译码器分别计算内码和外码的a p p ，在一定的译码复杂性下，这种新的交错译码法= - - i e a 接近m l 译法的效果，达到较低的比特误差概率。( c ) 混合级联卷积码 1 9 ，2 0 】输信输出码元图2 1 0 混合级联卷积码结构图混合级联卷积码它是一个卷积码和由串联的一个外码和内码的级联码并行组成，有两个交织器，其中一个对信源输出的信息序列交织后传送到卷积码编码器，另一个将外编码器的输出交织后输入内编码器。其译码方案是对每一个码作一个软入软出和一个计算a p p 的交错译法，这种码可以达到比并行和串行级联码更低的比特误差概率。t u r b o 码可以由两个或多个卷积码组成，也可由二个或多个分组码如r s 码组成 2 1 。2 、交织器的设计研究 2 4 2 8 1交织器的设计要求能较好改善交织前后的相关性和距离特性，最常用的交织器为行列交织器。改进方案有单独根据改善迭代相关性来设计的交织器 2 6 】 2 8 ；有根据改善距离特性和迭代相关性来设计的交织器 2 4 1 ；有根据蚂蚁算法设计的交织器【2 7 】；最优周期交织器 2 5 1 等。3 、m a p 译码算法的改进研究 5 5 1b a h l 译码算法计算量很高，如何简化算法是一个重要的研究方向。采用l o g - m a p 算法、m a x - l o g m a p 算法、s o v a 算法等算法可以明显的减小计算复杂度，但带来的代价是译码性能的降低。改进m a p 算法的另一种方法是在每步译码保留m a p 前若干个最大的分量或删去低于某个阈值的分量，从而可以充分利用信息，降低总计算量 5 5 1 。2 3 3t u r b o 码的应用t u r b o 码从1 9 9 3 年诞生以来虽短短五年，但己显示出它的优越性，因此吸引了相当一批信息论和编码理论研究者及工程技术人员投入对它的理论和应用的研究。第三代的移动通信系统中已经选用t u r b o 码作为各类非实时业务高速数据的纠错码，同时，在短帧情况下，由于t u r b o 码在工程实现上的改进，使其在实时语音业务中的前景也逐渐看好。可以预料在未来的几年中会有更多更重要的理论和应用成果出现。第三章t u r b o 码的性能仿真及分析3 1t u r b o 码的仿真如图所示：是一个完整的通信系统。图3 1 数字通信系统简化模型t u r b o 码性能的分析和仿真，需要放在这样一个完整的仿真通信系统中。通信系统的仿真的过程中需要产生不同分布的随机变量，利用计算机可以很方便的产生不同分布的随机变量。不同分布的随机变量的基础是均匀分布的随机变量。有了均匀分布的随机变量，可以用函数变换等方法得到其他分布的随机变量。3 1 1 均匀分布随机数的产生一个均匀分布的随机变量的是由若干样本组成的，这些样本则是一个个随机的数据。由于计算机的算术单元的位长是有限的，因此计算出来的样本数也是有限的。与真正均匀分布的连续随机变量相比，这些样本并不是连续占据某个取值区间，但在运算器字长足够长的情况下，它所表示的值能比较密集的充满某个区间，因此仍然可以把它看作连续随机变量，但为了与真正意义上的随机变量区别，把它称为伪随机数。1 、同余法产生伪随机数的一种实用的方法为同余法，它利用同余运算递推产生伪随机数序列。最简单的方法是加同余法：y ”1 2 y n + c ( r o o dm )3 1 1 a= 等3 1 1 b式中，m o d 为取模运算。利用式3 1 1 递推公式，可以产生 o ，1 均匀分布的随机数。为了保证产生的伪随机数能在 o ，1 内均匀分布，需要m 、c 、y o 为正整数。加同余法比较简单，但产生伪随机数效果不好。另一种同余法为乘同余法，它需要两次乘法才能产生 0 ，1 上均匀分布的随机数y n + 1 2 a y n ( m o dm )3 1 2 a- = 等3 1 2 b式中a 为正整数。用加法和乘法完成递推运算的称为混合同余法，即：yn + 1 5 a y n + c ( m o dm )3 1 3 ah t = 等3 - 1 3 b利用混合同余法产生的伪随机数具有较好的特性。以上方法产生的伪随机数达到一定数目后，会产生周而复始的现象，也就是说存在周期。为了使产生的伪随机数具有较大的周期，更为接近真实的随机数，m 的取值越打越好，一般选择m - - 2 6 ，b 是所选计算机运算器的字长。m 选为2的幂也有利于减小运算量，因为可以用移位运算代替除以m 的运算。混合同余法要达到最大周期的条件：( 1 ) c 与m 互素；( 2 ) 对m 的任意素因子p ，a i l ( m o d m ) ；( 3 ) 如果4 是m 的一个因子，a ! l ( m o d 4 ) ：则产生的随机数可获得的最大周期为m 。而乘同余法和加同余法却不能获得最大周期。能达到最大周期的混合同余法的递推公式为：y 。+ l = ( 4 a + 1 ) y 。+ ( 2 b + 1 ) ( m o dm )3 1 4 ak = 等3 1 4 b式中，a 和b 为任意正整数。2 、利用c 或c + + 里的r a n d o m 函数或r a n d 函数，但实际应用中发现r a n d o m 函数或r a n d 函数产生的效果并不好。此外，这种随机函数产生的随机数，在每次仿真的时候都不一样，不利于仿真性能的对比。3 1 2 随机变量的仿真根据随机变量函数变换的原理，如果能将两个分布之间的函数关系用显式表示，那么可以用一种分布的随机变量通过变换得到另一种分布的随机变量。设x 是分布函数为f x ( x ) 的随机变量，且分布函数f x ( x ) 为严格单调升函数，令y = f x ( x ) ，则y 必为在 o ，1 】上均匀分布的随机变量。反之，若y 是在【o ，1 上均匀分布的随机变量，那么：3 1 5则是分布函数为f x ( x ) 的随机变量。巧1 ( ) 为f x ( ) 的反函数。因此，要求某个分布的随机变量，先产生在 0 ，1 】区间上的均匀分布随机数，在经过3 1 5 的变换，便可得到所需分布的随机数。3 1 3 高斯分布随机数的产生在系统仿真中，通常遇到的噪声都是正态分布( 即高斯分布) ，其概率密度函数为：f ( c ) 2 了历1e 伽岫3，似c 3 1 6数学期望为m ，方差为0 2 。常见的高斯分布随机数的产生的方法有两种：一种是变换法，另一种是近似法。1 、变换法式3 1 6 中随机变量的概率分布函数f ( c ) 为：f ( c ) = if ( x ) d x3 1 7上式很难用简单的函数形式表达出来，因此很难直接求出其逆映射。概率论理论指出具有下述概率分布函数的瑞利分布随机变量rf ( r ) = 0f ( r ) = 1 - e 一。2 2r 03 1 8 a3 1 8 b与一队高斯随机变量具有下述关系：c = r c o s p3 1 9 ad = rs i n 口3 1 9 b其中0 为一个在( o ，2n ) 范围内均匀分布变量，参数a 是c 和d 的方差。3 1 8 式f ( 鼬的反函数为：r = 2 j 2 i n 1 ( 1 一爿) 3 1 1 0其中a 是( o ，1 ) 上均匀分布的随机变量。产生( 0 ，1 ) 上均匀分布的随机变量b ，定义：目= 2 廊3 1 1 1则由3 1 9 可以得到两个统计独立高斯分布变量c 和d 。如果a 、b 是两种互相独立的均匀分布随机数，那么下式给出的c 、d 便是数学期望为m ，方差为0 2 的离散高斯随机数。- - - _ 。_ - - _ - 。_ _ - _ _ _ _ _ _ _ _ _ _ - _ 。_ - 。一c = 4 2 8 2 l n 1 ( 1 一爿) c o s ( 2 z b ) + m3 1 1 2 ad = 4 2 8 2 i n 1 ( 1 一彳) s i n ( z j r b ) + m3 1 1 2 b2 、近似法由中心极限定理，n 个在【o ，1 】区间均匀分布的互相独立随机变量x i( i = 1 2 n ) ，当1 3 足够大时，其和的分布接近高斯分布。首先获得【o ，1 】区间均匀分布的随机变量b ，因此：月( 五一i 1 )a = 型i = _ 兰_3 1 1 3胛1 2a 即为数学期望为0 ，方差为1 的高斯分布随机数。弘2 嚣兹鬟嬲嚣麓一个重要原因就是采用了随机交勰交t u r b o 码能取得极为优异的性能的一个重要原凼就是米用j 睫硼l 父珉需父织器的设计在t u r b o 码的设计中有着重要地位。3 2 1 常用的交织方式1 、分块交织器( a ) 行进列出分块交织器行进列出分块交织器，它原来用于抗信道的突发错误，在t u r b o 中也一样实用。它的交织方式是采用行顺序读入、列顺序读出的方式。如下表所示：匠巨玉五豇习互匾酉垂醉! 医l 习习堕匠( b ) 堆栈分块交织器 3 4 1 文中，提出了另j m - - - 种分块交织器的交织方式。交织方式如下表所示：等待交织的序列( c ) 分块斜对角分块交织器也有人提出了另外一种分块交织器：分块斜对角交织( 3 6 】。交织如表所示：等待交织的序列( d ) 比特翻转法比特翻转法交织器的产生过程为：( i ) 将序号a i 表示为二进制数( a i ) l o = ( a i j 1 ，a i , j - 2 ，a i0 ) 2( i i ) 将此二进制数颠倒得到( a i p ，8 i ，1 ，a i j ) 2 - ( b i ) t o ，则十迸制数b i 即为序号a i 对应的交织后的位置。交织方式如表所示：等待交织的序列012345670 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1x ox lx 2x 3x 4x 5粕x 7交织后的序列0 0 01 0 00 1 01 1 00 0 11 0 10 1 11 l l04261537x ox 2x 6x l冯x 3x 7分块交织器的结构比较简单，交织均匀，能有效的消除突发错误，但由于其固有的周期性，使得应变能力不强。2 、随机交织器( a ) 伪随机交织器线性转换式随机交织就是设法找到一个可逆的比特位地址映射关系t ，将长度为2 m 数据序列的每一比特从一个缓冲区送入另一缓冲区，即i l l _ n 1 t 。其中：m = a m - l ，a m - 2 ，a 0 为交织前的比特位地址；t 为m m 可逆矩阵。如果t 是g f ( 2 )上最高次为m 一1 的本原多项式生成元，且r 为循环右移算子，则t ：f t ，r t ，r m 2 t ，r m 。t 7 。这种交织器的优点是不需要专门的存储空间存放2 ”个映射地址，但是这样交织得到的码元序列仍然具有较强的相关性。随机交织器产生2 ”个有限地址矢量的基底是( 1 ，2 4 ，2 m - i ) ，即基于t 转换的交织器只有m 自由度。如果序列的每一比特位都赋予随机产生的映射地址，然后用查表的方式实现码元交织，那么交织自由度可达2 ”。相应的，交织后的码元间的相关性也大大降低，且随交织深度的增加而明显改善。如图为读表式随机交织算法示意表：等待交织的数据d ld 2d 3d 4d 5d 6d 7d 8d 9d l od l ld 1 2地址表交织后的数据d 4d l| d l od 8d 2d 1 2d 6d 3d 9d i ld 7d 5( b ) s 随机交织器在以往的t u r b o 码交织器设计的研究 2 5 1 1 3 5 1 表明：码字重量为2 的输入信息序列对低权重的码字的分布和产生有着较大的影响。所以交织器的设计要考虑如何打乱码重为2 的输入序列。s 随机交织器的设计就是要解决这个问题。s 随机交织器的产生步骤为：s 为预先选定的门限制。产生一个l 到n 的随机数，与前面已经选好的s 个数比较，若与其中任一个距离小于s ，则这个数被拒收，改为接收下一个整数。重复此过程直到全部n 个整数都找到为止。当s 堆栈。2 、几种随机交织器的比较( a ) 交织长度为1 2 8 性能比较图：图3 - - 4 交织长度为2 5 6 的随机交织器的性能比较图( b ) 交织长度为2 5 6 性能比较图：图3 5 交织长度为1 2 8 的随机交织器的性能比较图( c ) 采用同样的随机交织和和每块采用不同随机交织的比较图3 6 同样的随机交织和和每块采用不同随机交织的性能比较图( d ) 说明从以上四图可以明显看出s 随机交织器在各种环境下都有着最佳的交织性能，且交织能力随s 的增加而加强。保奇偶随机交织器在码率为1 2 的时候，有着较佳的性能。每个交织块采用不同的随机交织器并不能取得比所有交织器都采用同一个随机交织器更好的性能。3 、分块交织器、随机交织器的比较( a ) 分块交织器、随机交织器的性能比较图：图3 7 分块交织器、随机交织器的性能比较图( b ) 说明上两图说明，好的分块交织器的产生比随机交织器有更小的运算复杂度，但却有着不亚于随机交织器的性能。3 ，2 3 交织器的分析方法1 、由相关性分析 3 4 、3 6 、3 8 】【3 4 文中提出了一种用相关特性来分析t u r b o 码交织器性能的方法。作者认为在交织前后，位置发生改变的码字越多越好。定义：两个长度为n 的二值数据序列x x l ，x 2 ，x n ) y ；( y i ，y 2 ，y n )( x i ，y i 取值0 或1 ) ，其相关系数为：卫r x r = 2 二( 2 x ；一1 ) ( 2 y j 1 )3 2 1i = 1 3 6 文中根据这种分析方法，设计了斜对角交织器。但在 2 5 ，4 9 文中中，通过仿真和分析，否决了这种单纯按照相关性来分析设计的方法，认为相关性并不能作为一个好的交织器性铑的分析和设计的标准。本文作者对移一位交织器进行了仿真，移一位交织器即交织后的位置是将交织前位置移动位。按照【3 4 】分析，这种交织器应该具有较佳的性能，但实际仿真显示，这种交织器性能并不好。因此相关性并不能作为交织器性能的唯一判断依据。2 、由距离特性分析 2 5 ，3 7 ，4 8 5 4 由信道编码理论，码字的错误概率与码字的重量分布有关， 5 4 】文中从重量枚举函数的角度，定性地分析t i n ，k 】码在a w g n 信道中的性能，给出了误码率近似表示式：r = = 一p b ( e ) ；告d 。e r f c ( j m 学) 3 2 2其中d 。= 詈a 。d m 为错误系数，a w j 为具有输入序列重量为j 的码字，凡为编w + j o码效率，m 为整个码字的重量。由上式可看出交织器的设计可围绕增大码重m ，和减小错误系数d 。来考虑。 2 5 ，5 0 5 3 】等文中根据此原理尝试着设计了一些交织器，也都在一定环境下取得了较好的性能，证明了距离特性的改善确实能改善t u r b o 码的性能。但是交织器如何改善距离特性，什么样的交织器能最佳的改善距离特性，现在并没有很好的方法。3 2 4 交织器的作用小节通过上面的仿真及其分析，可以得出以下结论：l 、卷积码和随机交织器结合在一起。交织器可以将信道中产生的突发错误随机化，在与卷积码结合起来，更可以起到改变码的重量分布，使t u r b o码的编码输出序列中，码重轻或码重重的码字尽可能的减少，使重量谱窄带化。以往研究表明，通过交织改变t i l r b o 码的重量特性能有效地提高t u r b o 的整体纠错性能。2 、通过好的交织器改善两个译码器的相关性，可以使t u r b o 码的迭代译码法有更好的收敛性。减小输入数据和每个译码器软输出值的相关性。即交织器的设计和分析，即应当考虑到相关性，对迭代译码算法的改善；也应当考虑通过交织改善码重的分布，以取得更好的译码性能。这两个因素到底对交织器以及t u r b o 码性能的影响有多大；如何定性的分析这两个因素的影响：以及但是如何恰当的考虑这两个因素的影响，设计好的交织器。至今，还没有发现好的方法。作者认为：交织器对距离特性的改善能提高本身t u r b o 码固有的性能，即编码性能，交织器对相关性的改善能提高t i l r b o 码的译码性能。3 3t u r b o 码的译码算法对性能的影响3 3 1不同译码参数法的性能比较1 、不同编码结构的性能比较：图3 8 不同编码结构的性能比较图由上两图可以看出，t u r b o 的译码能力随码结构的复杂度的增加而更好。特别是在码率为1 3 的时候。2 、不同交织大小的性能比较：图3 9 不同交织大小的性能比较图由上两图可以看出，t u r b o 的译码能力随交织器长度的增加而更好。3 、不同迭代次数的性能比较：图3 1 0 不同迭代次数的性能比较图2 由上两图可以看出，t u r b o 的译码能力随迭代次数的增加而更好。但迭代次数达到一定时，性能改善不明显。s 3 3 2t u r b o 码的结构对性能的影响 4 7 缸7 文中对如图所示两种具有不同译码器结构的t u r b o 码的性能进行了比较。y 他y ，y 2 0图3 1 i a ：解码结构i图3 1 i - - b ：解码结构2【4 7 】文中的仿真结果表明：解码结构2 解码性能优于解码结构l ，并且有这更小的复杂度和更短的延时。3 3 3归零处理对t u r b o 译码的影响【1 】在m a p 译码算法中，前向递推口：( j ) 和展( j ) 初始值一般是根据分量编码器的初始状态和终止状态进行初始化的。对于普通的非系统卷积编码器，很容易将其初始状态和终止状态设置为一个已知状态，比如零状态。而对于t u r b o 码的编码器，由于是r s c 码，采用了递归结构，其分量编码器需要额外的结尾处理( t r e l l i st e r m i n a t i o n ) 才能达到终止于零状态，而且由于交织器的存在将两个编码器同时归零就更为困难。为此，对口：( s ) 和屏( j ) 的初始化一般采用以下几种方法：1 、r s c l 和r s c 2 均不归零2 、r s c l 归零和r s c 2 不归零3 、r s c l 和r s c 2 均归零【1 文中结论为：当交织器长度小于4 0 9 6 时，分量编码器终了状态的归零处理对t u r b o 码的性能略有改善；当交织器长度大于4 0 9 6 时，t u r b o 码不必归零。如下图为r s c 码编码器的一种归零方法：图3 1 2r s c 码编码器的一种归零方法结构图当接向开关为2 ，为正常编码；当接向开关1 时为归零处理。6 3 4t u r b o 码的一种改善的迭代译码算法3 4 1 简介t u r b o 码的模拟结果表明：采用大小为6 5 5 3 6 的随机交织器，进行1 8 次迭代，则在e b h i o 0 7 d b 时，码率为l 2 的t u r b o 码在a w g n 信道的误比特率b e r 一 ol k i = 一1当z k i of 3 4 3( 3 4 4 )( 3 4 5 )( 3 4 6 )令a = 一以。一，i ( 3 4 7 )当6( 3 4 8 ) 时，认为z k - l 和z k包含的信息相等。6 为迭代终止的判断门限。当l k 1 和l k 完全相等时，的值为0 ，当l k _ l 和l k 只有一个值不等时，的值为2 n ，当l k _ l 和l k 完全不等时，的值为2 。因此，在应用中可以取6 2 n( 3 4 9 14 、迭代终止判决方法二一由输出信息来判决输入信息的变化虽然可以反映输出信息的变化，但是直接利用输出信息的变化来终止迭代应更为有效。由于迭代译码过程为一个收敛的过程，当本次译码输出k ：( 以) 与上一次译码输出( 吨_ 1 ) 相比变化很小时，可以认为本次译码效果不明显，可以推测下一次译码效果会更不明显，因此，此时可以让迭代终止。这种迭代终止判决方法与方法一相比，只是将判决的标准由输入z k 改为了a 2 ( 以) 其余保持不变。3 4 3 迭代终止判决方法的性能分析1 、对于不同交织长度的改善：图3 1 6 采用判决方法一的性能比较图图3 1 7 采用判决方法二的性能比较图上面两图为交织长度为5 1 2 ，2 5 6 ，1 2 8 ，码率为1 2 ，s o v a 译码法，迭代次数初始化为1 8 次，不同信噪比时，采用了判决方法1 、2 后的实际迭代次数。由上图，两种方法对短码的性能改善都好于长码。在相同的信噪比条件下，迭代次数随交织长度的减小而减少，特别是在信噪比大于1 5 d b ，对原有算法复杂度的改善极为明显。2 、对不同译码算法的改善图3 1 8 、3 1 9 为初始化迭代次数为1 8 ，s o v a 译码法和l o g m a p 算法，码率为1 2 ，交织长度为2 5 6 ，不同信噪比时，采用了判决方法后的实际迭代次数。由图3 - 1 8 、3 1 9 ，新算法对l o g - - m a p 算法迭代次数改善好于s o v a 算法，特别是在信噪比小于2 0 d b 时。图3 - 1 曼墨鼻型决方法的性能比较图图3 - 1 9 采用判决方法二的性能比较图3 、对译码性能的影响图3 2 0 方法一、二的交织次数比较图图3 2 l 方法一、二的性能比较图从上述几图，可以看出新算法对迭代次数的改善极为明显，特别是判决方法二。采用判决方法一后，译码性能没有下降，采用判决方法二后，译码性能有轻微下降。3 4 4 小结本节中介绍了一种新的迭代终止判决的方法，由仿真结果可以看出，采用了这种迭代终止判决方法后，在几乎没有增加误码率的同时，原有的译码迭代次数大幅度减少，其中方法二对译码复杂度的改善更好。采用了迭代终止判决的算法与传统算法相比，只增加了n 个存储空间存储和少量的运算。增加的运算相对于减少迭代次数而减少的运算量而言可以忽略不计。这种方法在短码及中、高信噪比时和采用l o g m a p 算法时更为有效。因此这种迭代终止判决的方法有极佳的实用价值。第四章t u r b o 码的硬件设计4 1e d a 技术的介绍4 1 1 数字系统硬件设计概述 4 2 自计算机诞生以来，数字系统的设计历来存在两个分支，即系统硬件设计和系统软件设计。但是随着计算机技术的发展和硬件描述语言h d l ( h a r d w a r ed e s c r i p t i o nl a n g u a g e ) 的出现，这种界线已经打破。数字系统的硬件构成及其行为完全可以由h d l 语言来描述和仿真。用h d l 语言来描述和仿真数字系统的硬件构成及其行为是硬件设计领域的一次变革，对系统的硬件设计将产生巨大的影响。1 、传统的系统硬件设计方法的特点i 采用自下而上( b o t t o mt ou p ) 的设计方法i i 采用通用逻辑器件i i i 在系统设计的后期进行仿真和测试i v