（通信与信息系统专业论文）turbo码的设计与实现.pdf

卜海交通，：学砷士论文：t u r b o 码的设计与实现 t u r b o 码设计与实现 摘要 7 t u r b o 码是近年来信道编码研究领域的一个热点。最早的关于t u r b o 码的论文发表与 1 9 9 3 年3 月的i c c 大会上当时c b e r r o u 和ag l a v i e u x 等人提出利用b p s k 调制和 t c 译码，在o7 d b 时就能达到无差错传输。由于其自身的特点和卓越的性能可被广泛应 瑚丁| 卫星通信、无线宽带、地面数字广播等领域。本文的工作紧密围绕t u r b o 码的原理和 实际应用，不仅在算法上做了大量仿真，同时针对算法的硬件可行性做了修改与简化，并 最终采h j 可编程逻辑器件实现，真正做到了从理论到应用的转变。作者参与的部分j ：作成 果已被美国g l o c o m 公司采纳，使用在了国际海事卫星组织的迷你多媒体m 站系统中。 、 具体而言i 1 全文r x j 容安排如下： ， 首先简单回顾了数字通信的基本结构，指出了信道编码在通信系统中的重要地位。接 着介绍香农定理与信道容量的概念，简要回顾了信道编码学科发展历史与现状，指出t u r b o 码的先进性。并简要介绍了t u r b o 码的基本特性。 其次，详细介绍t u r b o 码编码以及译码器基本原理，首先给定文章中用到的数字信道 的基本假设，在此基础上介绍了编码器的基本原理以及译码器的基本原理。详细推导了摄 人f l y , 然准州泽码器和最大后验概率准则译码器，给出t u r b o 码译码器结构。最后给出了一 种基r 乘积码的迭代泽码算法，并与基于卷积的t u r b o 码算法作了比较。 再涉：，详细阐明了t u r b o 码的两种硬件实现方案：采用多片数字处理芯片方案以及采 一一 用可编程逻辑器件实现方案。并针对每一种方案分别给出了算法的改进方式以及硬件实现 的框架和具体细节。比较两种实现方案，认为比较行之有效的方案是使用现场可编程逻辑 器件实现。 最后，重点介绍了作者参与开发的用于国际海事卫星组织的卫星通信系统中使用t u r b o 码实现移动卫星多媒体数据传输终端设备：简要介绍了系统的实现方案以及作者在这个项 目中做出的贡献。 关键词：软输入软输出译码，最大后验概率准则，交织器，卷积码 圭塑奎望查堂堡主丝塞! 旦! ! ! 堡塑垡生皇壅堡一 d e s i g n a n di m p l e m e n t a t i o no n t u r b oc o d i n g a b s t r a c t t u r b oc o d i n gi sah o t s p mi nt h ef i e l do f f o r w a r de r r o rc o r r e c t i o nc o d i n gr e c e n t l yt h ef i r s t p a p e r a b o u tt u r b oc o d i n ga p p e a r e di nm a r c h1 9 9 3i nl c cc b e r r o u a n dag l a v i e u xp u tf o r w a r da s c h e m eo f c o d i n gw h i c hi sc a l l e dt u r b oc o d i n gl a t e r t h i ss c h e m e h a sa no u t s t a n d i n gp e r f o r m a n c e ， w i t hb p s km o d u l a t i o n ， i tc a na c h i e v e0 7 d bw i t hn oe r m rt r a n s m i s s i o n d u et o i t so w n c h a r a c t e r i s t i ca n dp e r f o r m a n c e ，i tc a nb ew i d e l yu s e di n s a t e l l i t ec o m m u n i c a t i o n ，w i r e l e s s b r o a d b a n dc o m m u n i c a t i o na n dt e r r e s t r i a ld i g i t a lb r o a d c a s t i n g ，a t c t h i sp a p e r f o c u s e so nt h ed e s i g n a n di m p l e m e n t a t i o no f t u r b oc o d i n g n o to n l yg e t t i n gp l e n t yo fs i m u l a t i o nr e s u l t st oo p t i m i z et h e d e s i g n ，b u t a l s o g i v i n g t w o d i f f e r e n t w a y t or e a l i z e t h i s c o m p l e x a l g o r i t h ma l s o t h e a u t h o r h a s e v e r t a k e ns o m e j o b si nt h ei m p l e m e n t a t i o no f i n m a r s a t m 4 s y s t e mo f g l o c o m ，u s a m o r e s p e c i f i c a l l y ，t h i s d i s s e r t a t i o ni n c l u d e sf o l l o w i n gc o n t e n t s ： f i r s t l y ，r e t r o s p e c to fs o m eb a c k g r o u n dk n o w l e d g e o nt h eb a s i ca r c h i t e c t u r eo fd i g i t a l c o m m u n i c a t i o n ，e m p h a s i s t h ei m p o r t a n c eo f c h a n n e lc o d i n gi nt h ew h o l es y s t e mt h e ni n t r o d u c i n g t h ec o n c e p to fc h a n n e lc a p a c i t ya n ds h a n n o n st h e o r e ma f t e rr e v i e w i n gt h eh i s t o r yo fc h a n n e l c o d i n g ，t e l l i n g t h ea d v a n t a g ea n db a s i cc h a r a c t e r i s t i co f t u r b oc o d i n g s e c o n d l y ，i n t r o d u c i n gt h es t r u c t u r eo f t u r b oe n c o d i n g a n dd e c o d i n gi nd e t a i l sb a s e d0 nt h e f o u n d a t i o no f c h a n n e lh y p o t h e s i s ，d e r i v i n g t h e f o r m u l a o f m a p a n d v i t e r b id e c o d i n g w i t h t h e l a w o fm a x i m u m p o s t e r i o r ip r o b a b i l i t i e sa n dm a x i m u ml i k e l i h o o d t h e ni n t r o d u c i n ga n o t h e r a l g o r i t h mb a s e do np r o d u c tc o d i n g ，a n dc o m p a r i n g w i t ht h ec o n v o l u t i o n a lb a s e dt u r b oc o d i n g t h i r d l y ，s h o w i n gt w ow a y so fh a r d w a r er e a l t i m ei m p l e m e n t a t i o n ：i m p l e m e n t a t i o nw i t h m u l t i p l ed i g i t a ls i g n a lp r o c e s s o r so rw i t hf p g a a n dc o m p a r i n g w i t ht h e s et w op r o p o s a l s f i n a l l y ，i n t r o d u c i n g t h ei n m a r s a tm 4 s y s t e mw h i c ht h ea u t h o rh a sp a r t i c i p a t e di n ，a n d b r i e f l yi n t r o d u c i n gt h ea u t h o r sc o n t r i b u t i o nt ot h i sp r o j e c t k e y w o r d s ：s i s o ，m a p a l g o r i t h m ，i n t e r l e a v e ，s l i d ew i n d o w s i i 上海交通大学硕士论文：t u r b o 码的设计与实现 1 1 引言 第一章绪论 通信的目的要把对方不知道的消息及时可靠的( 有时还需秘密的) 传送给对方。因此， 要求一个通讯系统传输消息必须可靠与快速，在数字通讯系统中可靠与快速往往是一对矛 盾。若要要求快速，则必然使得每个数据码元所占的时间缩短、波形变窄、能量减少，从 而在受到干扰后产生错误的可能性增加，传送消息的可靠性减低。若要求可靠，使得传送 消息的速率变慢。因此，如何合理的解决可靠性与速度这一对矛盾，是正确设计个通信 系统关键问题。 在数字通信的很多场合，要求其基本上无误传输。但数字信号在传输过程中，由于受 到干扰的影响，信号码元波形会变坏，传输到接收端后可能发生错误判决。由于乘性干扰 ( 例如信道线性畸变等) 引起的码间干扰可以通过均衡的办法来基本消除，而加性干扰的 影响则需从其他途径来解决。通常，在设计数字通信系统时，首先应从合理的选择调制、 解调方法、加大发送功率、扩展信道频率等方面考虑，以使加性干扰不足以影响到使信道 误比特率达不到要求。若仍不能满足要求时，就需采用信道编码。 信道编码又称为差错控制编码，是提高数字传输可靠性的一种技术。它的基本思想是 通过对信息序列做某种变换，使原来彼此独立、相关性极小的信息码元产生某种相关性， 从而在接收端就利用这种规律性来检查或进而纠正信息码元在信道传输中所造成的差错。 差错类型主要有两类： 随机差错：差错是互相独立的，不相关的。存在差错的信道是无记忆信道或随机信道， 例如卫星信道。 突发差错：指成串出现的错误，错误与错误之间有相关性，个差错往往要影响到后 面一串字，例如短波和散射信道产生的差错。 在纠错编码技术中码的设计与错误性有关，对纠随机错误有效的码，往往对纠突发 差错的效果不好，所以要根据错误的性质来设计编码方案，才会有较好的效果。实际上两 种错误在信道上往往是同时并存的，一般是以一种为主来进行设计的。如果两种差错同样 严重，那就要寻找同时能够纠正两种错误的码。 圭塑窒望查堂堡圭堡墨! ! ! ! ! ! 塑塑堡生兰壅墼 一一 差错控制方式基本上分为两类，一类称为前向纠错( f e c ) ，另一类称为自动请求重发 ( a r q ) ，并在这两类基础上产生了一种结合两者优点的混合纠错( h e c ) 。 前向纠错( f e c ) 方式 这种方式在发端发送能够纠错的码，接收端在收到的信码中不仅能发现错误，而且还 能够纠正错误。这种方式的优点是不需要反馈信道，能进行一个用户对多个用户的同时通 信，特别适合于移动通信，此外译码实时性较好，但是译码设备比较复杂。 自动请求重发( a r q ) 方式 这种方式在发端发出能够发现错误的码，收端则根据编码规律将受到的信码进行判决， 若手段认为有错，则控制重发指令，通过反馈信道告诉发端，发端根据重发指令将有错的 那部分消息再次传送，直到正确接收为止。该方法的优点是译码设备简单，但需要有反馈 信道，并且实时性较差。 信息交换的日益增长是现代社会文明发展的一个重要特征。信息从源到目的地的传送 必须满足收到的信号尽可能的接近传送信号的质量。经典的通信系统结构如图1 1 所示。 图】电信通信系统结构框图 信息的产生可以由机器产生( 例如，图像，数据) 或人类产生l 例如，语音) 。不考虑 信源情况，信息必须转化为一组针对信道优化过的信号来传送。第一步是删除冗余部分来 使得信息传送率这部分由图中信源编码框来完成。为了保证我们要传送的信息安全，可以 采用加密法。数据必须受到保护以防止干扰导致的接收端信息接收错误。这种保护可以由 纠错控制来实现：前向纠错( f e c ) ，或者自动重发申请( a r q ) 系统。调制部分产生符合 传输信道特性的信号。 本论文集中讨论通讯系统中前向纠错控制方法，对一些调制技术也有提及。根据编码 上海交通大学硕士论文：t u r b o 码的设计与实现 理论，随着码字长度或编码器存储量的增加，可以实现更好的纠错性能或编码增益。但同 时最大似然解码算法的复杂度也随着指数级上升，导致应用困难。通过增加分组码或卷积 码码字长度来提高纠错能力的方法需要高端的计算系统。这导致了对采用简单的译码策略 取代最大似然译码算法的新的信道编码方案的研究。这种策略结台更有效地码字，允许每 个码字采用少复杂度译码器独立译码，采用迭代计算达到最优性能。 基于最大后验概率准则的并行级联卷积码的迭代译码算法，又称为t u r b o 码，就是按 上述思想在近几年发展起来的一种全新的信道译码方法。本文在对其做深入分析与仿真的 基础上，在回顾传统算法的同时，提出了算法的改进与简化。并给出可实现的硬件解决方 案，最后真正应用到了卫星通信系统中。 本章首先介绍了信道容量的概念，同时简单回顾了信道编码技术的基本概念和各种不 同算法和分类，指出t u r b o 码的先进性所在。最后简述了论文的章节安排和作者的主要工 作。 1 2 信道编码技术 1 2 1 香农定理与信道容量 在数字通信系统中，通过信道交换的最大平均互信息量被称之为信道容量。信道容量 的概念最早是由香浓于1 9 4 8 年提出，他指出当信息传送速率不高于信道容量，总可以找到 一种合适的信道编码和解码方案，使信息以任意小的出错概率通过信道传输数字信息。信 道编码就是用来达到这一目的的技术。纠错编码用增加冗余度方法使得传送信号容错性增 加从而达到克服差错的目的。接受端利用冗余度纠正信道产生的错误。香农的信道容量边 界定理可用如下公式表示： c 圳o + 争= b l 0 9 2 者 c 】 其中c 表示信道容量，b 表示信道带宽，s n 为传输信号的信噪比。从( 1 1 ) 式中可 以看到，信道带宽越大、信噪比越高，信道容量就越大。然而，对于加性高斯白噪声( a w g n ) 噪声能量与带宽成正比，即n = ”。b 。因此对于a w g n 信道，信道容量并不是随着带宽的 圭塑銮堕盔兰堡主笙奎：旦虫! 塑塑堡生皇圭婴一一 增加而无限增加。可以推得，当带宽趋向无限时，信道容量近似于： l i r a c = 溉胁引，+ 嘉- - - l o g 2 e 鲁n a 。熹 z ， 如图12 所示随着带宽增长，信道容量区域饱和。 图1 2 信道容量与信噪比示意图 实际应用中，为了比较不同编码方式、调制方式下码字纠错能力的高低，必须把公式 写成可比较的归一化公式。由此考虑到频带利用率n ，公式可改写为： c 一 即孛 ， 可行。占 ( 13 ) 式中的c 称为比特信道容量，相对应的可以称( 1 1 ) 式中的c 是码元信道容量， 归一化处理后，可得： 班1 0 9 ：( 1 + 矿知 ( 1 。) 式中：为归一化信道利用率，e 。称为每比特信号能量。由此可画出归一化香农信道 容量曲线如图1 3 ： 4 上海交通夫学硕士论文：t u r b o 码的设计与实现 图1 2 ：归一化信道容量曲线 跟据香农理论在曲线右边的点总是可实现的，而左边的点无论用什么调制方式都无 法做到无差错传输。当然，所谓的无差错传输是理论上的说法。在实际上，一般认为误码 率在1 0 e 一5 以下即为无差错传输，工业上也有要求在1 0 e 6 以下的。最早的关于t u r b o 码的 论文发表与1 9 9 3 年3 月的i c c 大会上，当时c b e r r o u 和a g l a v i e u x 等人提出利用 b p s k 调制和t c 译码，在o7 d b 时就能接近无差错传输( 见上图的左下点处) 。使用高带宽 利用率的1 6 q a m 体制方法时，在3 5 d b 时接近无差错传输( 见上图的右上点处) 。 1 2 2 传统信道编码方法 自从香农提出了信道容量概念以来，信道编码技术进入了个崭新的时期。1 9 5 0 年， 格宙( g o l a y ) 和汉明( h a m m i n g ) 首先提出了一种非平凡纠错码，它采用了一系列冗 余校验比特，利用它们达到了在相同信道下比无编码系统更好的效果，第一次把香农的理 论转化为可行的方案。从此，信道编码技术真正从简单的重发变为丰富多彩的应用技术。 从纠错编码历史上讲，乘积码是在较低码字长度下取得较高纠错性能而不增加译码复 杂度的第一次尝试。但不幸的是，尽管整个码字的纠错性能得到了提高，但对子码的交替 译码并没有得到期待的性能。随后级联码的出现取得了较好的效果。子码被分别称为内码 ( i n n e r ) 和外码( o u t e r ) a 译码时，首先对每个内码作译码，译码出的结果被外码采用进一 步译码。多电平编码采用了一些不同纠错容量的纠错码字。被传送的信号由这些码字绍合 上海交通大学硕士论文：t u r b o 码的设计与实现 而成。 所有这些码字有一个共同的缺陷：两个译码器间没有信启，交换。而t u r b o 码填补了这 个不足，它对相同的信息以不同的次序两次编码，这使得两个译码器间的信息交换成为可 能。信息序gr i s t 得越乱，交换信息间的不相关性越强，译码性能越好。 1 2 3t u r b o 码基本特性 基本概念：t u r b o 码的优点显然是其卓越的纠错能力，缺点是解码器的复杂度较大、相 对的译码延时较长。t u r b o 码基本特征是编码器由2 个通过交织器分隔的子编码器构成。子 编码器多采用卷积码，一般子编码器采用循环系统卷积码( r s c ) 。而交织器的作用是使得 两个子编码器被两个不同的序列激励。同样，2 个各自独立的译码器也通过交织器分隔。第 一各子译码器提供的信息可以被第二个子译码器使用，这里指的信息必须是“软信息”。同 样，第二个子译码器产生的软信息输出可以返回被第一个子译码器使用。由此，通过反复 的迭代译码，每比特信息的可信度随之增强。译码器迭代次数可以调整，但迭代次数的增 加会显著的增加算法复杂度。 1 3 本文的主要内容和安排 t u r b o 码是近年来信道编码研究领域的一个热点。由于其自身的特点和卓越的性能，可 被广泛应用于卫星通信、无线宽带、地面数字广播等领域。本文的工作紧密围绕t u r b o 码 的原理和实际应用，不仅在算法上做了大量仿真，同时针对算法的硬件可行性做了修改与 简化，并最终采用可编程逻辑器件实现，真正做到了从理论到产品的转变。作者参与的部 分工作成果已被美国g l o c o m 公司采纳，使用在了国际海事卫星组织的迷你多媒体m 站 系统中。 全文内容安排如下： 第一章首先简单回顾了数字通信的基本结构，指出了信道编码在通信系统中的重要地 位。接着介绍香农定理与信道容量的概念，简要回顾了信道编码学科发展历史与现状，指 出t u r b o 码的先进性。并简要介绍了t u r b o 码的基本特性。 第二章详细介绍t u r b o 码编码以及译码器基本原理，首先给定文章中用到的数字信道 6 圭塑奎望奎兰堡主丝苎! 旦! ! ! 塑竺堡盐皇塞墨一 的基本假设，在此基础上介绍了编码器的基本原理以及译码器的基本原理。详细推导了最 人似然准则译码器和最大后验概率准则译码器，给出t u r b o 码译码器结构。最后给出了一 种基于乘积码的迭代译码算法，并与基于卷积的t u r b o 码算法作了比较。 第三章详细阐明了t u r b o 码的两种硬件实现方案：采用多片数字处理芯片方案以及采 用可编程逻辑器件实现方案。并针对每一种方案分别给出了算法的改进方式以及硬件实现 的框架和具体细节。比较两种实现方案，认为比较行之有效的方案是使用现场可编程逻辑 器件实现。 第四章介绍了t u r b o 码在国际移动卫星组织多媒体系统中的应用方案以及性能测试结 果。 最后，总结了本文的工作，指出了进一步研究的方向。 7 上海交通大学硕士论文：t u r b o 码的设计与实现 2 1 引言 第二章基本原理与改进 多年来，为了避免太大的译码复杂度，人们一直试图用短码( 子码) 构造长码的方法 来逼近香农理论极限，如内外式级联码分级译码、乘积码等。但是，这种内外式级联码由 于采取内外码分别编码并分级译码，不管各子码采用何种最佳译码算法，最终它并非是“长 码”整体意义上的最佳译码，因此，该方案所能获得的编码增益并不大，离香农理论极限 还有很大差距。近年来，一种称之为t u r b o 码( 以下简称t c ) 的信道纠错编译码方式引起 编码界的极大重视。t c 的基本思想是利用若干个短码来构造长码，然后用短码间迭代译码 的方式，以较小的译码复杂度获得接近香农极限的纠错性能。 起初，t c 的构造有别于传统的内外式级联码，编码器是由若干个循环系统卷积码( r s c ) 编码器通过符号( 比特) 交织器并行级联而成，编码序列由信息位和各r s c 子编码器输出 的校验位交替串行输出组成：译码器则将接收到的己编码序列( 解调器软输出) 按信息位 和子码校验位分离重组，然后分别采用逐个符号( 比特) 的软输入软输出( s i s o ) 最大似 然译码算法，产生反映信息位可信度的软信息( 信息位对数似然比) ，再把上一级输出的软 信息作为下一级子译码器输入信息位的先验概率，通过交织解交织器在各子译码器之间反 复迭代译码，从而使t c 在整体上获得接近最大似然译码的性能。后来，人们将这种编译码 体制进一步推广到串行级联( s c ) 、兼有并行和串行的混合级联( h c ) 等多种构造方式， 通称为“级联码的迭代译码”。无论码的构造如何变化，该编译码体制中有两点是肯定的： 一，是子编译码器间通过符号( 比特) 交织解交织器相互隔离并传递信息：二，是子译码 器采用逐符号( 比特) s i s o 译码算法。其中，有效的逐比特( 符号) 软输入软输出最大似 然译码算法是级联码迭代译码的前提和核心。 本章以下各节将讨论：用于级码迭代译码的卷积码在最大似然准则下以及最大后验概 率准则下的s 1 s o 译码算法及其优缺点比较；简化的s i s o 算法的途径及其对迭代译码算法 的影响：以及t u r b o 码优化设计。 8 上海交通大学硕士论文：t u r b o 码的设计与实现 2 2 数字信道的性质与假设 为了方便以f 各节的阐述，本节对文中用到的数字信道做以下的假设以及统一所使用 的符号。 信源：马尔可夫数字信源，且p “o ) = p r o ) = 0 5 。 信道：离散无记忆信道( d m c ) ，信道为二进制对称信道，即信道转移概率矩阵为： p = 粥删= 1 ：2 加1 2 噪声：加性白高斯噪声( a w g n ) 。 调制技术：文章中若不具体指明采用的调制技术时，均认为采用b p s k 调制技术。 性能仿真统一采用b p s k 的调制方式，我们定义以下符号： i 殳 d k l 为信息比特流。它由n 个独立比特d k 组成，每个比特取0 和1 的概率相等。经 过码率为1 2 的卷积码编码器后输出为：x k y k 。编码输出经b p s k 调制后用以下符号表 示： d i 2 2 x , 一1 ( 2 1 ) b k 22 k 一1 ( 2 2 ) 经调制后信息的取值为：1 。用每组( a k ，b k ) 定义为一个传输码元c k 。则可记发 送码元序列为：c j = ( c rc ：c 一，简记为c 。 在接收端，记接收码元序列为：r l ”= ( 月，r ：r ，简记为r ，其中r k ：( x k ，y k ) ， 满足： x 2 口 + 仇 ( 2 3 ) y t = 札+ 目 ( 2 4 ) p k ，q k 是符合( o ，o2 ) 的a w g n 噪声。图2 1 清晰的展示了各符号间的关系： d k )十磊芒玎磊芒焉譬 x k y “ r k 9 圭童奎望查兰堡主笙苎：里! ! 壁塑堡丛皇壅翌 一 图21 ：信道模型中符号含义 均匀分布随机数发生器是仿真程序中使用的最基本模块，本文采用以下的伪随机数发 生器，确保随机数的均匀分布和不相关性，相关函数如下： u n i f o r mr a n d o mv a r i a b l eo ni n t e r v a lu o d o u b l e 0 ，2 ) p e r i o di s2 “3 5b d r i p l e ys t o c h a s t i cs i m u l a t i o n19 8 7 l n i t a i lv a l u eo f g l o b a ls t a t i cv a r i b l e ： “一i n t 6 4 s e e d x l o n g l o n g 。7 4 6 3 8 4 1 5 7 ； 一i n t 6 4 s e e d y l o n g l o n g 2 3 4 5 6 213 7 l ； i n t 6 4x o l o n g l o n g ，y o l o n g l o n g ； f x o l o n g l o n g = s e e d x l o n g l o n g ；y o l o n g l o n g = s e e d y l o n g l o n g ； d o u b l eu n i f o r m r v ( ) d o u b l eu o d o u b l e ； x o i o n g l o n g = ( x o i o n g l o n g + 8 4 0 4 9 9 7 + 1 ) & 3 4 3 5 9 7 3 8 3 6 7 ； u o d o u b l e = ( d o u b l e ) x o l o n g l o n g ( d o u b l e ) 1 7 1 7 9 8 6 9 1 8 4 ； r e t u r n ( u o d o u b l e ) ： 2 3 译码器原理 2 3 1 卷积码编码器 卷积码是爱里斯( e l i a s ) 于1 9 5 5 年最早提出的，它与分组码的不同之处是： 分组码无论是编码还是译码，前后各组是无关的，编码时一个码组的校验位只决定于 本组的信息位，译码时也可从已知长度的接收码组中还原本组的信息位。分组码要增加纠 错能力，就要增加校验位，从而使编译码设备复杂，特别是增加译码的困难。 而在卷积码中，个组的校验元不仅取决于本组的信息元，而且也取决于前m 组的信 息元。因此可表示成( n ，k ，m ) 码，其中k 输入信息比特数，o 为卷积码输出比特数，m 叫做编码的容量，它表示输入的信息组在编码器中需存储的单位时间数，n + ( m + 1 ) 称为编 1 0 上海交通大学硕士论文：t u r b o 码的设计与实现 码约束长度。文中讨论的卷积码集中在1 2 码率情况，在此前提下，卷积码的表示只需知道 编码器容量以及结构，通常采用两个8 进制数来表示编码器的容量及抽头位置。卷积码分 为循环系统卷积码( r e c u r s i v e s y s t e m a t i c c o d e ，简称为r s c ) 和非系统卷积码( n o ns y s t e m a t i c c o d e 简称为n s c ) 。以( 3 7 ，2 】) 码为例，图22 、2 3 分别为r s c 、n s c 编码器所示： 一1 + x k 图2 2 ：r s c ( 3 7 ，2 1 ) _ q x k 舔 d k 一一+ t t _ _ tu jt _ _ 二j t y k 图2 _ 3 ：n s c ( 3 7 ，2 1 ) 图2 2 中，编码器存储单位有四个( 图中标t 的方框) ，因此共有5 个抽头。假设编码 器输出使用得抽头位置系数为1 ，位使用的位置系数为0 ，则可以通过抽头系数唯一确定编 码器的逻辑结构。图中上半部分的编码器输出使用了所有抽头，用系数表示为全1 ，当 用8 进制数表示时即为3 7 。同样，编码器下半部分只用到了第一和第五个抽头，用8 进 制数表示为2 1 。所以图2 2 的编码方式可以用r s c ( 3 7 ，2 1 ) 码表示。 研究证明t u r b o 码中，r s c 译码性能比n s c 好，因此文中着重讨论r s c 情况。对循环 系统卷积码( r s c ) 而言，x k = d k 。在以后的章节中，编码使用r s c 情况下，一律用d k 表 可i 。 2 3 2 级联卷积码编码器 t u r b o 码编码部分采用的卷积码的并行级联结构，如图2 4 所示 圭塑奎望查堂堕圭丝茎：旦! 塑塑塑堡茎皇茎翌 一 图2 4 ：t u r b o 码编码器结构 k 图中，交织器的作用是将信源数据打乱后输入卷积码编码器。这样，同一组数据以不 同的次序分别经过卷积编码，可以最大程度的利用数据内在的信息。两个循环系统卷积码 可以相同，也可以不同。但采用不同的编码器会使编码器和译码器的复杂度大大增加，而 且实验证明并不会使性能有大的提高。因此一般而言，t u r b o 码编码器中采用两组相同的卷 积编码器。 合并器( p u n c t u r e ) 用来控制t u r b o 码编码器的编码效率。图中可发现，如果不使用合 并器t u r b o 码每一个信息位有两个校验位，则此时编码效率仅为1 3 。而使用了合并器后， 每信息比特对应的校验位按顺序依次取两个卷积编码器输出中的一个，而丢弃另一个校验 码。这样，编码效率可提高到l 2 。根据合并器不同的设计，可以生成效率不同的编码方案。 2 4 译码器原理 2 4 1 译码准则简介 图2 5 译码准则 一码惭一 事 固 蛋 磊一 i 圆 圆 一黼码 姗黼一 煳孵 一骺删 r，、，111l r1llff一 一歇则一 一默靴一 ， 看魏 遁研鸲一 垂 上海交通大学硕士论文：t u r b o 码的设计与实现 译码器的基本任务就是根据一套译码规则，由接收序列r 给出于发送的信息序列c 最 接近的估计序列c ，当c ，- c 时，译码器译码正确。常用的译码准则有两种，分别是最大 似然准则和晟大后验概率准则。根据两种不同的准则衍生出不同的译码算法，就是维特比 译码算法和最大后验概率译码算法( m a p ) 。 c 的估计方法是：对于所有的码字可能值p r ( c i r ) 最大。根据贝叶斯准则， p r ( c j 月) ：p r ( r ic ) p r ( c ) ( 25 ) 。p r ( r ) 根据信源假设，发送端每个码字的概率p r ( c ) 均相同，且p r ( r ) 与译码方法无关 因此：求p r ( c i r ) 的最大值等价于求p r ( r i c ，) 的最大值。p r ( r i c ，) 被称为最大似然 函数，求使得p r ( r i c ) 最大的c 的方法被称为最大似然准则译码。 而根据概率论定义，p r ( c i r ) 被称为最大后验概率，又根据信源信源的马尔可夫性， p r ( c 1 月) = r i p r ( c ，f 月) ( 2 6 ) j ；l 最大后验概率准则译码即求使( 2 5 ) 最大的码字c 。本章从上述两种准则入手，分别 推导两种准则下的译码方法。 2 4 2 最大似然准则与维特比译码 根据等概率马尔可夫信源性质， n p r ( cj r ) = 兀p r ( c , j r ) 根据贝叶斯准则 蝌”= 盥罴产 ( 2 7 ) ( 2 8 ) 因此：求p r ( c “r i ) 的最大值等价于求p r ( r ij c i ) 的最大值。对于a w g n 的信道 p r ( r c 女) = p r ( ( x 。，儿) i ( 吼，b 。) ) 2 p r ( x kia k ) p r ( y 慨) ( 29 ) 2 志唧( 一咛斗击唧卜咛斗 上海交通大学硕士论文：t u r b o 码的设计与实现 为了使计算方便，把( 2 7 ) 式两边取对数，得 n i n p r ( ci r ) = i n p r ( c ，ir ，) 卢0 ( 2 1 0 ) i n p r ( c ，lr 。) = l n p r ( r ，ic ，) + i n p r ( c 。) 一i n p r ( r ，) ( 2 1 1 ) 其中l n p r ( c ，) 是常数，而对某一固定的i ，i n p r ( r i ) 同时去掉并不影响序列判决。因此 只要取窆l np r ( r ，| c ，) 最大情况。而在a w g n 情况下，由( 2 9 ) 得 i n p r ( r jf ，) = 一c i “r ，一口，) 2 + ( j ，一6 ，) 2 ) + c 2 ( 2 1 2 ) 其中c 1 和c 2 为常数，c 】 0 。 所以只需取使得( r ，c ，) 2 和最小的序列，最后由序列c 与 d k ) 的一一映射关系得到信 息比特序列。这就是在a w g n 信道中按最大似然准则译码的具体推导，特别的，当编码器 采用卷积编码器时，以上方法即用欧拉距离作权重的维特比译码的数学原理。当然维特比 算法也可以用其他值作权重，得到不同的算法。 具体地讲，维特比算法是通过在每时刻k 按最大似然准则决定一条幸存路径并逐步延 伸的方法找出最佳状态序列的，选择幸存路径依据为最小路径度量准则。路径度量值如式 ( 2j 2 ) 所示。具体形式冈定义不同而有所变化，例如，对于a g w n 信道，路径度量值 f ? 可由下式求搿 m ，：争圭n 厂x m = ( o d ，= 一jn = l 其中x z 是第m 个译码序列在第j 时刻分支上长为n 的码字的第n 个比特，y ”是相应 接收到的模拟值，e ，n 。是信噪比，万为译码判决延时。那么选择幸存路径依据就是 嗡n ( z ? ) = r r j n ，三一+ 舅：。，一z ! ：) 2 ) 。：，。， 慰然，在时刻k 选取路释m 为幸存路径的概率与路径度量值m t m 存在以下关系 j p ( 路径m ) = j p ( 霹) 。ce - m ? ，m = 1 ，2 ( 2 1 5 ) 如果假设时刻k + ，( ，= 0 , 1 ，万) 有m 0 ， m ：，则路成埘；为幸存路径，选择正确的概率 为 4 上海交通大学硕士论文：t u r b o 码的设计与实现 j d ( 正确)之：受了，其中戤：m ；2 ，一m o = 一 e 一吣+ e 一峨1 + e 甑 ? 定义幸存路径m ，的对数似然比为 三( 聊，) = l o g ( j p ( 正确) ( 1 一j p ( 正确) ) ) = ： 于是t 可大致得出时刻k 信息位d 。对数似然比 l ( a t ) z 玩盟哩吐 ( 2 1 6 ) ( 2 1 7 ) 当取玩= - + 1 就是维特比译码的硬判决结果。式( 2 1 7 ) 这就是通常所说的软输入软输出 维特比算法( s o v a ) 的软输出值。 2 4 3 最大后验概率准则与m a p 译码 m a p 算法的全称是m a x i m u m a p o s t e r i o r i p r o b a b i l i t i e s ，即最大后验概率译码。根据( 2 5 ) 式，最大后验概率准则即是以p r ( c k l r ) 最大为准则的译码方案。与最大似然准则不同的 时后者指序列的译码而前者是每个码的判决准则。冈为发送序列c 与信源序例f d k - - - - 对 应，p r ( c k l r ) 最大等价于p r ( d k 限) 晟大。根据定义： p r g ：i l r ，”) ：p r p 。：f ，s 。：。i 尺) ( 2 1 8 ) 其中，s k 为k 时刻编码器存储单元的状态。i 为信源信息比特，取值为+ l 或i 。记 则根据全概率公式 由! j f j 听准则得到 五( m ) = p r ( d 。= f ，s 。= m i f ) ( 2 1 9 ) p r = i i 1 5 m (以 = 、i 尼 主童奎望查兰堡主笙壅! 旦生! 堡堕堡塑茎型二一 五( 脚) = p r ( 以= f ，s 。= ，r 1 n ) p r ( r 1 u ) p r ( d 。= f ，s 。= 脚，r ) p r 垡盘。j ! 。三! ! 兰! 三竺) p r 忸l ) ( 22 1 ) 考虑到时刻k 后的接收序列与k 时刻以前的观测值无关，( 2 2 1 ) 可以进一步写成 定义 五( m ) = v r ( d 。= f ，s 。= 珊，r ) p r 忙。id 。生兰l 三型 p r 群) a ：( 埘) = p r p 。= f ，s 。= 川，r ) 麒( m ) = p r c r ，l d 。= f ，s 。= 掰j 则式( 2 2 2 ) 可以写成： 枷，= 篙籽 ( 2 2 2 ) ( 21 9 ) ( 2 2 0 ) ( 2 2 3 ) 为了得到 值，我们必须求出、d 的值。幸运的是，、p 是可通过递推求解的。a 可以 重新写成： 口：( m ) = p r p 。= f ，s 。= 珊，r - ir 。) ：圭p r 0 。：删。= - ，s 。= 聊，乩= 朋，r - i ，见) 7 。1 = 0 = 窆p r ( d 。一。= j , s 。= m ，r 。) p r 0 。= f ，s 。= m ，r 。l d 。= j , s 。= m ) j = 0 上面最后一个等式是由于d k _ l 和s k _ 1 完全定义了在k - 1 时刻的路径，与接收序列尺j “无 关，因此可以继续简化，写成： 口：( 聊) = 口止，( 卅) p r ( 矾= f ，s 。= m ，r 。d k 一。= ，s = 肌) ( 2 2 4 ) m ，- o 同样，可以把b 重写成 6 、 足矾 1 l 扣 s i l 一以 足m i i 女 sf = 女 n v rp 、， 一 rm i 一瓯 ， = 卜 d j u p 脚 。 圭堂窒望奎兰堡主堡塞! 盟生! 里堕旦盐兰窒堡一 ( 研) = p r ( r “r 2i d 女= f ，s = 肌j ：圭p r p 。：，s 。= m ，r 。，r ：l d 。= f ，s 。= m ) ，= 0 ld += ，s = m ，r ，d = f ，s = 聊) p r ( d 女+ l = = ，s 。+ = = m ，r + l id 女= = f ，s 女= = m ) = p r 忙：l d 。= j s p r ( d 。：，s 。= ，r 。+ 。i d 。= f ，s 。= m ) 用迭代方程表示为 卢：( 埘) = 窆触。( m ) p r p 。= j ，s 。= m ，r 。i d 。= f ，s t = ) ( 2 2 5 ) m 。，0 观察式( 2 2 4 ) 及式( 2 2 5 ) 可以发现在递推公式中有一项公因式继续可以简化 p r ( d = f ，s 女= m ，r 女l d = ，s _ 】= 聊) = p r ( r tl d k = f ，s i = ，d h = ，s = 聊) p r ( d k = i i s 女= m ，d = ，s h = m ) p r ( s 女= m l d = - ，s = m ) = p r ( r 。| d 。= f ，s 。= m ) p r ( d k = f ) p r ( s 。= m i d 。= ，s “= 川) ：p r ( 月。1 d 。= f ，s i = 脚) i 11 p r ( s 。= 川1 d 。= ，s 。= 聊) 其中，p r ( s k = 脚i 矾一，= ，