（通信与信息系统专业论文）深空通信中的ldpc编译码技术的研究.pdf

摘要 摘要 低密度校验码是一种能逼近s h a n n o n 容量限的渐进好码，在长码时其性能 甚至超过了t u r b o 码，其译码采用具有线性复杂度的和积算法，复杂度大大低 于t u r b o 码，并且几乎所有错误部是可检的。由于低密度校验码具有诸多优点， 它已成为深空通信信道编码领域最受瞩目的研究热点之一，低密度校验码的应 用也已经被提到日程上。 本文结合深空通信的信道特点，介绍了低密度校验码的表示和构造；阐述 了低密度校验码的译码方法( 软判决译码算法和硬判决译码算法) ，对这两种算 法进行了比较，并作了一些优化：同时叙述了低密度校验码线性编码方法，而 且实现了低密度校验码的快速编码问题；最终给出了低密度校验码的硬件实现， 以便对低密度校验码的性能进行验证。 l d p c 码的实用化还要走相当长的一段路，虽然长码时l d p c 码的性能可以超越 t u r b o 码，但是短码却l l t u r b o 码差得很多。因此，l d p c 的编译码方面还需要进一 步研究。 关键词：深空通信l d p c 码信道译码量化译码h 矩阵 a b s t r a c t a b s t r a c t l o w - d e n s i t yp a d t y c h e c k ( l d p c ) c o d e sa l eac l a s so fc a p a c i t ya p p r o a c h i n g e r r o r - c o r r e c t i n gc o d e s b yu s i n gl o wc o m p l e x i t ys u m p r o d u c ta l g o r i t h m ，l d p c c o d e sc a ng e tn e a rs h a n n o nl i m i td e c o d i n gp e r f o r m a n c ew h i l ea l m o s ta l le r r o r sa r e d e t e c t a b l e l o n gl d p cc o d e s c a ne v e no u t p e r f o r mt u r b oc o d e s n o w , t h e a p p l i c a t i o no f l d p ch a s b e e np u to nt h ea g e n d a b a s e do l lf e a t u r e so fd e e p s p a c e c o m m u n i c a t i o nc h a n n e l ，f i r s t l y ，t h e r e p r e s e n t a t i o na n dc o n s t r u c t i o no fl d p cc o d e sa r ea d d r e s s e d s e c o n d l y , t h et w o d e c o d i n ga l g o r i t h mf o rl d p cc o d e s ，i e ，b i t f l i p p i n ga l g o r i t h ma n ds u m p r o d u c t a l g o r i t h ma l ed i s c u s s e d m e a n w h i l eo p t i m i z a t i o na l g o r i t h mi sp r o p o s e d t h i r d l y ，t h e e f f i c i e n te n c o d i n gp r o b l e mo fl d p cc o d e si sd i s c u s s e di nd e t a i l a tl a s t ，h a r d w a r e r e a l i z a t i o no fl d p cc o d e si sp r e s e n t e d ，s ot h a tt h e i rp e r f o r m a n c e sc a l lb ev a l i d a t e d a l t h o u g hl o n gl d p cc o d e sa r es u p e r i o rt ot u r b oc o d e s ，i ti sn o tt h ec a s ef o r s h o r tl d p cc o d e s s oc o d i n ga n dd e c o d i n go fl d p cc o d e sn e e dt ob er e s e a r c h e d f u r t h e r s ot h a tt h ep r o b l e mo fc h a n n e lt r a n s m i s s i o no fo u rc o u n t r y sd e e ps p a c e c o m m u n i c a t i o nc a nb es o l v e dp e r f e c t l y 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 q u a n t i z a t i o nd e c o d i n g l d p cc o d e sc h a n n e l d e c o d i n g i im a t r i x 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究_ ：= r ：作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已 经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或其它教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中做 了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：丝田盔垂r 期1 2 ：厶兰! 关于论文使用授权的说明 本人完全了解两安电子科技大学有关保留和使用学位论文的规定，即：研究生在校 攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发 表论文和使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论 文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采 用影印、缩印或其它复印手段保存论文。( 保密的论文在解密后遵循此规定) 本人签名： 导师签名： 丝盟叠 至缝查至 日期! z ! ! 一 日期p 3 c l 第一章绪论 第一章绪论 本章首先简要介绍了深空通信系统及信道模型，回顾了信道编码理论与技术的 发展历程，然后概述了低密度校验码的提出、发展和研究现状，最后总结了作者在 攻读硕士学位期间的研究工作，给出了全文的内容安排。 1 1深空通信与信道模型 深空通信是指比地球卫星还远的探测器之间或探测器与地球问的通信，其基本 特征是传输距离非常远1 1 i 。深空通信的信道特征是接收信噪比很低，而可用的信道 带宽相对较宽。在这种功率受限信道上进行可靠通信，采用信道编码技术是提高 深空通信系统的增益的一个重要关键技术。 深空通信与一般的地面通信、卫星通信等有一些不同的特点1 2 1 ： 1 距离远。月球距地球约3 8 万公里，而其它行星距地球都在几千万公里以上。 由于距离远，使信号衰减造成信噪比降低，另外，某些行星存在的电磁辐射引起 的干扰，使信噪比进一步下降，例如：对木星的测量表明，其磁场带电粒子的辐 射强度为地球的1 0 0 万倍。在低信噪比下通信是深空通信的一个特点。 2 时延大。地球到火星的探测器要飞行约6 个月，而信号的传输也要4 分钟( 距 离最远时要2 0 分钟) 。 3 工作频率高，频带宽。以往的深空探测器工作于s 和x 波段，新的探测器提 高到k a 波段。美国和日本采用x 波段，天线口径为6 4 米，为减小天线尺寸，采 用k a 波段，但该波段的频率高，对雨衰达1 4 d b 1 6 d b ，往往会抵消由信道编码 带来的好处，因此，频率也不能太高。 4 频道资源丰富，允许使用低频带利用率的编码和二迸制的调制方案。 美国1 9 9 7 年的m a r sg l o b a ls u r v e y o r 使用了( 7 ，1 2 ) 卷积码与( 2 5 5 ，2 2 3 ) r s 码构成的串行级联码。而在m e r 通信系统中，信道编码部分采用了约束长度 为1 5 的( 1 5 ，1 6 ) 卷积码与( 2 5 5 ，2 2 3 ) r s 码构成的串行级联码。在计划于2 0 0 6 年发射的m r o 数传系统的设计中，将在当前采用的8 4g h z ( x - b a n d ) 频段上采用 t u r b o 码和低密度校验( l d p c ) 码，以及采用带宽有效调制技术来提高通信的可 靠性和速率或移到更高的频率上，如3 2g h z ( k a - b a n d ) ，数据速率将达到1 2 mb i a s 。 我国的深空探测任务刚刚起步不久在探月计划中，使用的是r s 码与卷积码 的串行级联编码方案。 从上述深空系统所使用的编码技术可以看出，随着要求更高的数据速率和更 2 深空通信中的l d p c 编泽码技术的研究 多的同时任务数，未来的深空探测任务必须采用具有高编码增益的信道编码方式。 基于迭代译码技术的t u r b o 型级联码( 包括串行级联与并行级联) 和l d p c 码是 目前已知的两类最优秀的编码技术。 深空通信的信道可以建模为无记忆高斯信道( a w g n ) ，通常仅仅考虑二进制 编码方式。故有二进制输入高斯信道( b i a w g n ) ：输入为二值变量，输出为连续 变量，且信道中的加性噪声服从( 0 ，盯2 ) 的高斯随机变量。 0 l l y i n 图1 1二进制输入高斯信道( b i a w g n )图1 2r a 码的因子图模型 1 2信道编码理论及其发展 信道编译码部分是以特定的控制手段，引入适量冗余比特，以克服信息在传输 过程中受到的噪声和干扰影响。根据s h a n n o n 提出的信道编码定理，对任意一个平 稳离散无记忆有噪声信源，都有一个固定的量，称之为信道容量，记做c 。只要信 息的传输速率低于信道容量，就必然存在一种编码方法，使得信息出现差错的概率 随码长的增加趋于任意小；反之，当信息传输速率超过信道容量时，则不存在这样 的编码方法。这就是著名的信道编码定理，它给出了特定信道上信息传输速率的上 确界。 定理1 1 ( 信道编码定理) 1 3 1 ：任意离散输入无记忆平稳信道存在信道容量c ， 对预期的任一数据速率r 0 ，有可能设计一对编译码器， 以保证该信道中速率为露的数据传输具有小于矽的译码错误概率。 信道编码定理指出，在有扰信道中，只要信息传输速率小于信道容量，就有可 能实现任意可靠的信息传输。这个存在性定理提醒人们可以实现以接近信道容量的 第一章绪论 传输速率进行通信。但遗憾的是该定理采用的是非构造性的证明方法，其中并没有 给出逼近信道容量的码的具体编译码方法。 s h a n n o n 在信道编码定理的证明中引用了三个基本条件，即： ( 1 ) 、采用随机的编码方式； ( 2 ) 、码字长度趋近于无穷大； ( 3 ) 、译码采用最佳的最大似然译码。 一般可将信道编译码器所使用的纠错码从性能上分为坏码和好码。所谓坏码是 指只有将码率降至零才能使误码率为任意小的编码方式；而好码又可以分为当误码 率任意小时，码率逼近信道容量限的非常好码和码率可达到的非零最大值小于信道 容量限的一般好码。而在实际应用中，只能够使用以码长多项式的时间和空间复杂 度内完成编译码的纠错码，因而尽管一般的随机码是好码，但不能看作是实用码。 自信道编码定理提出以来，如何构造一个逼近信道容量限的实用好码成了众多 研究学者竞相研究的课题，并逐渐形成信息论的一个重要分支信道编码理论。 五十多年来，人们构造实用好码的探索基本上是按照s h a n n o n 所引用的基本条件的 后两条为主线展开的。通过众多学者，特别是有关数学和信息论学术界的研究人员 五十多年的共同努力，目前已经取得了很多成果。下面对其进行简要叙述。 纠错码【4 】1 5 】从构造方法上可分为分组码( b l o c kc o d e s ) 和卷积码( c o n v o l u t i o n a l c o d e s ) 两大部分。在分组码方面，第一个分组码是1 9 5 0 年发现的能纠正单个错误 的h a m m i n g 码。最有意义的是b o s e 和r a y c h a u d h u d 在1 9 6 0 年及h o c u e n g h e m 在 1 9 5 9 年分别独立发现的能纠正多个错误的b c h 码，以及r e c d 和s o l o m o n 在1 9 6 0 发现的非二进制r s 码。实际上，b c h 码可以看作是某个r s 码的子域子码，而r s 码又可以看作是b c h 码的特例。其后发现的分组码主要有1 9 7 0 年的g o p p a 码和 1 9 8 2 年发现的代数几何码。在所有这些分组码中，除了g o p p a 码和代数几何码中存 在个别达到g v 限的渐进好码外，其它均不是好码。分组码的译码主要采用基于代 数的硬判决译码。 卷积码最早由e l i a s 提出，早期被称为树码( t r e e c o d e s ) ，现在称为格图码( t r e l l i s c o d e s ) 或卷积码。卷积码具有动态格图结构。可用有限状态机来描述其状态。卷积 码的译码一般采用概率译码由于译码算法的简单、实用和易于实现，卷积码被广 泛应用于实践中。 1 9 6 6 年，f o r n e y 将分组码和卷积码结合起来，提出了级联码( c o n c a t e n a t e d c o d e s ) 的概念。级联码一般采用r s 码作为外码，卷积码作为内码。f o m e y 的研究 表明，级联码在性能得到较大改善的情况下，其译码复杂度并不显著增加。 总之，尽管随机码是理论上的好码，但由于其编码实现的困难性和无法承受的 译码复杂度而只被用作理论分析的工具，在信道编码定理和后来的许多编码理论成 果中，代数编码理论始终占据了主导地位，使得传统的信道编码技术受到临界速率 深空通信中的l d p c 编译码技术的研究 ( c d t i c a ir a t e ) ，也称做截止速率( c u t o f f r a t e ) r 的限制【6 】。 1 9 9 3 年t u r b o 码【7 1 的提出被看作是信道编码理论研究的重要里程碑。b e n o u 等 人将卷积码和随机交织器相结合，同时采用软输出迭代译码来逼近最大似然译码， 取得了超乎寻常的优异性能，并一举超越了截止速率，直接逼近s h a n n o n 提出的信 道容量限。 随着t u r b o 码的深入研究，人们重新发现g a l l a g e r 早在1 9 6 2 年提出的低密度校 验码1 9 1 1 1 0 l ( l o wd e n s i t yp a r i t y - c h e c kc o d e s ，简称l d p c 码) 也是一种具有渐进特 性的非常好码，它的译码性能同样可以逼近s h a n n o n 信道容量限 “1 1 1 2 1 1 4 1 。由于l d p c 码在中长码长时具有超过t u r b o 码的性能，并且具有译码复杂度更低，能够并行译 码及译码错误可检测等特点，成为目前信道编码理论的研究热点。研究表明，t u r b o 码只是l d p c 码的一个特例【1 5 】【1 6 】【1 7 1 ，两者都是基于图构造的低密度码，译码算法具 有等价性，从而使两者在基于图模型的编译码研究中得到了统一。 1 3低密度校验码的提出、发展和现状 1 9 6 2 年，g a l l a g e r 在他的博士论文中提出了二元正则l d p c 码，也被称做 g a l l a g e r 码1 9 1 。g a l l a g e r 证明了这类码具有很好的汉明距离特性，是满足g v 限的渐 进好码，在计算树上进行i 芘l o g ( 1 0 9 ( ) ) ( n 为码长) 次后验概率迭代译码可以获 得依码字长度指数降低的比特错误概率，但限于当时的计算能力，l d p c 码被认为 不是实用码，在很长一段时间内没有受到人们的重视。 1 9 8 1 年，t a n n e r 在他的一篇奠基性的文章中正式提出了用图模型来描述码字的 概念，从而将l d p c 码的校验矩阵对应到被称为t a n n e r 图【2 0 1 的双向二部图上采用 t a n n e r 图构造的l d p c 码，通过并行译码可以显著地降低译码复杂度。t a n n e r 还仔 细分析了最小和算法( m i n - s u ma l g o r i t h m ) 与和积算法( s u m - p r o d u c ta l g o r i t h m ) 两种信息传递算法，证明了基于有限无环t a n n e r 图的最小和译码算法与和积译码算 法的最优性。 t u r b o 码的发现重新引发了众多学者对l d p c 码的研究兴趣。m a c k a y 和n e a l 利用随机构造的t a n n e r 图研究了l d p c 码的性能，发现采用和积译码算法的正则 l d p c 码具有和t u f l j o 码相似的译码性能，在长码时甚至超过了t u r b o 码【1 4 1 1 1 9 1 ，这 一结果引起了信道编码界的极大关注。此后，d a v e ) 和m a c k a y 从减少t a n n e r 图上 小环路的概念出发提出了基于g f ( q ) ，q 2 的l d p c 码【2 0 i 2 ”，进一步提高了l d p c 码的译码性能。 在m a c k a y 和n e a l 重新发现l d p c 码优异性能的同时，s p i e l m a n 和s i p s e r 提出 了基于二部扩展图的扩展码田2 3 1 1 2 4 【2 卯。在对扩展码的研究中，他们证明了一个随机 构造的t a n n e r 图以很大的概率为好的扩展图，而由好的扩展图构造的线性纠错码是 第一章绪论 5 渐进好码，从而证明了采用随机t a n n e r 图构造的l d p c 码以很大概率是渐进好码。 l a b y 等人将采用非正则t a n n e r 图构造的扩展图用于删除信道，称之为t o r n a d o 码 1 2 s l 2 7 1 。由于采用了非正则的t a n n e r 图，t o r n a d o 码具有更大的扩展性和更好的收敛 性，纠删性能更强。此后，采用优化度序列设计的非正则t a n n e r 图被用于构造l d p c 码，称为非正则l d p c 码，与正则l d p c 码相比，非正则l d p c 码的性能得到显著 的提高伫8 1 1 2 9 1 1 3 0 】【3 1 1 1 3 2 1 。 近两年，r i c h a r d s o n 等人应用密度进化理论来测度l d p c 码的性能f 3 0 】l 翊。 r i c h a r d s o n 等人在对l d p c 码的研究中发现，译码信息的迭代传递过程中存在着译 码阈值现象，即当信噪比大于译码阈值时，迭代译码可使误码率趋于零。反之无论 采用多长的l d p c 码，经过多少次迭代译码，总存在一定的错误概率。研究表明， 译码阈值的大小与l d p c 码的构造参数密切相关，采用优化度序列设计的非正则 l d p c 码可以有效地改善阈值，因此密度进化理论可以用于指导l d p c 码的优化设 计。 c h u n g 等通过对密度进化理论的研究，进一步提出了应用高斯逼近原理来简化 译码闭值计算和收敛性分析，从而使测度l d p c 码性能的模型由多参数动念系统的 密度进化理论模型简化为单一参数动态系统的高斯逼近模型2 9 l 3 1 1 。 d i v s a l a r 、m c e l i e c c 等人提出的重复累积码( r ac o d e s ，r e p e a t - a c c u m u l a t ec o d e s ) p 别 是一种构造非常简单的t u r b o 1 i k e 码，然而其性能却比t u r b o 码出现之前的任何码 都好，离s h a n n o n 限在1 5 d b 之内。r a 码的分量码是( n ，1 ，n ) 的重复码和2 状态、码 率为i 的卷积码( 其生成多项式为g ( d ) = 1 ，( 1 + d ) ) 分量码之日j 通过伪随机交织器连 接，如图1 2 所示。其他一些学者也提出一些简单码类，其性能与r a 码相当，有 的甚至更好。香港城市大学李坪博士所提出的c t ( c o n c a t e n a t e dt r e ec o d e s ) 1 3 叫就是 一例c t 码可以看成是一种l d p c 码，其译码复杂度很低，但是性能却和同样码 长的t u r b o 码相当 理论的发展也促进了应用的推广，在l d p c 码理论研究取得丰硕成果时( 2 0 0 1 年i e e e 的信息论汇刊出了关于图码和迭代译码的专刊1 3 7 和1 9 9 9 年举行的i m a t a l k s - 1 9 9 9s u n l m c rp r o g r a m ：c o d e s s y s t e m sa n dg r a p h i c a lm o d e l s ) ，l d p c 码的实用 化也在进行之中。l o e l i g e r 等学者认识到和积算法非常适合模拟v l s i 实现p 捌。l d p c 码的图模型表示很自然地可以用于电路实现，而且和积算法的运算也非常适合用晶 体管的非线性物理特性实现。用模拟v l s i 实现和积算法比用数字v l s i 在速度、功 率方面都有很大改善，主要的瓶颈在于同通常数字电路的接口上。h a g e n a u e r 等学 者也对模拟译码器作了研究 3 9 1 。此外，在l d p c 码的实用化中，量化译码设计也是 一个非常重要的问题。李坪、x i a o y uh u 等学者都曾对l d p c 码的量化译码作过研 究。( 本文将在第四章对l d p c 码的量化译码作深入的研究和分析。) 低密度校验码是一种能逼近容量限的渐进好码，在长码时其性能甚至超过了 6 深空通信中的l d p c 编译码技术的研究 t u r b o 码。此外，低密度校验码的译码采用了具有线性复杂度的和积算法，译码复 杂度大大低于t u r b o 码。低密度校验码的优异性能及其在信息可靠传输中的良好应 用前景已引起学术界和l t 业界的高度重视，成为当今信道编码领域最受瞩目的研 究热点之一。 1 4 本文的主要研究工作和内容安排 作者结合国家自然科学基金项目，采用理论分析和计算机仿真相结合的方法， 对深空通信中的低密度校验码的理论进行了深入研究，取得了一些研究成果。全文 共分六章，具体安排如下。 第二章系统地阐述了低密度校验码( l d p c ) 的构造问题，重点讨论了一致校 验矩阵的构造方法；第三章阐述了l d p c 码的译码原理，包括软判决译码及硬判决 译码，同时介绍置信传播算法的思想，最后讨论了低密度校验码的量化译码；第四 章阐述了l d p c 码的编码原理，介绍了通用的编码方法，最后讨论了l d p c 码的快 速编码闯题；第五章提出涤空通信系统中应采用的编译码方案，并对其进行了性能 仿真，这包括横向和纵向两个方面；第六章讨论l d p c 码的硬件实现方面的问题， 介绍l d p c 码译码器的实现结构。 第二章低密度校验码的构造 第二章低密度校验码的构造 7 本章首先简要介绍了低密度校验码的构造方法及发展现状；接着给出了如何构 造l d p c 码的一致校验矩阵的方法，重点讨论了g a l l a g e rl d p c 码和准循环l d p c 码的特点和构造方法，为l d p c 码的硬件实现做好准备。 2 1发展现状 低密度校验码( 1 0 wd e n s i t yp a r i t yc h e c kc o d e s ) 是一种线性分组码。之所以称它 为低密度校验码是因为它的校验矩阵日= ( 。阳是稀疏矩阵，即非零元素( 在 g f ( 2 ) 域上即为1 ) 的个数占总元素个数的比例非常小。众所周知线性分组码可以 由它的生成矩阵g = 岛 。决定，给定生成矩阵g ，码字集合可以表示为： c = x e 碍i x = e a , g , ，a a ) 其中，g 为生成矩阵g 的第f 行。等价地，线性分组码也可以由校验矩阵日来 决定。给定校验矩阵，码字集合可以表示为 c = x ，7i ( x ， ) = 0 ，j = 1 , 2 ，行一七) 其中，鹿为校验矩阵日的第i 行。因此选定了校验矩阵，那么这个线性分组码 也就确定了。根据校验矩阵的不同，低密度较验码分为两大类：正则低密度校验 码( r e g u l a rl o wd e n s i t yp a r i t y ) 和非正则低密度校验码( i r r e g u l a rl o wd e n s i t yp a r i t y ) 。 正则低密度校验码的校验矩阵每行( 列) 中的非零元素个数是相同的，而非正则低密 度校验码的校验矩阵每行( 列) 中的非零元素个数未必相同。根据校验矩阵中的元素 取自的域不同，低密度校验码可以分为二元低密度校验码和q 元低密度校验码。本 文中仅考虑二元低密度校验码在g f ( q ) ( q 2 ) 上的情形可以由二元情形推广得 到，具体可以参考文献 4 1 , 4 2 1 。 对l d p c 码来说，在不考虑码长和次数分布对的情况下，编码校验矩阵的结构 就成了影响其性能的重要因素，反映在二分图上对编码性能有重要影响的就是图 中圈的长度分布，需要采用一定的方法对校验矩阵进行构造，获得好的编码。 2 2l d p c 码校验矩阵的构造 2 2 1 g a l l a g e r l d p c 码 g a l l a g e r 提出采用，j ，助来表示一个j 下则低密度校验码【1 0 l ，其中，l 表示码长， _ ，表示校验矩阵中每列所含1 的个数，而k 则表示校验矩阵中每行所含i 的个数。 8 深空通信中的l d p c 编译码技术的研究 g a l l a g e r 采用随机置换的方法来构造校验矩阵，方法如下： i ) 将校验矩阵h 分成- ，个子矩阵日，h 2 ，h ，每个子矩阵有伽一k ) y 行， 并且每个子矩阵的每列有且只有一个1 ； 2 ) 子矩阵日。中的l 里下降的阶梯状排列，即第，行的k 个1 从第o l 涉+ 】位排到 第讯位； 3 ) 其余的子矩阵通过对日1 进行随机列置换得到，所有置换是等概出现的。 若一个伽，工助正则低密度校验码的校验矩阵是满秩的，设校验矩阵有所行， 根据校验矩阵中l 的总数是固定的，有： m k ：n j j 竺： ( 2 1 】 因此，这个工p 正则低密度校验码的码率可以简单计算如下： r r - - m l 一? 1 一善( 2 - 2 ) ”腭石 llllo oo0 o o o 0 0 000 0 0 00 0 0 o oliilo o 0 0 o o o o 0 o 0 o 0 0 000 000l1l10 0 0 0 0 0 0 0 o 0 0 ooooo 0 o o ol1ilo 0 0 0 o 0 o o 00 0000 00 0 0 0 0 llll 10 0010 0 0l0 00l0 0 0 0 0 00 olo o olo 0 olo 0 o o o ol0 0 0 o0i oo ol0 0 0 0 0 0l0 0 0l0 0 0 0 0l0 0 0 0 0 0l0 0 0l0 0 010 0 o o o o o o10 o o1o 0 01o o ol l0 o o oloo o o ol0 0 0 0 010 0 olo o o o l0 00l000 0l0 0 0 0 o olo o 0 olo o o ol 00 0 0 0l0 0 0 0lo ooolo o o ol0 010 0 0 0 o 0ol0 0 0 0l 0 0 0 010 0 0 0l 图2 1 ( 2 0 ，3 ，4 ) 低密度校验码的校验矩阵 从上面的构造方法不难知道，由o a l l a g e r 的方法构造的校验矩阵并不是满秩 的：每个子矩阵的所有行相加都得到全l 向量。因此，由o a l l a g e r 的方法构造的 低密度校验码的码率要略大于式( 2 - 2 ) 所计算的码率。g a l l a g e r 曾给出了一个( 2 0 ，3 4 ) 低密度校验码的校验矩阵，如图2 1 所示。 这里，称由上述方法可以构造的低密度校验码类( e n s e m b r e ) 为o a l l a g e r 码类。 关于g a l l a g e r 码类的两个结果：第一个是关于最小距离的。所谓最小距离是指码 字集合中，距离最近的两个码字之问的距离。g a l l a g e r 码类中，码的最小距离是一 个随机变量，该随机变量的分布函数可用图2 2 所示曲线作为上界。对，3 和k ， 的g a l l a g e r 码类而言，当码长趋于无穷时，图中的曲线逼近阶跃函数( 跃交点处的 坐标值与码长的比值是一个固定值，记为靠) 。因此，当码长h 足够长时，实际上 第二章低密度校验码的壮j 造 9 g a l l a g e r 码类中的所有码的最小距离至少为嗍。第二个结果是关于误比特率的。 g a l l a g e r 证明：对于g a l l a g e r 码类，在对称无记忆信道中，采用最大似然译码时， 其误比特率随着码长的增加呈指数形式下降。这两个结果说明g a l l a g c r 码类是相 当好的吗类。m a c k a y 和d a v c y 曾指出对任何码长和码率，当平均列重歹= 3 时， 随机构造的g a l l a g e r 码离现在所知最好的码的最小距离在零点几个d b 2 内t 4 4 1 。 n 6 j t n 图2 2 最小距离分布函数简图 2 2 2 m a c k a y 的构造方法 短环的存在会给置信传播译码造成译码困难。因此，m a c k a y 希望将校验矩阵 代表的二部图中的短环的数目控制在最小范围。下面举个例子以说明短环对译码 和最小码重的影响。考察代表校验矩阵的二部图的部分： 图2 3 低密度校验码二部图的一部分 图中存在两个4 环( 如粗线所示) 。如果三个变量节点的接收值都发生错误( 考 虑硬判决的情况) ，即它们的取值由五变为而0 1 ( 0 表示模二加) ，则5 个校验节点 代表的校验关系仍然成立l 在这种情况下，这部分无法正确译码。 上面的分析虽然很简单，但是它表明：短环的存在会损害和积译码算法的有 效性，并且还有可能导致低码重码字的出现( 上图导致了一个重量为3 的码字) 。 避免出现短环的方法有很多i 1 1 4 5 - 4 7 ，大部分方法都属于代数方法，也有一些 是采用启发式搜索，比如x i a o - y uh u 的p e g ( p r o g r e s s i v ee d g eg r o w t h ) 方法这里 需要指出的是用p e g 方法构造的中、短码长低密度校验码足当前所知具有相同参 数的最好的低密度校验码之一1 4 5 1 。相对而言，消除4 环比较简单，只需要保证校 i p 1 0 深空通信中的l d p c 编泽码技术的研究 验矩阵中任意两列忽和 ，最多只有一个共同的l ，用数学式子表示就是 和h j 内积 的汉明重量小于等于l ：w e i g h t ( ( 1 ，啊) ) s l 。 低密度校验码的译码复杂度与校验矩阵的密度紧密相关：校验矩阵的密度越 大，译码复杂度越大：校验矩阵的密度越小，译码复杂度越小。因此，适当引入 一些重量为2 的列会降低译码复杂度，不过必须采用一些方法以避免小重量码字 的出现。m a c k a y 提出了如下的4 种可以避免具有4 环的校验矩阵的构造方法： 构造方法i a 这是一种基本的构造方法，仍然采用随机构造校验矩阵的方法。在随机构造 校验矩阵时，保证列重固定不变，行重尽可能均匀，并且任意两列最多只有共同 的l 。以列重为3 ，码率为l 2 的低密度校验码的校验矩阵构造为例，用构造方法 1 a 构造的校验矩阵形如图2 4 所示。 构造方法2 a 若校验矩阵的维数为m x n ，则让m 2 列的列重为2 。这些列重为2 的列由两 个m 2 x m 2 的单位阵构成。其他要求同构造方法l a 。以码率为1 3 的低密度校 验码矩阵构造为例，用构造方法2 a 构造的校验矩阵形如图2 4 所示。 构造方法i b 。2 b 对用构造方法l a 和2 a 构造的校验矩阵进行消列，将某些精心挑选的列取掉 使得校验矩阵中不含小于某个长度，的环( 比如，= 6 ) 。 此外，m a c k a y 也采用了重叠置换矩阵的方法来构造正则【5 0 l 和非正则低密度校 验码1 5 l 】。 ) ( 8 ) 构造方法l ab ) 构造方法2 a 图2 4m a c k a y 的系统描述框图 2 2 3 超轻( u l t r a - l i g h t ) 法 m a c k a y 矛l j 用了最多为粤列、重为2 的列以减少矩阵的重量。对二进制编码来 说更多的重为2 的列是不可接受的，因为这会增加译码的误码率，并导致不可检测 的译码错误。而非二进制的编码可以包含更多的重为2 的列而不显著降低误码率， 这种构造方法t 扫m a c k a y 的构造法2 a 变化而来，该构造方法中堆积了一系列更小的 单位矩阵。 超轻构造法a ：构造了个粤重为2 的列之后，进一步在一个粤粤的单位阵旁放 第二章低密度校验码的构造 置两个警号的单位阵。重复该过程直到最多有m 个重为2 的列被构造出来，每次 都将新的小单位阵放在上次构造的某一单位阵旁，这样矩阵行的重量为3 ，4 或更高， 这依赖于上述过程重复了几次。最后填充剩余的列，使每行的重量尽可能的相等。 如图2 5 c a 所示。 超轻构造法b ：该构造方法与a 相似，只不过小单位阵的放置使得每行的重量在 填充剩余部分之前最多为2 。如图2 5 ( b ) 所示。 ( a )( b ) 图2 5 超轻( u l t r a - l i g h t ) 法的系统描述框i 璺l 2 2 4 准循环l d p c 码 准循环l d p c 码实际上属于g a l l a g e rl d p c 码，只是它不是采用随机列置换。 一个长为n = p k 的准循环的规则( j ，k ) l d p c 码的校验矩阵可表示为： l m p 娣0 ； 瞄 ( 2 3 ) 其中b均为单位方阵，循环右移瑾后构成的矩阵。 p x pp x p 。- ， 由于其结构的特殊性，准循环l d p c 码只要有一个小环，就至少有p 个同样大 小的环，而小环对码的性能影响很大，因此构造时要避免小环的存在。准循环l d p c 码的环的分布只与口，的取值有关，因此对它的环的分析比较简单。 将各个小矩阵循环右移的位数写成一个矩阵为： 000 1 o ： 。l ：l j 口：一：刊 c z 棚 在该矩阵上按行列交替顺序画一个环路，若奇数节点上的数值和与偶数节点 深空通信中的l d p c 编译码技术的研究 上的数值和相同( 模p ) ，则该环路构成一个环，否则该环路不构成环唧j 。对于相同 码长和码率的消去4 环后随机构造的准循环l d p c 码的性能基本相同，而且消4 环最 简单，只需保证( 2 - 4 ) e e 任意画一个矩形的两个对角线元素和相等( 模p ) 。其具体构 造算法如下： 步骤1 初始化：将所有子矩阵循环右移的位数初始化为0 。 步骤2 从第2 行第2 列开始按先列后行的顺序，在1 到p - l 之间产生随机数，每产 生一个新随机数就与己经产生的所有随机数进行比较，若有相同的就 重新产生一个该位置的随机数并重新进行比较，直到该随机数与己经 产生的所有随机数都不同为止。 步骤3 从第2 行开始，让其与后面各行丌始逐行检查两行所构成的所有矩形的 两个对角线元素模p 和是否相等( 无需检查第l 列) ，若发现有相等的，返 回步骤2 。 上面的步骤2 保证了包含第1 行和第1 列元素的所有矩形的对角线元素模p 和不 会相等，步骤3 保证了其它矩形的对角线元素模p 和不会相等，因此该算法生成的 准循环l d p c 码不会有4 环的存在。当然在产生随机数的同时，也可以考虑其它矩 形的对角线元素模p 和是否相等，但当p 的值比较大，而j 和k 的值比较小时，上算法 的重复次数还是相当少的。可以使用以上算法来产生准循环l d p c 码的校验矩阵各 个子矩阵循环右移的位数的。 准循环的规则( i ，k ) l d p c 码的最小汉明距离具有上限( 件1 ) ! 5 3 j ，因此对于给 定j 和k 的准循环的规则( j ，k ) - l d p c 码，其最小汉明距离不会随着码长的增加而增大， 这就导致它在高信噪比时性能不如随机构造的g a l l a g e r l d p c 码，即有较高的错误 平层。但是，只有少数的应用会要求特别低的误码率，一般误码率在l o 。了以下即 可满足系统要求。 2 2 5 h - 旋转矩阵构造法 针或逆时针旋转9 0 。可得到1 7 。，以同样的方式可依次得到n 。和兀。矩阵兀。还可 兀= 曙i 习，n 。= 匮5 习，n 。= e ；习，兀。= 匠；习 g s ， 第二章低密度梭验码的构造 1 3 式。将各个子矩阵n ，兀。，n 。，n 。随机排列，并与双下对角线矩阵组合可构 叫翻叫七 2 2 6p e g 方法 1 0o；石，r 口刀c 石。 ：7 b 7 a 。 。 靠c珏8 110 石c 石d万一霈口 o1l 石。 万一万口万c 图2 6 万一法构造的锥阵h 该方法是一种使得变量节点的局部围长( e p 由一变量节点出发又回到一变量节 点所经历的最少边数) 最大的构造方法。假设在图t a n n e r 上前j - 1 个变量节点的边 已构造出来，在构造下一个变量节点的边时，每次向图上添加一条边，新添加的边使 得经过变量节点j 的最小环的围长最大。由于小环的存在对译码性能的影响，利用 p e g 方法构造的奇偶校验矩阵使得最小环的围长最大。所构成的矩阵如图2 7 所 示； l j00，i i ， 圩= 1 010，a矿 。i 1 001i口2 盯4 a 2 忙一i 图2 7p e g 法构造的校验矩阵h 通常，使用密度进化理论优化设计长l d p c 码的度分布序列足很成功的。但是， 它是否适用于短码设计尚不清楚。并且给定度序列分都下，随机构造的l d p c 码的 t a n n e r 图中有较多小环存在。目前，虽然还没有精确的理论分析环对译码性能的影 响，但人们普遍认为迭代译码算法在无环图上是一种最优译码，在有环图上，由 于大量环的存在影响了图中传递信息的独立性，影响了迭代译码算法的最优性。 影响码字性能的因素很多，如最小距离分布、度分布等，h ux i a o y u 等人提出的 p e g ( p r o g r e s s i v ee d g eg r o w t h ) 算法主要考虑因子图中环的影响p ”。 2 3 1 正则l d p c 码 2 3l d p c 码的结构 前面所讲的g a l l a g e r 码就是正则l d p c 码，任意一个二进制的线性分组码，都 可以简单的用二分图将编码表示出来。一个二分图是一个包括两个顶点集合的图， 只有属于不同集合的顶点间可能有边相连同一集合的顶点之间没有边相连。若 将二分图的两个顶点集合分别称为信息节点集合和校验节点集合。而将信息节点 集合中的节点( 信息节点、变量节点或左节点) 对应码字中的比特或者说校验矩阵的 坐深空通信中的l d p c 编译码技术的研究 列；将校验节点集合中的节点( 校验节点或右节点) 对应编码的码字所满足的校验约 束方程或者说校验矩阵中的行。若某个校验约束方程中出现了某个码字比特，则 在相应的信息节点和校验节点之问连一条边。定义与某个项点相关联的边数为该 顶点的次数( d e g r e e ) ，该“次数”用柬表示某个节点的约束程度。这样生成的二分 图就是相应分组码的二分图表示。 l d p c 码编码的二分图表示如图2 8 所示。图中用黑色的节点表示信息节点，白 色的节点表示校验节点。每个校验节点表示一个校验约束方程( h 矩阵的一行) 。在 该编码中，若没有校验约束，自由度为1 2 ( 1 2 个变量节点) ，6 个线性约束最多减少6 个自由度 ：。运算后将信息传送给父亲节点。这里“积”运算并不是一般意义上的数值 乘积。如果信息是参数化的函数，则其运算是相应的函数运算，其结果也是参数 化的函数。同理，s 啪运算也是相应信息函数的运算。计算在根节点而处结束，边 缘函数g 。( 而) 等于节点t 接收到所有信息的乘积。需要注意的是在边k 厂 上传递的 信息，无论从变量节点苫到因子节点，还是从因子节点，到变量节点，都是只是变 深空通信中的l d p c 编译码技术的研究 量x 的函数。可以看到，在每个因子节点，s u m 操作都是针对传送信息的边所对应 的变量节点进行的，相似的在变量节点，所有的信息都是该变量的函数，积也是 该变量的函数，