（通信与信息系统专业论文）turbo码码字特性分析及其在高性能turbo编码方案中的应用.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 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 码自由距离和码字重量谱的研究尚 不充分。 本文首先回顾了信道编码理论，然后在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 码距离谱搜索 算法。其次，针对快速算法计算不尽准确的缺点，本文提出了基于 冲击响应分析方法的改进方案，使得计算结果更加准确，并针对计 算结果对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 码的编码端进行了改进，得到了更好的误比特率性能。 论文工作为进一步研究和改进t u r b o 码码字重量谱的搜索算法进 行了有益的探索，论文的有关搜索结果对于研究高性能t u r b o 编译码 技术有很好的参考价值。 关键词：t u r b o 码，距离谱，约束子码算法，冲击响应分析 a b s t r a c t t u r b oc o d e ，a ne r r o r c o r r e c t i n gc o d e sw i t hn e a rs h a n n o nl i m i t p e r f o r m a n c e ，a r er e g a r d e da sm i l e s t o n ei nt h eh i s t o r yo fc h a n n e lc o d i n g t h e o r y t h ei d e a so fd e s i g n i n gc h a n n e lc o d i n gi nt e r m so fi n c r e a s i n gt h e m i n i m u mh a m m i n gw e i g h ta r ec h a n g e di n t or e d u c i n gt h em u l t i p l i c i t i e s o ft h el o ww e i g h tc o d e w o r d s d u et ot h ep r e s e n c eo fi n t e r l e a v e r ，i ti s d i f f i c u l tt oa c c u r a t e l yc a l c u l a t et h ed i s t a n c es p e c t r u mo ft u r b oc o d e s l i k et r a d i t i o n a lc o n v o l u t i o n a lc o d e s n o w a d a y st h er e s e a r c ho ft u r b o c o d e sa r e e m e r g e d ，h o w e v e r ，t h ea n a l y s i so ft h ea c c u r a t ed i s t a n c e s p e c t r u mo ft u r b oc o d e si sn o ts u f f i c i e n t i nr e t r o s p e c tt oc h a n n e lc o d i n gt h e o r ya n dt u r b oc o d i n gs t r u c t u r e ， t h ec o m m o na l g o r i t h m sf o rt u r b od i s t a n c e s p e c t r u ms e a r c h i n g a r e r e v i e w e da tf i r s t b a s e do nt h ec o n s t r a i n e ds u b c o d ea l g o r i t h m ，t h em o s t e f f i c i e n t a l g o r i t h m f o rt h e a c c u r a t et u r b od i s t a n c e s p e c t r u m d e t e r m i n a t i o n ，am o r ee f f i c i e n ta l g o r i t h mc o m b i n e dw i t h i r e p u l s e r e s p o n s ea n a l y s i sm e t h o di sp r o p o s e di n t h i st h e s i st oe s t i m a t et h e m i n i m u mh a m m i n gw e i g h to ft h ec o n s t i t u e n te n c o d e rw i t hi n t e r l e a v e d i n p u to r d e r s f u t h e r m o r e ，s e v e r a li m p r o v e da l g o r i t h m sc o r r e s p o n d i n g t oi m p u l s er e s p o n s e a n a l y s i sm e t h o da r ep r o p o s e dt os p e e du pt h e c o m p u t a t i o na sw e l l i na d d i t i o n t h ed i s t a n c es p e c t r u mo ft u r b oc o d e i se m p l o y e di nt h ei m p r o v e dt u r b oc o d i n gs c h e m e si no r d e rt oa c h i e v e ab e t t e rb i te r r o rr a t ep e r f o r m a n c e t h ew o r ki nt h i st h e s i sp r o v i d e sh e l p f u le x p l o r a t i o no nf u r t h e rs t u d y a n di m p r o v e m e n to ft u r b oc o d e w o r dw e i g h ts p e c t r u md e t e r m i n a t i o n a l g o r i t h m t h er e s u l t s i nt h i st h e s i so f f e ru s e f u lr e f e r e n c ef o rh i g h q u a l i t yt u r b oc o d i n ga n dd e c o d i n gt e c h n i q u e s k e yw o r d s ：t u r b oc o d e ，d i s t a n c e s p e c t r u m ，c o n s t r a i n e d s u b c o d e a l g o r i t h m ，i m p u l s er e s p o n s ea n a l y s i s 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 通信的目的在于如何将信息及时可靠地传送给对方。快速和可靠 是衡量一个通信系统性能的最主要指标。为了提高系统的可靠性，对 抗信道的干扰，就必须采用差错控制技术。所以，纠错检错设备是通 信系统中不可或缺的组成部分。 伴随着信息理论和数字通信技术成长起来的纠错编码技术已经历 经了数十余年的长足发展。纠错码技术正是研究如何寻找一种在实际 上易于实现，而且能够达到有效可靠通信的编译码方法。如今，各种 纠错编码技术已经深入到通信、数据传输与存储等诸多领域，成为众 多的业界标准。其中，前向纠错技术( f e c ) 能够自动地发现并且纠正接 收信息中的错误，实时性好，所以，对它的研究也最为深入和广泛。 近年来随着电子技术和集成电路技术的发展，纠错编码技术不但早已 应用于实际的通信系统中，而且不断的有更高性能、更低功耗的译码 器出现。正是这种实际应用与纠错码理论研究的相互促进，使得纠错 编码技术获得了蓬勃的发展。在新一代移动通信系统和无线局域网中， 为了实现高速宽带数据的可靠传输，纠错码技术已成为关键技术环节。 而且随着研究的深入，纠错码技术已经不仅仅局限于收发双方的编译 码器，而是融入整个通信系统之中，成为涉及信道估计、均衡、映射 调制方式等诸多部分的整体差错控制技术。未来社会中，人们对高速 无线宽带通信的需求，以及日益紧张的无线频谱资源，必将导致纠错 编码技术的进一步发展。 1 1 信道编码理论的基本内容 现代信息和编码理论的奠基人c e s h a n n o n 在1 9 4 8 年提出了著名 的有噪信道编码定理 1 】，在定理中s h a n n o n 给出了在数字通信系统中实 现可靠通信的方法以及在特定信道上实现可靠通信的信息传输速率上 限。同时，该定理还给出了有效差错控制编码的存在性证明，从而促 进了信道编码领域研究的快速发展。 为更好地理解信道编码在数字通信系统中的地位和作用，下面首 先介绍通用数字通信系统的基本组成结构【22 。，如图1 1 所示。 图1 1 数字通信系统模型 图中信源编码器是将信源发出的消息如声音、图象等转换成二进 制或多进制形式的信息序列，信源通常包含冗余信息，这主要是因为 在信源中相邻符号之间存在一定的相关性，而且每个符号出现的概率 是不同的。为提高传输带宽利用率和信息传输效率，在信息传输之前 先利用信源编码器来消除这些冗余，可以利用最少的码元来代表要传 输的信息。传输信道存在一定的噪声和衰落，必然会对其上传输的信 息引入失真和信号判决错误，因此需要采用差错控制码来检测和纠正 这些比特错误。信道编码器的作用是在信息序列中嵌入冗余码元，提 高其纠错能力。与原始信息序列中的冗余码元不同，经过信道编码添 加的冗余码元的作用是减小传输中发生的信号和码元的错误，提高系 统的可靠性。信道编码是实现信号可靠传输的必要手段之一。调制器 将信息变换为适合信道传输的信号，解调器将收到的信号解调为二进 制或多进制形式的符号序列，通过信道译码器对错误进行纠正，再通 过信源译码器恢复成原来的消息。 s h a n n o n 通过信道编码定理指出：只要信息传输速率r 小于信道容 量c ，总存在使传输错误概率任意小的差错控制编码方法。也就是说， 对于一个给定的有扰信道，如果r c ，必定不存在有这种编码方法。因此，信道容 量是一个界限，在此界限之内，几乎可以无错误地传输信息，反之， 在此界限外，就不可能做到无错误地信息传输。 该定理包含三个方面的含义：一、采用随机编译码方法；二、编 码长度趋于无限长：三、译码过程采用最佳的最大似然译码方案。自 s h a n n o n 提出有噪信道编码定理以来，信道容量c 一直被认为是一种不 可达到的容量限，在实际信道编码中更多的时候是使用截止速率 ( c u t o f f r a t e ) r o 作为实际可以实现的信道容量。但t u r b o 码的出现，突 破了截止速率r o 的限制。t u r b o 码通过在编码器中引入交织器，使码字 具有近似随机的特性；通过分量编码器并行级联实现了通过短码构造 长码；在接收端采用了最大后验概率译码算法。由于其编译码方式充 分考虑了s h a n n o n 信道编码定理的假设条件，从而获得了接近s h a n n o n 理论极限的性能，这一理论成果一经公布立即在编码界引起轰动。目 前，在w c d m a 和e d m a 2 0 0 0 第三代移动通信系统中【4 2 】，支持高速分组 数据传输的关键技术之一就是t u r b o 码编译码技术 2 】f 1 4 1 ，中国的第三 代移动通信系统t d s c d m a 标准也采纳了t u r b o 码编译码技术。 从上世纪4 0 年代末开始，人们就不断的努力试图找出s h a n n o n 所说 的“好码”。在这一过程中，很多性能优良的码被发现，如b c h 码、r s 码、r e e d m u l l e r 码以及一些特定的卷积码等等，这些码在实际的通信 系统中得到了广泛的应用，并收到了很好的效果，但是这些码同 s h a n n o n 指出的信道编码极限仍有不小的距离，因为这些码都具有很强 的数学结构而不够“随机”。以至于人们开始对s h a n n o n 的论断产生了 怀疑。直到1 9 8 2 年，u n g e r b o c k 将编码和调制结合起来，提出了格状编 码调制( t r e l l i sc o d em o d u l a t i o n ，t c m ) 后，信道编码理论才有了大的突 破。格状编码调制在带限信道下能够比较接近香农极限，因此t c m 的 提出成为信道编码领域的一个重要里程碑。 在u n g e r b o c k 提出t c m 之后的1 0 年时间里，信道编码理论在通向 s h a n n o n 极限的道路上又陷入了困境，一直没有太大的进展。直到1 9 9 3 年，在i c c ( i n t e r n a t i o n a ii n f o r m a t i o nc o n f e r e n c e ) 大会上，c b e r r o u ， a g l a v i e u x 和p t h i t i m a js h i m a 提出t u r b o 码的概念。t u r b o 码巧妙地将卷 积码和随机交织器结合起来，实现了随机编码的思想：同时采用软输 出迭代译码来逼近最大似然译码。b e r r o u 等人使用约束长度为5 的子 码，采用长度为6 5 5 3 5 的交织器，在码率为1 2 时t u r b o 码经过1 8 次迭代 译码之后，在a w g n 信道上当e b n o o 7 d b 时的误比特率( b e r = l o 巧) ， 达到了逼近s h a n n o n 限的性能 3 】。t u r b o 码的提出更新了编码理论研究 的概念和方法，即编码理论的研究从早期的基于纯代数结构的构造与 译码方法，变为了现在主要是基于概率的软判决译码方法；编码方案 的比较也由以前的相互比较过渡到了现在大多与s h a n n o n 限进行比较； 同时部分编码理论家也开始变为实验科学家。因此，t u r b o 码被认为是 继1 9 8 2 年t c m 技术问世以来，信道编码理论与技术研究上所取得的最 伟大的成就，具有里程碑的意义。 由于文献【3 】中t u r b o 码的优异性能并不是从理论研究的角度给出 的，而仅仅是计算机仿真的结果。因此，t u r b o 码的理论基础还不完善， 对t u r b o 码的作用机制尚不清楚，对迭代译码算法的性能还缺乏有效的 理论解释，这促使了学术界对t u r b o 编译码方案的内在机制进行深入研 究和探讨【4 】【5 6 1 1 7 】。 1 2t ur b o 码的研究现状 s h a n n o n 理论证明，随机码是好码，但是它的译码却太复杂。因此， 多少年来随机编码理论一直是作为分析与证明编码定理的主要方法， 而如何在构造码上发挥作用却并未引起人们的足够重视。直到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 ) ，是由c b e r r o u 等在i c c 9 3 会议上提出的。它巧妙地将卷积码和随机交织器结合在一起，实现了 随机编码的思想，同时，采用软输出迭代译码来逼近最大似然译码。 文献 3 中的模拟结果表明，如果采用大小为6 5 5 3 5 的随机交织器，并 且进行l8 次迭代，则在e b n o 0 7 d b 时，码率为1 2 的t u r b o 码在 j 州g n 信道上的误比特率( b e r ) 1 0 一，达到了逼近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 码的发现，标志着信道编码理论与技术的研究进 入了一个崭新的阶段，它结束了长期将信道截止速率r o 作为实际容量 限的历史。 1 9 9 3 年t u r b o 码的论文发表之后，十余年来有众多研究人员对其 进行了深入广泛的研究和探讨，取得了一系列的成果，下面分几个方 西南交通大学硕士研究生学位论文第5 页 面进行阐述。 在t u r b o 码研究成果发表以后，人们首先面临的任务是理解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 码的本质仍缺乏全面透彻的认识。到目前为止，最有效的成 果是1 9 9 6 年发表在i e e et r a n s a c t i o n so ni n f o r m a t i o nt h e o r y 上的两篇 论文【5 】【6 】。在文献【5 】中，j h a g e n a u e r 等首次清晰地阐明了迭代译码 的原理，系统地给出了二进制分组码与卷积码的软输入与软输出译码 算法，包括m a p 与a p r i o r i s o v a 算法；提出了基于相对熵的迭代停 止判决条件；并基于计算机模拟结果指出，在低码率时由卷积码构成 的t u r b o 码性能较好，而在高码率时，由分组码构成的t u r b o 码的性 能较好。在文献【6 】中，s b e n e d e t t o 等首次提出了均匀交织器( u n i f o r m i n t e r l e a v e r ) 的概念，并基于此，从码的重量枚举函数出发，利用一致 界( u n i o nb o u n d ，也称联合界) 技术给出了t u r b o 码采用所有交织器时的 平均性能上界，启发式地说明了随着迭代次数的增加，迭代译码收敛 于最大似然译码，该文献也是首次系统地对t u r b o 码性能进行系统分 析。此外，在该文中，s b e n e d e t t o 等还探讨了分量码与交织器对t u r b o 码性能的影响，提出了交织增益的概念，指出增加交织深度可以减少 t u r b o 码在低比特错误概率( b e r ) 时的“错误平层( e r r o rf l o o r ) ”效应。 关于t u r b o 码的研究，近十多年来己经召开了三次( 9 7 年、o o 年、 0 3 年) 国际会议专门探讨其理论、技术及应用。t u r b o 码的研究已经由 单纯的计算机性能仿真发展到理论的建立，并有力地推动了检测，调 制，均衡等技术的发展。 总体归纳起来，围绕t u r b o 码编译码技术，国内外已有的研究工作 包括【3 8 3 9 4 0 4 1 】【4 3 】【4 4 】【4 5 】： 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 码与空时码； 西南交通大学硕士研究生学位论文第6 页 t u r b o 码在a w g n 信道、衰落信道中的性能研究； 深空通信中的低码率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 】中的优异性能，是在码长为6 5 5 3 6 ，迭代次数为 1 8 次的情况下取得的，这就增加了译码复杂性，而较短的交织器 不可能达到好的性能，因此往往要根据实际需要来确定性能和计算 复杂性之间的平衡来设计相应的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 码方案和性能： t u r b o 码在c d m a t d m a 等多址系统及m i m o 0 f d m m i m 0 u w b 系统中的应用： t u r b o 码编译码的v l s i 的实现； t u r b o 码的各种应用：在无线移动卫星通信中和在数据多媒体通 信中的应用。特别是在移动网络、移动计算以及个人通信系统等领 域中的应用。 1 3 论文研究内容和贡献 1 3 1 论文的研究意义 自从1 9 9 3 年c b e r r o u 3 等人提出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 码的性能分析和优化 编码设计中，t u r b o 码的自由码距，乃至重量谱特性扮演着非常重要的 角色【4 】【6 】。因此近年来，围绕如何分析、估计、乃至准确计算( 搜索) 出特定t u 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 u r b o 码距离谱特性搜索算法 具有重要意义。 根据t u r b o 码“谱窄化”特性，b l a c k e r t 等人针对模p 交织器，分 析了给定交织器长度条件下t u r b o 码“有效码距”( e f f e c t i v ed i s t a n c e ) 的理论上界：随后，b r e i l i n g 和h u b e r 采用组合分析方法，得出了更紧 的“有效码距”的理论上界。除了有关有效码距的理论分析而外，最 近针对特定t u r b o 编码器的自由码距或有效码距的搜索算法研究也很 活跃。b e r r o u 等人所提出的冲击错误( i m p u l s ee r r o r ) 算法【1 8 ，o b e r g 和s i e g e l 提出的重量2 输) k ( w e i g h t - 2i n p u t ) 算法，s e g h e r s 所提出的错 误事件( e r r o re v e n t ) 算法，为估计或准确计算t u r b o 码的有效码距或自 由码距提供了有效的手段和方法。但这些算法都存在着估计结果不尽 准确，或计算过于复杂等缺点。 1 3 2 论文的研究内容 通过分析、研究和比较国内外已有的t u r b o 码码字自由码距和距 离谱的搜索算法，我们得出如下结论：为了有效地搜索t u r b o 码码字 的自由码距和距离谱特性，必须充分考虑t u r b o 编码器分量编码、交 织器等内在因素对搜索算法的影响。近年来，g a r e l l o 等人一般性地提 出了准确搜索特定t u r b o 码自由码距，乃至重量谱的有效计算方法一 一约束子码算法【17 】。约束子码算法的最大优点在于其提供了在特定交 织器条件下高效搜索t u r b o 码自由码距或重量谱的有效算法。因此在 约束子码算法框架下，解决t u r b o 码自由码距搜索的关键问题转换为 寻找约束条件下t u r b o 码分量编码，特别是第二分量编码最小汉明输 出重量的计算或估计问题。g a r e l l o 等人采用修正v i t e r b i 算法来准确计 算约束条件下t u r b o 码第二分量编码最小汉明输出重量。为了避免在 交织长度较长情况下，克服修正v i t e r b i 算法计算过于复杂的问题， r o s n e s 等提出了一种在约束条件下估计第二分量编码最小汉明输出重 量的改进算法【2 9 】。 结合有关分析，本论文拟定如下研究目标：采用约束子码算法搜 索常用t u r b o 编码器码字自由码距和距离谱特性，并在此基础上对其 进行分析改进，得到具有更低错误平层和更好收敛性能的高性能t u r b o 编码方案。 针对论文的研究目标，论文的主要研究内容包括： 基于约束子码算法大框架下的冲击响应分析i r a 算法改进，用冲击 响应分析算法取代约束子码算法中交织后约束条件下对第二分量 编码器最小码重估算的修正v i t e r b i 算法。 结合i r a 和约束子码算法的t u r b o 码码字重量谱特性计算机搜索算 法。在搜索得到的码字特性基础上，对t u r b o 码的关键比特采用“伪 符号”方案，分析其对t u r b o 码性能的影响。 论文研究拟解决的关键技术问题包括： i r a 搜索算法； 结合i r a 和约束子码算法的t u r b o 码码字重量谱特性计算机搜索算 法； t u r b o 码编码器优化设计和性能分析。 1 3 3 论文的贡献 冲击响应分析算法( i m p u l s er e s p o n s e a n a l y s i s ，i r a ) 是q i n g c h u n c h e n 等人2 0 0 6 年在i t w 会议上提出的，结合i r a 算法的约束子 码算法是一种新的计算机搜索算法，也是论文工作的主要贡献。 基于单位冲击响应序列的快速算法来替代修正v i t e r b i 算法，实现 对约束条件下的第二分量编码器最小码字重量的快速估算。 此外，论文不仅关注于t u r b o 码自由码距的计算机搜索，还将通 过计算机搜索，分析具有较小汉明重量的t u r b o 编码器码字重量 谱特性，以及讨论非系统非对称编码器改进以及对关键比特改进 以后t u r b o 码码字性能分析。 1 4 论文的研究方法及组织结构 本文采用理论分析和程序仿真两种研究方法对t u r b o 码码字重量 谱性能进行了研究。论文以目前比较实用的约束子码搜索码字重量谱 算法为依据，对其中估算第二分量编码器最小重量的修正v i t e r b i 算法 进行了改进，程序全部在v i s u a l c + 十6 0 环境下调试编译得到相应的数 据结果。 本论文的组织结构如下： 第一章简单介绍了本论文的背景知识，s h a n n o n 信道编码理论， 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 编码方案。 最后总结了全文，并对论文下一步的工作方向进行了展望。 西南交通大学硕士研究生学位论文第1 0 页 第2 章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 码距离谱特性。此外， 针对t u r b o 码距离谱特性的常见搜索算法，以及距离谱特性在t u r b o 编码中的应用等问题进行了简单的描述。 2 1t u r b o 码编码器结构 1 9 9 3 年c b e r r o u 等人最初提出的t u r b o 码采用的是并行级联卷积 码的结构，即p c c c ( p a r a l l e lc o n c a t e n a t e dc o n v o l u t i o n a lc o d e ) 。图 2 1 给出了由两个分量编码器组成的t u r b o 码的编码框图。 叫分蚴码器l 卜_ l 交织墨l且生 舞 叫分t 编码量2 卜l 图2 1p c c c 的编码器结构 t u r b o 码编码器主要由分量编码器、交织器以及删余距阵组成。分 量码一般选择为递归系统卷积( r s c ) 码，这是因为r s c 所构造的t u r b o 码在纠错性能上要明显优于非反馈卷积码所构成的t u r b o 码。两个分 量码可以采用相同的生成多项式，也可以采用不同的生成多项式。 在t u r b o 编码过程中，两个分量码的输入信息序列是相同的，长 度为n 的信息序列l 1 在送入第一个分量编码器进行编码的同时作为系 统位输出u ，同时u 经过交织器交织处理后的交织序列n 送入第二个 分量编码器。两个分量编码器输入序列完全相同，所不同的仅仅是码 元的输入顺序。两个分量编码器输出的校验序列分别为p , q 。为提高码 西南交通大学硕士研究生学位论文第1 l 页 率和系统频谱效率，可以将两个校验序列经过删余距阵删余后再与系 统位输出i i 一起复接成完整的码字序列输出。 编码器中交织器的作用是实现t u r b o 码近似随机编码的关键。交 织器实际上是一个一一映射函数，作用是将输入信息序列中的比特位 置进行重置，以减小两个分量编码器输出校验序列的相关性，提高输 出码字的汉明码重。 卷积编码器是构造t u r b o 码的要素，所以t u r b o 码的表示方法也 是建立在卷积码的基础之上的。通常卷积码是不带反馈的，所以只有 前馈多项式，而r s c 码是带反馈的( 如图2 2 ) ，所以t u r b o 码的多项式 是由前馈多项式与反馈多项式来表示的，即g ( d ) = 刀( d ) 尉( d ) ，尼( d ) 是 前馈多项式，d ( d ) 是反馈多项式。对于图2 2 所示的t u r b o 码，其生成 多项式可以写成 g ( d ) ：掣：堡唑二：兰：2 ： 、7 d l d j 矗+ d i d + + d ，d 打) 一n o 十h i d + 开p 2 + + n , _ l d - i + h p d ( d ) 一d o + d i d + d 2 d 3 + + 如d 埘+ d p 图2 - 2 递归卷积编码器结构图 2 2t u r b o 码性能理论分析 2 2 1t u r b o 码的性能限 d d i v s a l a r 等在文献【7 】中假定交织器是随机独立置换，从卷积码 的转移函数出发，应用一致界( u n i o nb o u n d ，也称联合界) 技术给出了 t u r b o 码采用最大似然m l 译码时的比特错误概率上界。文献根据生成 多项式的性质，只考虑汉明重量为2 的自结尾序列的影响，给出了 t u r b o 码自由码距的上限和误比特率渐进特性的下限，文中还对在删余 情况下的自由距离进行了简单的讨论，并给出了在删余情况下自由码 距的上限。在文献【9 中，作者在只考虑汉明重量为2 的输入序列时用 几何分析方法，给出了t u r b o 码最小码距的上限。相关分析表明，t u r b o 码的最小码距随交织长度增加的速度不会大于码长的平方根。因此和 一般的线性码相比，t u r b o 码是渐进坏码。文献 1 0 】对一致限进行了更 深入地分析，作者分析了在各种不同交织器情况下一致界的偏差程度， 结果表明，在高信噪比时，尤其是当交织长度很大时，偏差逐渐趋于 零。由于一致界在低于截止速率r o 时发散，因此t md u m a n 等应用 g a l l a g e r 界技术对此进行了改进，在均匀交织的情况下，对并联和串 联t u r b o 码给出了适用于较大信噪比范围误码率和误比特率的更紧的 性能界 1 1 】。在文献【3 0 】中，作者将基于g a l l a g e r 界推导出来的“简单 界”( s i m p l eb o u n d ) 应用到串联t u r b o 码中删余t u r b o 码中，并得出了 一些有益的结论。文献 1 l 】对删余t u r b o 码的性能进行了研究。应用原 码的条件重量估算函数推导出了删余t u r b o 码的误码率的一个平均上 限，在推导过程中使用了超几何删余( h y p e r g e o m e t r i cp u n c t u r i n g ) 的方 法。并指出，使用超几何删截得到的特性要高于其它所有删截方案的 平均特性。 2 2 2t u r b o 码距离谱特性 近年来，围绕建立t u r b o 码性能的系统分析方法，相关的理论分 析成果主要包括基于t u r b o 码码字重量谱( 距离谱) 的性能分析方法 和t u r b o 码码字重量谱( 距离谱) 特性分析，以及t u r b o 码性能理论 界研究。 p e r e z 等人在文献【4 】中对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 w g n 信道条件下t u r b o 码的性能： 耶蔑等扑等 仁” 式中d ，c ，表示自由码距( 输出码字的最小汉明重量) 。b e n e d e t t o 等人 西南交通大学硕士研究生学位论文第l3 页 的研究结果表明，在均匀交织器假设条件下，随着交织器长度的增加， t u r b o 码的自由码距办。主要由汉明重量为2 的输入序列决定 6 】。d 。， 表示输出码字的最大汉明重量；月表示编码码率，表示交织器的长度； 讥表示重量为d 的码字的平均信息量，它可以通过下式计算得到： 2 苟 ( 2 - 2 ) 这里w d 表示所有重量为d 的码字所对应的输入序列重量的累积之和； 0 表示重量为d 的码字个数。t u r b o 码重量谱主要可以用三个参数来 表示，即码字重量西，重量为正的码字个数m ，以及所有输出码字重 量为t 所对应的输入信息序列的汉明重量累积之和w ，。 一般的，t u r b o 码重量谱可以用输入输出重量列举函数l o w e f ( i n p u t o u t p u tw e i g h te n u m e r a t i n gf u n c t i o n ) 表示： a ( w ，z ) = a 。：w ”z ( 2 3 ) 这里爿。：表示重量为d = w + z 的码字个数，其中w 是输入信息序列的重 量，z 是对应所产生的校验元的重量。更特别的时候，z = z l + ：2 ，z 1 z 2 分 别代表第一、第二分量编码器所产生的校验码重。显然， 虬= a ” ( 2 - 4 ) w + z - - d 文献【l o 】在对如( 2 1 ) 式所示的一致限进行深入分析的基础上，对 在各种不同交织器情况下一致界的偏差程度进行了分析。相关分析结 果表明，在高信噪比时，尤其是当交织长度很大时，一致界的偏差趋 于零。但由于一致界在低于截止速率r o 时发散，因此t m d u m a n 等 应用g a l l a g e r 界技术对此进行了改进，在均匀交织的情况下，对并联 和串联t u r b o 码给出了适用于较大信噪比范围误码率和误比特率的更 紧的性能界 1 1 】。g a l l a g e r 界定义如下： 令p 。定义码字j 。传输时，产生最大可能译码错误的概率，这个概率 由如下的上界定义： 阢伽却 阢k 。) r p ( 2 5 ) r1 其中彤卜) 定义了给定码字工传输下，信道输出y 条件密度函数。p 和a 是任意非负实数。 因此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 码的大致性能。这一点在对于t u r b o 码的编译码性能研究中相当重要，所以我们围绕t u r b o 码重量谱特性 的研究也就显得意义重大。 2 3t u r b o 码距离谱搜索算法 2 3 1 输入重量2 搜索算法 重量2 输入序列算法主要是根据p e r e z 的t u r b o 码距离谱特性分析 的相关结论所提出来的一种非常简化的搜索t u r b o 码的自由码距的算 法。采用s b e n e d e t t o 和g m o n t o r s i 等人所提出的均匀交织器( u n i f o r m i n t e r l e a v e r ) 的概念【6 ，p e r e z 等分析了在所有长度为的伪随机交织 器条件下t u r b o 码的平均距离谱特性，研究结果表明，t u r b o 码距离谱 存在所谓的“谱窄化”效应，即随着交织长度的增加，具有较小重量 的t u r b o 码字将主要取决于重量为2 的输入信息序列( 即w = 2 ) 。重量 2 输入序列算法的主要思想是只考虑输入重量为2 的信息序列所产生 的非零码字的汉明重量的最小值d 2 。显然，重量2 输入序列算法所搜 到的是t u r b o 码的有效距离( e f f e c t i v ed i s t a n c e ) ，通常而言。有效距离 要比t u r b o 码的自由码距大，即d 枷d 恐。根据p e r e z 研究的谱窄化效 应，在采用均匀交织器且交织器长度足够长的时候，那么重量2 输入 序列算法所搜到的t u r b o 码的有效距离就是t u r b o 码的自由码距，即 d 竹* = d 。r 衲2 。) 。 重量2 输入序列算法在实际t u r b o 码重量谱搜索中存在以下不足： 由于p e r e z 分析时所采用的理想均匀交织器在现实中难以实现，且一 般情况下交织器的长度要受到传输时延的约束而不能太长( 例如在 w c d m a 中，交织长度n 5 1 1 5 ) 。此外，对于实际的t u r b o 编码，很 西南交通大学硕士研究生学位论文第1 5 页 多情况下t u r b o 码的自由码距不是由重量为2 的输入序列所决定，即 d 触 d 矬。因此在更多的情况下，基于重量2 输入序列算法只能用于 粗略地估计t u r b o 码的自由码距，并进而用于初步评估t u r b o 码交织 器的设计等。此外，重量2 输入序列算法的有关结果还可以用于为其 他搜索算法提供待搜索自由码距范围。 2 3 2 错误事件算法 j s e g h e r s 较早提出了基于错误事件( e r r o re v e n t ) 的计算机搜索算 法来确定特定的t u r b o 编码器的最小自由码距。所谓错误事件，是指 那些能被t u r b o 码分量递归卷积编码器反馈多项式整除、且生成较小 汉明重量的输入信息序列( 通常长度远小于交织器长度 d 。其对应的编 码具有如下特征，即编码将从全零状态开始，并