（通信与信息系统专业论文）turbo码译码算法研究及其fpga实现.pdf

哈尔滨工程大学硕士学位论文 摘要 在通信系统中，人们一直致力于信息传输的有效性和可靠性的研究，信 道纠错编码技术一直是人们研究的重点。1 9 9 3 年，t u r b o 码的提出。以其接 近s h a n n o n 极限的优异的译码性能在编码界引起了轰动，并成为研究纠错编 码的热点课题。经过十几年的研究和发展，目前，t u r b o 码已经走向了实用 化的道路，如何用硬件实现有效的t u r b o 码编译码器成为了人们研究的重点。 论文以基于f p g a 实现t u r b o 码译码器为研究目标，首先分析了t u r b o 码的基本编译码原理和3 g p p 标准的t u r b o 码编码结构和交织算法。然后重 点分析了m a p 译码算法，l o g - m a p 译码算法和m a x l o g m a p 译码算法， 并对三种译码算法进行了详细的理论推导和计算复杂度的定量分析比较，对 影响t u r b o 码译码性能的主要因素进行了m a t l b 仿真分析。 论文在深入分析比较上述三种译码算法的基础之上，选择m a x l o g - m a p 译码算法进行了t u r b o 码译码器的f p g a 设计实现。主要针对f p g a 实现的 数据量化、定点数据表示方式、m a x l o g m a p 算法子译码器关键运算单元的 f p g a 设计和基于3 g p p 标准的t u r b o 码译码器的内交织的f p g a 设计进行 了深入研究，完成了固定译码长度的t u r b o 码译码器的f p g a 设计实现，并 利用m o d e l s i m 和m a t l a b 分别对译码器进行了功能时序验证和f p g a 定点 仿真测试。 关键词：t u r b o 码；f p g a ；m a x l o g m a p 译码算法 哈尔滨工程大学硕士学位论文 a b s t r a c t i nc o m m u n i c a t i o n s y s t e m s ，p e o p l ec o n s i s t e n t l y d e v o t et h e m s e l v e st o r e s e a r c h0 1 1e f f i c i e n c ya n dr e l i a b i l i t yo f d a t at r a n s m i s s i o n ，c h a n n e le n o rc o r r e c t i o n c o d i n g t e c h n o l o g yi sa l w a y st h ee m p h a s i so ft h er e s e a r c h s i n c et u r b oc o d ew a s p r o p o s e di n1 9 9 3 ，i th a sr e c e i v e dg r e a ta t t e n t i o na n db e c o m ear e s e a r c hh o ts p o t d u et oi t sn e f u - s h a n n o nl i m i t e dg o o dc o d i n gp e r f o r m a n c e a f t e rm o r et h a nt e n y e a r s r e s e a r c ha n dd e v e l o p m e n t ，t u r b oc o d eh a sb e g u nt oa p p l yi nt h er e a l c o m m u n i c a t i o ns y s t e m s n o w , h o wt oi m p l e m e mt h et u r b oe n c o d e ra n dd e c o d e r w i t hh a r d w a r ee f f e c t i v e l yh a sb e c o m ear e s e a r c hh o ts p o t i no r d e rt 0i m p l e m e n tt h et u r b od e c o d e rb a s e do nf p g a ，f i r s t l y , t h i st h e s i s h a sa n a l y z e dt h ef u n d a m e n t so ft u r b oc o d ea n dt h e3 g p pt u r b oe n c o d e ra n d i n t e r n a li n t e r l e a v ea l g o r i t h m s e c o n d l y , t h i st h e s i sh a sc a r r i e do nd e t a i l e dt h e o r y a n a l y s i sa n dc o m p u t e sc o m p l e x i t yc o m p a r i s o no fm a pa l g o r i t h m ，l o g - m a p a l g o r i t h ma n dm a x l o g m a pa l g o r i t h m a n dh a sa l s oa n a l y z e dt h em a j o rf h c t o r s a f f c c t i n gt h et u r b oc o d i n gp e r f o r m a n c e w i t l lm a t l a bs i m u l a t i o n s b a s e do ni n t e n s i v ea n a l y s i so ft h r e ed e c o d i n ga l g o r i t h m s ，t h i st h e s i sh a s a d o p t e dm a x - l o g m a pd e c o d i n ga l g o r i t h m t o c a l t y o nt h e d e s i g n a n d i m p l e m e n t a t i o no ft u r b oc o d eb a s e do nf p g a d a t aq u a n t i z a t i o n ，f i x e d - p o i n t p r e s e n t a t i o n , t h ef p g ad e s i g no fk e yc o m p u t em o d u l e si nm a x l o g m a p s u b - d e c o d e ra n di n t e r n a li n t e r l e a v e ri nt u r b od e c o d e ro f3 g p ps t a n d a r dh a v eb e e n d i s c u s s e d f i n a l l y , a 矗x e dd e c o d i n gl e n g t ht u r b od e c o d e rb a s e do nf p g ah a s b e e nd e s i g n e d ，a n df u n c t i o nt i m i n gv e r i f i c a t i o na n df p g a f i x e d p o i n ts i m u l a t i o n h a sb e e ns e p a r a t e l yc a r r i e do nw i t hm o d e l s i ma n dm a t l a b k e yw o r d s ：t u r b oc o d e ；f p g a ；m a x l o g m a pa l g o r i t h m 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和 文献的引用已在文中指出，并与参考文献相对应。除文 中已注明引用的内容外，本论文不包含任何其他个人或 集体已经公开发表的作品成果。对本文的研究做出重要 贡献的个人和集体，均己在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 作者( 签字) ：宙套面 日期：2 d d 7 年7 月z 于日 哈尔滨工程大学硕士学位论文 第1 章绪论 随着社会的发展和进步，信息的传播在人们的生产生活中起着越来越重 要的作用。现代通信正朝着宽带化、智能化、综合化和个人化的方向发展， 如何降低误码率，提高通信的可靠性，是这些新技术不可避免的问题。因此， 信道纠错编码的研究和使用仍然是当今通信领域研究的重要课题。 1 1 引言 1 9 4 8 年，信息论的开创者c e 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 c o m m u n i c a t i o n ) 的论文，标志着 信息与编码理论学科的创立。文中提出了著名的信道编码定理：任何一个通 信信道都有确定的信道容量c ，只要信息传输速率r 小于c ，则存在一种编 码方法，当码长n 充分大，并采用最大似然译码( m l d ) 时，译码的错误率 可以达到任意小。这种无差错传输必须满足以下3 个基本条件： 1 采用随机性编译码； 2 编码长度l m ，即分组的码组长度无限； 3 译码过程采用最佳的最大似然译码( m l ) 方案。 从s h a n n o n 信道编码定理可知，在信息传输速率r 不大于信道容量c 的 情况下，从码组长度趋于无穷大的码集合中随机的选取编码码字，并且在接 收端译码采用最大似然译码算法时，译码错误率可趋于零。虽然该定理仅仅 是一个存在性定理，没有给出具体实现差错控制编码的方法，但却从理论上 给出了纠错码的理论极限，同时也指明了纠错码研究的方向和目标。 正是在信道编码定理的指引下，编码理论的学者们为构造出好的长码和 译码复杂度可接受的译码算法而提出了很多的编码方案。 1 9 4 6 年，工作于贝尔实验室的数学家r h a m m i n g 提出了第一个差错控 哈尔滨| t 程大学硕士学位论文 制码汉明码，这个编码的方法成为了分组码的基本思想阁。随后g o l a y 在研究汉明码的基础之上，提出了两个以他自己名字命名的二元g o l a y 码、 三元g o l a y 码。1 9 5 4 年，m u l l e r 提出了r e e d m u l l e r 码9 1 ，并由r e e d 提出了 相应的译码算法h ，形成了比汉明码和g o l a y 码更为先进、实用的分组码。另 一个具有代表性的是纠错码是h o e q u e n g h e m 在1 9 5 9 年，b o s e 和 r a y c h a u d h u r i 研究组在1 9 6 0 年几乎同时提出的b c h 码”1 ，这是一类具有良 好的通用性和较高的编码效率，译码算法简单实用的好码。 以上几种编码都是分组码，虽然分组码在理论分析和数学描述上已经非 常成熟，并且在实际的通信系统中也得到了广泛的应用，但是分组码固有的 缺点制约了它的进一步发展：( 1 ) 分组码是面向数据块的，译码过程中必须 等待整个码字全部接收到之后才能开始译码，特别是数据块较长时，造成的 系统延时非常大：( 2 ) 分组码要求精确的帧同步，需要对接收码字或帧的起 始符号时间和相位精确同步；( 3 ) 大多数分组码的译码算法都是硬判决算法， 而不是对解调器输出未量化信息的软译码，造成了一定程度的增益损失，特 别是在低信噪比条件下，分组码的纠错能力表现得很差。 1 9 5 5 年，e l i a s 等人提出了卷积码，很好的解决了分组码的固有问题。直 到1 9 6 7 年v i t e r b i 提出了基于似然译码的v i t e r b i 算法后嗍，卷积码得到了极 为广泛的应用。其中约束长度为7 ，码率1 2 和1 3 的o d e n w a l d e r 卷积码已 成为商业卫星通信系统中的标准编码方法。在太空探测器，移动通信领域都 将卷积码作为差错控制编码方案。为了解决译码性能和译码复杂度的矛盾， f o m e y 在1 9 6 6 年提出了串行级联码的编码方案。其基本思想是通过短码级 联构造长码的方法来提高纠错码的纠错能力，并且允许将最大似然译码分为 几个较简单的译码步骤，得到一个次最优但实际可行的译码策略，也符合 s h a n n o n 信道编码定理构造好码的思想。在信息理论的发展过程中，人们研 究表明，在接收机中解调器采用软输出可以得到比硬输出高2 d b 左右的附加 编码增益。1 9 7 4 年，b a h l ，j e l i n e k 和r a v i v 共同提出了最大后验概率( m a p ) 译码算法( 也称为b c j r 算法) m ，并适用于任何线形分组码和卷积码，由于 2 哈尔滨工程大学硕士学位论文 计算较复杂，当时并未引起注意，但为t u r b o 码的产生起了奠基的作用。直 到1 9 9 3 年，在瑞士日内瓦召开的国际通信会议( i c c 9 3 ) 上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 提出了一种震惊整个编码界的新型信道编码方 案m l r b o 码9 1 。仿真结果表明，在采用长度为6 5 5 3 6 的随机交织器并迭代 译码1 8 次的情况下，信噪比为0 7 d b ，采用b p s k 调制，码率1 2 的t u r b o 码在加性高斯白噪声信道上的误比特率达到1 0 一，和s h a n n o n 极限仅相差 0 7 d b ，从而掀起了研究t u r b o 码的热潮。 1 2t u r b o 码的研究现状 自1 9 9 3 年t u r b o 码的论文发表以后，由于其接近s h a n n o n 极限的优异译 码性能在编码界引起了轰动，成为了人们研究的热点。但是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 码的编码结构，交织器设计和译码算法等方面取得了一定的进展，但 是到目前为止，还没有形成系统而完善的分析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 c s d s 建议中；第四代移动通信的研究方案中，t u r b o 码 作为信道编码的备选方案之一【i ”。 和其它的信道编码方案相比较，t u r b o 码虽然采用了迭代译码的原理， 具有优异的译码性能，但是仍存在有待于改进的缺陷”“： 1 译码算法相对较为复杂，计算量大； 3 哈尔滨工程大学硕士学位论文 2 编译码器中交织器的引入，译码器采用迭代译码，导致译码延时较大， 从而限制了t u r b o 码在高速实时通信系统中的应用； 3 存在着所谓的地板效应( e r r o r - f l o o r ) ，即在误码率下降到一定程度以 后，再增加信噪比的情况下，误码率就下降地很慢，并趋于恒定； 4 理论分析困难，目前尚未有对t u r b o 码编译码器进行完整的理论分析 与估计，一般都是通过计算机仿真模拟其性能。 7 就硬件实现t u r b o 码而言，许多的科研院所和大公司都已经推出了t u r b o 码的相关芯片和正在研究更适于现代通信系统的t u r b o 码芯片。南澳大利亚 大学s m a l lw o r l d 通信研究组最先开始开发t u r b o 编译码器并推出了t u r b o 码 产品，新加坡o l d 公司推出了用于t u r b o 编解码的专用芯片e m i k 0 7 ， a d v a n c e dh a r d w a r e 推出了单芯片t u r b o 乘积码( t c p ) 编解码器a s t r ol e ， 世界上两大著名的f p g a 供应商x i l i n x 和a l t e r a 公司都推出了基于自己f p g a 芯片的t u r b o 码编译码器的i pc o r e 。总的来说，推出的专用芯片和i pc o r e 是 用于特殊用途的，参数单一，缺乏灵活性，存储量大，功耗较大，而且价格 昂贵，专用芯片还有一定的起订数量要求，阻碍了t u r b o 码的实用化推广。 目前，t u r b o 码分量译码器采用的实现算法通常有s o v a 算法和m a p 算 法的简化算法l o g m a p 算法，m a x - l o g m a p 算法。s o v a 算法具有最低的 译码复杂度，但是性能也是最差，译码性能也不稳定；l o g m a p 算法具有硬 件实现最佳的译码性能，但复杂度最大；m a x l o g m a p 算法复杂度低于 l o g m a p 算法，高于s o v a 算法，性能仅次于l o g m a p 算法。硬件实现中， 普遍采用复杂度和性能都适中的m a x l o g m a p 算法。 t u r b o 码已经在实际的通信系统中得到应用，但是随着通信技术的发展 和人们对通信业务的需求仍需进行改进。目前，国内外研究t u r b o 码硬件实 现，主要朝着以下三个方向发展： l 减小译码延时，提高数据吞吐量； 2 降低译码的复杂度，减小编译码器对硬件资源的消耗； 3 降低编译码器芯片的功耗。 4 哈尔滨工程大学硕七学位论文 1 3 本文主要内容和结构 本文以基于f p g a 实现t u r b o 码译码器为研究目标，采用3 g p p 标准的 编码和交织方案，对t u r b o 码的m a p 译码算法，l o g - m a p 译码算法和 m a x - l o g m a p 译码算法进行了深入的算法复杂度和译码性能仿真比较。在此 基础之上，选择合适的译码算法进行t u r b o 码译码器的f p g a 实现设计。本 文具体内容安排如下： 第2 章主要介绍t u r b o 码的基本编译码原理，分析了t u r b o 码编译码器 的基本结构，并对3 g p p 标准的编码和交织方案作了详细的介绍，为后面 f p g a 设计提供理论基础。 第3 章主要对t u r b o 码的m a p 、l o g m a p 和m a x l o g - m a p 译码算法进 行了详细的理论推导，对三种译码算法的计算复杂度进行了定量比较分析和 译码性能的仿真比较，并对影响译码性能的因素进行了分析，最后确定采用 m a x l o g m a p 译码算法进行t u r b o 码译码器的f p g a 实现设计。 第4 章详细介绍了t u r b o 码译码器的f p g a 实现设计，对m a x l o g m a p 子译码器的关键运算单元的结构设计，时序控制逻辑的设计做了详细的介绍， 最后给出了t u r b o 码译码器的测试方法，对设计的t u r b o 码译码器的译码性 能和理论算法仿真性能做了比较，并对进一步完善t u r b o 译码器指明了研究 方向。 5 哈尔滨工程大学硕士学位论文 第2 章t u r b o 码编译码原理 t u r b o 优异的译码性能源自于它独特的编码结构和迭代译码的思想。本 章详细的介绍了基本的t u r b o 码编码结构和迭代译码过程，并在最后详细的 介绍了3 g p p 标准的编码和交织方案。 2 1t u r b o 码编码原理 2 1 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 s ) 。图2 1 所示，即为一典型的p c c c 编码结构。 图2 1p c c c 编码结构 由图2 1 可知，t u r b o 码的编码器主要由两个递归系统卷积码( r s c ， r e c u r s i v es y s t e m a t i cc o n v o l u t i o n a lc o d e s ) 分量编码器，交织器，删余矩阵和 复接器组成。 在t u r b o 码编码过程中，长度为n 的信息序列k ) 在送入第一个分量编 码器的同时作为系统输出k ) 直接送至复接器，同时k 经过交织器，后的 交织后序列缸。) 送入第二个分量编码器。其中以= i ( k ) ，0 七s n 一1 。，( ) 为交织映射函数，为交织长度。两个分量码的输入信息序列的内容是完全 6 哈尔滨工程大学硕士学位论文 一致的，只是信息码元的输入顺序不同。两个分量编码器对应的输出为校验 序列酋p 和k ， 。为提高码率和系统频谱利用率，可以将两个校验序列经过 删余矩阵删余校验位后( 得到仁f ) 再与系统输出k 一起经过复接器构成 t u r b o 码编码器输出码字序列h 。 2 1 2r s c 递归系统卷积码 在t u r b o 码编码器中，为了得到更好的编码性能，一般采用递归系统卷 积码( r s c ) 作为分量编码器。和传统的卷积码相比较，递归系统卷积码最 大的特点是它存在着反馈。常用的r s c 编码器一般由2 4 级移位寄存器构成， 用生成多项式表示为：g ( d ) 2 1 1 ，嚣器。“l ，表示系统比特，9 0 ( 。) 表示为 反馈多项式，g l ( d ) 表示为前向多项式，g o ( d ) 和g l ( d ) 用八进制数表示，图 2 2 所示为生成多项式为( 7 ，5 ) 的递归系统卷积码。 2 1 3 交织器 图2 2 ( 7 ，5 ) 递归系统卷积码 在很早以前，人们已经将交织器应用于通信系统中。其中最典型的应用 是采用纠随机错误的信道纠错码来纠正突发形式的错误。另外一个应用是在 级联码系统的内码和外码之间，利用交织器尽可能分散外译码器输出的突发 7 哈尔滨1 = 程大学硕士学位论文 错误，使进入内译码器的错误基本上是随机的。 在t u r b o 码的编译码系统中，交织器扮演着一个非常重要的角色，它的 主要作用是将输入信息序列比特顺序重置，减小分量码输出的校验比特之间 的相关性，同时提高输出校验序列的码重，从而在迭代译码过程中降低误比 特率。c b e r r o u 等人在提出t u r b o 码时就给出了设计性能较好的交织器的特 点和基本原则“”：( 1 ) 通过增加交织器的长度，可以使译码性能得到提高； ( 2 ) 交织器应该使输入序列尽可能地随机化，从而避免编码生成低重码字的 信息序列在交织后仍旧生成低重码字，导致m b o 码的自由距离减小。下面 简单介绍几种常用的交织器”。 1 分组交织器 分组交织器是一类最简单的交织器。它的交织映射规则为：将数据序列 按行的顺序逐行写入m n 的矩阵，输出时将数据逐列读出，完成数据的交 织。这类交织器结构简单，交织均匀，能有效地抗突发错误，但是由于其自 身的周期性特征使之抗周期性错误性能差”邶1 。 2 分组螺旋交织器 分组螺旋交织器是一种改进的分组交织器。它的交织映射规则为：将数 据序列行的顺序写入m n 矩阵，其中肘和互素。数据输出时从矩阵的左 上角开始向右下方向读数据，每下一行同时右移一位( 即行列索引同时递增 l ，也可以从矩阵的左下角开始向右上方向读取数据) 完成数据的交织。这种 交织器是普通分组交织器的变形，结构简单，对短序列交织效果较好，但是 交织后的序列码元去相关性不彻底”圳1 。 3 伪随机交织器 。 伪随机交织器是众多交织器中性能最好的一种交织器，它是通过交织映 射随机生成的交织器。对于不同的帧长有不同的交织方案，对于信息序列中 的每一比特都有一个随机给出的映射地址，然后通过查表的方法完成数据的 交织“”。该类交织器大幅度的降低了交织后序列码元之间的相关性。 在实际应用过程中，我们应该根据系统的实际需求，折中的考虑性能和 8 哈尔滨工程大学硕士学位论文 实现复杂度，选择合适的交织器。理论上来说，我们遵循以下原则”8 ：( 1 ) 最大程度地置乱原数据的排列顺序，避免置换前相距较近的数据在置换后仍 相距较近，特别要避免置换前相邻数据在置换后再次相邻；( 2 ) 尽可能避免 与同一信息位直接相关的两个分量编码器中的校验位均被删余：( 3 ) 对于不 归零的编码器，交织器设计时要避免出现“尾效应”图案：( 4 ) 在满足上述要 求的交织器中再选择一个好的交织器，使码字之间的最小距离( 或自由距离) d 。尽可能大，而重量为d 。的码字数要尽可能少，以改善t u r b o 码在高信 噪比时的性能。 2 1 4 删余矩阵 删余的目的是为了尽量提高码字的码率而达到小的错误概率的传输。如 图2 1 所示，两个分量编码器输出的校验比特戤9 和雠9 j 通过删余矩阵周期 性的删除一些校验比特后就得到了校验序列扛f = 讧：9 ，x ；9 。通过设置不同 的删余矩阵，我们可以得到不同的码率。删余矩阵p l = 11 ，1 1 】，p 2 = 10 ， i1 】，p 3 = 10 ，0l 】分别对应的码率为i 3 ，4 5 ，1 2 。在实际通信系统中用的 最多的是l 3 和1 2 码率。 2 1 5 归零处理 在m a p 译码算法中，前向递推吼0 ) 和后向递推屏g ) 的初始条件值， 一般都是要根据r s c 分量编码器的初始状态和编码结束状态而确定的。对于 普通的非系统卷积编码器，很容易将其初始状态和结束状态置为一已知状态， 比如零状态。而对于t u r b o 编码器，由于采用了递归结构，其分量编码器需 要额外的结尾处理才能达到结束于零状态。对于不同的t u r b o 码编码器的归 零处理，一般都赋予不同的递推初始值，如表2 1 所示。 9 哈尔滨丁程大学硕士学位论文 表2 i 不同归零处理的吼g ) 和成0 ) 递推初始值 、 译码器l 递推初始值 译码器2 递推初始值 r s c i 和r s c 2( 0 ) = l , a r 。o o ) = 0( o ) = 1 , a 。g o ) = 0 均不归零p w ( 0 - - 1 悖 风g ) = 1 2 7 r s c i 归零( o ) = 1 , a 。g o ) = 0口。( o ) = l ，口。0 o ) = 0 r s c 2 不归零 风( o ) = 1 ，风g o ) = o风g ) = 1 2 r s c i 和r s c 2 口。( o ) = 1 , a 。0 o ) = 0口。( 0 ) = l ，口。g o ) = 0 均归零 。( o ) = 1 ，。g o ) = 0风( 0 ) = 1 ，o o ) = 0 表2 1 中，v 表示r s c 分量编码器中的寄存器个数。对分量码的不同归 零处理，对t u r b o 码的译码性能有不同的影响，在本文第3 章进行仿真比较。 2 2t u r b o 码译码原理 与t u r b o 码的编码结构相比较，t u r b o 码的译码过程就显得较为复杂。 图2 3 所示为t u r b o 码的译码结构，其译码器主要包括予译码器1 、子译码器 2 、交织器和解交织器。 l a l h 坤 y ， 图2 3t u r b o 码译码结构 t u r b o 码的译码过程是一个循环迭代译码的过程”，首先，接收到的信道 信息序列被解复为信息位序列k ，子译码器i 校验位序列似， 和子译码器 1 0 哈尔滨工程大学硕士学位论文 2 校验位序列侈：9 三项。对于子译码器l ，信息位序列k ，子译码器1 校 验位序列以， 和先验信息位序列犯q ( 前一次迭代子译码器2 输出的外信 息位序列：) 经过解交织后得到，对于第一次迭代仁q = 0 ) 输入子译码 器l ，经过译码运算得到子译码器1 的外信息位序列伍e 。) ，经过交织器后得 到子译码器2 的先验信息位序列 肠： ，连同交织后的信息位序列溉 ，子译 码器2 校验位序列坛9j 输入子译码器2 ，经过译码运算得到子译码器2 的外 信息位序列犯p ：) ，经过解交织器后得到子译码器1 的下一次迭代的先验信息 位序列仁q ) ，至此完成一次迭代译码过程。当循环迭代译码达到一定迭代次 数后，停止迭代运算，子译码器2 的软输出信息序列解交织后通过硬判决得 到译码后信息序列k ，从而完成整个译码过程。 2 33 g p p 标准的t u r b o 码编码和交织方案 前面介绍了普通的t u r b o 码编码结构，下面具体介绍一下3 g p p 标准中 t u r b o 码编码器，本文中的t u r b o 码译码算法和仿真，都是围绕着该编码器 进行的。 2 3 13 g p p 标准的t u r b o 码编码结构 3 g p p 标准的t u r b o 码编码器结构如图2 4 所示，整个编码器由两个r s c 分量编码器和一个内交织器组成”“。 输入序列j 二j 。l ，j 辩 工童世坚卿a l 社酬致刚。 2 3 23 g p p 标准的t u r b o 码的归零 3 g p p 标准中的t u r b o 码编码器在每一帧数据编码完成时，需要对两个分 量编码器进行归零处理。当编码开始时，编码器的3 个移位寄存器都处于0 状态，随着信息序列的移入，寄存器的状态随之改变。当编码结束时，如图 2 4 编码结构所示，每个r s c 分量编码器的输入端开关向反馈端( 虚线端) 闭合，根据r s c 分量编码器的移位寄存器状态，形成反馈归零码字，从而使 分量编码器回到0 状态，同时输出归零尾码字序列h + 1 ，靠+ l ，x 。+ ：，+ ：， 1 2 哈尔滨j 程大学硕十学位论文 2 3 33 g p p 标准的t u r b o 码交织方案 为适应移动通信信道的要求，3 g p p 标准的t u r b o 码内交织器，采用了 独具特色的分级交织算法，针对不同的帧长有不同的交织图样，交织深度为 4 肚5 1 1 4 。具体算法步骤如下： 1 根据交织深度置确定交织矩阵的行数r 和列数c ( 1 ) 确定交织矩阵的行数r ( 从上至下依次为0 ，l ，r 一1 ) f 5 ， ( 4 0 k s l 5 9 ) r = 1 0 , i f ( ( 1 6 0 k _ 2 0 0 ) o r ( 4 8 1 k 5 3 0 ) ) ( 2 1 ) 【2 0 ，矿似= o t h e r s ) ( 2 ) 确定交织矩阵的列数c ( 从左至右依次为0 ，l ，c 1 ) i f ( 4 8 1 k 5 3 0 1t h e nc = p = 5 3 e l s e f p l 矿k r x 0 1 ) c = p矿r x 扫一1 ) 6 ，且吼 q ( , - o ，i = 1 , 2 ，r l ，其中g r d 为求 最大公约数。 ( 4 ) 计算序列“) r r ( f 1 = q f ，i = 0 , 1 ，r 一1 a 1 4 哈尔滨工程大学硕士学位论文 其中p ( f ) ，f 0 ，l ，r l ，为根据交织深度k 而确定的四种行间交换 模式，如表2 3 所示 表2 3t u r b o 码内交织器行间交换模式 行间交换模式 交织深度足行数r ( r r n r ( r - o ) ( 4 0 k 1 5 9 ) 5 ( 1 6 0 ks 2 0 0 ) o r ( 4 8 1 ks5 3 0 ) 1 0 k 时，将对应的数据删除( 删除的多余比特数为r x c k ) ， 不作为内交织器的输出，完成信息序列的交织。 2 4 本章小结 本章主要介绍了t u r b o 码的基本编译码原理，对普通的t u r b o 码编码结 构，译码结构进行了介绍，重点介绍了3 g p p 标准的t u r b o 码编码方案和独 具特色的内交织器算法，本文后续章节的译码算法和仿真都是围绕着该编码 和交织方案来展开的。 1 6 哈尔滨1 = 程大学硕士学位论文 第3 章t u r b o 码译码算法及性能仿真 t l i r b 0 码译码算法主要分为两大类，一类是由v i t e r b i 演化而来的s o v a 算法，另一类是性能优异的m a p 算法，以及由m a p 算法延伸而来的 l o g - m a p 算法和m a x - l 0 9 m a p 算法o ”。s o v a 算法具有最低的译码复杂度， 但是性能最差，并且译码性能不够稳定。m a p 算法具有最优的译码性能，但 是由于计算中存在着大量的乘法和指数运算，译码复杂度高，不便于硬件实 现，通常作为理论分析的参考。l o g - m a p 算法删和m a x l o g m a p 算法都 是由m a p 算法简化而来，通过将原来的运算转化到对数域进行，从而将乘 法运算变成了加法运算，避免了指数运算，降低了译码复杂度嘲“。就译码性 能而言，l o g - m a p 算法仅次于m a p 算法，m a x l 0 9 - m a p 算法次于l o g m a p 算法但要好于s o v a 算法。就译码复杂度而言，m a x l o g - m a p 算法的译码 复杂度低于l o g m a p 算法，更易于硬件实现8 ”。考虑到硬件实现的需要，本 文只就m a p 算法、l o g 。m a p 算法和m a x l 0 9 m a p 算法进行了理论分析和 m a t l a b 编程性能仿真，未对性能最差的s o v a 算法进行理论分析和 m a = h ，a b 编程性能仿真。 3 1m a p 译码算法 1 9 7 4 年b a h ，c o c k c ，j e l i n e k 和r a v i v 共同提出了最大后验概率( m a p ) 译码算法川，也是以他们命名的著名的b c 瓜算法。它是基于网格的软输入软 输出译码算法，译码准则是在噪声信道下对马尔可夫过程的状态或输入输出 进行逐一估计。下面，本文将完整而详细的推导m a p 译码算法。 图3 1 为m a p 子译码器，输入信息序列y = ) ，= d l ，y 2 ，y 一，y ) 。 其中，y k = b ：， ) 。表示信息序列的长度，l a ( u 。) 是关于的先验信息， 1 7 哈尔滨工程大学硕士学位论文 l ( u 。) 是关于的对数似然比。 为 其定义如下： 工口f ( 3 1 ) ( 3 2 ) 对于b p s k 调制，在加性高斯白噪声( a w g n ) 信道上的输入输出关系 兵= 厄( 2 x ；一1 ) + n ： y ：= 厄b x 2 一心+ n ( 3 - 3 ) ( 3 - 4 ) 其中，2 x ；一i ，2 x f l 为已调双极性编码符号，工f o ，1 ) ，e ，为每 一码字能量，通常取e = 1 ，疗：，行f 为独立同分布的高斯噪声样值，其均值为 0 ，方差盯2 = o 2 。 m a p 译码器的目的就是要根据式( 3 2 ) ，按照下列规则进行判决： 咖器剖笔 s ， 下面我们将利用b c j r 算法对式( 3 2 ) 的计算进行详细的推导。根据 b a y e s 规则和联合概率性质，式( 3 - 2 ) 可以写为： 1 8 哈尔滨工程大学硕士学位论文 l ( u 。) ( 3 - 6 ) 式( 3 6 ) 中，求和是对所有由= 1 ( 或= 0 ) 引起的s k l 寸瓯的状 态转移进行的，鼠。代表网格图的k - 1 时刻的状态，s k 代表网格图的k 时刻 的状态为了表示简单，文中后面将用s 表示k l 时刻的状态，j 表示七时刻 的状态。 观察式( 3 6 ) 可知，为了计算0 。) 就要计算尸p 。= j ，s 。= s ，y ，) ，可 按式( 3 7 ) 进行： p g 。，s ，j ，) = ，g ，j ，_ y 一，y 。，) ，。) ( 3 7 ) 由b a y e s 规则，并假定信道为无记忆信道，式( 3 7 ) 又可写为： p g ，s ，) 式( 3 - 8 ) 中： 11s j 糕：艘y 黔圹1 川s ) _ p b ，叫n 。) = p 鲁。is ) p 舨，s ) ，衍一1 ) _ p g ，) ，：一1 ) ( 3 8 ) = p 0 墨。is ) p 。，s is ) p g ，y ? 。1 ) = 反g ) 以g ，s ) 口。g ) a k - j g ) = j p g ，y 屏g ) = p 嚣。1s ) “s ) = 尸p ls ) ( 3 - 9 ) ( 3 - 1 0 ) ( 3 1 1 ) 其中，式( 3 - 9 ) ，( 3 1 0 ) ，( 3 1 1 ) 分别定义为前向递推，后向递推和状 态s 和状态j 之间的分支转移概率。 1 9 “杪沙 p p = = 哈尔滨t 程大学硕士学位论文 式： 将式( 3 - 7 ) - - ( 3 1 1 ) 代入式( 3 - 6 ) 即可得也的对数似然比l ( u 。) 的表达 3 1 1 前向递推 。g ) 几g ，s ) 展g ) 三“) 。1 “萎巧瓦网 纠 由式( 3 9 ) 前向递推的定义，根据b a y e s 规则，无记忆信道的特点和联 合概率的性质，可以将式( 3 9 ) 进