（信号与信息处理专业论文）深空通信中ldpc码译码性能分析.pdf

摘要 摘要 深空通信传输距离遥远，信号能量衰减严重，需要用高增益的信道编译码等 技术措施来确保信息可靠传输。低密度奇偶校验( l o w d e n s i t yp a r i t yc h e e k ，l d p c ) 码以其卓越的性能，正在深空通信领域得到越来越多的关注。因此，如何对l d p c 码译码性能进行有效地分析，并设计出性能优越的l d p c 码是本文所要研究的关键 问题。 本文首先在讨论了l d p c 码的基本概念及编码算法基础上，重点对和积译码、 最小和译码及其改进等译码算法进行了详细地分析。实验结果表明，改进的最小 和译码算法的准确性逼近和积译码算法，复杂度较低，适合工程应用。 其次，研究了l d p c 码的几种译码性能分析方法。其中，e x i t 图法是从互信息 的角度分析l d p c 码译码性能，较密度进化理论和高斯逼近法具有更好的准确性和 鲁棒性，但是e x i t 图法存在不能自动搜索译码阈值和度分布对的问题。针对这一 问题，本文提出了一种新的译码性能分析方法a p s o e x i t 图法。该方法设计 了衡量e x i t 曲线匹配程度的全局代价函数，运用a p s o 算法对度分布对进行快速迭 代优化，迭代过程中无需固定c n d ( c h e e kn o d e sd e e o d e r 校验节点译码器) 曲线， 可以获得e x i t 曲线更加匹配的优化度分布对和更高更接近s h a n n o n 眼的译码阈值。 最后，将a p s o e x i t 图法搜索到的度分布对和译码阈值应用于校验矩阵构造 中，得到了性能优良的l d p c 码。同时将l d p c s p c 联合编译码方法引入深空通信， 设计出两种适合于深空通信的l d p c 码编译码方案。仿真结果表明，所提出的 a p s o e x i t 图法译码性能分析方法有效可行，两个设计方案在信噪比大于0 7 d b 时，误比特率均低于1 0 ，可以满足深空通信的需求。 关键词：深空通信l d p c 码和积译码算法a p s o e x i t 图法 a b s t r a c t a b s t r a c t d u et o l o n gd i s t a n c ea n dg r e a ts i g n a ll o s so fd e e ps p a c ec o m m u n i c a t i o n ，i ti s n e c e s s a r yt oa d o p th i 曲一g a i nc h a n n e lc o d e sa n do t h e rt e c h n i q u e st o p r o t e c tt h e i n f o r m a t i o nt r a n s m i s s i o nr e l i a b l ya n de f f e c t i v e l y l d p c ( l o w d e n s i t yp a r i t yc h e c k ) c o d e sh a v e b e e nr e c e i v e dm o r ea n dm o r ea t t e n t i o nf o rt h e i ro u t s t a n d i n gp e r f o r m a n c ei n d e e ps p a c ec o m m u n i c a t i o n t h i st h e s i sd e a l sw i t hi s s u et h a th o wt oa n a l y z ed e c o d i n g p e r f o r m a n c ee f f e c t i v e l y , a n dt od e s i g ns u p e r i o rp e r f o r m a n c eo fl d p cc o d e s b a s e do na n a l y s i so fb a s i cc o n c e p t so fl d p cc o d e sa n d e n c o d i n ga l g o r i t h m s ，b p , m i n - s u ma n di m p r o v e dm i n s u m d e c o d i n ga l g o r i t h m sa r ed i s c u s s e di nd e t a i l e x p e r i e n c es h o w st h a tt h ei m p r o v e dm i n s u ma l g o r i t h mi sc l o s e rt ob pa l g o r i t h mi n a c c u r a c y , a n dl e s sc o m p l e x i t yi np r a c t i c a la p p l i c a t i o n t h e n ，s e v e r a ld e c o d i n gp e r f o r m a n c ea n a l y s i sa l g o r i t h m sa r er e s e a r c h e d e x i t c h a r ta l g o r i t h mw h i c hi su t i l i z e dt oa n a l y z ep e r f o r m a n c e t h r o u g hm u t u a li n f o r m a t i o n ，i s m o r ea c c u r a t ea n dr o b u s tt h a nd e n s i t ye v o l u t i o nt h e o r ya n dg a u s s i a na p p r o x i m a t i o n m e t h o d s an e wa p s o e x i tc h a r ta l g o r i t h mi sp r o p o s e ds i n c en o i s et h r e s h o l da n d d e g r e ed i s t r i b u t i o n sc a n tb es e a r c h e db ye x i tc h a r ta l g o r i t h ma u t o m a t i c a l l y a n o v e r a l lc o s tf u n c t i o ni sd e s i g n e dt om e a s u r et h em a t c h i n gd e g r e eo fe x i tc u r v e s t h e n t h ed e g r e ed i s t r i b u t i o n sa r eo p t i m i z e d i t e r a t i v e l yb ya d a p t i v ep a r t i c l es w a r mo p t i m i z e r ( a p s o ) a l g o r i t h m ，w h i c hd o e s n tn e e dt of i xt h ec n dc u r v e t h e r e f o r e ，m o r em a t c h e d d e g r e ed i s t r i b u t i o n sa n dh i g h e rn o i s et h r e s h o l dc l o s e rt os h a n n o nl i m i tc o u l db e 0 b t a i n e d f i n a l l y , ac h e c km a t r i xi ng o o dp e r f o r m a n c ei sc o n s t r u c t e db ym e a n so ft h ed e g r e e d i s t r i b u t i o n s o p t i m i z e d f r o ma p s o e x i tc h a r t a l g o r i t h m t w o l d p c e n c o d i n g d e c o d i n gs c h e m e sw i t hl d p c s p ca l g o r i t h ma r ed e s i g n e da c c o r d i n gt ot h e r e q u i r e m e n to fd e e ps p a c ec o m m u n i c a t i o n s i m u l a t i o nr e s u l t ss h o wt h a tb o t hs c h e m e s c a nr e a c hb e rl e s st h a n10 一w h i l es n ri sa b o v e0 7 d b a n da p s o e x i tc h a r t a l g o r i t h mi se f f e c t i v ef o rd e c o d i n gp e r f o r m a n c ea n a l y s i s k e y w o r d s ：d e e ps p a c ec o m m u n i c a t i o n s u m - p r o d u c ta l g o r i t h m l d p cc o d e s a p s o e x i tc h a r t a l g o r i t h m 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：查丝日期兰塑：f ：! 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本人签名： 导师签名f 日期兰幽：! ： 日期丝望! 么：z 第一章绪论 第一章绪论 1 1 研究背景和意义 深空探测【1 ( d s e ：d e e ps p a c ee x p l o r a t i o n ) 是指脱离地球引力场，进入太阳系 空间和宇宙空间的探测。主要有两方面的内容：一是对太阳系的各个行星进行深 入探测，二是天文观测。深空探测是在卫星应用和载人航天取得重大成就的基础 上，向更广阔的太阳系空间进行的探索。随着2 1 世纪的到来，深空探测技术作为 人类保护地球、进入宇宙、寻找新的生活家园的唯一手段，引起了世界各国的极 大关注。通过深空探测，能帮助人类研究太阳系及宇宙的起源、演变和现状，进 一步认识地球环境的形成和演变，认识空间现象和地球自然系统之间的关系。从 长远来看，对深空的探测和开发具有十分重要的科学和经济意义，深空探测将是 2 1 世纪人类进行空间资源开发与利用、空间科学与技术创新的重要途径。2 1 世纪 深空探测的重要领域是月球探测、火星探测、水星与金星探测、巨行星及其卫星 的探测、小行星与彗星探测五个领域。并且近年来，各国的深空探测也取得了惊 人的成果。欧空局子1 9 9 8 年提前公布了名为“欧洲月球2 0 0 0 的探月计划；俄罗 斯在国内经济困难的情况下也不甘落后，制定了第二个月球探测开发计划一并已 开始实施，最终目标是在月球上建立月球基地；日本已于1 9 9 8 年7 月发射了行星 一b 火星探测器；英国在2 0 0 3 年发射了火星着陆器；美国更是雄心勃勃，除了计 划载人重返月球外，还制定了十年火星探测计划；2 0 0 6 年2 月中国政府发布的国 家中长期科学技术发展规划纲要( 2 0 0 6 - - 2 0 2 0 ) 将探月工程列为国家中长期科技发 展的重大专项，并于2 0 0 7 年1 0 月发射嫦娥一号，开始了为期一年的探月活动。 但是，目前在深空探测中，由于传输距离非常远，信号能量衰减严重，需要 用各种措施来弥补，因此深空通信的技术水平一直处于测控领域的最前沿，其中 包括高增益的编码和复杂的译码技术。随着卷积码的序列译码及其优化算法的出 现，深空通信系统采用纠错编码的优势得以体现。序列译码的应用使纠错编码系 统的性能得到显著改善。1 9 7 2 年飞往木星的“先锋1 0 号 和1 9 7 3 年飞往土星的 “先锋l l 号 使用由m a s s e y 和c o s t e l l o 构造的码率为1 2 ，约束长度为k _ 3 2 的 ( 2 ，1 ，1 2 ) t 系统q l i ( q u i c k 1 0 0 k i n ) 卷积码，译码采用改进的f a n o 树搜索三位软判决 序列译码算法。该系统在e b 佻为2 7 d b 时就达到l o 5 的b e r ，相比未编码的b p s k 系统，获得了6 9 d b 的编码增益。 纠错码【2 1 也即信道编译码，是深空探测中的关键技术之一，可以大大提高深空 2 深空通信中l d p c 码译码性能分析 通信的性能。从1 9 4 8 年香农在他的开创性论文通信的数学理论中首次提出在 有扰信道中实现可靠通信到目前为止，纠错码已有五十多年的历史，由最初的b c h 码逐步发展到目前越来越受关注和应用的t u r b o 码【3 a 】和l d p c 码【孓7 1 。l d p c 码虽 早在1 9 6 3 年就由r g g a l l a g e r 发明的，但是由于当时条件的限制，l d p c 码一度 被人们所忽略，直到t u r b o 码的发明才让人们重新意识到了l d p c 码。和t u r b o 码一样，l d p c 码也具有逼近香农限的性质，并且非正则l d p c 码性能甚至优于 t u r b o 码。因此，熟悉和了解l d p c 码的编译码原理及其性能分析对设计更适合于 深空通信、性能更优的码型起到了积极的指导作用。 1 2 纠错码的发展 纠错码是数字通信系统中的一个重要环节8 1 ，其目的在于提高通信的可靠性降 低低差错率。而所谓的通信系统就是完成信息传递所需的所有设备的总和，如图 1 1 所示，由于数字通信具有抗干扰能力强、便于差错控制、便于使用现代数字信 号处理、易于加密、可以综合传递各种信息等优点，因此数字通信系统更适应于 现代通信的要求。 。 图1 1 数字通信系统模型 而纠错码是深空通信中的重要环节，在香农的信息论建立以后，汉明 ( h a m m i n 曲、斯列宾( s l e p i a n ) 、普兰奇( p r a n g e ) 等人在5 0 年代初，根据s h a n n o n 的 思想，给出了一系列设计好码和有效译码的方法。随后，纠错码受到了越来越多 的通信和数学工作者的重视，使纠错码无论在理论上还是在实际中都得到了飞速 的发展。 五十年代至七十年代，主要研究各种有效的编译码方法，奠定了线性分组码 的理论基础。所以，在此基础上人们利用代数中的一些理论，通过代数的方法构 造了许多纠错码，并研究了与之相适应的译码算法。这些码字大部分都是线性分 组码，比如戈雷码、汉明码、循环码和b c h 码，它们的译码算法主要采用大数逻 辑译码和捕错泽码。但是这些码字都是短码，其纠错译码算法的复杂度是随着码 第一章绪论 3 长的增加成指数级增长，长码的实现十分困难，投入实际使用的主要是短码，而 这些短码的性能距离香农限很远。要达到香农限，必须要码长较长的编码，g a l l a g e r 在1 9 6 2 年提出了一种码字，这种编码因为校验矩阵的稀疏性，使得译码的复杂度 与码长保持线性的关系，码长较长时依然可以有效地译码。然而当时人们普遍认 为级联码更容易实现，以及一些技术条件的限制，导致人们忽视了这种编码的存 在。 卷积码【2 】也是在同一时期提出的另一类重要的纠错码，它在编码过程中引入了 寄存器，增加了码元之间的相关性。在相同复杂度的条件下可以获得比线性分组 码更高的编码增益，但是这种相关性同时也增加了分析和设计卷积码的复杂性。 随着人们对卷积码研究的深入，在卷积码的译码算法方面也出现了序列译码和 v i t e r b i 译码算法。因为v i t e r b i 译码算法的出现，卷积码逐渐成为研究和应用的重 点，后来出现了t c m 格栅编码调制技术，进一步确定了卷积码在纠错码应用中的 主导地位。 纠错码主要就分为如上所述的线性分组码和卷积码两类，它们各有优缺点。 此外由于在实际应用中短码的性能有限，只有长码才能得到优秀的性能，于是人 们设想是否能够在短码的基础上构造长码，由此提出了短码的级联或乘积来得到 长码，在提高编码性能的同时，能够在短码的基础上具有较低的译码复杂度。 到八十年代和九十年代初，法国的c b e r r o u 等人在卷积码和级联码的基础上， 于1 9 9 3 年提出了一种全新的编码方案t u r b o 码【4 1 ，在信道编码理论和应用中取得 了突破性的进展。这种编码能够在码长较长时逼近香农的理论极限，同时译码复 杂度也是可以接受的。t u r b o 码采用并行级联递归的编码器结构，是一种系统的卷 积码，其译码算法主要有m a p 算法、l o g m a p 算法和s o v a 算法等。t u r b o 码 之所以具有逼近香农限的性能，是因为其独特的编码结构和新的译码思想，其关 键技术是交织器的使用。t u r b o 码在子编码器中采用了反馈型的系统卷积码，且在 子编码器间引入交织器减少了子编码器间信息的相关性，模仿了随机编码的形式， 同时在译码中采用了软输入软输出的递推迭代译码形式，引入了迭代译码的思想。 在t u r b o 码获得巨大成功的启发下，另一类具有相似特征和性能的编码复活 了，这就是l d p c 码。l d p c 码是g a l l a g e r 提出的，d j c m a c k a y 、m n e a l 和n w i b e r g 等人对l d p c 码重新进行了研究，发现l d p c 码同样具有逼近香农限的性能。 m g l u b y 和m m i t z e n m a c h e r 等人对l d p c 码进行了推广，提出非正则的l d p c 码，这种码型的性能能够赶上甚至超过t u r b o 码的性能。同时，与t u r b o 码的译码 算法相比，l d p c 码的译码复杂度有很大的降低。 4 深空通信中l d p c 码译码性能分析 1 3l d p c 码研究现状 l d p c 码最早是由麻省理工学院r g g a l l a g e r 于1 9 6 3 年发明的【q 7 1 。在其博士 论文中，g a l l a g e r 提出了正则l d p c 码的构造方法、编译码算法以及最小汉明距离 分析和译码算法的性能分析。由于当时的条件限制，编译码器的硬件实现几乎是 不可能的：同时，因为没有足够计算能力的计算机，所以精确细致的仿真也不能 实施，g a l l a g e r 只能给出高于1 0 4 的误码率。因此，尽管l d p c 码有很好的纠错能 力，但仍被人们忽略了3 0 多年。 1 9 8 1 年，t a n n e r 在他的一篇奠基性的文章中正式提出了用图模型来描述码字 的概念，从而将l d p c 码的校验矩阵对应到被称为t a n n e r 图的双向二部图上。 t a n n e r 图的提出对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 码。上世纪9 0 年代后期，m a c k a y ， n e a l 等人重新发现了l d p c 码。通过大量仿真，m a c k a y 等人表明，和t u r b o 码一 样，l d p c 码也具有逼近s h a n n o n 限的性质。 m a c k a y 、l u b y 提出的非正则l d p c 码将l d p c 码的概念推广。非正则l d p c 码的性能不仅优于正则l d p c 码，甚至还优于t u r b o 码的性能，是目前已知的最 接近s h a n n o n 限的好码。 r i c h a r d s o n 和u r b a n k 也为l d p c 码的发展做出了巨大的贡献。他们提出了一 种r u 快速编码方法，在很大程度上减轻了随机构造g a l l a g e r 法在编码上的巨大运 算量需求和存储需求。其次，还发明了密度进化理论，能够有效的分析出一大类 l d p c 码译码算法的性能限。最后，密度进化理论还可以用于指导非正则l d p c 码 的设计，以获得尽可能优秀的性能。 k o u 和l i n 等人从代数、几何理论着手，用确定性算法构造出了性能也很好的 正则l d p c 码。和随机构造的正则l d p c 码相比，尽管性能上有很小的损失，但 具有严谨的数学结构，构造和性能分析更加精确；和随机构造的l d p c 码相比， 具有更低的错误平层，可以应用于有线通信、深空通信以及磁盘存储工业等对误 码率要求更加苛刻的场合；可以具有循环或者准循环的结构，极大的降低编码复 杂度，也为译码提供了更加方便的选择。 除此之外，在工程实现上，l d p c 码的研究也是非常广泛的。主要有基于f p g a 的实现、基于d s p 的实现以及v l s i ( 超大规模集成电路) 的实现。目前在第四代 移动通信中l d p c 码的提案已经提交；并且已有很多系统采用l d p c 码，基于l d p c 的编码方案也已被下一代卫星数字视频广播标准d v b s 2 采纳；i e e e 8 0 2 3 工作小 第一章绪论 组在面向双绞线的1 0 g b s 以太网标准“1 0 g b a s e t ”草案中，也采用了l d p c 码。 另外，由于l d p c 码在数学模型上的成功性，人们用l d p c 码对许多编码进行了 重新研究，获得了许多新的认识和成果。 m 。c h i a n i 等对l d p c 码用于有记忆衰落信道时的性能进行了评估。b m y h r e 提出一种速率自适应l d p c 编码调制的方案用于慢变化平坦衰落信道，经推广还 可应用于p e c a r q 系统。 f l a r i o n 开发的集成了v - l d p c 的f l a s h - o f d m 移动无线芯片组己可用于p 的 移动宽带网。v o c a lt e c h n o l o g i e s ，l t d 推出了一种用于w l a n 的l d p c t u r b o 码；研究表明采用该方案后用于i e e e 8 0 2 1 l a b gw l a n 移动终端的电池寿命可延 长至原来的4 倍。 总之，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 码的研究方向主要有：( 1 ) 码 的设计；( 2 ) 选择合适的硬件( 以降低编译码的运算复杂度) ；( 3 ) l d p c 码应用于深 空通信中。目前，l d p c 码已成为深空通信技术的首选。 1 4 论文的主要内容及章节安排 综合考虑l d p c 码的特点和其现有的分析方法，本文在讨论l d p c 码基本概 念、校验矩阵构造方法及编码算法的基础上，重点对译码算法及译码性能分析方 法进行了深入研究，分析对比了不同译码算法及参数对译码的影响，以及不同译 码分析方法各自的优缺点，并在此基础上提出了一种新的译码性能分析方法。将 新方法应用于校验矩阵的构造中，并将l d p c s p c 联合编译码方法引入到深空通 6 深空通信中l d p c 码译码性能分析 信中，设计了两套适合于深空通信的l d p c 码编译码方案。 具体章节安排如下： 第一章绪论，介绍课题的研究背景、意义、纠错码技术的发展史和l d p c 码的研究现状以及本论文的主要工作。 第二章介绍了l d p c 码的基本概念及其相应的校验矩阵构造方法和编码算 法，提出了将q c e p e g 校验矩阵构造方法和r u 快速编码相结合，进行编码生成 码字。 第三章研究了l d p c 码硬判决和软判决译码算法，对比分析了软判决译码 算法中各种不同的译码算法及其改进算法。结合深空探测实际需求的特点引入 l d p c s p c 联合编译码方法，实验表明，该方法可以有效降低译码门限与误码平层。 第四章分析比较了各种l d p c 码译码性能分析方法：密度进化理论( d e ) 、 高斯逼近方法( g 蛐、e x i t 图( e x t r i n s i ci n f o r m a t i o nt r a n s f e rc h a r t ) 法。根据不同方 法各自的优缺点提出了一种新的译码性能分析方法a p s o e x i t 图，该方法能够得 到更优的度分布对以及更大的噪声门限值。 第五章根据深空通信的具体需求，设计了两套用于深空通信的l d p c 码编 译码方案，并给出了具体的编译码参数及方法。仿真实验表明，两套方案在信噪 比大于0 7 d b 时，b e r 均低于1 0 ，达到了深空通信指标的需求而且易于实施。 第六章整篇论文的工作总结与展望，在回顾论文工作的基础上，总结了工 作取得的研究成果并提出了以后工作中还需深入研究的一些地方，指出了后续工 作的改进方向。 第二章l d p c 码概述及编码算法 7 第二章l d p c 码概述及编码算法 l d p c 码揭示了一种新的具有低密度校验矩阵的线性分组码。它利用校验矩阵 的稀疏性解决长码的译码问题，可以在线性时间内译码，同时又近似于香农提出 的随机编码，获得了优秀的编码性能，并经过近几年的研究，人们在正则码的基 础上进行推广提出了性能更好的非正则l d p c 码。但是，对l d p c 码来说，在不 考虑码长和度分布对的情况下，编码校验矩阵的结构就成了影响其性能的重要因 素，反映在二分图上对编码性能有重要影响的就是图中环的大小，由此，需要采 用一定的方法对校验矩阵进行构造，获得好的编码。本章首先介绍了l d p c 码的 基本概念及其表示方法和分类，然后根据现有各种校验矩阵构造方法和编码算法 介绍了深空通信方案中所采用的校验矩阵构造方法和编码算法。 2 1l d p c 码概述 2 1 1l d p c 码基本概念 l d p c 码是线性分组码中较为特殊的一种，但是目前l d p c 码并没有严格的数 学定义。考虑到其结构的特点和叙述上的方便，对l d p c 码做如下定义。 l d p c 码是一个m 行刀列的稀疏矩阵日的零空间，日称为l d p c 码的校验矩 阵，并且满足： ( 1 ) 矩阵的行重、列重与码长的比值远小于1 ； ( 2 ) 任意两行( 列) 最多只有1 个相同位置上的l ； ( 3 ) 任意线性无关的列数尽量的大。 n 为码长，校验位长度为m ，信息位长度为k = 刀一m 。行重、列重指的是日矩 阵某一行或某一列所包含的非零元素( 即“l ”) 的个数。行重p 表示每个校验矩阵 方程对一定数目的码元变量进行校验约束，列重力表示每个码元变量受到一定数目 的校验约束。其中，第一个条件的满足是保证l d p c 码校验矩阵目的稀疏性；第 二个是为了尽可能的减小小环对码性能的影响，这将在下面章节进行描述；第三 个约束条件主要是为了保证信息之间的独立性。因此，满足上面三个约束条件的 矩阵称为l d p c 码的校验矩阵。如果校验矩阵日的列重和行重是变化不等的，称 其为非正则l d p c 码，否则为正则l d p c 码。这部分将在l d p c 码的分类中进行 详细阐述。 深空通信中l d p c 码译码性能分析 2 1 2t a n n e r 图 任意一种线性分组码都可以表示成为t a n n e r 图【9 】( 编码二分图) 的结构。二 分图中将节点分为两个不同的集合，变量节点集合和校验节点集合。任意一个子 集内部各个顶点之间没有边相连，任意一个顶点都和一个不在同一个子集里的顶 点相连。l d p c 码又称为稀疏图码，它可以用一个二分图来表示，通过它的校验矩 阵日。的m 个校验方程和甩个变量，确定两个节点集合：变量节点集合和校验节 点集合。如果某个变量参与了某个校验方程，则这两个不同集合的节点之间有一 条边相连。 l d p c 码的二分图又称为t a n n e r 图，是由t a n n e r 在1 9 8 2 年首次用来表示低密 度码的，一个t a n n e r 图和一个校验矩阵完全对应。如图2 1 所示，图中的圆形称 为变量节点，变量节点与校验矩阵的列( 也即码字中的每一位) 一一对应；图中 的正方形称为校验节点，校验节点与校验矩阵的行( 也即各个校验方程) 一一对 应。通常将连接到一个节点的边的数量称作为这个节点的度，实际上一个节点的 度就是该节点对应的行或列重。 毛+ 屯+ = 0 x 2 + x 4 + x 6 2 0 毛+ + 毛= 0 五+ 黾+ 气= 0 11o o1o o o1 1oo 1o 0 lo1 1 1o 01 1 图2 1t a n n e r 图 在上面的t a n n e r 图中而一z ，一_ 一z 2 一为构成一个有向的闭合环路，由x 2 起始， 最后返回x ，长度为4 。在一个l d p c 码的编码过程中，会存在许多这样的闭合环 路，其中最短的闭合环路的长度，称之为最小圈长( g i n h ) ，上图中的百n h 为4 。一 个l d p c 码的矩阵的结构对码的性能有决定性的影响。由于l d p c 码译码采用迭 代译码，其算法的推导是基于在节点间传递的信息统计独立，当l d p c 码校验矩 阵对应的t a n n e r 图中有环存在时，某一节点发出的信息经过一个环长的传递会被 传回节点本身，从而造成自身信息的叠加，破坏了独立的假设，影响译码的准确 性。因此，在设计l d p c 码的校验矩阵时，尤其要避免最短环环4 的出现，环4 的出现将极大地影响l d p c 码的性能。因此希望在l d p c 码的t a n n e r 图中大环多， 小环少。 第二章l d p c 码概述及编码算法 9 2 1 3l d p c 码的分类 根据t a n n e r 图是否为正则的二分图将l d p c 码分为正则l d p c 码和非正则 l d p c 码【1 0 】。若l d p c 码所对应的t a n n e r 图为正n - 分图，则此l d p c 码称为正 则l d p c 码；若对应的二分图为非正n - 分图，则此l d p c 码称为非正则l d p c 码。 g a l l a g e r 最初所定义的l d p c 码是正则l d p c 码。所谓正则l d p c 码是指校验 矩阵日满足列重和行重分别等于常数( 五，力= ( 屯，吐) ， 码率为 r = 1 1 p = 1 一d 。由于正则 码的校验矩阵的行重和列重均保持不变，v d o l d p c 所以校验矩阵中“1 ”的个数随着码长的增加而成线性增长，而校验矩阵的元素则成 平方增长。所以当码长很长时，校验矩阵日是非常稀疏的低密度矩阵。正则l d p c 码通常用( ，名，p ) 来表示，其中为码长，兄为列重，p 为行重。 正则l d p c 码规定了日矩阵每一行具有相同个数的“1 ”，每一列也具有相同个 数的“1 ”。这种规定限制了编码性能的提高。如果允许校验矩阵的行或列中非零元 的个数发生变化，同时保证矩阵的稀疏性，那么编码和译码算法仍然适用，而编 码的性能却能够得到极大的提高。这是因为在这种编码中，如果对应t a n n e r 图中 的校验节点和变量节点有合适的次数分布，则能够得到性能更高的编译码性能， 使之能够赶上甚至是超越t u r b o 码，这也即是非正则l d p c 码。对于非正则l d p c 码，相应的二分图中各节点的度数不相同，通常用度分布序列 五，五，乃 和 岛，p 2 ，岛，) 来表示，其中z ，表示t a n n e r 图中与度为歹的信息节点相连的边占总 边数的比率，肛表示与度为i 的校验节点相连的边占总边数的比率，d 。和以分别表 示信息节点和校验节点的最大度数，应有 以 乃= 1 ， j = l 以 岛= l i = 1 ( 2 一1 ) 边度分布序列可用多项式来表示，即 d。?d 五( x ) = 乃工产1 ，夕( 力= 肛z 卜1 ( 2 - 2 ) j = l i = 1 此时，码率r 满足：r = i f p ( x ) d x f 允o ) d x 。 从直观上来看，非正则l d p c 码的性能优于正则l d p c 码。这是因为对于每 一个信息节点来说，希望它的度数大一些，这样它从相关联的校验节点得到的信 息就能越多，越能准确地判断它的正确值。对每一个校验节点来说，情况则相反， 希望校验节点的度数小一些，因为校验节点的度数小，它能反馈给其邻接的信息 节点的信息就越有价值。而非正则图比正则图能更好更灵活地平衡这两种相反的 要求。在非正则l d p c 码中，当变量节点和校验节点的总度数一定时，度数大的 1 0 深空通信中l d p c 码译码性能分析 变量节点从校验节点得到的信息较多，能够很快地被正确译码得到正确值，这样 它就可以给校验节点更加正确的概率信息，从而提供给度数较小的变量节点更多 的信息，使度数较小的变量节点也能更好地被正确译码。也即大度数的信息节点 首先获得正确的值，把它传输给对应的校验节点，通过这些校验节点又可以获得 度数小的信息节点的正确值。 2 2l d p c 码编码算法 2 2 1 校验矩阵的构造 基于准循环扩展【1 1 ( q c e ：q u a s i c y c l i ce x t e n s i o n ) 技术设计的非正则r a 码 ( i r a ：i r r e g u l a rr e p e a t a c c u m u l a t e ) ，由于设计简单，编码快速，便于工程实践等 优势已被列入到i e e e 8 0 2 1 6 e 标准中，然而对l d p c 码校验矩阵的限制会导致误码 性能的下降；而基于p e g l l 2 1 ( p r o g r e s s i v ee d g e g r o w t h ) 构造的l d p c 码，性能优越， 参数选择灵活，但设计较为复杂，不便于工程实现。因此本节提出了一种新的基 于q c e p e g 的l d p c 码构造方法。用该方法设计的中短长度的非正则l d p c 码， 其性能不仅优于p e g 码，且具有设计简单，编码快速等优点，易于工程实现。 q c e p e g 构造方法在设计度为2 和3 的变量节点时，由于该类变量节点通常 占全部变量节点的百分之八十左右，在设计校验矩阵时应重点保护，故采用q c e 法；对于度数大于3 的变量节点，由于该类变量节点的度分布比较零散，故采用 p e g 法依次添加到扩展以后的校验矩阵中，从而满足优化度分布对的要求和平均 围长尽可能大的要求。因此，综上所述，利用q c e p e g 算法构造m n 阶校验矩 阵的步骤如下： ( 1 ) 根据度分布多项式计算度为2 和3 的变量节点的个数，分别记为m 和m ； ( 2 ) 构造一个m 行，m + m 列的基矩阵日。，其中，m = 2 n ，m = 3 n 】， 】代表取整运算，z 为一正整数，称为扩展因子； ( 3 ) 将基矩阵中的每一条边重复n 次，从而得到扩展后的矩阵； ( 4 ) 用p e g 法将剩下的变量节点依次添加到扩展后的矩阵中，从而完成最终校 验矩阵的构造。 用上述方法构造的基矩阵通过q c e 法扩展可以使得由度为2 和3 的变量节点 组成的圈尽可能大且分布均匀，从而达到对其重点保护的目的。在此基础上，再 用p e g 法将剩下的变量节点添加到扩展后的检验矩阵中，从而使最终的l d p c 码 在平均围长尽可能大的同时满足优化度分布对的要求。实验表明，中短长度的 q c e p e g 码，性能不仅优于p e g 码，且设计更为简单，编码复杂度与i e e e 8 0 2 。1 6 e 标准中的i r a 码相当，各项指标均优于普通的p e g 码，有着良好的应用前景。 第二章l d p c 码概述及编码算法 2 2 2l d p c 码编码 l d p c 码面临的一个主要问题是其较高的编码复杂度和编码时延，对其采用直 接编码方法将会有二次方的编码复杂度，在码长较长时这是难以接受的。但是校 验矩阵的稀疏性却使得l d p c 码的线性编码成为可能。 假设l d p c 码的校验矩阵以。和相应的码字v 满足风。y r = 0 ，编码前的信 息序列为s = s 1s ：，& 一拼) 。l d p c 码的直接编码方法是将校验矩阵以。通过高斯 消去法【5 1 ，转化成等价的下三角形式，然后进一步初等变换得到右边单位阵形式 h = p i l l ，由g = 【，l ，】得到生成矩阵，从而由1 ，= s g 直接编码，如图2 2 所示。 图2 2与h 矩阵等价的f 三角矩阵g 通过上面的编码方法可以看出，在对校验矩阵巩。作高斯消去时，主要操作 包括与运算和异或运算( 模二加) ，其运算量大约为码长的三次方即o ( n 3 ) 。经过高 斯消去而获得的矩阵g ，通常已不再具有稀疏性，所以在按照递推方式获得校验 位时，编码运算量大概是o ( n 2 ) ，即l d p c 码编码器的直接实现具有码长的二次 方复杂度。 直接编码方法具有码长的二次方复杂度，主要是由于高斯消去法破坏了原有 奇偶校验矩阵的稀疏性。针对l d p c 码所面临的编码问题，t j r i c h a r d s o n 和 r l u r b a n k e 提出了重排稀疏校验矩阵的行或列，从而得到具有近似下三角结构的 校验矩阵，利用下三角系数方程可以在线性时间内求解，适当处理后就可以实现 线性时问编码。该方法称为r u 算法，它利用了校验矩阵日的稀疏性，适用于任 何稀疏校验矩阵，由于其编码快速且不会导致性能损失，故在深空通信中得以广 泛应用。 r u t 玛】算法流程： 首先，采用贪婪算法将校验矩阵进行行列变换，得到近似下三角结构，如图 2 3 所示。 t l l l r i j 上 1 2 深空通信中l d p c 码译码性能分析 n 吖1 1 ， g r 国：g r ab冒玑 cde ， 霉 图2 3r u 算法示意图 然后，将码字分成三部分，即1 ，= ( up tp ：) ，其中u 是系统码信息位，a 和岛 是校验位，岛长度为z ，p 2 长度为( m z ) 。根据h v r = 0 可得 彳“7 + 却- ：+ t p ：= 0 ( 2 3 ) ( e t - 1 4 + c ) u 1 + ( e t _ 1 b + d ) p ：= 0( 2 - 4 ) 令缈= ( e t 。1 b + d ) ，由校验矩阵日的性质可知妒= i ( 或者循环移位) ，则 彳= ( e t - 1 a + c ) u r ，p 2 t = t - 1 ( a u r + 骈) ，计算可按以下步骤完成： ( 1 ) 计算彳甜r 和c u r ； ( 2 ) 计算e 丁一1 ( a u r ) ； ( 3 ) 计算矸，群= e t 卅( a u7 ) + c u r ； ( 4 ) 计算p ；，p ；= r - 1