（通信与信息系统专业论文）ldpc码编译码算法研究及应用.pdf

分类号 密级 重庆邮电大学硕士学位论文 论文题目l d p c 码编译码算法研究及应用 英文题目s t u d yo na l g o r i t h ma n da p p l i c a t i o no fl d p c c o d e s 硕士研究生扬尧 指导教师睦盘堂副塾撞 学科专业通篮当篮息系统 论文提交日期! ：! ：! ：! ：论文答辩日期：竺2 ：! ：! ! 论文评阅人圭女篮：垒塾垫： 一 一! 垒垦整鱼兰 答辩委员会主席f 筮f 壁垡：灶i 垒 2 0 0 7 年5月1 0日 重庆邮电大学硕士论文 摘要 信道编码技术是移动通信系统的关键技术之一，以信道编码为核心内 容的前向差错控制也一直是通信理论中的热点课题。卷积码和t u r b o 码在 第二代移动通信系统和第三代移动通信系统中取得的成功让人炫目，但是 对于其在下一代移动通信系统的可行性，很多人都持谨慎态度：卷积码对 数据通信的可靠性让人怀疑，而t u r b o 码的高复杂度译码算法增加了终端 的功耗。 低密度奇偶校验( 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 ) 码的出 现让人们看到了新的选择。l d p c 码由麻省理工学院的g a l l a g e r 博士发 明于上世纪6 0 年代，但是直到3 0 多年后才真正为人们所重视。l d p c 码 是一种性能逼近香农( s h a n n o n ) 限的好码，其描述简单，对严格的理论 分析具有可验证性；译码复杂度低于t u r b o 码，且可实现完全的并行操作， 硬件复杂度低。因此，l d p c 码迅速成为信道编码领域的新宠，在无线通 信、深空通信、有线通信以及存储工业等各个领域展开了应用。 本文首先简述了通信系统以及信道编码理论的基础知识，并且对线性 分组码的基本原理作了阐述。本文重点介绍了l d p c 码的定义、几种最 主要的编译码算法以及主要译码算法的性能分析，基于对m p 译码算法的 分析，在经典b p 算法的基础上进行优化，得到了改进的归一化最小和算 法。然后，本文从简化编码结构和降低译码复杂度方面考虑，提出一种 t u r b ol d p c 码，它利用t u r b o 级联码的编码结构，用同样度分配的非规 则l d p c 码作为分量码，以t u r b o 码的编码方式构成。最后，通过构造信 道条件，搭建仿真链路，进行了链路仿真。仿真结果证明了在低信噪比情 况下，t u r b ol d p c 码优于同长度的非规则的l d p c 码和t u r b o 码。 关键词：低密度奇偶校验码，t u r b o 码，置信传播算法，密度进化 重庆邮电大学硕士论文摘要 a b s t r a c t c h a n n e lc o d i n gi so n eo ft h em o s t i m p o r t a n tt e c h n o l o g i e si nm o b i l e c o m m u n i c a t i o n t h er e s e a r c h e r so nt h ec h a n n e lc o d i n gt h e o r ya r eg i v e na g o o do p p o r t u n i t ya g a i n i nt h es e c o n da n dt h i r d g e n e r a t i o n m o b i l e c o m m u n i c a t i o ns y s t e m ，c o n v o l u t i o nc o d ea n dt u r b oc o d em a d eah u g es u c c e s s ， a n dc a nt h e yb ew i n n e ra g a i n ? m a n yr e s e a r c h e r sa r en o tv e r yo p t i m i s t i c ：t h e c o n v o l u t i o nc o d ei sn o tp o w e r f u le n o u g ht oe n s u r et h er e l i a b i l i t yw h i l et h e t u r b oc o d ed e c o d e rc a nn o ts u p p o r tt h es u p e r - h i g hd a t ar a t e t h er e n a i s s a n c eo fl o w d e n s i t yp a r i t y c h e c k ( l d p c ) c o d eo f f e r e dan e w c h o i c e l d p cc o d ew a si n v e n t e db yd r g a l l a g e ri nt h ey e a ro f19 6 2 ，b u ti t s i m p o r t a n c ew a sn o tr e a l i z e du n t i lt h ee n do ft h ei a s tc e n t u r y l o wd e n s i t y p a r i t yc h e e kc o d ei sag o o dc o d ew h o s ec a p a b i l i t yi sn e a rt os h a n n o nl i m i t l d p cc o d e sh a v ec e r t a i na d v a n t a g e s ，s u c ha s s i m p l ed e s c r i p t i o n so ft h e i r c o d es t r u c t u r ea n df u l l yp a r a l l e l i z a b l ed e c o d i n gi m p l e m e n t a t i o n s ，s t r i c tt h e o r y a n a l y s i s ，a n da d a p tt or e a l i z a t i o nb yh a r d w a r e w i t ht h es u c c e s si nt h ef i e l d s o fs p a c ec o m m u n i c a t i o n ，f i b e rc o m m u n i c a t i o na n ds t o r a g ei n d u s t r y , l d p ci s b e c o m i n gap o w e r f u lc o m p e t i t o r i nt h i st h e s i s ，t h eb a s i so fc o m m u n i c a t i o na n dc h a n n e lc o d i n gt h e o r yi s i n t r o d u c e db r i e f l y a f t e rt h ed e f i n i t i o no fl d p cc o d e ，t h ee n c o d i n ga n d d e c o d i n ga l g o r i t h m s ，a l s ot h ep e r f o r m a n c ea n a l y s i so fd e c o d i n ga l g o r i t h m s ， a r es t u d i e d w i t ht h ea n a l y s i so fm pd e c o d i n ga l g o r i t h m s ，t h i st h e s i si m p r o v e s b pd e c o d i n gm e t h o d s a tl a s t ，s t u d yt h ep e r f o r m a n c eo fu s i n gt u r b ol d p c c o d e s ，t h r o u g ht h es i m u l a t i o nr e s u l t s t h et u r b ol d p cc o d ei sp r e s e n t e d w h i c hu s e st w os a m ed e g r e ed i s t r i b u t i o np a i r so fi r r e g u l a rl d p cc o d e sa st h e t w oc o m p o n e n tc o d e si nt u r b os t r u c t u r e s i m u l a t i o nr e s u l t ss h o wt h a ta tl o w s n r ，t h en e wt u r b ol d p cc o d ei ss u p e r i o rt oi r r e g u l a rl d p cc o d ea n dt u r b o c o d ei np e r f o r m a n c e k e yw o r d s ：l d p cc o d e s ，t u r b oc o d e s ，b e l i e f p r o p a g a t i o n ，d e n s i t ye v o l u t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重鏖 噬曳太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 意。 学位论文作者签名：声5 乳 签字日期： n 1 年步月9 日 学位论文版权使用授权书 本学位论文作者完全了解重庞整皇太堂有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权 重迭鲣壹太堂可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：硒乳 导师签名：体食堂 签字日期：伽1 年 月，o 日签字日期：l 即- 年，月p 日 重庆邮电大学硕士论文笫一章绪论 第一章绪论 1 9 4 8 年，信息论的开创者香农( s h a n n o n ) 在他那篇著名的论文通信 的数学理论中提出并证明了：对于一个信道容量为c 的有扰信道，消息 源产生信息的速率为r ，只要r c ，则不存在编译码方式来实现无 误传输。这一结论为信道编码指出了方向，但它仅是个存在性定理，并 未给出怎样去寻找这种性能优良的码。 5 0 多年来，在信息技术发展和实际需要的不断推动下，人们一直在寻 求实现复杂度合理的更优秀的编译码方法，去逼近s h a n n o n 定理的理想界 限。令人鼓舞的是，在这个过程中，已经取得了许多伟大的进展，从早期 的分组码、代数码、r s 码、到后来的卷积码，以及今天的t u r b o 码，l d p c 码，所能达到的性能和s h a n n o n 限问的距离不断缩小。到目前为止，纠错 编码技术已经发展成为几乎各类数字通信系统以及计算机存储和运算系统 中必不可少的元素之一。随着科学的进步和实际的需要，纠错码理论将进 一步发展，其应用范围也必将进一步扩大。 1 1 数字通信系统模型 通信系统的基本目的在于将信息由信源高效、可靠、有时还需安全地 传送到信宿。有扰通信信道中的噪声会不可避免地对传输信息产生不同程 度的干扰，从而可能降低通信可靠性。所以通信系统设计的核心问题就是 在存在随机噪声的信道中如何克服干扰，减小信息传输的差错，同时又不 降低信息传输的效率，即如何解决系统的有效性与可靠性之间的矛盾。一 般地，通信系统的可靠性用误比特率( b e r ) 来衡量，其有效性则用信息传 输速率r 比特信道符号来衡量。早期的人们普遍认为：通信系统的可靠 性与有效性之间是一对不可调和的矛盾，一方的改善总是以牺牲另一方为 重庆邮电大学硕士论文第一章绪论 代价，并指出当功率受限时，在有扰通信信道上实现任意小错误概率的信 息传输的唯一途径就是把信息传输速率降低至零。s h a n n o n 信息和编码理 论的奠基性论文“通信的数学理论”发表之后，改变了这一观点。他首次 阐明了在有扰信道上实现可靠通信的方法，指出实现有效而可靠地传输信 息的途径就是通过编码【2 j 。根据s h a n n o n 的信息理论，数字通信系统的基 本组成如图1 1 所示【3 j 【4 儿卯。 圃 地j 丁孬翮 图1 1 数字通信系统模型 s h a n n o n 的信息理论从通信系统的整体最佳化来研究信息的传输和处 理。比特是一种通用的信息表示形式，它本身并不依赖于信源或信道特征。 这就允许我们分别设计图1 1 所示的两个阶段的信息处理，即信源编码和 信道编码。s h a n n o n 不失最佳性地证明了这种分离性【2 儿 。 图1 1 中的信道部分只是信息传输所通过媒介的一种抽象，实际的信 道是多种多样的，如电缆、光缆、存储设备、甚至我们所处的实际空间及 外太空等等。对于通信系统设计者来讲，了解系统中信道的特性是必需的。 根据信道的输入输出的取值连续与否可以将其分为离散信道、连续信道和 离散输入连续输出信道；根据信道统计特性是否随时间改变可以将其分为 平稳信道和非平稳信道：根据信道的输出之间是否具有相关性可将其分为 记忆信道和无记忆信道；根据信道的特性对输入端是否具有对称性可以将 其分为对称信道和非对称信道。实际应用中所涉及到的信道大多都是离散 输入的平稳无记忆对称信道，下面给出几种常用的编码信道模型【4 】【5 1 1 6 】【7 】。 二进制对称信道( b s c ) ：输入为二值变量0 、1 ，输出也为二值变量0 、 l ，且传输过程中发生错误( 输入为0 输出为1 或输入为1 输出为0 ) 的概率 与输入无关： 二进制删除信道( b e c ) ：输入为二值变量0 、1 ，输出或为输入的二值 变量0 、1 ，或为删除e ，且通常传输过程中不同输入被删除的概率相同； 二进制输入高斯信道( b i a w g n ) ：输入为二值变量，输出为连续变量， 且信道中的加性噪声为服从n ( o ，万2 ) 的高斯随机变量。 重庆邮电大学硕士论文 第一章绪论 1 2 信道编码理论及其发展 图1 1 中的信道编译码部分是以特定的控制手段，引入适量冗余比特， 以克服信息在传输过程中受到的噪声和干扰影响。根据s h a n n o n 提出的信 道编码定理，对任意一个平稳离散无一记忆有噪声信源，都有一个固定的 量，称之为信道容量，记做c 。只要信息的传输速率低于信道容量，就必 然存在一种编码方法，使得信息出现差错的概率随码长的增加趋于任意小： 反之，当信息传输速率超过信道容量时，则不存在这样的编码方法。这就 是著名的信道编码定理，它给出了特定信道上信息传输速率的上确界。 定理1 1 ( 信道编码定理) ：任意离散输入无记忆平稳信道存在信道容量 c ，对预期的任一数据速率r 0 ，有可能设计一对编 译码器，以保证该信道中速率为r 的数据传输具有小于p 的译码错误概率。 信道编码定理指出，在有扰信道中，只要信息传输速率小于信道容量， 就有可能实现任意可靠的信息传输。这个存在性定理提醒我们可以实现以 接近信道容量的传输速率进行通信。但遗憾的是该定理采用的是非构造性 的证明方法，其中并没有给出逼近信道容量的码的具体编译码方法。 s h a n n o n 在信道编码定理的证明中引用了三个基本条件，即： ( 1 ) 、采用随机的编码方式： ( 2 ) ，码字长度趋近于无穷大； ( 3 ) 、译码采用最佳的最大似然译码。 一般可将信道编译码器所使用的纠错码从性能上分为坏码和好码。所 谓坏码是指只有将码率降至零才能使误码率为任意小的编码方式：而好码 又可以分为当误码率任意小时，码率逼近信道容量限的非常好码和码率可 达到的非零最大值小于信道容量限的一般好码。虽然s h a n n o n 指出一个随 机选择的码以很高的概率为好码，但随机码的最大似然译码的复杂度往往 与码长呈指数关系，即在误码率随码长趋于无穷而趋向于零的同时，译码 复杂度以指数增长，而在实际应用中，只能够使用以码长多项式的时间和 空间复杂度内完成编译码的纠错码，因而尽管一般的随机码是好码，但不 能看作是实用码。 自信道编码定理提出以来，如何构造一个逼近信道容量限的实用好码 成了众多研究学者竟相研究的课题，并逐渐形成信息论的一个重要分支 信道编码理论。五十多年来，人们构造实用好码的探索基本上是按照 s h a n n o n 所引用的基本条件的后两条为主线展开的。虽然从理论上讲，除 重庆邮电大学硕士论文 第一章绪论 了目前己知的码外，几乎所有的码都是好码，但到目前为止，构造出真正 意义上的实用好码还有较长的距离。虽然如此，通过众多学者，特别是有 关数学和信息论学术界的研究人员五十多年的共同努力，目前己经取得了 很多成果。下面对其进行简要概述。 纠错码洲8 】从构造方法上可分为分组码( b l o c kc o d e s ) 和卷积码 ( c o n v o l u t i o n a lc o d e s ) 两大部分。在分组码方面，第一个分组码是1 9 5 0 年 发现的能纠正单个错误的h a m m i n g 码；在整个5 0 年代，基于代数理论又 发现了多个短码长的分组码，如1 9 5 4 年g o l a y 发现的g o l a y 码以及r e e d 和m u l l e r 发现的r m 码，p r a n g e 在1 9 5 7 年发现的循环码等。最有意义的 是b o s e 和r a y - c h a u d h u r i 在1 9 6 0 年及h o c u e n g h e m 在1 9 5 9 年分别独立发 现的能纠正多个错误的b c h 码，以及r e e 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 ec o d e s ) ，现在称为格 图码( t r e l l i sc o d e s ) 或卷积码。卷积码具有动态格图结构，可用有限状态机 来描述其状态。由于缺乏有效的理论研究工具，对卷积码的有效研究成果 不是很多，目前性能好的卷积码的构造方法主要借助于计算机搜索来获 得。卷积码的译码一般采用概率译码，由于译码算法的简单、实用和易于 实现，卷积码被广泛应用于实际中。 1 9 6 6 年，f o r n e y 将分组码和卷积码结合起来，提出了级联码 f c o n c a t e n a t e dc o d e s ) 的概念。级联码一般采用r s 码作为外码，卷积码作 为内码。f o r n e y 的研究表明，级联码在性能得到较大改善的情况下，其译 码复杂度并不显著增加。 根据对接收信号处理方式的不同，纠错码的译码可以分为硬判决译码 和软判决译码。硬判决译码是基于传统纠错码观点的译码方法，解调器首 先对信道输出值进行最佳硬判决，再将判决结果送入译码器，译码器根据 解调器的判决结果，利用码字的代数结构来纠正其中的错误。而软判决译 码则充分利用了信道输出的波形信息，解调器将匹配滤波器输出的一个实 数值送入译码器，由于实数值包含了比硬判决更多的信道信息，译码器能 够通过概率译码充分利用这些信息，从而获得比硬判决译码更大的编码增 益。 4 重庆邮电大学硕士论文第一章绪论 总之，尽管随机码是理论上的好码，但由于其编码实现的困难性和无 法承受的译码复杂度而只被用做理论分析的工具，在信道编码定理和后来 的许多编码理论成果中，代数编码理论始终占据了主导地位，使得传统的 信道编码技术受到临界速率( c r i t i c a lr a t e ) ，也称作截止速率( c u t o f fr a t e ) 的限制1 4 1 。 1 9 9 3 年t u r b o 码【9 儿”j 的提出被看作是信道编码理论研究的重要里程 碑。b e r r o u 等人将卷积码和随机交织器相结合，同时采用软输出迭代译码 来逼近最大似然译码，取得了超乎寻常的优异性能，并一举超越了截止速 率，直接逼近s h a n n o n 提出的信道容量限。t u r b o 码是一种可实用非常好 码，它的出现标志着信道编码理论研究进入了一个崭新的阶段。t u r b o 码 成功的根本原因在于其实现方案中长码构造的伪随机性是核心，它通过随 机交织器对信息序列的伪随机置换实现了随机编码的思想，从而为 s h a n n o n 随机编码理论的应用研究奠定了基础。 随着t u r b o 码的深入研究，人们重新发现g a l l a g e r 早在1 9 6 2 年提出的 低密度校验码【7 儿“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 2 】【1 3 】【1 4 儿1 ”。由于l d p c 码具有在码长较长时超过t u r b o 码的性能， 并且具有译码复杂度更低，能够并行译码及译码错误可检测等特点，成为 目前信道编码理论的研究热点。研究表明，t u r b o 码只是l d p c 码的一个 特例【1 6 】【1 7 】【18 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 。g a l l a g e r 证明了这类码具有很好的汉明距离特性，是 满足g v 限的渐进好码，在计算树上进行i o c l o g ( 1 0 9 ( n ) ) ( 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 图【i 州的 双向二部图上。采用t a n n e r 图构造的l d p c 码，通过并行译码可以显著地 降低译码复杂度。t a n n e r 还仔细分析了最小和算法( m i n - s u m a l g o r i t h m ) - 与 重庆邮电大学硕士论文 第一章绪论 和积算法( s u m p r o d u c t a l g o r i t h m ) 两种信息传递算法，证明了基于有限无环 t a n n e r 图的最小和译码算法与和积译码算法的最优性。但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 r b o 码相似的译码性能，在长码时甚至 超过了t u r b o 码 2 0 1 2 1 1 ，这一结果引起了信道编码界的极大关注。此后， d a v e y 和m a c k a y 从减少t a n n e r 图上小环路的概念出发提出了基于g f ( q ) ， q 2 的l d p c 码【2 2 】【2 3 1 ，进一步提高了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 提出了基于二部扩展图的扩展码f 2 4 1 【25 1 。在对扩展码的研究中，他们 证明了一个随机构造的t a n n e r 图以很大的概率为好的扩展图，而由好的扩 展图构造的线性纠错码是渐进好码，从而证明了采用随机t a n n e r 图构造的 l d p c 码以很大概率是渐进好码。l u b y 等人将采用非正则t a n n e r 图构造的 扩展图用于删除信道，称之为t o r n a d o 码 2 6 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 码的性能得到显著的提高 3 0 1 1 3 1 3 2 1 1 3 3 3 4 1 。 ， 同时，w i b e r g 结合t u r b o 码和网格图的研究，将t a n n e r 图推广到包含 隐含状态变量的因子 ( f a c t o rg r a p h ) 1 9 1 【2 2 】【35 1 ，对t u r b o 码和l d p c 码的 研究在因子图的基础上得到统一。w i b e r g 对因子图的研究发现，对任意给 定系统，无环图的状态复杂度是最大的，有环图的状态复杂度则会大大降 低，从而证明了基于有环t a n n e r 图的l d p c 码具有较低的译码复杂度。 w i b e r g 同时还证明了最小和算法和和积算法在本质上的同一性，在格图译 码中，最小和算法退化为v i t e r b i 译码算法，和积算法退化为b c j r 译码算 法。 近两年，r i c h a r d s o n 等人应用密度进化理论来测度l d p c 码的性能 3 2 1 1 3 6 l 。r i c h a r d s o n 等人在对l d p c 码的研究中发现，译码信息的迭代传递 过程中存在着译码阙值现象，即当信噪比大于译码阈值时，迭代译码可使 误码率趋于零，反之无论采用多长的l d p c 码，经过多少次迭代译码，总 存在一定的错误概率。应用中心极限定理，r i c h a r d s o n 等人证明了有限随 重庆邮电大学硕士论文第一章绪论 机有环图的译码阈值可以逼近无环图的译码阈值。通过建立在无环图上的 密度进化理论，可以精确地计算无环图上l d p c 码的译码阈值，分析其译 码收敛条件，从而近似估算有环t a n n e r 图上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 码性能的模型由 多参数动态系统的密度进化理论模型简化为单一参数动态系统的高斯逼 近模型 4 0 1 4 引。 1 4 本文主要研究工作和内容安排 本文主要讨论了目前信道编码领域的热点课题一一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 码的译码方法。主要介绍了硬判决译码算法 和软判决译码算法，并且给出了其仿真的性能比较，此外还详细讨论了密 度进化理论。 第五章，讨论了t u r b ol d p c 码的理论基础和构造方法，并且给出了 性能限和仿真的结果。 最后，总结全文，讨论下一步的工作和需要解决的问题。 7 重庆邮电大学硕士论文第二章l d p c 码简介 2 1 线性分组码 第二章l d p c 码简介 因为低密度奇偶校验码是一种特殊的线性分组码，所以本章将首先对 线性分组码做一个概述，为讨论l d p c 码作铺垫。更详尽的叙述请参阅文 献【2 4 1 。 这一部分将讨论线性码的一些特性。 定义l ：整数0 ，l ，2 ，q 1 ，q 是自然数，在模p 加和乘运算下构成 个伽逻华域o f ( q ) 。 定义2 ：如果一个分组码c ，包含n 个由g f ( q ) 中的元素构成的码字 ( c o ，c l ，c 刖) ，则当且仅当c 构成一个g f ( q ) 上的矢量子空间时， 称c 为q 进制线性码。在这篇论文里，本文只考虑二进制码，所 以q = 2 。 定义3 ：线性码的维数等于对应的矢量空间的维数，一个长度为n ，维数 为k 的线性码总共包括2 0 个长度为n 的码字。 线性码还有如下一些有用的性质： 性质1 ：任意码字的线性组合仍然是一个码字。此性质的一个结论是线性 码必然包含一个全零码字。 性质2 ：线性码的最小距离等于其中一个最轻非零码字的汉明重量。 这一性质表明确定线性码的最小距离( 决定检错和纠错能力) 要比一般 的分组码要容易的多。 性质3 ：线性码中不可检测的错误图案与传输的码字无关，且由所有的非 零码字组成。 假设( g o ，g l ，一，g k 1 ) 是组成( n ，k ) - - 进制码空闭的一组基底，对任意一 个码字c c ，存在唯一的表达形式 c 。a o g o + a i g l + + a k 1 9 k i 因为所有基元的线性组合仍然是一个码字，所以存在长度为k 的码组 ( a o , a l ，a n i ) 和c 中码字之间的一一映射。以下矩阵g 就是由基矢按行排 列而成。 8 重庆邮电大学硕士论文第二章l d p c 码简介 g = g o 0 g j ，0 ： g x 一1 ，0 g o ，l g l ，l ： g x 一1 i ( 2 1 ) 这一矩阵叫做码字c 的生成矩阵。通过生成矩阵和信息比特相乘可用 来直接编码k 位的数据组。令m = ( m o ，m l ，m k - 1 ) 为待编码的二进制组。 c = m g = ( m o ，埘l ，m r 1= m o g o + m l g l + + m r l g r i ( 2 2 ) 线性码c 的对偶空间表示为c 。，是一个( n k ) 维的矢量空间。c 1 的一 个基 h o , h l ，”，h n k i ) 可构造一个校验矩阵h 。 h = | j i o 啊 ： h n k o 啊o ： 1 ： 州 - i ： n ，o n 1 一一l ( 2 3 ) 校验定理：矢量c 是码字的条件是当且仅当e h = 0 。 校验矩阵也提供了确定最小码距的方便途径。若线性码c 的校验矩阵 为h ，则c 的最小码距等于使各列线性组合之和等于零的最小非零列数。 如果c 的码重为w ，则e ho 是h 中的w 列的线性组合。以上表达式定 义了重为w 的码字和h 中w 列线性组合的一一映射关系。 如果使用系统码会大大简化数据组的译码。考虑一个生成矩阵为g 的 线性分组码c ，通过高斯消去和列交换，通常可以得到如下形式的生成矩 阵。可以由生成矩阵的各行线性无关以及列秩等于行秩证明上述结论。 g = 【i 。问= 1 o o ；p o ，。p o ，l p o - - i ? 。? ! p ：，p 1 ，t p i , n - 一 ：!： 0 0 1 ；p - 1 ，。p f l l p 一i 一f 一 ( 2 4 ) 当一个数据组使用系统生成矩阵编码后，原始数据组会毫无变化地位 于输出码字的前面k 位。对生成矩阵的高斯消去并不会改变相关码字的码 序列。但另一方面，列变换可能会产生不属于原来码空间的码字。如果要 求特定的码字被用到时就不能进行列交换，则需要对前k 位以外的系数做 一些调整，这会增加编码和译码设计的复杂度。 对于一个给定的系统码生成矩阵，相应的校验矩阵可以表示为： 9 等： 白；趾 rv-1l 重庆邮电大学硕士论文 第二章l d p c 码简介 h = - p r k 。】： 一p o 。oa o 一p o ，1一p 1 i 一p o h x i p 、_ k d 1o ol ： 0 o o 0 。： l ( 2 5 ) 对二进制码，p r = p 7 。应该注意到，我们总能将给定校验矩阵的生成 矩阵，通过高斯消去转换成系统形式。 2 2 低密度奇偶校验码( l d p c 码) l d p c 码是线性分组码中较为特殊的一种，但是目前l d p c 码并没 有严格的数学定义。考虑到其结构上的特点和叙述上的方便，参照l i n 的 观点【17 1 ，本文对l d p c 码做如下的定义。 l d p c 码是一个m 行n 列的稀疏矩阵h 的零空间，h 称为l d p c 码的校验矩阵，并且满足： l 、矩阵的行重、列重与码长的比值远小于1 ； 2 、任意两行( 列) 最多只有1 个相同位置上的1 ； 3 、任意线性无关的列数尽量的大。 这样的l d p c 码码长为n ，校验位长度大约为m ，信息位长度为k m n m 。 一个规则l d p c 码是指校验矩阵h 满足列重和行重分别等于常数 d ，和d 。，因为我们并没有要求校验h 是满秩矩阵，所以其码率为： r 1 - 翌：1 一生 ( 2 6 ) n d c ( 2 7 ) 式是一个n = 1 0 ，d v = 2 ，d c = 4 , r = 0 5 规则l d p c 码的校验矩阵。 h ( 2 7 ) 如果校验矩阵h 的列重和行重并不是常数，我们就称其为不规则 l d p c 码，我们可以认为规则l d p c 码是不规则l d p c 码中的一个特例。 不规则l d p c 码可以用重量分布多项式来方便的描述。假设最大列重和 最大行重分别是d 和d 罗，则h 的列重分布多项式丸( x ) 可以表示为： j _ 兄( 力= x “ ( 2 8 ) l ，2 1 0 o o 0 1 1 o 0 1 o 1 o 0 l 1 o o l 0 o l o 1 o l o o 1 l o o l o o o 1 l o o l 0 l o 1 o o 重庆邮电大学硕士论文第二章l d p c 码简介 其中，k 是重量为i 的列所占的比例，同时九( 1 ) = 1 。类似的，h 的行重分 布多项式p ( x ) 可以表示为： p i 是重量为i 的行所占的比例，p ( x ) 也满足p ( 1 ) = 1 。此时，码率r 满足： 川一甓 亿 值得注意的是，对于一个给定的码长n 和行、列重量分布多项式，我们得 由上面的叙述我们知道，l d p c 码是由其校验矩阵h 定义的。我们 知道，对于一个线性分组码，其校验矩阵并不是唯一的。也就是说如果对 于线性分组码的校验矩阵做行变换，得到的矩阵也是这个码的校验矩阵。 但是，对于l d p c 码这种特殊的线性分组码而言，由于译码算法的设计和 性能分析的需要，我们仅仅关心其属于稀疏矩阵的这个校验矩阵，因此， 定义一个l d p c 码必须给出这个稀疏的校验矩阵才有意义。对于l d p c 码的生成矩阵，并没有其他特殊的限制。 为了分析的方便，我们可以用因子图来表示一个l d p c 码”】。图中的 变量节点c i ( i = o ，l ，n 1 ) 与校验矩阵的列( 也即码字中的每一位) 一一对 应，校验节点( j = 0 ，1 ，m 1 ) 与校验矩阵的行( 也即各个校验方程) 一一 对应。c i 和f ；相连接，当且仅当校验矩阵中对应位置的元素是1 。这样， 该因子图是一个偶图，其邻接矩阵就是该校验矩阵。图2 1 是( 2 7 ) 式中校 验矩阵的因子图。由于l d p c 码定义中的第2 条的限制，因子图中不会 存在长度等于4 的圈( 对任意一个偶图，圈的最小长度为4 ) 。 c o c ic 2 c ，c c ；c 凸c lc 9 图2 1l d p c 码的因子图表示 一般而言，不规则码的性能要优于规则码，但是实现的复杂度和分析 的复杂度都要大得多。非规则码的编译码方法与规则码相似，而其性能却 优于规则码，这是因为非规则码的“波浪效应”，在l d p c 码的随机双向 图中，对信息节点来说，其度数越高，它从校验节点所获得的信息也就越 重庆邮电大学硕士论文 第二章l d p c 码简介 多，也就能更准确的判断其校验值；反之，从校验节点的角度来看，希望 度数低，其度数越低，那么传播到相邻节点的有用信息也就越多。而非规 则码的随机双向图就很好的平衡了信息节点与校验节点二者对度数的要 求。而所谓的“波浪效应”也就是度数大的信息节点首先获得正确值，然 后度数小的信息节点也可以获得正确值【4 l 】【4 ”。 非规则码的产生，使规则l d p c 码的定义产生了变化。在非规则码中， 度的变化范围很大，往往最大度可达几十或上百，因此，我们更广泛地把 度的变化很微小的l d p c 码都称之为规则的。 1 2 重庆邮电大学硕士论文第三章l d p c 码编码算法 第三章l d p c 码编码算法 3 1 传统编码算法 l d p c 码传统编码算法和一般的线性分组码十分类似，需要求出生成 矩阵。若已知长度为k 的输入信息向量k ，以及k x n 的生成矩阵g ，码字 c 就可以容易的得到：c = k g 。 在获得校验矩阵h 后，利用h 和g 之间的正交性可以用高斯消元法 来得到生成矩阵g 。假设稀疏矩阵h 有如下形式：h = c i i c 2 】。其中c 2 是一个m m 的稀疏方阵，并且在二元域上是非奇异阵，那么o 就可以式 给出： 广r1 g 72 la i o 1 ) 很容易验证，这样的g 满足h g 7 = 0 。其中，i k 是一个k 阶的单位矩阵， 这样得到的码具有系统码的形式。l d p c 码一般都具有系统码的形式，否 则由码字来恢复消息比特将会是一个十分困难的过程。如果在二元域上h 的秩是r ，而且c 2 是奇异矩阵( r m ，结束。 3 、如果该列中还有其他不为0 的元素，将该元素所在的行与第i 行 相加。然后将i 加l 。返回上个步骤。 这样得到的h 的前r 列是线性独立的。因此g 也能方便的求解出。 上述矩阵求逆过程的运算量的复杂度阶数是m 2 n 【7 1 ，但是整个过程只 需要做一次。 重庆邮电大学硕士论文第三章l d p c 码编码算法 一般而言，这样得到生成矩阵g 不是稀疏矩阵，因此在编码时所用到 的矩阵乘法的运算量阶数是o ( n z ) 。 在这种算法中，存储生成矩阵g 需要消耗相当大的资源。假设使用最 理想的存储方式，每比特存储g 矩阵中的一个元素，我们也需要k x m 比 特的存储空间。当码长较长时，由于巨大的运算量和存储量，这样的算法 在实现上是十分困难的。因此这种算法目前没有太大的现实意义，一般用 于性能仿真中。 3 2l d p c 码的快速编码 l d p c 码的校验矩阵是非常稀疏的，但它的生成矩阵却并不稀疏，通 常m 与n 的比值是【o ，1 】之间不可忽略的数，这使得其编码复杂度往往与其 码长的平方成正比。因此，相对于l d p c 码的译码来说，它的编码反而具 有较高的复杂度，这一点与t u r b o 码不同( 其编译码复杂度均为线性) 。 文 2 6 1 2 7 1 对l d p c 码的快速编码问题进行了研究，指出虽然l d p c 码的 编码复杂度与其码长的平方呈正比，但采用适当的编码算法，相应的系数 可以取得很小。文【2 7 l 给出实现l d p c 码的快速编码的方法，即e f f i c i e n t 编 码算法，可以有效的解决巨大的运算量和存储空间消耗的问题。 3 2 1 算法描述 e f f i c i e n t 编码算法的核心思想是考虑生成矩阵h 具有某种特殊的形 式，即所谓近似下三角矩阵的形式，如图3 1 所示。 鼓铲猕“警? 鬻t 誉i 黧，；： 瓠。 ；7 算了警雾。 ，爹； 。芬篱 鬻誊 j 菇豢氛 z + 辨 。 。a 黪鼙襄? 。，” 。静4 + 季“：纛j j ? 够囊 l 。0 毫，。巍”翟萼”。：i”1 麓，+ j 、礞 篓。0 叠。嚣确施施& 德f j 恕德。：童砖g 图3 1 具有近似下三角矩阵形式的校验矩阵 为方便起见，我们用分块矩阵的形式来表示校验矩阵h 。a 是一个 ( m g ) x k 的矩阵，b 是一个( m g ) x g 的矩阵，t 是一个( m - g ) ( m g ) 的方阵