（通信与信息系统专业论文）turbo码并行无冲突交织器的设计与仿真.pdf

摘要 摘要 t u r b o 码自1 9 9 3 年在瑞士日内瓦召开的国际通信会议上由教授c b e r r o u 等提 出以来，由于其在低信噪比下所表现出来的接近香农限的性能，有关t u r b o 码设 计及性能的理论研究成为国际信息与理论界的研究热点。随着人们日益增长的通 信需求，对译码时延的要求也愈发苛刻，故而如何降低高译码延迟成为需要迫切 解决的问题，而并行译码方法的出现大大提高了t u r b o 码的并行译码速度。但并 行译码存在的问题是交织器的随机特性可能会导致多个数据同时写入同一个存储 器，这就造成了存储器的访问冲突，进而会影响译码速度。如何设计出无冲突交 织器是并行t u r b o 译码器的难点。 近年来，一些性能优良的并行无冲突交织器的提出大幅度提高了并行译码速 度，但是这些无冲突并行交织器也存在一些不尽如人意的地方，本文建立了基于 t u r b o 码并行译码仿真平台，经过对现有交织器性能的大量测试后，提出了两种 新的并行无冲突交织方式：基于剩余定理的并行无冲突交织器和基于简单模运算 的并行无冲突交织器。前者是基于剩余定理的解的唯一性和并行无冲突交织器的 设计要求设计出一种运算较为简便，适合高度并行化的可变帧长的并行交织器， 而后者是在整环上利用简单的模运算生成的性能优良的任意长度并行无冲突交织 器。经过仿真验证并通过与现有交织器的比较、分析得知本文提出的两种交织器 获得了优良的性能并在某些方面较现有交织器具有一定的优点。 关键词：t u r b o 码并行交织并行无冲突交织器 a b s t r a c t b e c a u s eo ft h ep e r f o r m a n c eo fn e a r i n gt h es h a n n o nl i m i tu n d e rl o ws n r , t u r b o c o d e sa n di t sr e l a t e dt h e o r yh a v eb e c o m et h er e s e a r c hf o c u si nt h ef i e l do fi n t e r n a t i o n a l i n f o r m a t i o na n dt h e o r i e ss i n c es h o w nb yp r o f e s s o r sc b e r r o ut u r b oo ni n t e m a t i o n a l c o m m u n i c a t i o nm e e t i n gh e l di ng e n e v a , s w i t z e r l a n di n19 9 3 w i t ht h eg r o w i n g n e e d so fc o m m u n i c a t i o n , t h ed e m a n d i n gf o rd e c o d i n gl a t e n c yb e c o m em o r es t r i c t , t h e r e f o r eh o wt or e d u c et h eh i g h - d e c o d i n gl a t e n c yh a st ob ea i lu r g e n tp r o b l e m t h e n t h ee m e r g e n c eo ft h ep a r a l l e ld e c o d i n gg r e a t l yi m p r o v e dt h ed e c o d i n gs p e e do ft u r b o c o d e s b u tt h e r es t i l le x i s tap r o b l e mt h a tt h er a n d o mn a t u r eo fi n t e r l e a v e rm a yr e s u l ti n ac o n d i t i o nt h a tm u l t i p l ed a t as i m u l t a n e o u s l yw r i t t e ni n t ot h es a m em e m o r y , w h i c h c a u s e dm e m o r yc o l l i s i o n h o wt od e s i g nac o l l i s i o n f r e ep a r a l l e li n t e r l e a v e rb e c o m ea d i f f i c u l t yf o rd e c o d i n go ft u r b oc o d e i nr e c e n t y e a r s ， an u m b e ro fe x c e l l e n t p e r f o r m a n c ec o l l i s i o n - f l e e p a r a l l e l i n t e r l e a v e r sa r ep r o p o s e dt oi m p r o v ed e c o d i n gs p e e dd r a m a t i c a l l y , b u tt h e r ea r es t i l l s o m ed i s s a t i s f a c t i o n se x s i s t n ep a p e re s t a b l i s h e das i m u l a t i o np l a t f o r mo np a r a l l e l d e c o d i n go ft u r b oc o d e s a f t e ral a r g en u m b e ro fp e r f o r m a n c et e s t so nt h ee x i s t i n g i n t e r l e a v e r ，w ep r o p o s e dt w on e wp a r a l l e lc o l l i s i o n - f r e ei n t e r l e a v e r s ：c o l l i s i o n - f r e e p a r a l l e li n t e r l e a v e rb a s e do nr e m a i n d e rt h e o r e ma n das i m p l em o d e le o l l s i o n f r e e p a r a l l e li n t e r l e a v e r n 圮f o r m e ro n ei ss i m p l ei no p e r a t i o n , s u i t a b l ef o rh i g h l yp a r a l l e l v a r i a b l ef r a m el e n g t h , b a s i n go nt h eu n i q u es o l u t i o no ft h er e m a i n d e rt h e o r e ma n dt h e r e q u i r e m e n t sf o rd e s i g n i n gt h ec o l l i s i o n - f r e ep a r a l l e li n t e r l e a v e r a n dt h el a t e ro n ei s a l le x c e l l e n ti np e r f o r m a n c e ，r a n d o mi nl e n g t h , g e n e r a t e db ys i m p l em o d u l oa r i t h m e t i c o nt h ei n t e g r a ld o m a i np a r a l l e lc o l l i s i o n - f r e ei n t e r l e a v e ra f t e rs i m u l a t i o na n dt h r o u g h c o m p a r i s o n 、析t l lt h ee x i s t i n gi n t e r l e a v e r , w ef o u n dt h a tt h et w op r o p o s e di n t e r l e a v e r s a r ee x c e l l e n ti np e r f o r m a n c ea n db es u p e r i o ri ns o m er e s p e c t st h a nt h ee x i s t i n g i n t e r l e a v e k e y w o r d s ：t u r b oc o d e p a r a l l e li n t e r l e a v e rc o l f i s i o n f r e ei n t e r l e a v e r 第一章绪论 第一章绪论 1 1 研究背景及意义 s h a n n o n 在证明信息速率达到信道容量可实现无差错传输时引用了3 个基本 条件【1 】= 1 ) 采用随机性编译码。 2 ) 编码长度l 趋于无穷，即分组的码组长度无限。 3 ) 译码过程采用最佳的最大似然译码。 也就是说在信道传输，在信道传输速率r 不超过信道容量c 的条件下，只有 在码组长度无限的码集合中随机地选择编码码字，并且在接收端采用最大似然译 码算法时，才能使误码率接近为零。但是最大似然译码的复杂性随编码长度的增 大而增大，当编码长度趋于无穷大时，最大似然译码是不可能实现的。所以人们 认为随机性编译码仅仅是为证明定理存在性而引入的一种数学方法，在实际的编 码构造中是不可能实现的。 但是1 9 9 3 年，在瑞士日内瓦召开的国际通信会议上( i c c ) 上，法国不列颠 通信大学的教授c b e r r o u 、a g l a v i e u x 和他们的泰国籍博士p t h i t i m a j s h i m a 首次 提出了一种新型的信道编码方案- t 1 l m 码 2 1 。仿真结果表明，在采用长度为 6 5 5 3 6 是随机交织器，信噪比e 0 0 7 d b 并采用二进制相移键控( b p s k ) 调 制时，码率为1 2 的t u r b o 码在加性高斯白噪声( a w g n ) 信道条件下经过1 8 次 迭代译码后的误码率( b e r ) 1 0 ，达到了与香农限仅相差o 7 d b 的优异性能。 由于其令人惊异的优异性能，t u r b o 码一经提出，就受到了编码界的极大关注。 1 9 9 5 年，d d i v s a l a r 和ep o l l a r a 的通过仿真1 3 】得出t u r b o 码在a w g n 信道 上的误比特率很小，达到了近s h a n n o n 限的性能( 1 2 码率的s h a n n o n 限是0 d b ) ， 这一超乎寻常的性能立即引起了信息与编码界的轰动，并成为信道编码研究的热 点之一，它标志着信道编码理论与技术的研究进入了一个崭新的阶段，结束了长 期将信道截止速率作为实际容量限的历史。 t u r b o 码巧妙的将卷积码和随机交织结合在一起，实现了随机编码的方法， 同时，采用软输出迭代译码来逼近最大似然译码。t u r b o 码的提出，使信道编码 领域的研究发生了很大变化。早期人们主要基于代数结构进行编码和译码，现在 更重视基于概率的软判决译码方法。同时，t u r b o 码的提出也使得编码研究家不 仅重视理论分析，也更重视计算机仿真。 t u r b o 码的主要特点之一是在两个编码器之间采用了交织器，交织器在信息 序列进入第二个编码器之前对它进行交织，实现数据置换，这样可以保证第一个 2t u r b o 码并行无冲突交织器的设计与仿真 编码器产生小重量校验序列的输入序列以很大的概率使第二个编码器产生大重量 的校验序列。这样，即使分量码是较弱的码，产生的t u r b o 码也可能具有很好的 性能，这就是所谓的t u r b o 码的“交织增益 。 t u r b o 码不仅在性能上有所提高，在译码复杂度上也比串行级联码低很多。 如果采用随机编码，当编码长度增大时，纠错码的性能会接近s h a n n o n 限，但相 应的译码复杂度也会随之急剧增大，使得译码过程计算量过大而不可实现。t u r b o 码采用基于简单分量码的迭代译码算法来达到近似随机码的效果，这样就大大降 低了译码复杂度，而同时，t u r b o 码译码的复杂度主要取决于分量码的译码复杂 度和迭代次数。它的译码复杂性与分量码的状态数和迭代次数成正比，而与交织 器的大小无关( 交织器影响的是所需要的存储容量和译码时延) ，这也是t u r b o 码广受欢迎的重要原因之一。 2 0 0 4 年底，第三代移动通信系统标准化组织启动了关于3 gl t e 的研究和标 准化工作【4 j ，在3 gl t e 系统中依然采用t u r b o 码作为数据业务的信道编码，标准 l t e 要求译码速度达到1 0 0 m b p s ，而当时的译码速度只能达到5 0 m b p s 左右，而 多个译码器同时译码，即并行译码方法【5 】的出现大大提高了t u r b o 码的译码速度。 但与此同时并行译码存在的问题也显露出来，即交织器的随机特性可能会导致多 个数据同时写入同一个存储器，这就造成了存储器的访问冲突。故而如何设计出 无冲突交织器是并行t u r b o 译码方式的重点与难点。 1 2 相关内容研究现状 t u r b o 码以其优异的性能，促进了信道编码性能的提高，也使得t u r b o 码在 很多领域，如移动通信、深空通信、数字视频广播、卫星通信等得到广泛应用。 面对t u r b o 码的优异性能，人们首先希望能够在理论上对它进行解释。s e r g i o b c n e d e t t o 等人利用均匀交织器的假设条件推导出了t u r b o 码的归一化性能界【6 j 。 d d i v s a l a r 等人根据卷积码的转移函数，给出了t u r b o 码采用最大似然译码时的 误比特率上界 t i 。另外，d d i v s a l a r 等人根据系统卷积码的特点提出了有效自由距 离的概念【8 】。l c p e r e z 等人从距离谱的角度分析了t u r b o 码的性能1 9 j 。h e g a m a l 和a r h a m m o n s 将t u r b o 码迭代译码中的s i s o 处理单元看做是一个信噪比增益 器，将迭代译码结构看做是一个非线性动态反馈系纠1 0 1 。d a r i u s hd i v s a l a r 等人利 用密度演进分析了t r u b o 码的收敛性【1 1 1 。s t e n b r i n k 提出了用外信息转移图 ( e x i t ) 图来分析迭代译码的收敛性【1 2 j 。 为了降低t u r b o 码的译码复杂性，人们希望能够降低分量译码器的复杂性。 在降低分量码译码器的复杂性方面，比较有代表性的次优译码算法有软输出的 v i t c r b i 算法( s o v a ) 、m a x l o g m a p 算法、s w - b c j r 算法和t - b c 瓜算法等。 第一章绪论 3 这些算法以少许的性能损失为代价而获得了较低的实现复杂性，从而推进了 t u r b o 码的实际应用。 交织器的设计也是t u r b o 码设计的一个重要方面，交织器设计的好坏直接影 响t u r b o 码的距离谱和性能。交织器主要分两类：规则交织器和随机交织器。通 过对随机交织器进行限制，可以得到满足不同要求的交织器。k a n d r e w 对交织器 的数学理论进行了研究【1 3 1 。w j b l a c k e r t 设计了使两个分量编码器同时归零的分组 交织器【1 4 1 。为实现对删余t u r b o 码信息比特的等差保护，a s b a r b u l e s c u 和 m s c h o 分别提出了保奇偶交织器【1 5 】和模k 交织器【1 6 1 。j y u a n 提出了分量码与 交织器的联合设计方法【l 丌。 信道编码中交织器的作用一般是对抗突发错误，在t u r b o 码中，交织器除了 以上的作用外，还起到一个更重要的作用，即改变码的重量分布，将原始信息序 列置乱，使得交织前后的信息序列的相关性减弱。交织长度越长，随机性越高， 相邻反馈信号的相关性就越低，从而可以很好地实现迭代译码。交织器的设计直 接影响到整个码的性能，而什么是最好的交织方法一直没有定论。 目前交织器的研究主要集中在可实现强、时延短的交织器设计。t u r b o 码中 ， 交织嚣的主要作用是为了降低各分量编码器输出的校验比特之间的相关性，以取 得更好的迭代译码性能。所以交织器的设计对t u r b o 码，特别是短帧t u r b o 码，。j j t 至关重要。根据不同的设计准则，t u r b o 码的交织器可分为两大类，确定性交织 器和随机交织器。 随机交织器就是将数据序列中元素的位置按照伪随机方式进行重置，从而得 到交织映射方式。s 随机交织器是一种改进的随机交织器，在1 9 9 9 年被首次提出， 通过限制相隔小于s 的两个信息比特在交织后距离一定要大于s ，扩展了低重输 入序列，提高输出码字重量，从而获得较伪随机交织器更好的性能。许多学者如 h 1 ls a d j a d p o u r , c f r a g o u l i ，pp o p o v s k i ，l d i n o i ，w ：f e n g , j h y u a n 和z h o n g y u 等又分别提出了改进的s 随机交织器【1 8 瑙】。h rs a d j a d p o u r 等在2 0 0 1 年提出了 一种基于迭代译码适应准则( i t e r a t i v ed e c o d i n gs u i t a b i l i t yc r i t e r i o n ) 设计的s 随机 交织器。wf e n g 等在2 0 0 2 年提出了编码匹配交织器也是基于s 随机交织器设计 的，通过减少最低码重码字个数来降低误码率。z h o n g y u 等在2 0 0 4 年提出了 一种混沌交织器，与随机交织器和s 随机交织器相比具有复杂度低，系统时延短， 参数少的优点。 当t u r b o 码采用随机交织器时在编码端和译码端都需要一张交织表，而在一 些情况下。如帧长很长或有多个不同的大量的交织表需要存储时往往实现起来比 较难【2 4 j 。而确定性交织器因为交织和解交织表都可通过计算得到，不需存储交织 表，实现起来比较容易。确定性交织器往往可通过大量仿真选取能获得较好的最 小码距的参数，如s c r o z i e r 等在2 0 0 3 年提出的d r p ( d i t h e r e dr e l a t i v ep r i m e ) 交织 4 t u r b o 码并行无冲突交织器的设计与仿真 器【2 5 1 。有些确定性交织器不仅能够获得比随机交织器更好的性能，而且实现起来 比较容易，如c j c o r r a d a - - - b r a v o 等在2 0 0 3 年出的基于置换多项式的交织器例， j s u n 和o s c a r y 在2 0 0 5 年提出的基于置换多项式的交织器【2 7 j 。 在并行交织方式方法被提出后，除了能够获得较好的性能的要求外，由于并 行冲突导致的时延使得无冲突并行交织器的研究成为热点。a j i t n i m b a l k e r 等提出 正则置换( a r p ) 和二次多项式置换( q p p ) 并行无冲突交织i 器r 2 8 】较随机交织器 具有优异的性能且解决了存储器冲突的问题。j i n g - l i n gy a n g 在2 0 0 9 年提出的通 过最优化内存重映射交织方式1 2 , 9 ，利用重映射方法解决了内存冲突，使得非并行 交织器在重新映射后达到无冲突状态，减小译码时延。这些性能优良的并行无冲 突交织方法的提出大幅度提高了并行译码速度，但是这些无冲突并行交织器也存 在一些不尽如人意的地方，比如需要存储大量参数、块长度与并行度限制、无意 义译码时延、特定长度译码性能差等。本文建立了基于t u r b o 码并行译码仿真平 台，经过对现有交织器性能的大量测试后，提出了两种新的并行无冲突交织方式： 基于剩余定理的并行无冲突交织器和基于简单模运算的并行无冲突交织器。经过 仿真验证并通过与现有交织器的比较，分析并得出两种新交织器的优点和适用的 情况。 1 3 论文主要工作及章节安排 本文主要对现有的并行交织器进行了大量仿真，并在分析后提出两种新的并 行交织方法，最后对交织结果进行对比分析得出结论。主要工作如下： 首先，深入了解t u r b o 码的基本理论、编码译码方法、交织器作用与设计方 法、以及并行无冲突交织条件。 其次，建立t u r b o 码并行交织仿真平台，并对现有多个无冲突并行交织方法 进行仿真与性能分析。 最后，提出两种新的并行无冲突交织器，进行仿真并与现存交织器性能对比 分析后得出两种新的交织器的优点和适用情况。 一 本文分为五章，具体章节安排如下： 第一章绪论指出了本文的研究所基于的背景和研究的意义，并介绍了相关内 容的研究现状，最后介绍了本文的主要研究内容和章节安排。 第二章简要介绍了t u r b o 码基本理论、编码译码方法、交织器作用与设计方 法，最后介绍了并行无冲突交织条件及并行无冲突交织器的设计。 第三章详细介绍了现有的性能较为优良的并行无冲突交织器，在此基础上建 立t u r b o 码并行交织器仿真平台对这些现有交织器进行仿真并进行性能分析。 第四章通过对无冲突并行交织器设计方法的掌握和对现有无冲突并行交织器 第一章绪论5 仿真与性能分析，提出两种新的并行无冲突交织方式：基于剩余定理的并行无冲 突交织器和基于简单模运算的并行无冲突交织器。然后通过对两种新交织器与现 有交织器性能比较得出新的交织器的优点和适用情况。 第五章对全文进行了总结，并对后面进一步的工作进行了展望。 第二章t u r b o 码及并行交织理论7 第二章t u r b o 码及并行交织理论 2 1t u r b o 码基本原理 t u r b o 码通过使用交织器而实现了随机性编码的思想；将短码有效结合实现长 码，并采用迭代译码来逼近最大似然译码，达到了接近s h a n n o n 理论极限的性能。 本章将着重介绍一下t u r b o 码的编译码器结构及其性能影响因素。 2 1 1t u r b o 码编码原理 随着对于t u r b o 码研究的深入，人们发现串行级联结构也可以达到并行级联 结构的接近于香农限的优异性能，而且相比较于并行级联码，串行级联结构并没 有错误平层。这里，我们仅仅考虑了并行级联结构。图2 1 中，我们给出了含有 两个子编码器的t u r b o 码的编码结构框图。如果这两个子编码器为相同的递归系 统卷积码( r s c ) ，就构成了标准t u r b o 码【3 0 】。 复 用 图2 1t u r b o 码的编码结构框图 假设我们将信息序列分为长度为的分组，并分别进行编码处理。这样，对 于每个原始信息序列分组u = ( ，u 2 ，材) ，一方面被直接送入子编码器l ，从而 得到信息序列【，的检验序列x p l ；另一方面，原始信息序列【，经过交织器的处理 之后得到信息序列u = ( 研，“：，甜0 ) ，我们将这个信息序列送入子编码器2 ，从而 u 的校验序列x 彤。在得到x p l 和x p 2 之后，通常要对这两个序列进行删余，即 按一定的规则删去其中的一些校验比特，从而得到了最终的校验序列x p 。最后， 将系统比特x 5 和校验比特x ，复用在一起，我们就得到了最终编码后的码字x 。 即复用单元的作用是将这几路并行的数据流变为一路串行的数据流，得到一个完 整的码字。 一般来说，删余单元可以用相应的元素只有o 和1 的矩阵来表示。对于上述 的t u r b o 码来说，记删余矩阵为尸，它的每行对应一个编码器的校验序列删余模 式。那么对于第i 个子编码器的第，个校验比特来说，如果p ( i - 1 ，j ( m o d c ) ) 一0 ， 那么删去这个校验比特，否则保留这个校验比特。由于删余单元删去了一些校验 8 t u r b o 码并行无冲突交织器的设计与仿真 比特，它可以提高t u r b o 码的码率。 如果子编码器l 和子编码器2 的码率分别为墨和足，删余率( 即保留下的校 验比特所占的比率) 分别为和疋，这两个子编码器经删余后的码率就分别为 碍= 志和是= 百j 丽r 2 。很容易可以看出，随着和乞的增加，碍和 垦逐渐减小。同时，相应的码的码率就为尺2 面尚，它随着碍和 p 7 p 7 的减小而减小。 针对不同的信道状况，我们需要使用不同的码率。于是，如果只有两个子编 码器，为了得到不同的码率，我们可以通过改变子编码器的码率或者改变删余矩 阵这两个方式来完成。为了提高码率，可以提高分量编码器的码率或者是降低删 余率；为了降低码率，可以降低分量编码器的码率或者提高删余率，当然，也可 以通过选用含有多个分量编码器来达到这个目的。 那么对于标准t u r b o 码，如果有曷= 垦= 1 2 ，且不进行删余，即，i = 吃= 1 ， 那么最终得到的t u r b o 码的码率为1 3 。忽略有关时延，假定两个分量编码器同时 输出，则不采用删余技术时，t u r b o 编码器在第k 时刻的输出为砟= ( ，磁p l ，2 ) ， 其中彬和p 分别是两个子编码器在七时刻的校验信息比特。于是，如果不考虑 编码器归零，编码输出比特序列为毛，屯& h ，对这个序列使用b p s k 进行调 制时，在信道上发送的信息序列为q ，c 2 q c a , ，且有： q = ( ，p l ，簟2 ) = ( ( 2 一1 ) 属，( 2 1 1 ) 瓦，( 2 x f 2 - 1 ) 瓦) 式( 2 1 ) 经过信道传输、解调，接收机匹配滤波器在七时刻输出的采样值为 坛= ( 以，m p l ，2 ) ，译码器的任务就是从此接收序列来估计发送符号。 由于在具体的通信系统中采用t u r b o 码时交织器必须具有固定的结构，同时 是基于信息序列的，因此在一定条件下可以把t u r b o 码看成是一类特殊的分组码 来简化分析。但这不包括一类能够实现连续编码的面向流的t u r b o 码。如果交织 器的大小固定而且分量码的编码初始状态为零状态且对编码器进行迫零处理，则 t u r b o 码就是一个线性分组码。 在实际的工程应用中，如3 g 标准w c d m a 、t d s c d m a 等，分量码通常采 第二章t u r b o 码及并行交织理论9 用递归系统卷积码且进行迫零处理。一个码率为1 2 的( 7 ，5 ) 递归系统卷积码 ( r s c ) 的结构如图2 2 所示【3 1 1 。 2 1 2t u r b o 码译码原理 图2 2 ( 7 ，5 ) r s c 卷积码 一般来说，最优的译码算法是最大后验概率译码，而在先验等概的条件下， 最大后验概率译码等价于最大似然译码。 香农信道编码定理的证明中假设先验等价，因此要求译码采用最大似然译码， 使用最大似然译码算法的计算复杂性随着分组长度的增加而呈现指数增加，于是 分组长度太大时，对t u r b o 码直接进行译码不具有可实施性。 t u r b o 码译码的基本原理t 3 0 1 是把接收到的长码的复杂译码分成若干步，并通 过迭代的方法完成，计算复杂度得到很大程度上减小，但却可以达到逼近最大似 然译码的效果。即t u r b o 码虽然采用了次最优的迭代译码算法，但分量码采用的 是最优的最大后验概率译码算法，于是最终可使译码性能接近最大似然译码。众 所周知，软判决译码比硬判决译码能保留更多的信息量，所以分量码应该采用软 输入软输出译码算法。对应于t u r b o 码编码中的两个分量编码器，t u r b o 码的译 码是由两个软输入软输出译码器串行级联组成。在两个子译码器之间相互传递 “软 信息，以减少信息损失。 假定t u r b o 码译码器的接收序列为y = ( y 。，y p l , y ，2 ) ，校验信息经解复用之后， 分别被送给分量译码器d e c l 和d e c 2 。于是，两个分量译码器的输入序列分别 为： d e c l ：y l = 0 5 ，y p l ) d e c 2 ：y 2 = ( y sy ，2 ) 根据最大后验概率译码准则，t u r b o 码译码器的最佳译码策略是，根据接收序 列y 计算后验概率p ( u kly ) = p ( u 。i 乃，北) ，选取最大概率所对应的作为译码输 出。显然，这对于码长较长的码字来说，计算复杂度太高。在t u r b o 码的译码方 案中，将乃和咒分开考虑，由两个分量译码器分别计算后验概率p ( u il 少l ，罡。) 和 1 0 t u r b o 码并行无冲突交织器的设计与仿真 p ( u kiy 2 ，) ，并通过d e c l 和d e c 2 之间的多次迭代，使它们收敛于最大后验概 率译码的p ( iy l ，y 2 ) ，从而达到近香农限的性能。这里，e 。和置：为外信息，其 中骂。由d e c 2供，在d e c l 中用作先验信息，砭由d e c l 提供，在d e c 2 中用 作先验信息。 图2 3t u r b o 码译码结构框图 t u r b o 码的译码结构如图2 3 所示，它由两个软输入软输出译码器d e c l 和 d e c 2 串行级联组成，交织器与编码器中所使用的交织器相同。译码器d e c l 对 分量码r s c l 进行最佳译码，产生关于信息序列u 中每一比特的似然信息，并将 其中的“外信息 经过交织送给脚c 2 ，译码器d e c 2 将此信息作为先验信息， 对分量码r s c 2 进行最佳译码，产生交织后的信息序列中每一比特的似然比信息， 然后将其中的“外信息 经过解交织送给d e c i ，进行下一次译码。这样，经过 多次迭代，d e c l 或d e c 2 的外信息趋于稳定，似然比渐进值逼近于对整个码的 最大似然译码，然后对此似然比进行硬判决，即可得到信息序列u 的最佳估值矽。 分量码译码器在第f 次迭代时d e c l 和d e c 2 的软输出分别为： 牟( ) = 厶以+ 琶l ( ) 】( h “笃2 ( ) 】( ) 式( 2 2 ) 鹾( - ) = 厶蛾+ z ；2 f u k ) p + 【巧l ( u k ) p 式( 2 3 ) 整个迭代中，外信息的转移过程为： 脚c l d 肥2 _ 砸c 1 专d 嬲2 寸 其实，通过迭代译码结构来提高纠错编码方案性能的想法，最早出现在 g a l l a g e r 提出的低密度奇偶校验码( l d p c ) 码中。当时，g a l l a g e r 将信息划分为 内信息和外信息，并指出对迭代译码有用的只有外信息而已。外信息是译码过程 中得到的附加信息，与输入系统信息和先验信息无关。 第二章t u r b o 码及并行交织理论 在t u r b o 码译码器中，外信息经过交织或解交织器后送给另一个分量译码器 做为先验信息输入。迭代译码通过外信息的交换来提高译码性能。因此，外信息 是决定迭代译码性能的关键性因素。另外，由于只有外信息可用于迭代，那么在 迭代译码中，分量译码器之间的信息交换应不相关，即要求交织器应能最大限度 地置乱原信息序列。 由此我们可以看出：t u r b o 码译码的最大特点在于它采用了迭代译码结构，通 过两个分量译码器之间外信息的交换来提高译码性能。 2 1 3t u r b o 码性能影响因素 根据t u r b o 码的编译码结构及理论分析可以得出，影响t u r b o 码性能的主要 因素有三个： ( 1 ) 编码器中成员码的结构。成员码的结构直接关系到整个t u r b o 码编码码字 的最小距离，好的成员码应能够在给定限制长度和编码速率的基础上，尽可能地 提高码字地自由距离； ( 2 ) 交织器的设计。交织器设计的好坏会影响自由距离码字数目的多少，尤其 是在信息序列重量较低的情况下，交织器要能使第一个成员编码器输出低重码字 时，使第二个成员编码器输出的码字具有较高的码重； ( 3 ) 译码算法的选择。泽码算法是决定译码性能的关键因素之一，主要如何实 现性能与复杂度的平衡。 由此可见，交织器在t u r b o 码中的占有非常重要的作用，下一章将介绍交织器 的作用和设计原理。 2 2 1 交织器的作用 2 2 交织器作用与设计方法 很早以前人们就将交织器应用于通信系统中，典型的应用是当随机化传输序 列中出现错误时，可以采用纠随机错误的信道纠错码来纠正突发形式的错误：另 外一个应用就是在级联码系统的内码和外码之间，外码译码器的输出可能包含突 发错误，因此交织器设计的关键就是如何选择参数使其尽可能地分散突发错误， 使进入内码译码器的错误基本上是随机的。因此使用交织器的目的主要是抗信道 突发错误。即将信道或者级联码内码译码器产生的突发错误随机化，把由于受到 噪声干扰而导致具有相关性的数据恢复成相互独立的数据。而在t u r b o 码中，两 个r s c 编码器之间的交织器除了具有上述功能以外，还有一个重要功能一减小校 验比特之间的相关性，进而在迭代译码过程中降低误比特率。 1 2t u r b o 码并行无冲突交织器的设计与仿真 交织器使t u r b o 码中低重量的码字和高重量的码字数目减少，增加了具有“平 均”码重的码字数目，从而提高t u r b o 码的整体纠错性能。例如，假设输入信息 序列在r s c 编码器1 输出低重量的码字，那么由于交织器的存在，将r s c 编码 器2 的输入序列中比特分布模式适当改变，就避免了在r s c 编码器2 的输出端再 产生低重量的码字，从而提高了t u r b o 码的整体性能。由此可见，交织器的引入 改变了输入序列的距离特性。同时，t u r b o 码的强纠错能力还源于它在译码过程 中巧妙地利用了附加信息在子译码器问进行多次迭代译码地结果，而这些反映相 应信息位译码判决可信度的附加信息之所以能被相互利用，归功于插在它们之间 的交织与解交织器，即它们的“置乱 作用使在同一时刻送入各子译码器的信息 序列码元几乎不相关。综上所述，交织器的使用是实现t u r b o 码近似随机编码的 关键，交织器性能的好坏将直接影响到t u r b o 码的纠错能力，交织器的选择成为 t u r b o 码应用研究中的重要环节。 交织器很早就用于信道纠错码技术当中【3 2 1 。在以往的差错控制编码中，使用 交织器主要是为了抗击信道突发错误，即交织器可以将不可译的突发错误转化为 可译的随机错误。而在t u r b o 码中，除了上述作用外，交织器还要负责改善t u r b o 码的距离谱和提高迭代译码的性能。 大多数信道编码都是基于信道差错满足统计独立的特性而设计的【3 3 。，但实际 信道往往是突发错误和随机错误并存的组合信道，在这些信道中直接使用针对随 机错误的信道编码不好。交织技术是一种时间频率扩展技术，它使得信道错误的 相关度减小，这样，在传输过程中即使发生了成串差错，恢复成一条相继比特串 的消息时，差错也就变成单个或长度较短的差错，这时再用信道编码的纠错功能 纠正差错并恢复原信息。即交织器的存在可以使得不可纠正的成串错误转换成可 纠正错误。 在t u r b o 码的实现方案中，长码构造的伪随机性是决定码字性能的关键。在 发送端，其伪随机性是通过编码器中的交织器以及并行级联方式来实现的，在接 收端的译码器中，伪随机性是交织器、解交织器和反馈迭代译码共同作用的结果。 与信道传输时加交织以均化噪声、化突发差错为随机差错的目的有所区别，t u r b o 码的交织是为了防止信息的不良反馈；换一种角度，是为了让轻码交织成重码( 谱 窄化) ，让不可纠差错模式变为可纠模式( 噪声均化) ，也就是说，其主要作用是 对输入信息序列的比特顺序进行重置，使交织前后的序列相关性减小。好的交织 器能把低重量的输入序列中连续“l 的比特分散，当信息序列经第一个编码器编 码后得到的校验码重较低时，交织器能使信息序列在交织后进入第二个编码器编 码后输出的校验码有较高码重，从而保证总的编码输出码重。t u r b o 码通过交织 器就把两个系统分量编码器并行级联，从而使码字具有很好的距离谱特性，并且 通过迭代方式可以有效地译码。从而交织器的引入使信道编码的设计方法从增加 第二章t u r b o 码及并行交织理论 码字的最小汉明距离转向了减少低重量码字的个数。 总之，交织器设计的好坏直接关系着整个t u r b o 码系统性能的优劣，同时， 在接收端的译码过程中，需要恢复交织序列的原始数据符号，这个工作由解交织 器完成。因此，交织器所采用的交织映射函数必须是一一映射函数，这样才能保 证对数据序列解交织后其顺序与原始顺序的一致性。 常用交织器有分组交织器、随机交织器以及固定交织器等，有关交织器的设 计方法，在后面将得到讨论。 2 2 2 交织器的设计方法 b e r r o u 等人首次提出t u r b o 码的时候，对如何设计出好的交织器就曾有一些 建议，其中特别强调的是剐： ( 1 ) 增大分组长度( 实际上也就是交织器的长度) 将能提高性能； ( 2 ) 交织器应当能够将输入序列随机化以避免某些低重量的输入序列交织后 仍然不变，从而减小了t u r b o 码的有效自由距离。 - 以下，我们列出关于设计t u r b o 码交织器的几点基本要求【3 5 】： 1 ) 随机化 交织器对于信息序列的随机化将明显地影响到系统的性能，这一点在应用中 是比较明显的，并且已经得到了广泛承认。对交织器随机化的要求，一个重要原 因就是通过对低重量的信息序列进行随机化处理，从而使编码器输出的码字的自 由距离增大，以便达到提高性能的目的。 通常认为，随机化要求的另一个作用为它将会降低解码过程中校验序列的相 关性。这个理由和我们在传统的无线系统中使用交织器的理由非常接近，在该种 情况下，正是由于噪声样式中存在的时间相关性，此时应用随机交织器，将能够 有效的提高纠错编码的误比特性能。 此外，这里的随机化要求和即将提到的扩散化要求在某种意义上是矛盾的， 这两者要求之间存在着互为消长的影响关系。 2 ) 扩散化 为了将连续的突发错误扩散开来，需要使得在信息序列中接近的比特在交织 之后尽可能地远离，以防止连续错误比特在交织后仍然过于集中而导致无法进行 正常译码。这就要求在交织过程中相邻的s 个比特经过交织之后它们之间的距离 至少为s 。因此，交织器的扩散化要求也被称作是s 距离要求。一般来说，s 值 越大，t u r b o 码的性能也越好，但是交织器的生成也越困难。 3 ) 模k 特性 在t u r b o 码中为提高编码效率，通常可以在不改变编码结构的前提下通过删 1 4 t u r b o 码并行无冲突交织器的设计与仿真 余操作将t u r b o 码的码率提高。但是，由于进行了交织，因此对校验信息比特的 删余通常会导致对信息比特的不等差错保护。这是因为经过交织和删余后，某些 信息比特可能对应有多个校验比特，而某些信息比特则没有相应的校验比特。 通过对交织器的适当设计可以消除交织后对信息比特的不等差错保护问题。 奇偶交织器能够改善码率为l 2 的t u r b o 码的性能。这是因为奇偶交织器可以保证 信息序列中的奇数位置的比特交织后仍位于奇数位置，而偶数位置的比特交织后 仍位于偶数位置，从而可以确保第一个分量编码器输出的校验比特和第二个分量 编码器输出的校验比特经过删余后对应每个信息比特有且仅有一个校验比特保 留。 如果将限制放宽到模k ，k 2 ，则只有满足当i m o d k = 0 时，有 z r ( i ) m o d k = 0 以及当i m o d k 1 ，2 ，k - l 时，有，j r ( i ) m o d k l ，2 ，k - l 时 才是可以接受的。这样的交织能够在保持删余码模k 属性的同时引入更多的随机 性。 4 ) 对称性 一般情况下，交织器和解交织器是不同的，因此进行交织和解交织操作需要 不同的硬件设备和查找表。可以通过选择对称交织器来实现用一个交织矢量来完 成交织和解交织的过程。对于对称交织器，其交织过程和解交织过程是完全一致 的，即如果对数据序列进行两次交织运算，得到的输出序列仍为原来的数据序列， 因此只用一个交织矢量就可以完成交织和解交织过程。 由于在满足对称性时，交织过程和解交织过程只涉及到两个元素之间位置的互 换，因此可以大大降低交织和解交织过程的存储要求。 对称交织器的好处是可以简化系统实现的复杂性，同时从仿真结果也可以看 到，对称交织器的对称性可以引入一定的交织增益。 上述四点仅是交织器设计的一般要求，这些要求可以使得依照这些要求设计 的交织器译码性能不会太差，但具体的性能影响还要参考编译码方法及信道情况。 在并行译码的情况下，仅满足以上四点是不够的，因为内存冲突会导致译码时延 大幅增长。在下一节将会介绍并行交织理论及满足哪些条件的交织器在并行译码 中能够得到较好性能。 2 3 1 分块并行译码方法 2 3 并行交织理论 但是，随着对处理速度要求的提高，以及多处理器系统的发展，需要寻找比 以上方法更能提高数据吞吐量的方法。这里给出了一个方法，即采用分块并行处 理的方法，同时对形个子