（电路与系统专业论文）通信系统中ldpc码编码技术的研究.pdf

南京邮电大学硕士论文 中文摘要 摘要 自从香浓开创性的建立起信息论以来，已经5 0 年有余，在市场需求的不断推动下， 人们一直不懈努力，以寻求复杂度合理的更优秀的编译码方法，去逼近香浓理论的理想界 限。令人鼓舞的是，在这个过程中，已经取得了许多进展。在t u r b o 码巨大成功的带动下， m a c k a y 等人重新研究了最早由g a l l a g e r 于1 9 6 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 码 的结构特性、校验矩阵和编译码原理。 针对多进制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 码，实现 容易，复杂度低。 l d p c 码的专利早已过期，使用完全免费。因此，l d p c 码是一种性能优异、物美价廉 的纠错码，必将在下一代移动通信系统的信道编码方案选择中占据一席之地，拥有广阔的 市场前景。 关键词：信道编码；规则码；非规则码；l d p c 码；围长 a b s t r a c t i nt h el a s t5 0y e a r s ，t h a n k st oc l a u d e e s h a n n o n ，w h op r e s e n t e dt h ec o n c e p to f i n f o r m a t i o nt h e o r yi nt h el a s tc e n t u r ya n dt h em a r k e t i n gn e e d ss t i m u l a t e du sal o tt of i n dag o o d c o d e ，t oa p p r o a c ht h ew e l lk n o w ns h a n n o nl i m i t e x h i l a r a t i n g l y , m a n yd e v e l o p m e n t sh a v eb e e n a c h i e v e di nt h i sp r o c e s s a f t e rt h eg r e a ts u c c e s so ft u r b oc o d e s ，m a c k a ye t c ，r e d i s c o v e r i e dt h e l d p cc o d ew h i c hw a sf i r s td i s c o v e r e db yg a l l a g e ri n19 6 2a n dp r o v e di ti sak i n do fg o o dc o d e w h i c hh a sa b i l i t yo fa p p r o a c h i n gs h a n n o nl i m i t n o w a d a y s ，l d p cc o d eh a sb e c o m eah o ts p o t o fr e s e a r c hi nt h ea r e ao fe r r o rc o r r e c t i n gc o d ea n dh a sab r i l l i a n tf u t u r ei nm a n ya r e a s i nt h i sp a p e r t h eb a c k g r o u n d ，t h e o r ya n dr e s e a r c hd e v e l o p m e n to fl d p cc o d e sa r e i n t r o d u c e d ，i ta l s oi n t r o d u c e st h es t r u c t u r a lp r o p e r t i e s ，c h e c km a t r i c e s ，a n dt h ec o d i n ga n d d e c o d i n gp r i n c i p l eo fl d p cc o d e s i ta n a l y z e st h em a i nf a c t o r st h a ta f f e c tl d p cc o d e s p e r f o r m a n c e ，a n dt h er e l a t i o n s h i p sb e t w e e nt h ep e r f o r m a n c ea n dt h el e n g t ho fc o d e ，t h el e n g t h o fc y c l e ，t h en u m b e ro fi t e r a t i o na n dt h ei n f o r m a t i o no fc h a n n e l i ta l s oa n a l y z e st h ec o d i n ga n d d e c o d i n gi ng f ( q ) f i e l da n dg i v eas u b - o p t i o n a la l g o r i t h mt op e r f o r mt h ep r o c e e d ，b yu s i n g s i m p l i f i e da l g o r i t h m ，s o m ed a t au s e di nc o d i n gh a v e b e e nl i s t m o s to ft h el d p cc o d e sa r ec o n s t r u c t e db yr a n d o mm e t h o d so rc o n s t r u c t e dd e l i b e r a t e l y b ya l g e b r aw a y s i nt h i sp a p e r w ep r e s e n tan e w m e t h o dt oc o n s t r u c tl d p cc o d e sw i t hl a r g e g i r t hb a s e do ng r a p h ，a n dw ec a l l e dt h e mt h eg r a p hc o d e s ，t h eu s eo fi n t e r l e a v e r si nl p d c c o d e sa l s oi n v o l v e d t h r o u g hs i m u l a t i o n ，t h i sp a p e rp r o v e st h a tt h eg r a p hc o d e sp e r f o r mb e t t e r t h a nt h ec o m m o nl d p cc o d e s ；w h a t sm o r e ，t h e ya r er e g u l a r ( o rq u a s i r e g u l a r ) c o d e sw h i c h c o u l db ee a s i l yp r a c t i c ew i t hl o wc o m p l i c i t y w ed on o th a v et op a yf o rt h el d p cc o d e sf o rt h es a k eo ft h ee x p i r e dp a t e n tr i g h t t h e r e f o r e ，l d p cc o d e sa r eg o o de r r o rc o r r e c t i n gc o d e sw i t hf r e ec h a r g ew h i c hw i l lm a k em o r e a d v a n t a g ei nt h ef u t u r e s ol e t ss a yt h a tt h el d p cc o d ew i l lb eap r e f e rc h a n n e lc o d ei nt h e n e x tg e n e r a t i o nm o b i l ec o m m u n i c a t i o n k e y w o r d s ：c h a n n e lc o d i n g ，r e g u l a rc o d e s ，i r r e g u l a rc o d e s ，l d p cc o d e s ，g i r t h l l 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：灶日期：盟妒，乙 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：迎导师签名：越豫魄型 南京邮电大学硕士研究生学位论文 第一章绪论 第一章绪论 在数字通信系统中，由于信道特性的不理想和噪声的影响，接收端根据接收信号判定 的发送信息不可避免地会发生差错，在这种情况下采用信道编码是降低误码率的重要手段。 而在移动通信系统中，由于其传播环境更为复杂，所以对信道编码的纠错能力有着更高的 要求。 在过去的5 0 多年来，在香浓信息论【l l 的指导下，纠错编码技术不断进步，不断涌现出 性能更加接近香浓限的编码方法，从第一代移动通信系统中采用的b c h 码到第二代移动通 信系统中采用的卷积码f 2 j ，再到第三代、第四代移动通信中采用的t u r b o 3 1 码和l d p c 码【4 1 。 l d p c 码，即低密度校验码( l o wd e n s i t yp a r i t yc h e c kc o d e s ) ，是于1 9 6 2 年由m i t 的r o b e r tg a l l a g e r 在他的博士论文【6 】咔一提出，该论文论述了基于低密度校验矩阵的纠错码， 提出了两个刨新性的观点：用简单的稀疏校验矩阵的随机置换来模拟随机码；在信息 的先验概率和信道特性已知情况下的迭代译码方法。可惜的是，他所做的工作由于客观条 件的限制在很长的一段时间内被科学界所遗忘。经数十年的沉寂，随着计算机计算能力的 增强和相关理论( 如图论、信度传播理论、t u r b o 码理论等) 的发展，m a c k a y 和n e a l 又 重新发现了它，并证明了它在与基于信度传播理论( b p 理论) 的迭代译码算法相结合的条 件下具有逼近香浓限的性能1 5 】。l d p c 码的重新发现是继t u r b o 码之后在纠错编码领域的又 一重大进展。 l d p c 码的特点是：精心设计的l d p c 码其性能优于t u r b o 码，具有较大灵活性和较 低的差错平底特性【6 】描述简单，对严格的理论分析具有可验证性，译码复杂度低于t u r b o 码，硬件复杂度低，所以更适合硬件实现且可实现完全的并行操作，吞吐量大，极具高速 译码的潜力。 l d p c 码的优异性能及其在信息可靠传输中的良好应用前景( 例如光通信、卫星通信、 深空通信、下一代移动通信系统、高速与甚高速率数字用户线、光和磁记录系统等) ，已引 起世界各国学术界和产业界的高度重视，成为当今信道编码领域最瞩目的研究热点。近几 年国际上对l d p c 码的理论研究已取得重要进展，在应用基础乃至工程应用方面的研究亦 正在全方位开展。可以预见，在不久的将来l d p c 码将凭借它良好的纠错性能和较低的复 杂度，必然会在未来移动通信系统中发挥重要的作用。 南京邮电火学硕士研究生学位论文 第一章绪论 1 1 信道编码理论 通信系统的基本目的在于将信息由信源高效且可靠( 有时还需安全) 地传送到信宿， 其应用领域包括深空通信、光纤通信、移动和固定无线通信、因特网数据传输和数据存储 等。但是，在信息传输的通道信道中不可避免地存在各种各样的噪声与干扰，使得信宿与 信源相比总不完全一致，从而降低通信系统的可靠性。传统的观念认为，在功率受限的情 况下，在有扰信道上实现无差错信息传输的唯一办法是使传输的速率为零。1 9 4 8 年，贝尔 实验室科学家香浓发表了一篇题为通信的数学理论的论文改变了人们传统的看法，为 现代通信和信息论的发展奠定了理论基础。在这篇论文中，香浓首次阐明了在有扰信道中 实现可靠通信的方法，指出实现有效而可靠地传输信息的途径是编码。一般而言，数字通 信系统可分成信源、信源编码器、信道编码器、编码信道、信道译码器和信源译码器和信 宿七个部分，如图1 1 所示。 图1 - 1 数字通信系统 根据通信的数学理论一文可知：任意离散输入无记忆平稳信道存在信道容量c ， 对于预期的任一数据速率r 0 ，有可能设计一对信道编译码器，以 保证该信道中速率为r 的数据传输具有小于p 的译码错误概率。 对于一个确定的信道，即带宽一定时，香浓证明了信道容量c 取决于传输信号与噪声 的比值( s n r 臣 i 信噪比) ，信道容量c 是关于信噪比值的增函数。设一个信道容量c 确定时， 当信息传输速率r 无限逼近c 时，为了实现无差错传输所需要的最小信噪比值被称为香浓 ( 容量) 限。 该信道编码定理指明，在有扰信道中，通过合适的编码，只要信息传输速率小于信道 容量，就有可能实现任意可靠性要求的信息传输。不幸的是，此定理的证明仅仅是存在性 证明，并没有给出编码的具体方法。 2 南京邮电大学硕：t 研究生学位论文 第一苹绪论 自从香浓提出信道编码理论以来，众多学者争相寻找逼近香浓容量限的纠错码的具体 构造方法，并且逐渐形成了信息论的一个重要分支信道编码理论。 从构造方法上信道编码可分为分组码和卷积码两大类。在分组码方面，第一个分组码 是1 9 5 0 年发现的能纠正单个错误的h 锄m i n g 码【7 j ，其后，又发现了多个码长较短的分组码， 女 i g r a y 码、r m 码、循环码等。在1 9 5 9 年发现的能纠多个错误的b c h 码以及在1 9 6 0 年发现 的非二进制r s 码在分组码领域具有十分重大的意义。需要指出的是，分组码的译码主要采 用基于代数的硬判决译码。 卷积码最早由e l i a s 于1 9 5 5 年提出，它具有动态格图结构，可用有限状态机来描述其状 态。由于缺乏有效的理论研究工具，对卷积码的有效研究成果不是很多，对于性能好的卷 积码，主要借助于计算机进行搜索来获得。与分组码不同，卷积码的译码采用概率译码， 被广泛应用于实际工程中。1 9 6 6 年，f o m e y 提出了级联码( c o n c a t e n a t e dc o d e s ) ，一般采 用精心选择的r s 码作为级联码的外码，卷积码或分组码作为级联码的内码。f o m e y 的研究 表明，级联码在译码复杂度没有显著增加的前提下，较大程度地改善了码的性能。 根据对接收信号处理方式的不同，纠错码的译码可分为硬判决译码和软判决译码。硬 判决译码是基于传统纠错码观点的译码方法，解调器首先对信道输出值进行最佳硬判决， 然后将判决结果送入译码器，译码器根据这一判决结果，利用码字的代数结构来纠正其中 的错误。与硬判决译码相比，软判决译码则充分利用了信道输出波形信息。解调器将匹配 滤波器生成的一个实数值送入译码器，由于这个实数值包含了比硬判决更多的信息，译码 器可以通过概率译码充分利用这些信息，从而使译码具有更大编码增益。与硬判决译码相 比较，软判决译码在加性高斯白噪声( a w g n ) 信道上有2 3 d b 的编码增益，在衰落信道 中编码增益要超过此值。由于解调器向译码器输入的是实数值，这种软判决译码又被称为 软输入( s o f t i n p u t ) 译码。 软判决译码有两类基本的译码算法：一类是最小码字错误概率软判决译码，女h f o m e y 的广义最小距离译码、c h a s e 算法和v i t e r b i 算法等：另一类是最小符号错误概率软判决译码， 如最大后验概率( m a p ) 译码算法【8 】及本文后面所要讲述的和积译码算法等。 显然，考虑到级联码的外码也可采用软判决译码，那么需要对内码的软判决译码进行 修改。在级联码中，内码采用软输入译码，输出仍然是硬判决信息，从而使得外码无法充 分利用内码的译码信息，如果将内码的输出改成反映译码可能性的概率值来表示，这样就 可以让外码也采用软判决译码算法译码，进而改善整个译码的性能。这种对软判决译码进 行修改的算法被称为软输出译码。软输出译码算法主要有逐符号m a p 算法和修正v i t e r b i 算 法，如s o v a t 9 j 等。 3 南京邮电大学硕士研究生学位论文 第一覃绪 论 构造接近香浓容量限的纠错码一直是信道编码理论研究的理想目标，但直至j j 2 0 世纪9 0 年代以前，这个目标仍是可望而不可及的。1 9 9 3 年，c b e r r o u 等人提出的t u r b o 码【3 j 被看作 信道编码理论领域的重要里程碑。c b e r r o u 等人将卷积码和随机交织器相结合，同时采用 软输出迭代译码来逼近最大似然译码，取得了超乎寻常的优异性能。在a w g n 信道中，采 用b p s k 调制的1 2 码率t u r b o 码，码长为6 5 5 3 5 时采用随机交织器进行交织，在1 8 次迭代译 码的情况下，在信噪比为0 7 d b 时，比特误码率可以达到l o 一，距香浓限仅0 0 0 4 5 d b 1 0 】。 t u r b o 码的性能一举逼近了香浓容量限，是一种信道编码理论界一直梦寐以求的可实用的好 码，它的出现标志着信道编码理论研究进入了一个崭新的阶段。 t u r b o 码实际上是两路卷积码的并行级联，一路信息位直接进行编码，另一路信息位则 要先经过一个交织器，进行信息位的随机置换，然后进行编码。交织器有将突发错误离散 化的作用，但更重要的作用是它改变了码的重量分布，减少了重量很小和重量很大的码字 的出现，重量谱集中在中等重量的码字上，改变了码字的距离特性；随机交织使信息位之 间尽可能具有长的关联，让两个短的卷积码实现了等效随机长码的性能，使码的特性接近 香浓随机编码思想，从而获得了逼近香浓限的性能。 t u r b o 码的优异性能也来源于其迭代译码原理，即采用软输入软输出( s i s o ) 的迭代 译码算法，迭代过程中分量译码器之间互相传递外信息( e x t r i n s i ci n f o r m a t i o n ) ，用来促进 各分量码的译码。随着迭代次数的增加，迭代译码高概率渐进收敛于最大似然译码，是一 种低复杂度的次最佳译码。这就是所谓的“t u r b o 原理”，t u r b o 码这一名称也是来自于此。 在t u r b o 码的研究过程中，人们重新发现g a l l a g e r 早在1 9 6 2 年就提出的低密度校验码亦 是一种好码，它的译码性能同样可以逼近香浓限而且它的译码复杂度和码长呈线性关系。 由于l d p c 码在码长稍长时，性能就能超过t u r b o 码，并且译码复杂度低、具有可并行译码 以及译码错误可检测性等特点，l d p c 码成为了信道编码理论新的研究热点之一。研究表 明，t u r b o 码只是l d p c 码的一个特例，两者都是基于图模型上的低密度码，译码算法具有 等价性，从而使两者在基于图模型的编码研究中得到了统一。 1 2l d p c 码的研究进展 l d p c 码具有非常好的性能，但是其校验矩阵大多还是由计算机随机构造的，没有找 到一种好的系统化的设计方法来得到其校验矩阵。目前对构造好码的研究主要分为两个方 面，一个是通过寻找好的构造码的分析方法，另一个是构造综合性能更好的码。在分析方 法构造l d p c 码方面，y uk o u 和s h ul i n 等人对于基于有限几何的l d p c 码做了研究【l 1 2 j ， 4 南京邮电大学硕士研究生学位论文 第一荦绪论 利用几何方法构造码，给出了4 种基于欧几里德空间的点和线设计出的码。这些码具有很 好的最小距离特性。有限几何l d p c 码可以采用很多种译码方法，采用b p 传播迭代译码 算法可以获得很好的性能，更重要的是它可以表示成循环码或者半循环码的形式，利用生 成多项式决定的简单反馈移位寄存器就可以实现编码，编码时间与码长呈线性关系，这种 特性是其他l d p c 码所不具备的，在实际应用中非常重要；同时有限几何l d p c 码可用不 同的方法扩展或截短到其他的码。s j j o h n s o n 和s r w e l l e r 也给出了一种称为k i r k m a n t r i p l e 系统的组合设计方法构造非随机的l d p c 码【1 3 l ，在码长较短时性能好于随机的码。 而b a n ev a s i c 利用反p a s c h 仿射几何设计出了最小距离至少为6 的码【1 4 1 。 在构造综合性能更好的码方面，研究者们提出了很多不同的方法。在给定二部图的校 验节点数和最大的校验节点的度数时，j c a m p e l l o 年1 d s m o d h a 给出了一种比特填充的方 法来构造二部图【1 5 】1 1 6 】，可以得到码率更大的码。y o n g y im a o 幂1 a m i rh b a n i h a s h e m i 介绍了 一种当码长和度数确定时寻找好码的方法1 1 7 】。r i c he c h a r d 和s h i hc h u nc h a n g 提出了i 旋转 l d p c 码【博l ，该码最大的特点就是易于硬件实现。x i a o y uh u 幂i e e l e f t h e r i o u 等人用逐步边 增加的方法设计具有好的距离特性的码且该编码可以线性实现1 1 9 1 。 在下一代移动通信中，对信道编码的要求越来越高，传统的卷积码已经不能满足其需 求，而l d p c 码正是这样一种具有很多优良特性，可以作为下一代移动通信系统编码方案 的一种好码。 1 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 码要么是随机生成的，要么是通过代数的方法构造而成的，本文提出了 一种基于图论的方法构造的主要就围长因素进行改进的l d p c 码，并就其与交织器的联 合使用做了些探讨。 全文共分为六章，具体安排如下： 第一章是本文的绪论，对编码理论及目前的研究进展做了概述。 第二章主要介绍了导致l d p c 码被重新发现的t u r b o 码，包括编码和译码算法及一些 相关仿真数据。 南京邮电大学硕士研究生学位论文 第一章绪论 第三章介绍了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 码中如何使用做了一些探讨。 第六章概括性的总结了全文的工作，并对今后的研究方向进行展望。 6 南京邮电大学硕士研究生学位论文 第二章t u r b o 码 第二章t u r b o 码 t u r b o 码的诞生直接导致了l d p c 码的被重新发现，所以，提到l d p c 码就不能不提 到t u r b o 码，为此，本文首先简单的回顾一下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 码的研究方向主要有：t u r b o 码与多阶编码调制结合、与空时码结合以及把 t u r b o 码的思想和均衡技术结合等。 t u r b o 码是一种级联码，可分为并行级联( p c c c ) 和串行级联( s c c c ) 两种。在此 主要介绍并行级联的t u r b o 码。 本章首先介绍了t u r b o 码的编译码结构，接着对改进的译码算法s o v a 算法做了 详细的介绍，最后介绍了几种常用的交织器并就s o v a 译码算法下联合了交织器的t u r b o 码的性能做了计算机仿真。 2 1t u r b o 码的编码结构 2 1 1t u r b o 码编码器的基本结构 不o t u r b o 码由两个循环系统卷积码编码器通过一个交织器并联而成，其结构如图2 1 所 岛 。 ” c i l 截 编码器l 断 i 交织器 器 q 编码器2 图2 1t u r b o 码的基本结构 7 南京邮电大学硕士研究生学位论文第二章t u r b o 码 从图2 1 可以看出，信息位“直接进入编码器1 产生校验位q ，经过交织器后进入编 码器2 产生校验位岛。因此，虽然两个子编码器都对输入序列进行编码，但两个子编码器 所对应的输入序列却是不一样的。由于t u r b o 码是系统码，因此信息位直接输出产生， 即c o 等于u 。由图2 一l 可得出，输入个信息位产生三位输出，因此如果没有截断，图2 - 1 所示的t u r b o 码的码率为1 3 。通常情况下图2 1 中的两个编码器是相同的。 2 1 2 非系统卷积码( n s c ) 和循环系统卷积码( r s c ) 从图2 - 1 可知道t u r b o 码是由卷积码组成的，因此要讨论t u r b o 码，首先先来介绍一 些卷积码的基本知识。 1 卷积码 卷积码是这样一种编码方法：它将k 个信息比特编成刀个比特，k 和，2 通常都很小， 特别适合以串行形式进行传输且延时比较小。 卷积编码器包括一个由段组成的输入移位寄存器，每段有k 级，共n k 位寄存器； 一组n 个模2 加法器；一个由刀级组成的输出移位寄存器。对应于每段k 个比特的输入序 列，输出刀个比特。所以刀个输出比特不但与当前的k 个输入比特有关，而且与以前的 ( 一1 ) 尼个输入信息比特有关。整个编码过程可以看成是输入信息序列与由移位寄存器和 模2 加法器连接方式所决定的另一个序列的卷积，卷积码也是由此而得名的。通常把 称为约束长度( 也有部分参考文献中把n n 或( 一1 ) 称为约束长度) 。常把卷积码记作 ( 以，k ，n ) ，它的编码速率为r = k 玎。 卷积码的纠错性能随的增加而增大，而差错率随的增加而指数下降。在编码器 复杂性相同的情况下，卷积码的性能优于传统的分组码：但卷积码没有分组码那样严密的 数学分析手段，所以目前大多是通过计算机进行好码的搜索。这样带来的坏处是，当码长 很长的话，计算机搜索耗时非常长。 在卷积码中，有三个非常重要的概念：汉明距离、汉明重量和自由距离。两个卷积码 码字的汉明距离指这两个码字的对应位上数字不同的位的个数；汉明重量指码字中非零位 的个数，一个码字的汉明重量可以是这个码字和全零码字之间的汉明距离：自由距离指卷 积码中的任意两个码字的最小汉明距离，因此它也是所有可能的非零码字的最小汉明重 量。 r 南京邮电大学硕士研究生学位论文 第二荦t u r b o 码 在设计t u r b o 码时要用到两种特殊的卷积码编码器：非系统卷积码( n s c ) 编码器 和循环系统卷积码( r s c ) 编码器。 2 非系统卷积码( n s c ) 图2 2 所示的是一个非系统卷积码编码器，其中r 表示寄存器。 图2 - 2 非系统卷积码编码器 9 1 3 9 2 ， ( 1 ) 生成多项式 编码器的生成多项式表征了编码器的输出比特和移位寄存器中的内容之间的关系。通 常使用向量( 蜀，9 2 ，g n ) 表示卷积码的生成序列。如果移位寄存器的第f 位与编码器输出 的第歹位的加法器相连，则生成序列如的第，比特为1 ，否则为0 。图2 2 中编码器对应 的生成多项式为： g l = g l o ，g 9 1 2 9 1 3 ) = l ，1 ，0 ，1 ) ( 2 1 ) 9 2 = 9 2 0 ，9 2 l ，9 2 2 ，9 2 3 ) = 1 ，0 ，1 ，1 ) 当引入时间延迟因子d 后，可以用多项式的形式表示为： ( g l ，9 2 ) = ( 1 + d + d 3 ，1 + d 2 + d 3 ) ( 2 2 ) ( 2 3 ) 通常使用八进制形式表示它，则图2 - 2 所示的非系统卷积码编码器用八进制表示为 ( 1 5 ，1 3 ) 。 ( 2 ) 输出数据流 从图2 - 2 可见，输出比特( ，) 和输入比特吨之间的关系可以表示为： 或= g i ，矾扪r o o d 2 9 ( 2 4 ) 南京邮电大学硕士研究生学位论文 第二章t u r b o 码 = g ：，反，m o d 2 i = o ( 2 5 ) 采用多项式的形式，用d ( d ) 表示输入序列破，因此图2 2 中的输出对应的 ( x i ( d ) ，x 2 ( d ) ) 可以表示为： ( 一( d ) ，x 2 ( d ) ) = d ( d ) ( 1 + d + d s , 1 + d 2 + d 3 ) ( 2 6 ) ( 3 ) 编码器状态 在此用移位寄存器中的内容表示编码过程中编码器的状态。假定在输入信息序列前编 码器的状态为0 ，也就是说编码器的初始状态为全零状态。由于图2 2 所示的编码器共有 三个移位寄存器，因此这个编码器只能有八种可能的状态：0 0 0 , 0 0 1 ，0 11 ，1 】1 。在k 时 刻，当以进入编码器前可以称编码器正处在& 。状态，以进入编码器后使得编码器的状 态变为& ，输出的序列对( 或，) 由输入比特巩和编码器状态& 一，共同决定。 3 ，循环系统卷积码( r s c ) 图2 3 是一个循环系统卷积码编码器的结构图。首先，它是一个系统码，也就是说它 的输出中包含原始信息序列。从图中可以看出，循环系统卷积码的编码结构中包含有反馈 结构，这个反馈结构导致了r s c 的记忆性要比n s c 来得更长。 ( 1 ) 生成多项式 编码器的生成多项式为： 图2 3 循环系统卷积码编码器 g l = g i o ，g i l ，9 1 2 ，9 1 3 ) = 】，1 ，0 ，1 ) l o ( 2 7 ) 南京邮电大学硕士研究生学位论文 第二章t u r b o 码 9 2 = 9 2 0 ，9 2 l ，9 2 2 ，9 2 3 ) = l ，0 ，1 ，1 ) ( 2 8 ) 上式和n s c 的差别在于蜀。指加法器前的支路，而9 2 。指加法器和移位寄存器r 1 之间 的节点，因此对于r s c 来说，g 。总是1 。r s c 编码器的多项式表示形式为： 略m 篙等， 协9 ， 其对应的八进制形式为( 1 ，1 3 1 5 ) ，为书写方便，一般简记为( 1 5 ，1 3 ) 。 ( 2 ) 输出数据流 输出比特( t ，) 中包含信息位，因此对于每比特有： = 以，对于所有的尼 ( 2 1 0 ) 校验位由以和移位寄存器中的内容共同决定。和n s c 编码器不同，r s c 编码器中 的移位寄存器的内容受到生成多项式蜀的影响。校验位，信息位以以及之间的关系 如下： 可以将多项式表示形式记为： = 或+ g i ，- j ，m o d 2( 2 1 1 ) t = l = 9 2 ，1 , k 一，m o d 2( 2 - 1 2 ) i = o ( d ) , x 2 ( d ) ) 训d ) ( 1 ，篇等) ( 2 - 1 3 ) ( 3 ) 终止状态 在使用卷积码编码器时为了使译码简便，通常在编码开始和结束时，都要使编码器状 态归零。对于移位寄存器个数为v 的n s c 编码器，做到这一点很容易，只需输入v 个零即 可。对于r s c 编码器来说，如果同样使用v 个输入，使编码器状态归零，这v 个比特的数 据就不能是全零数据了，这是r s c 编码器中的反馈结构产生的结果。例如对于图2 3 的 r s c 编码器，如果当前的状态是1 1 0 ，则为使编码器状态归零输入就是1 0 1 。 2 1 3 截断器 图2 1 中的t u r b o 码编码器如果使用图2 3 所示的r s c 编码器作为其分量码编码器， 南京邮电大学硕士研究生学位论文 第二章t u r b o 码 那么由于图2 3 的r s c 编码器的码率为1 2 ，因此整个t u r b o 码的码率就是1 ( 2 + 1 ) ，即 1 3 。通常情况下，码率越低，其冗余就越大，所以如果要获得高于1 3 的码率，就要使 用截断器，周期性地删除些校验位。例如，要获得1 2 的t u r b o 码，可以删除编码器l 的奇数校验位和编码器2 的偶数校验位。截断又可称为收缩，收缩模式可用收缩矩阵p 表示。收缩矩阵的第一行代表第一个编码器的输出序列的收缩模式，第二行代表第二个编 码器的输出序列的收缩模式，以此类推。当收缩矩阵的某元素为1 时，所对应的数据位将 被传送，否则，该数据将被删除，这样做带来的后果就是信息的丢失，将会在一定程度上 恶化系统的性能，所以所删除的校验位一般不宜太多。 2 2t u r b o 码的译码 2 2 1 译码器结构 t u r b o 码的优异性能不仅在于它独特的编码结构，还在于其中的交织器的使用，更重 要是与编码结构相匹配的译码算法。香浓信息论告诉大家，最优的译码算法是概率译码算 法，也就是最大后验概率算法。但在t u r b o 码出现之前，信道编码使用的概率译码算法是 最大似然( m l ) 算法，虽然早在1 9 7 4 年就已经提出了作为m a p 算法的一种的b c j r 算 法f 2 0 j ，但由于其复杂性高，一直未应用于实际系统中。m l 算法是m a p 算法的简化，即 假设信源符号等概率出现，因此是次优的译码算法。 t u r b o 码的译码算法最早是在m a p 算法的基础上改进而来的，称之为b c j r 算法， 后来又产生了复杂度相对较低，更适应工程实践的l o g m a p 算法【2 1 1 、m a x l o g m a p 算 法【2 l 】以及软输入软输出v i t e r b i 算法( s o v a 算法【2 2 】) 。 t u r b o 码译码器结构如图2 4 所示。 图2 - 4t u r b o 码译码器结构 南京邮咆大学硕士研究生学位论文 第二章t u r b o 码 从图中可以看出，它由两个分量译码器构成。这两个分量译码器对应于编码器中的两 个编码器1 和2 ，如果两个编码器是相同的，那么这里的译码器也是相同的。交织器也和 编码器中使用的交织器是一样的，解交织器和交织器是配套使用的。每一个分量译码器都 可以产生一个叫做外部信息的变量厶。( 诈) 或厶。( ) ，这个变量在迭代过程中被传递。在 第一次译码时，由于没有厶。( 坼) ，所以译码器1 的输入只有接收到的信息位蚝和对应于 第一个编码器产生的校验位的接收比特碟，它们经过译码器后计算出外部信息的变量 厶。( 以) 。由于在t u r b o 码的编码器端，由编码器2 产生的校验位是经过交织后的信息位产 生的，因此在译码时，译码器2 的输入信息也要经过交织，所以译码器2 的输入是y 磊和 经过交织后的系统位以以及厶。( 吒) ，译码器2 的输出经过解交织后作为下一次的输入再 传递给译码器1 ，这样就形成了迭代过程。到达预定的迭代次数后译码器2 的输出经过解 交织后就可以得到信息比特的对数似然比( l l r ) 。从上面的分析可以看出t u r b o 码译码 器具有以下的特点： 1 串行级联； 2 迭代译码； 3 在迭代译码过程中交换的是外部信息； 4 概率译码。 2 2 2s o v a 算法 s o v a 算法也称为软输出的v i t e r b i 算法，它是在v i t e r b i 算法的基础上改进而来的。 由于在t u r b o 码出现之前，v i t e r b i 算法已经广泛应用于工程之中，因此和其他几种算法相 比，s o v a 算法更适合应用于工程中。 s o v a 算法是h a g e n a u e r 在1 9 8 9 年提出来的。他将v i t e r b i 算法进行了改进，改进后 的算法不仅能得出最大似然路径，而且能计算出每个信息比特的后验概率，这样就使 v i t e r b i 算法可以级联使用。 s o v a 算法对传统的v i t e r b i 算法做了两点改进：首先在计算路径的度量时，考虑了 先验信息，而且让先验信息在两个分量译码器之间传递；其次，算法可以以后验概率的形 式为每一个信息比特提供软输出。 v i t e r b i 算法的基础是寻找能够使后验概率最大的状态序列，即 南京邮电大学硕士研究生学位论文 笫二章t u r b o 码 尸( 箕ly j 忌) - - e ( s ；, ，y j 2 ； ( 3 ) 与码长和日矩阵的行数相比，p 和兄都很小。 南京邮屯大学硕士研究生学位论文 第三豪l d p c 码基础 图3 1 ( 2 0 ，3 ，4 ) l d p c 码的校验矩阵 矩阵h 的每列均包含五个“1 ”，表示每个码元变量受到相同数目的校验约束，每行均 包含p 个“1 ，表示每个校验方程对相同数目的码元变量进行校验约束。由于p 和五都很 小，校验矩阵日具有很低的“密度”，因此由校验矩阵日所确定的码被称为l d p c 码( l o w d e n s i t yp a r i t yc h e c kc o d e ) 。g a l l a g e r h 正u f 了当兄 2 时，这类码具有很好的汉明距离特性。 规则l d p c 码通常用( ”，五，p ) 来表示，其中刀为码长，五和p 的含义不变。图3 1 给出了一个 ( 2 0 ，3 ，4 ) 规贝j j l d p c 码的校验矩阵。 当校验矩阵各列( 行) 中“1 的个数不全相同时，就得到了非规贝f l d p c 码【3 j j 。非规 贝, o l d p c 码通常用度序列分布函数来表示，在给出l d p c 码的二部图描述之后本文将介绍非 规贝3 j l d p c 码的度序列表示。 3 2l d p c 码的二部图表示及非规则l d p c 码 因子图模型是当前较为常用的表示l d p c 码的图模型，它归纳了目自仃所有的图模型定 义，提供了一个关于迭代译码的一般性框架。因子图模型实质上是表达一个全局函数到一 组局部函数乘积的有效分解。 因子图是表达一个形如式( 3 6 ) 的函数因式分解结构的二部图： g ( x t ) = h u ( ) ( 3 - 6 ) 其中，是离散下标集，是 而，恐，矗) 的一个子集，厂( ) 是以子集中元素为变量的函 数。因子图中，有对应于薯的变量节点和对应于乃的因子节点，当且仅当一是乃的自变量 时，变量节点薯和因子节点乃之间有边相连。 1 9 o o o o o l o o o o 0 o i o o 0 o o o o l o o o i o o o o o o o l o o o o o o d o o o o ooo o o o o o d o o o l o o o o o l o o o o o 0 o j o o o l o o o o ；o o o o o l o