（信号与信息处理专业论文）现代码中迭代译码的研究.pdf

北京邮电大学博j ：学位论文 摘要 摘要 信道编码是数字通信系统中不可缺少的一个环节。 近几年，随着信道编码理论的发展与进步，以t u r b o 码【1 l 】，l d p c 码 1 3 】 为代表，出现了一批性能卓越的编译码方案。尤其是在码长较长的情况下，它们 能够逼近香农极限。优异的性能吸引了越来越多的研究工作者，投入到关于它们 的研究工作中，从而也建立一批相关的理论。为了和经典的编码理论相区别，人 们往往习惯把这些新的理论，称为现代编码理论，也把这一部分码称为现代码。 所有的现代码都具有两个共同的特点：一个是编码的随机构成。这使得码重 谱的分布接近于随机码；另一个就是采用迭代译码近似逼近最大似然译码。这样 使我们可以用一个较小的复杂度来实现对于长码的译码。这两个重要的性质，都 是符合香农信息论理论的。 本论文着重研究现代码的迭代译码的研究。现代码的迭代译码虽然能够较好 的逼近最大似然译码。但是它多维非线性的特点，也使得传统的研究方法和研究 工具不再适用。因此，有多种新的研究理论被分别提出。本文介绍并总结了其中 三种研究方法以及它们的区别与联系：统计分析，非线性分析和图形分析。 首先，本文介绍了迭代译码的统计分析方法。基于统计分析方法的“高斯假 设“和“对称条件 ，提出了一种新的应用于m c c d m a 系统的a r q 结构。该 系统有别于传统的a r q 系统，并不是将所有检测出错误的帧都要求重传，而是 根据不同的业务需求( 误码率要求) ，只要求重新传输误码比特数高于门限值的 帧。 其次，本文介绍了迭代译码中基本的动态非线性理论。此基础上，扩展了非 线性分析理论，对迭代译码动态系统的各个不同阶段，做了更全面的叙述，从而 丰富了迭代译码的非线性分析理论。基于对迭代译码各个不同阶段的认识，我们 提出了一个新的迭代停止准则。从试验的仿真结果来看，新的方案大大提高了系 统的性能，接近于理论极限。 最后，基于图形分析理论，本文提出了一套新的t u r b o 码交织器的性能度量 工具( c c s ) 。仿真结果表明，运用c c s 设计的交织器性能优于目前已知的交织 器性能。与此同时，我们也给出了一个新的交织器扩展因子的理论上界，新的上 北京邮i 乜大学博 ：学位论义 摘要 界比原有的理论上更紧。 ， 关键词：t u r b o 码，l d p c 码，现代码，迭代译码，统计分析，非线性迭代 系统，图形分析，a r q ，交织器 。 北京邮电大学博：t 等丝笙壅 竺! ! ! 垒墨! a b s t r a c t e r r o rc o r r e c t i o nc o d i n gp l a y sac r u c i a lr o l ei nd i g i t a lc o m m u n i c a t i o ns y s t e m s r e c e n t l v _ m o r er e s e a r c h e r sh a v ed e v o t e d t ot h es t u d yo np o w e r f u lm o d e mc o d e s ，s u c h 豁t l l 灿a n dl o w d e n s i t y p a r i t yc h e c k ( l d p c ) c o d e s ，d u et ot h e i rt m p r e s s t v e p e r f o r m a n c ec l o s et os h a n n o nl i m i t t o d i f f e r e n t i a t et h er e l a t i v et h e o r yf r o mt h e c l a s s i c a la l g e b r a i cc o d i n gt h e o r y , t h e ya r ec a l l e da sm o d e m e r r o rc o r r e c t i o nt h e o r y t h em o d 锄e r r o rc o r r e c t i o nc o d e ss h a r et w oc h a r a c t e r i s t i e s ：r a n d o m n e s sa n d i t e r a t i v ed e c o d i n g r a n d o m n e s sa tt h ee n c o d e r b e n e f i t st h ec o d c w o r dw e i g h ts p e c t r u m ， w h i c ha p p r o x i m a t e st h ew e i g h ts p e c t r u mo f ( c o n c e p t u a l l y ) r a n d o mc o d e s t h e i t e r a t i v ed e c o d i n ga s y m p t o t i c a l l ya c h i e v e st h ep e r f o r m a n c eo fm a x i m u ml i k e l i h o o d ( m l ) d e c o d i n g ，a sw e l la sm a i n t a i n i n ga c c e p t a b l ed e c o d i n gc o m p l e x i t y e v e nf o rl o n g b l o c k - 1 e n g mc o d e s t h e s et w oa d v a n t a g e sn o to n l ya s s i s tp r a c t i c a li m p l e m e n t a t i o n , b u ta l s oa g r e e sw i t ht h es h a n n o nt h e o r e m t h i sw o r ke x p l o r e sf u n d a m e n t a la s p e c t so fi t e r a t i v ed e c o d i n g a l t h o u g hi t e r a t i v e d e c o d i n gp r o m i s e st h eo p t i m a lm ld e c o d i n ga s y m p t o t i c a l l y , i t sn o n - l i n e a rp r o p e r t y m a k e st r a d i t i o n a la n a l y t i c a lt o o l si n v a l i d t h e r e f o r e ，m a n yn e w t h e o r e t i c a lt o o l sh a v e b e e np r o p o s e d t h i sw o r ki n v e s t i g a t e s t h r e e a p p r o a c h e s ：s t o c h a s t i c a n a l y s l s ， n o n - l i n e a ra n a l y s i s ，a n dg r a p ha n a l y s i s f i r s t , w ei n t r o d u c et h e s t o c h a s t i ca n a l y s i sa p p r o a c h b a s e d o ng a u s s i a n a s s u i n p t i o na n ds y m m e t r i cc o n d i t i o n , w ep r o p o s e an e wa r qa p p l i c a t i o no n m c c d m as y s t e m s d i f f e r e n tf r o mt h et r a d i t i o n a la i s y s t e m s ，t h i sa p p r o a c hd o e s n o tr e q u i r er e - t r a n s m i t t i n ga l le r r o n e o u sf r a m e s i n s t e a d ，o n l yc e r t a i nf r a m e s ，w i t h m o r ee r r o r st l l a nt h eg i v e nt h r e s h o l d ，a r er e - t r a n s m i t t e d h e n c e ，t h ee f f i c i e n c yo f t h e e n t i r es y s t e mi sg r e a t l yi m p r o v e d n e x t w eb r i e f l yr e v i e wt h ed y n a m i cn o n - l i n e a rt h e o r e mi n i t e r a t i v ed e c o d i n g u p o nt h i s ，w ee x t e n da n dc o m p r e h e n s i v e l yi l l u s t r a t e v a r i o u ss t a g e so fi t e r a t i v e d e c o d i n gs y s t e m ；i nt u r n , g r e a t l ye n r i c ht h et h e o r e mo f n o n - l i n e a ra n a l y s i si ni t e r a t i v e d e c o d i n g w ef u r t h e rp r o p o s ea n o v e ls t o p p i n gc r i t e r i o n s i m u l a t i o nr e s u l t sr e v e a lt h a t t h en e w s t o p p i n gc r i t e r i o ne n h a n c e ss y s t e mp e r f o r m a n c e f i n a l l y , e n l i g h t e n e db yt h eg r a p ht h e o r y , w ep r o p o s ea n o t h e rm e t r i c ( c s s ) t o e v a h i a t et h ep e r f o r m a n c eo fi n t e r l e a v e r , w h i c hi so n eo ft h et w od o m i n a n t c o m p o n e n t si nt h ed e s i g no ft u r b oc o d e s t h ec s s m e t r i cn o to n l yq u a n n z e sa n d p r e d i c t st h ep e r f o r m a n c eo fi n t e r l e a v e r s b u tc a n a l s ob eu t i l i z e da sd e s i g nc r i t e r i o n t h ei n t e r l e a v e rd e s i g n e da c c o r d i n gt oc s sh a sb e e nd e m o n s t r a t e dt op r e s e n tb e t t e r p e r f o r m a n c ec o m p a r i n g w i t hm a n ye x i s t i n gi n t e r l e a v e r s k e yw o r d s ：t u r b oc o d e s ，l d p cc o d e s ， n o n l i n e a ri t e r a t i v es y s t e m ，g r a p ha n a l y s i s ， m o d e mc o d e s ，s t o c h a s t i ca n a l y s i s ， a r q ，i n t e r l e a v e r 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其它人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 、 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：塑毖日期l 兰亟竺 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 j 本人签名：! 盟咝j日期：垫立窆兰 导师签名： 北京邮电人学博1 ：学位论文 第l 章引言 第1 章引言 随着社会的进步和科技的发展，人们对通信技术的要求也进一步提高。人们 希望在任何时间，任何地点，能够和任何人进行通信，或者能够享受到语音、图 像等各种各样的多媒体服务。由于数字化的进程，我们可以把所有的这些服务都 归结为数字业务。现在的问题是如何在各种复杂的信道环境中，在有限的传输能 量和带宽下，设计出可靠而高速的数字通信系统。我们要求它能够有很低的误码 率，有较高的传输速率，能够对抗多种恶劣的信道环境，而且要保证有效的利用 传输功率和带宽。与此同时，还要兼顾系统复杂度的问题。 1 1 数字通信系统 下面，我们给出了数字通信系统的结构框图，这里重点介绍一下系统中的信 道编码模块： 图1 - 1 数字通信系统模型 图1 1 是一个数字通信系统的结构框图。在现实世界中，大部分的信号源都 应该是模拟的。在送入数字通信系统之前，它们被抽样、量化、形成数字信号。 通常情况，这个新形成的信息源是有着大量的冗余信息。它们要么是前后符号之 间有着各种各样的相关性，比如在图像中，我们会有大片面积属于相同颜色；要 么是符号发生的概率并不是均匀分布的。根据香农信息论，我们可以采用编码的 方法，并用更少的比特数来代替这些冗余的信息源。这种编码被称之为信源编码， 它被用来去除信源中的冗余部分。 信源编码后，信息序列被送入信道编码模块。信道编码的目的是，给需要传 送的信息加入了一些冗余信息，以保证在接收端我们能够正确的收到这部分信 息。与前面我们所去除的冗余信息不同的是：这部分冗余信息是我们所能控制的， 北京邮电大学博1 ：学位论文 第1 章引言 是我们有意加上去的。为什么在原有信息的基础上，加入一些冗余信息能够保证 系统的可靠传输呢? 首先，我们可以把我们所要传输的信息序列想象成一个多维 空间上的一个点，如图1 2 所示。这样，所有这些可能的点就构成一个多维的信 号空间。另一方面，由于信道和噪声的影响，在接收端我们将收到一个被干扰后 的信号，而不是发送信号本身。当然这个干扰不是无止境的，满足一定的能量限 制。在给定发送信号s 的条件下，大部分可能的接收到的信号发生在s 附近的 、一个区域。 不失一般性，我们可以假设这个区域是一个以墨为圆心的圆荔。如果此时我 们有另外一个以岛为圆心的圆以( 墨也是信号空间中的一个成员) ，与办相交于 岛2 ( 在图l 一2 中，我们用阴影部分来表示) 。那么对于落在岛2 中的接收信号， 我们将很难确定它所对应的发送信号。也就是说，有可能出现接收端的判断错误。 对此，在信道一定的情况下，一个有效的办法，就是加大s 与& 之间的距离， 从而减小磊2 的面积，进一步减小接收信号出现在缶2 的可能。通过加入冗余信 息，我们把一个低维数的空间上的点映射到了高维数的信号空间中。点的分布变 得更加稀松，点与点之间的距离也就随之增大了。 图1 - 2 信道编码空间模型 为了进一步有效的利用信道带宽，提高带宽利用率，我们往往不直接采用比 特进行传输，而是将若干比特组成符号，再映射到多维数字调制的星座图上，例 如：正交相位调制( q p s k ) ，正交幅度调制( q a m ) 等等。从广义上来说，编 码和调制都属于空间映射，都是为了在一定的带宽和传输功率下，增加信号点之 间的欧式距离。因此，1 9 8 2 年，u n g e r b o e c k 1 2 3 联合编码和调制设计，成功 的提出了格型编码调制( t c m ) ，并获得了3 d b 的性能增益。 数字调制之后是信道模块。这里我们所说的信道，指的是数字信道。我们知 北京邮i 乜大学博t - 学位论文第1 章引言 道，实际中的物理信道，包括电缆信道、光纤信道、红外信道、深空无线信道、 水底声纳信道和存储信道都属于模拟连续信道。但从某种意义上来说，它们都可 以等效成离散信道模型。有很多著名的数字信道模型，例如比特对称信道( b s c c h a n n e l ) ，加性高斯白噪声信道，瑞利衰落信道等。 在接收端，接收到的信号被送到数字解调器中进行处理。对于软判决，信号 的似然比( l l r ) 被用来表示某种信号被发送的可能性，然后被送入译码器，进 行译码。对于硬判决，在送入译码器之前，解调器要先进行一次判决，某一个信 号点被判定成为对应的发送信号。 至于后面的信道译码和信源译码就是发送端信道编码和信源编码的逆过程。 当然，还有很多数字通信技术，我们没有提到和列入基本数字通信系统中，比如 码分多址( c d m a ) ，正交频分调制( o f d m ) ，a r q 技术等。 1 2 信道编码的发展 在本论文中，我们将着重研究上述系统中的信道编码和译码模块。自从1 9 4 8 年香农提出信息论以来，5 0 多年的时间，信道编码技术取得了很大的进步，从 一个数学推论的证明过程，演变成了各个通信系统所不可缺少的组成模块。香农 信息论已经证明，如果以r 统计特性理论， 非线性系统理论， 图形理论， 陷阱理论 1 3 论文的结构和安排 本论文主要集中于对现代码迭代译码结构的研究。首先，我们对现有的三种 理论：统计特性理论，非线性系统理论，和图形理论进行了逐一的分析和总结。 其次，我们扩展了统计特性理论和非线性系统理论，进一步细化并指出了迭代译 码在迭代过程中所表现出来的各个不同阶段。 基于对迭代译码迭代过程中各个不同阶段的认识和对其输出外信息的统计 特性的研究，我们提出了一种新的迭代译码停止准则以及一种新的a r q 结构。 试验数据显示该a r q 结构可被用于m c c d m a 系统和深度衰落信道下，并具有 北京邮电大学博。f ：学位论文一第1 章弓l 言 较好的性能。与此同时，我们也通过扩展图形理论的研究，提出了一种基于译码 性能的新的交织器衡量准则。在该准则的指导下，我们设计出了比现有交织器更 好的交织器。 论文的结构按照以下安排： 在第二章中，我们对t u r b o 码的分类、编码结构和译码算法，作了详细的介 绍。针对编码器的每一组成部分，成员码，交织器，删余器以及结尾方法，我们 逐一作了详细地分析。对于译码算法，我们介绍了一种最常用的基于b c j r 算法 的m a p 译码方法。 在第三章中，我们介绍了l d p c 码的定义以及它常见的几种表示方法，并简 单的提到了因子图( t a n n e r 图) 。接着我们对规则l d p c 码和不规则l d p c 码的设 计方法作了简单的总结。针对不同的信道，我们介绍了和积译码的概率表达。 在第四章，我们对迭代译码作了总的概括和介绍，列出了目前研究的目标和 存在的问题。在上面两章，我们分析和介绍了两个迭代译码的特例t u r b o 码和 l d p c 码，在细节上它们之间存在着很大的差别。为了研究的方便，我们在第四 章提供了一个对于各种迭代译码普遍适用的模型。同时，我们也介绍了迭代译码 的性能曲线的共性，作为以后研究的参考。 作为具体的研究方法，在第五章中，我们介绍了统计特性理论。统计特性理 论，是将输入、输出看成随机过程，通过跟踪和研究它们某个或者某几个统计变 量的变化，来描述系统的特性的。首先，我们介绍统计特性理论的两大假设条件： 高斯假设和对称假设。通过这两个条件，原来的n 维系统，被一维系统所代替。 接着，我们介绍了目前统计特性理论中，最为人们所接受的e x i t 理论。 应用统计分析理论，我们在第六章提出了一种新的a r q 结构。该结构可以 区分错误帧中错误比特的数量。并针对不同的业务需求，只将不满足要求的帧进 行重传。这尤其适用于m c c d m a 等深度快衰落的情况下。新的a r q 结构比以 往的结构更为灵活。 统计特性理论，只反映了迭代系统随信噪比变化，两端的特性，忽略中间部 分的细节。因此，在第七章，我们介绍了动态系统理论。首先，我们用动态系统 理论，对迭代译码系统的定点情况进行了分析。迭代译码系统中，存在两个定点： 含糊定点和非含糊定点。在低信噪比的时候，系统收敛到含糊定点，随着信噪比 的增加，含糊定点失去了它的稳定性，系统开始过渡到非含糊定点。 进一步，我们详细叙述了迭代译码，在此过渡期间，可能出现的几个阶段。 并给出了在这些阶段迭代译码的运动轨迹。基于以上对各个阶段的细分和分析， 我们在第七章，提出了一种新的迭代停止原则。利用外信息的最小值作为参考， 北京邮电人学博：卜学位论文 第1 章引言 我们可以清楚认定译码所处的三个主要阶段，含糊定点，混沌和非含糊定点，从 而做出适当的决定。 最后，在第八章，我们运用图形分析理论对t u r b o 码中的坏的特性及其影响 作了详细地分析。通过定义环的相关系数，对交织器的环给t u r b o 码的性能所带 来的影响进行了量化。进一步，我们提出了c c s 作为衡量交织器性能的指标。 仿真结果显示c c s 相对于以前的衡量标准更加准确。在c c s 的指导下，所设计 的互质交织器拥有比其它交织器更好的性能。其间，我们还证明并给出了一个扩 展因子的更紧的新的界。 北京邮电人学博。i ：学位论文 第2 章t u r b o 码 第2 章t u r b o 码 谈及现代编码理论，就不能不提到t u r b o 1 1 码。它虽然不是最早出现的现 代编码，( l d p c 应该说是最早提出的现代码。l d p c 码最早是由g a l l a g e r 在它1 9 6 0 年的m i t 博士论文中提出的 1 3 。但是限于当时的技术条件，有一个好的仿真结 果被给出，也就没有引起人们的注意。) 但是它的出现却将现代编码理论大大地 向前推进了一步。其优异的性能超出了人们的预料，也引起了人们的广泛的兴趣。 在经过很多人的验证后，人们终于认可了t u r b o 码的伟大成就。但是t u r b o 码只 是给我们提供了一种逼近香农限的方法，并没有告诉我们逼近的原因。从而对其 优异性能的解释工作，对其结构的改进与设计都成了新的热点问题。直到现在， 我们也没有一个对t u r b o 码性能完整而精确的解释。在这方面的研究工作仍在进 行中。 t u r b o 码，是由法国人c b e r r o u 和a g l a v i e u x 1 1 在1 9 9 3 年的i c c 国际 会议上首次提出的。它巧妙地将卷积码和随机交织器结合在一起，实现了随机编 码的思想，与此同时，采用软输出迭代译码来逼近最大似然译码。仿真结果表明， t u r b o 码在低于香农极限0 7 d b 的情况下，可以得到1 0 - 5 的误码率，抗误码性能 十分优越。优异的性能，引起了绝大多数人的怀疑，但同时也引起了人们对随机 编码和迭代译码的关注。在经过很多人的验证后，人们终于认可了t u r b o 码的伟 大成就。直到后来，d m a c k a y 和r n e a l 1 2 ， 1 5 重新发掘了l d p c 码。这两 个码共同支撑起了现代编码理论的大厦。 这罩值得一提的是，发明t u r b o 码的人并不是专门做编码研究的。整个想法 是从系统控制理论借鉴而来的。这也同时说明，通信编码理论是一个多方面，多 角度的系统科学。也预示了我们在对迭代译码进行分析中，可以借鉴和引用其它 学科的方法，例如统计物理和控制理论等等。我们将在后面的章节中对此做详细 的说明。 在本章中，我们将着重介绍基本的t u r b o 码编码和译码的结构。并对每一种 情况给出简单的分析和性能曲线。 2 1t u r b o 码的编码 香农定理告诉我们，构建一个码长趋于无穷的码是逼近香农极限的一个重要 条件。卷积码简单且易于实现的编码、译码结构给我们呈现了一种简单的实现长 北京邮l b 人学博i ：学位论文 第2 章t u r b o 码 码的方法。但实际上，受到自身结构的限制，卷积码的性能并不是特别理想。另 一种实现长码的方法是级联码。通过串行级联两个短码，我们就得到了一个长码。 t u r b o 码也是一种级联码。与传统级联码不同的是，在两个级联的成员码中 间，我们加入了交织器。也正是由于交织器的加入，使得随机编码的实现成为可 能。另外一个重要的不同是，t u r b o 码采用迭代译码，而在传统级联码中我们往 往是顺序译码。 t u r b o 码按照级联方式来分可以分为：并行级联码( 图2 1 ) ，串行级联码( 图 2 2 ) 和混合级联码( 图2 3 ) 。由于并行级联码是最早提出的，其它结构只是它 的衍生。 我们将以并行级联码为例，介绍t u r b o 码的各部分结构。 信息序列 l 露 分量码 x 。 复 编码器1 x p l 编码序列 删 接 一 x 余- r 1r ，i 一l y ( p 2 器 x p 器 i 痹圣口婆i “- j 万夏髑i 一 ix 瓠研i - 1 编码器2 i 一 图2 1 并行级联码 图2 2 串行级联码 信息 。 成员编码器l 交织器1成员编码器2 序列 复 接 器 交织器2 成员编码器3 图2 3 混合级联码 北京i l l l je g 人学博 ：学位论文 第2 章t u r b o 码 典型的并行级联码编码器由两个相同的成员码编码器、交织器、删截矩阵以 及复接器组成，其结构如图2 1 所示。 信源传来的信息数据u = ，“：，甜在进入编码器后，分为三路，一路信息 序列直接进入复接器形成最后的编码的系统位部分s = 而，s ：，s ，一路送入分 量码编码器l ，生成校验序列j p l = d ，p ，p i 。还有一路经过一个n 位的交织 器，形成一个新序列甜k 叫，甜知，材0 ( 长度与r 4 容没变，但比特位置经过重新排 列) 。送入分量码编码器2 ，生成校验序列p 2 = 彳，雳，p 寻。一般情况下，这两 个分量码的编码结构相同。 序列p 1 与p 2 经过删截矩阵进行删除合并得到了信息数据的校验序列送入复 接器，复接器将信息序列与校验序列进行并串转换得到编码输出。 有的t u r b o 码编码器，可能会包含不止两个成员码编码器，此时相应的交织 器的数目也要增加。 一 删截矩阵通过删除压缩合并各成员码编码器的输出校验序列来调整t u r b o 码编码器的编码速率，比如删截矩阵交替选取两个成员码编码器输出的校验序列 使得各有一半发送出去，就可以得到码率为1 2 的t u r b o 码，若校验序列全部发 送，则码率为1 3 。从理论上说，通过改变删截矩阵的设计可以得到任意码率的 t u r b o 码。下面我们对成员码，交织器以及删截矩阵进行一一的分析和介绍。 2 1 1 成员码 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 码中，通常来说，我们所用的卷积码，被称为带反馈的系统卷积码 ( r s c ) 。这是指我们所用的卷积码，具有两个性质，一是系统码，二是带有反 馈。其中系统码这一性质不是必需的，曾经有人提出非系统码的t u r b o 码，并指 出非系统码的t u r b o 码的性能要比系统码的t u r b o 码好。但是带反馈这一性质 确是必不可少的。事实上，单单就卷积码来言，不带反馈的卷积码( n r s c ) 要有 比带反馈的卷积码( r s c ) 更好的性能。那为什么我们还要采用带反馈的卷积码 北京邮电大学博1 ：学位论文第2 章t u r b o 码 呢7 这是因为带反馈的卷积码在应用到t u r b o 码的结构中后，能得到更好的码重 谱。众所周知，线性码最小码重越大，就有越好的性能。t u r b o 码之所以有着如 此好的性能曲线，就是因为它有着更好的码重谱。在t u r b o 码中，当一个信息序 列在第一个成员码中产生了低码重的校验序列，我们希望通过交织器改变它的次 序后，能在第二个成员码中产生高码重的校验序列。这对于不带反馈的卷积码是 无法实现的。由于系统码的关系，低码重的码主要是由低码重的信息序列所产生。 对于不带反馈的卷积码( n r s c ) 来说，低码重的码只能生成低码重的校验序列。 这一点与r s c 不同，即使是在输入码重为2 的情况下，它也可以产生高码重的 码。 图2 _ 4 和图2 5 显示了r s c 和n r s c 的码重谱。 图2 4r s c 的码重谱 北京邮电人学博：b 学位论文 第2 章t u r b o 码 图2 5n r s c 的码重谱 2 1 2 交织器 从上面的分析中，我们已经知道交织器对于t u r b o 码的码重谱有着重要的 影响。因为在后面的章节中，我们会有详细的讨论，在这里我们只给出交织器的 基本定义：交织器是一个单输入，单输出的设备，它将输入的序列打乱顺序，重 新输出，但不改变输入的值。我们可以用一个函数z r ( i ) 来表示。其中i 个元素在 原来序列中的位置，x ( 0 则表示对应元素在输出序列中的位置。图2 - 6 给出了一 个简单的交织器的例子。 输入序列0 1 1000101 i l23 4 56789 交织器 万( f ) 7 输出序列 100001110 图2 - 6 交织器 北京邮电人学博士学位论文第2 章t u r b o 码 2 1 3 删余器 严格来说，删余器不是t u r b o 码的一个必要的组成部件。它的作用是改变 t u r b o 码的编码速率。当然我们也可以通过改变成员码的结构来改变总的t u r b o 码的速率。但是在实际系统中，针对于不同的服务和不同信道环境，我们希望都 能够采用不同的码率。对于服务质量高和信道差的情况下，我们希望低码率来保 证可靠的通讯。相反，对于服务质量要求不高和信道好的情况下，我们希望增加 传输效率，从而需要较高的码率。 因此上，我们希望码率能够不断的变化，但是如果靠改变成员码的话，无论 是造价和复杂度都会变得很高。幸运的是，t u r b o 码有着其它码所不能比拟的适 应性。也就是说如果我们通过删除一部分校验位的方法来改变码率的话，不会比 你专门重新设计成员码，有太多的性能损失。这种通过删除一部分校验位的方法 来改变码率的方法， 我们也称为删余或者打孔。这就好像打孔机一样我们把多余的校验位打掉。 通常情况下，我们可以用一个矩阵来表示删余。例如一个1 3 码率的t u r b o 码输 出为x = s 。，爿，彳，屯，e ，雳，p 知，p 寻。经过p = 1 l o ；l o l 】后， ，= 毛，科，s ：，p ；，s ，烈，露，一，速率为1 2 。 2 1 4 结束方法 除了上面所讲的t u r b o 码的几个基本部件外，另一个重要的问题是成员码的 结束方法。我们已经提到对于卷积码，有三种不同的结束方法：归零，不归零和 循环。对于t u r b o 码来说，我们有两个成员码，通常由下面几个可能的组合： 第一个成员码归零；第二个成员码不归零 令两个成员码同时都归零 夺两个成员码都采用循环结束方法 北京邮电人学博十学位论文 第2 章t u r b o 码 2 2t u r b o 码的译码 信息序列x 解交 织器 外信勘1 似然值l 1 外信g z 2译码输 图2 7t u r b o 码译码器 硬判决 丛到 - i 篓蠢 图2 7 给出了t u r b o 码的译码结构。t u r b o 译码器的完整译码过程为： 首先对从信道接收到的序列经串并转换，分离出信息序列x 和校验序列y 1 、 y 2 ( 对于码率为1 3 的t u r b o 码，两个r s c 编码器输出的校验序列被完全发送， 因此在接收端不需要改动，而对于其它码率的t u r b o 码，比如1 2 码率，两个校 验序列经过删截矩阵后，分别被删去了部分校验位，因此在接收端对应位应填 0 ) 。 译码器l 输入的是先验概率信息( 对于第一次迭代过程，初始值置零) 、接 收的未编码信息序列x ( 以交织器长度为单位帧长输入) 和校验序列y 1 ，经 s i s o 译码后输出后验概率( 即外部信息) z 1 。由于外部信息与先验信息及输入 响应的系统信息无关，而且译码器l 没有利用校验序列y 2 ，所以译码器l 的输 出仅在交织后作为译码器2 的先验信息输入，而不能用作对信息序列的判决。 同时接收的信息序列x 经交织器处理后，和校验序列y 2 也作为译码器2 的 输入。其中交织的作用是使在所有时刻先验信息、接收信息、和校验信息相对应。 译码器2 产生新的外部信息z 2 和似然函数比l 2 ，其中外部信息再次经解交织后 作为译码器1 的先验信息输入，形成了译码的迭代过程。而译码器2 的输入包含 了校验序列y 1 和y 2 的全部信息，故在经过若干次迭代后， 译码器2 的软输出( 似然函数比) l 2 经过解交织，并作硬判决，成为输入 信息序列的t u r b o 译码输出结果。 在每一个译码单元中，我们可以使用m a p ，l o g m a p ，m a x l o g m a p ，以及 s o v a 等等译码算法。最常见的是m a p 译码，也就是b c j r 算法【1 0 】。下面我们 列出了b c j r 算法的主要公式。 我们假设对于某个译码单元来说，输入为r 1 = ( x ，l a , ) ，其中】，是从信 北京邮电人学博1 ：学位论文第2 章t u r b o 码 道接收到的信道信息，三口y 是从另一个译码器传递过来的外信息。对于第r 1 个 比特来说，输入信息又可以具体为对应于系统位的信道信息，对应于校验位的信 道信息以及外信息毛= 磊，菇，钟，三) 然后，我们可以定义每一位上的似然比为 人一一糍 一。( j ) 一( 兄，s ，s ) 成( s ) ( 2 - 1 ) = h 袁蠹而磊磊丽丽 其中墨和s 分别是在n - l 和1 1 可能的状态。口，和r ( f f 别是和状 态有关的概率密度，下面我们将给出它们的定义。 如果假设系统采用b p s k 调制，信道是a w g n 信道，噪声的方差是仃2 ，我 们定义y 为 专( 文( 2 卜1 ) + 却( 2 群一1 ) ) + i l a n ，盯。 _ 一( 尺甩，s 。，s ) 2 e k 聒七 p r ( s 玎= siu ”= f ，s 一一l = s ) ， 其中群是从状态s 转移到状态s 时，钟所对应的校验位。概率 p r ( & = si = f ，瓯一。= s ) 是1 ，或者0 。如果从s 转移到s ，对应的信息位甜。与 i 一致，则p r ( s 。= s l u n = f ，最一l = s ) 为1 ；否则，就是0 。 我们可以通过迭代的方法得到口和。我们注意到当计算口和，状态转移 的方向是相反的。 北京邮f 乜大学博 ：学位论文 第2 章t u r b o 码 口疗( s ) = 尾( s ) = 其中y 是状态的个数。 y 1 一。( s ) ( 疋，s ，s ) s = o 尸0 & 一( s ) 一( 尺疗，s ，s ) jj = o i = o 兰酗1 + l ( s ) 一+ l ( 一 q 。 ! 三q ! ! v l 一( s ) 以i ( 兄，s ，s ) 由于编码总是从零状态开始，我们定义口的初始值为 啪，= 器= 确 p 4 ， 对于的初始状态将随结束方式的不e l 而不同。 如果结束方式是归零的，则 眦，= 0 三i 二 p 5 ， 如果结束方式是不归零的，则 风g ) = 专，s - o ，2 y - 1 ( 2 - 6 ) 最后，我们可以计算外信息为 l e = a n 一三口拧一三屯，( 2 7 ) 其中三为 北京邮电大学博l 学位论文第2 章t u r b o 码 ， 2 血疗2 7 霸( 2 - 8 ) 上面，我们简要介绍了t u r b o 的发展和编译码结构。对于t u r b o 的每一个组 成部分以及其设计的要点，我们都给出了我们的解释。下面，我们将介绍另一种 重要的l d p c 码。本文的研究工作也主要是围绕这两个码来进行的。 北京邮电大学博卜学位论文第3 章l d p c 码 第3 章l d p c 码 t u r b o 码的成功同时导致了另一类具有相似特征，并同样具有逼近香农限性 能的码一l d p c ( l o w d e n s i t y p a r i t y - c h e c k ) 码一被”重新”发现【1 2 1 5 。l d p c 码最 早是由g a l l a g e r 在它1 9 6 0 年的m i t 博士论文中提出的 1 3 】。 在接下来的3 5 年时间里，除了少数例外( 如z y a b o l v 和p i n s k e r 1 7 ，t a n n e r 【1 8 】，和m a r g u l i s 1 9 的工作) ，l d p c 码基本上被遗忘了。l d p c 码可分为二进 制l d p c 码和多进制l d p c 码，这里我们主要讨论二进制l d p c 码。 本章讲述有关l d p c 码的理论研究和实际实现方面的一些基本知识。包括： l d p c 码的矩阵表示和图形表示方式，l d p c 码的分类，l d p c 码的常见设计方 法， 以及l d p c 码的编码译码方法。 3 1l d p c 码的表示方法 与经典码类似，作为一类线性分组码，l d p c 码可以用矩阵来描述。两种 常用的矩阵( 生成矩阵和校验矩阵) 在描述一个码的时候是基本等价的，而且 是可以互相转化的。对l d p c 码，通常大家选择用校验矩阵表示方法。l d p c 码的校验矩阵非常稀疏( 即校验矩阵绝大部分元素是零，非零元素非常少) ， t a n n e r 提出了图形描述方法。本节着重介绍这两种表示方法。 3 1 1 矩阵表示 与其它线性二进制码一样，一个( n , k ) l d p c 码的码空间可以看作向量空间 只的一个k 维子空问c 。因此，我们可以找到c的一组基 b = g o ，g l ，g k i ，对于信息位f 2 ，= o ，1 ，k - 1 ，码字c c 可以写成 c 2 u o g o + u l g l + + u k l g k l 。 即c = u g ，其中u 是行向量【- 0 u 1 z l k l 】， g 是七珂生成矩阵，其行向 量是，g l ，一l 。 对应的，我们可以找到它的( 聆一k ) x k 校验矩阵h ，满足胡r = 0 。定义 n l 为h 矩阵的行数， 即m = n - k ，那么h 矩阵的行向量忽，f 0 ，1 ，m - 1 ) 组成 c 上的生成矩阵。 北京邮电大学博十学位论文第3 章l d p c 码 l d p c 码通常划分为规则l d p c 码和不规则l d p c 码。 规则l d p c 码指l d p c 码的h 矩阵，每列恰有纹个l ， 每行恰有 啡= a ( n m ) 个1 ，其中吐“m ( 等价的缈， c o , 时， 这类码的码重分布很好。此外，这类码的编码复杂度较低。g a l l a g e r 码己被用 在c d m a 通信系统中。此后，由m a c k a y 等人继续扩展。 3 2 2 m a c k a y 码 m a c k a y 独立发掘了l d p c 码 1 2 1 ，并指出此类码具有接近香农限的性能。 它的个人网页上列出了一系列可用于硬盘存储、无线通信等环境下的性能优秀的 l d p c 码，其中绝大多数是规则l d p c 码。 下面列举它的部分设计方案： 1 ) 随机构造一个h 矩阵，尽量使列重为鳞，并保