（通信与信息系统专业论文）ldpc码的编译码研究及优化.pdf

中文摘要 随着移动通信系统高速率业务需求的不断增加，前向纠错编码技术越来越受 到人们的关注。g a l l a g e r 在1 9 6 2 年提出的低密度奇偶校验码( l d p c ) 是一类可以 用稀疏矩阵或二分图定义的线性分组码。它具有非常好的特点：性能逼近香农限， 描述简单，易于进行理论分析，译码可并行操作，适于硬件实现。 本文首先简述了l d p c 码的起源、当前发展概况，详细介绍了l d p c 码的定 义以及其t a n n e r 图表示，在规则码的基础上给出了非规则码的定义，最后，介 绍了g a l l a g e r 编码方法以及改进的有效编码设计方法。 然后，本文研究了l d p c 码通用的两类译码方法，比特翻转算法和置信传播 算法，在置信传播算法每一轮迭代过程中，关于各个节点的置信信息需要在变量 节点和校验节点之间传递。在此基础上深入研究了l d p c 码的加权比特翻转算 法，提出了改进的两步比特翻转算法，并给出了高斯信道b p s k 调制下的具体算 法实现。分析了算法复杂度并给出了m a t l a b 仿真结果，表明此算法是解码复 杂度与纠错性能两者之间的一种很好的折衷。 最后，本文介绍了现在通用的几种l d p c 码的构造方式，包括g a l l a g e r 构 造算法，m a c k e y 构造算法，基于b i b d 构造方法，基于有限几何的构造方法。 在此基础上详细研究了准循环l d p c 码的构造方式，提出了基于q 矩阵的准循 环l d p c 码的构造方式，详细分析了码长，码率，构造方式，译码方式等对码性 能的影响，a w g n 信道下的仿真结果表明其具有逼近随机l d p c 码的误码率性 能。 关键词：l d p c 码：两步比特翻转算法；准循环l d p c 码；q 矩阵；b p 算法： a b s t r a c t w i t ht h ei n c r e a s i n gd e m a n df o rh i g h - s p e e ds e r v i c e si nm o b i l ec o m m u n i c a t i o n s y s t e m s ，f o r w a r d e r r o r c o r r e c t i o n ( f e c ) c o d e st e c h n i q u e s a r e r e c e i v i n g m o le a t t e n t i o n l 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 e sf i r s td i s c o v e r e db yg a l l a g e ri n19 6 2 a r eac l a s so fl i n e a rb l o c ke r r o r - c o r r e c t i n gc o d e st h a tc a l lb ed e f i n e db yt h ev e r ys p a r s e p a r i t y - c h e c km a t r i xo rt h eb i p a r t i t eg r a p h t h e yh a v ev e r ya t t r a c t i v ep r o p e r t i e s ：e r r o r p e r f o r m a n c ea p p r o a c h i n gs h a n n o nl i m i t s ，s i m p l ed e s c r i p t i o n ，c o n v e n i e n tt h e o r e t i c a l a n a l y s i sa n dr e s e a r c h ，e a s i l yd e c o d e di nc o m p l e t ep a r a l l e lw a y sa n ds u i t a b l ef o r h a r d w a r ei m p l e m e n t a t i o n i ti sf i r s t l yi n t r o d u c et h a tt h ep r e s e n ts i t u a t i o no ft h ed e v e l o p m e n ta b o u tl d p c c o d e s ，t h e d e f i n i t i o no ft h el d p cc o d e sa n dt h e i rt a n n e rg r a p h s b a s e do nt h e d e s c r i p t i o no fr e g u l a rl d p cc o d e s ，t h ei r r e g u l a rl d p cc o d e sa r ep r e s e n t e d i nt h e e n d ，t h eg a l l a g e re n c o d e ra n de f f i c i e n te n c o d e r a lei n t r o d u c e d t w o g e n e r a ld e c o d i n gm e t h o do fl d p cc o d e s ，c a l l e db i t f l i pd e c o d i n ga l g o r i t h m a n db e l i e fp r o p a g a t i o na l g o r i t h m ，w h i c hm e a n st h a tt h eb e l i e fm e s s a g eo fe a c hn o d e w a sp r o p a g a t e db e t w e e nt h ec h e c kn o d e sa n dt h eb i tn o d e s a lei n t r o d u c e d t h e nb a s e d o nt h ew e i g h t e db i t f l i pa l g o r i t h m ，ai m p r o v e dm e t h o dc a l l e dt w o - s t e pb i t f l i pa l g o r i t h m i si n t r o d u c e d ，t h e np r e s e n tt h ep e r f o r m a n c eu n d e ra w g nc h a n n e la n db p s kt r a n s m i t u s i n gm a t l a b ，t h er e s u l t ss h o wt h a tt h i sa l g o r i t h mi so n eo ft h eb e s tm e t h o dw h i c h c a l ls a t i s i f yt h ep r o p e r t ya n dt h ec o m p l e x i t y a tl a s t ，s e v e r a lm e t h o d so fd e s i g nt h ep a r i t ym a t r i xhi si n t r o d u c e d ，i n c l u d i n g g a l l a g e rd e s i g nm e t h o d ，m a c k e yd e s i g nm e t h o d ，d e s i g nb a s e do nb a l a n c e di n c o m p l e t e b l o c k d e s i g n a n df i n i t e g e o m e t r i e s a f t e rt h a t ，q u a s i c y c l i c l d p cc o d e si s p r e s e n t e d i ti s s h o w e dt h a th o wt os t r u c t u r et h eq c l d p cc o d e sb a s e do nq m a t r i x b e s i d e st h ee f f e c t i o no ft h el e n g t ho fc o d e s ，t h er a t eo fc o d e sa n dt h ed e s i g n m e t h o d ，d e c o d i n ga l g o r i t h m a r es t u d i e d t h es i m u l a t i o nr e s u l t su n d e ra w g n c h a n n e ls h o wt h a tt h e s ec o d e sw h i c hc a l lb eo b t a i n e db yt h i sm e t h o da r ea sg o o da s r a n d o ml d p cc o d e s k e yw o r d s ：l d p c ；t w o s t e pb i t f l i pa l g o r i t h m ；q c l d p c ；qm a t r i x ；b p a l g o r i t h m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得吞叠蕉堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名两久自戚 签字r 期： 1 。口7 年口f 月咀日 学位论文版权使用授权书 本学位论文作者完全了解苤盗苤堂 有关保留、使用学位论文的规定。 特授权苤鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：歌臼臧 导师签名： 幽厮鲜 i 签字r 期：如露7 年。f 月吐r 签字r 期：少哆年月lr 第一章绪论 1 1 研究背景及意义 第一章绪论 随着无线通信和移动通信业务的快速发展，增强编码效率和通信能力成为迫 切的需求。为了提高频谱利用率，最大限度地利用频域、时域资源，寻找更加接 近香农极限的实用好码成为研究的热点。 l d p c ( l o w d e n s i t yp a r i t y c h e c k ) 码是一种可接近香农极限的信道编码技术。目 前的研究均表明l d p c 码是信道编码中纠错能力最强的一种码，而且由于其译码 器结构实现简单，可以用较少的资源消耗获得极高的吞吐量，因此应用前景相当 广泛。l d p c 码与高效调制技术相结合，能满足下一代无线通信技术的发展要求。 目前，l d p c 编译码技术已在d v b s 2 ，i e e e 8 0 2 1 1 和光纤通信等领域得到初步 应用。另外，在未来的深空通信、卫星数字视频和音频广播、磁光存储系统、 固定无线通信( p h s ) 、电缆调n 解调器和数字用户线( d s l ) 这些前沿的开发领域 里，低密度校验码都将有其用武之地。l d p c 码迭代译码思想现已广泛应用于通 信技术其它方面，研究译码算法为实现迭代信道估计，信道检测提供了新思路。 综上所述，l d p c 编译码技术是时下的热点和发展方向。论文研究适用于未 来通信系统的l d p c 码，有较强的理论意义和实际意义。 1 2 数字通信系统组成 通信系统旨在将信息由信源高效、可靠、安全地传送到信宿。有扰通信信道 的噪声会对传输信息产生干扰，从而可能降低通信可靠性。所以，通信系统设计 的中心问题是在随机噪声干扰下如何有效而可靠地传输信息。在数字通信系统中 可靠与快速往往是一对矛盾。若要求快速，必然使每个数据码元所占用的时间缩 短、波形变窄、能量减少，从而在受到干扰后产生错误的可能性增加，传送信息 的可靠性减低。若要求可靠，则使得传送消息的速率变慢。通信系统设计人员最 关心的是如何在数据源功率和带宽有限，系统复杂性和设备造价尽可能小的条件 下实现尽可能准确的信息传输，信道编码是消除和降低信息错误概率的有效手段 之一。为了更好的理解信道编码在数字通信系统中的地位和作用，下面首先介绍 通用数字通信系统的结构。 第章绪论 图1 - 1数字通信系统结构图 编码信道 在上面的系统框图中，把传输信道称为调制信道( 又称狭义信道) ，而把包 括调制器、传输信道和解调器在内的部分称为编码信道( 又称广义信道) ，它的 输入是二( 多) 进制的数字序列，输出一般也是二( 多) 进制的数字序列。 发送端包含四个模块：信源、信源编码器、信道编码器和数字调制器。信源 编码就是用二进制( 或多进制) 序列来表示信源输出的过程，其目的是除去信源 的冗余以减少通信负担，因而也称为数据压缩。信道编码与信源编码正相反，它 通过在信息序列中引入冗余来实现通信的可靠性。数字调制就是将信息序列映射 成适合信道传输的信号的过程。对应地在接收端也有相应的四个模块用于实现相 反的过程。 系统中信息传输引入的干扰会导致错误的接收信号，信道编码的目的就是在 发送的信息序列中有意地引入一些冗余，从而使信道引入的差错最小化。假定信 道编码器输入k 个信息单元，输出玎个信息单元，则通常称这1 , 个信息元为一个 码字，比值r = k n ( r 2 ) 的多进制l d p c 码，从 而进一步提高了l d p c 码的译码性能1 7 】。s l i n 等基于有限几何和r s 码分解构 造了定义在g f ( q ) ( q = 2 p ) 上的l d p c 码和q c l d p c 码，取得良好性能【引。j r o s e n t h a l 和pv o n t o b e l i 州研究了基于r a m a n u j a 图和按照m a r g u l l i s 的概念构建的 正则l d p c 码，其性能优于随机构造的( 3 ，6 ) 正则码。 当码长无穷长，不存在短环路的条件下，针对不同的信道和不同的译码算法， 采用高斯近似、密度进化和e x i t 等分析方法，能精确的分析出l d p c 码的理论 极限。当码长为有限长时，目前已经对二进制删除信道【l o 】和a w g n 信道【l l 】下的 性能进行了分析。l d p c 码的实际应用往往是在非标准信道，存在着非常严重的 多径效应和多普勒效应的影响。文献 1 2 1 1 3 研究了l d p c 码在r a y l e y g h 、r i c e 信道下的表现，结果表明在上述信道下，l d p c 码依然有很好的性能。 在以上工作的基础上，l d p c 码的研究在译码算法的简化、密度进化的改进、 非规则码的度数设计、校验矩阵的构造、距离特性和性能界的分析、在通信和数 据存储器中的应用以及l d p c 码的实现等各方面陆续展开，并取得了很多有价值 的成果，而且在实际系统中得到了应用。f l a r i o n 公司开发的f l a s h o f d m 移动无 线芯片组采用l d p c 码作为纠错方案，可用于基于i p 的移动宽带网，大大增加 了传输距离，增强了对无线信道环境的抵抗能力，数据速率可达3 m b i t s 。v o c a l t e c h n o l o g i e sl t d 推出了一种用于w l a n 的l d p c t u r b o 不对称解决方案，下行 链路采用l d p c 码，上行链路采用t u r b o 码，可以实现节能的目的。据称采用该 方案后用于i e e e8 0 2 1 1 a b gw l a n 移动终端的电池寿命延长至原来的4 倍。 虽然由于l d p c 的再发现比t u r b o 晚几年，使l d p c 码与3 g 标准失之交臂， 但是近年来l d p c 码以其优异的性能、简洁的形式及良好的应用前景备受青睐， 可以应用于空间通信、光纤通信、个人通信系统、a d s l 和磁记录设备等，多个 通信标准己经将l d p c 码作为信道编码方案，主要是： l 、d v b s 2 标准，信道编码采用l d p c 级联b c h 的方案。目前己经有a h a 4 第一章绪论 公司、意法半导体公司等拥有支持d v b s 2 信道编码方案的自主知识产权的i p 核和相应编解码芯片，同时，x i l i n x 公司也提供了l d p c 码编码器的i p 核。 2 、中国数字电视地面广播标准，采用具有自主知识产权的q c l d p c 级联 b c h 作为信道编码方案，共支持三种码率：0 4 、0 6 和0 8 。 3 、中国广电总局制定的中国移动多媒体广播标准( c m m b ) ，采用结构化的 l d p c 码与r s 码级联。 4 、8 0 2 1 6 e 标准也将l d p c 码作为信道编码选项，并提供了两种快速编码方 法。目前，美国a l b e r t a 大学的研究人员己经成功地在f p g a 上实现了该l d p c 码的编码器设计及验证。 除了用作信道编码外，l d p c 码作为数据压缩编码和公钥加密系统中的加解 密方法也都具有优越的性能。 虽然l d p c 码的理论和应用研究已取得相当大的进展，但仍有许多尚待解决 的问题： l 、l d p c 码校验矩阵的构造，尽管在构造最优的l d p c 码方面取得了一些 进展，但目前还没有一套系统的办法来构造所需要的好码，特别是在码字长度有 限、码率一定的条件下，构造性能优异的好码是一个非常具有挑战性的课题，这 方面的研究可以借助有限域理论、图论等相关理论。 2 、l d p c 编码系统的联合优化设计，将编码技术与调制技术、空时编码技 术、o f d m 技术结合进行性能优化是当前及将来的发展方向之一。 3 、寻找适合硬件实现的编译码方法也是一个非常值得研究的课题。 1 5 论文内容安排 本文讲述了l d p c 码的编译码原理，包括l d p c 码的编码，l d p c 码的译码 及l d p c 码的构造。着重介绍了译码中的两步比特翻转算法和构造方法中的基于 q 矩阵的q c l d p c 码的构造。第一章简述了课题的背景和l d p c 码的发展历史。 第二章，介绍了l d p c 码的基础知识及编码方法。第三章介绍了l d p c 码的译码 方法，提出了改进的w b f 算法以，详细分析了两步比特翻转算法的复杂度及性 能。第四章对l d p c 码的构造方法进行了分析，同时对基于q 矩阵的q c l d p c 码进行了详细的分析和性能仿真。第五章对今后的工作做了进一步的展望。 1 6 本章小结 本章首先对课题研究的背景及意义进行了简要介绍。之后，简述了数字通信 5 第一章绪论 系统的构成及信道编码的基础知识；然后对l d p c 码的历史及发展，应用现状进 行了总结。最后，对本论文的内容和论文的组织结构进行了介绍。 6 第二章l d p c 码基本原理 第二章l d p c 码基本原理 2 1 线性分组码的基本概念 2 1 1 线性分组码的定义 分组码是纠错码中最基本的一类编码方法，这里仅讨论分组码类中最常用的 一个子类线性分组码。 线性分组码是把信息划成k 个码元为一段( 信息组) ，通过编码器变成长为 刀个码元的一组，称为码字( 码组) 。在二进制情况下信息组共有2 个，因此通 过编码器后，相应的码字也有2 ，称这2 个码字集合为线性分组码，用( n ，k ) 表示，刀表示码长，七表示信息位，码率r = 七n 。二元线性分组码必须满足如下 两个条件： 1 、码字集合中的任意两个码字经过模2 加之后得到的结果仍然是码字集合 中的一个码字。 2 、码字集合中包含有全零码字。 从数学的角度讲，可以把一个( 玎，七) 线性分组码看成二元刀维线性空间上 的j | 维子空间。因此，( ”，七) 线性分组码可以通过由七个线性无关的二元刀维 矢量集合 繇，蜀，繇。) 来得到。得到的码字实际上是这些刀维矢量根据信息 序列分组中各个比特的取值而得到的线性组合。 2 1 2 生成矩阵和校验矩阵 线性分组码的编码过程可以描述为一个信息矢量聊和一个矩阵相乘的结果 c = n l 木g( 2 1 ) 其中，g 是由露个刀维矢量 g 。，函，& 一。 构成的矩阵，称为生成矩阵；m 是信息序列 m o ，m ) ：c 是编码得到的力维编码输出 c o ，q ，c 川 ， 其中矢量与矩阵的乘积是在二元域g f ( 2 ) 上进行的。 与每个线性分组码相联系的还有另外一种有用的矩阵，对于任意有j i 个线性 独立行的k * n 矩阵g ，存在有一个具有 一七行线性独立的( 刀七) 宰玎阶矩阵h 。 它使得g 的行空间中的任意向量都和h 的行正交，且与h 的行正交的任意向量 都在g 的行空间中，因此用另一种方法来描述由g 生成的( 刀，七) 线性码：一 第二章l d p c 码基本原理 个刀维向量c 是g 生成的码字中的码字，其充要条件为 c 幸r = 0 7( 2 2 ) 此时h 称为一般校验矩阵。因为g 中的每一行及其线性组合均为( ，l ，七) 码的一个码字，所以： g h7 = 0( 2 3 ) 2 1 3 线性分组码的最, j x 足f i 离 好的编码方式应该使得到的码字之间的区别尽可能大。对于二元码而言，码 字集合中任何两个码字之间的区别就表现在它们相应位置上比特取值的区别。 定义2 1 ( 以，七) 分组码中，任何两个码字之间距离的最小值，称为该分组码的最小汉 明距离，简称为最小距离。即 = m i n ( d ( x ，y ) ) ( 2 4 ) x 。y e ( n , k ) 例如( 3 ，2 ) 码，n = 3 ，k = - 2 ，共有2 2 = 4 个码字：0 0 0 ，0 1 1 ，1 0 1 ，1 1 0 ，显 然= 2 。 叱。是线性分组码的另一个重要参数，它表明了分组码抗干扰能力的大小。 因此有时线性分组码也有( 以，k ，丸。) 表示。下面给出线性分组码最小距离和校 验矩阵之间的关系。 定理2 1 。 ( ，z ，k ，) 线性分组码的最小距离等于的充要条件是，校验矩阵中任意 1 列线性无关。 可以证明，对于一个最小距离为k 的( 玎，动线性分组码，其最小汉明距离 与其纠错能力有如下关系： 1 、检测e 个随机错误，要求码的最小汉明距离“p + l ： 2 、纠正t 个随机错误，要求“2 t + 1 ； 3 、纠正，个随机错误，同时检测e ( e t ) 个随机错误，则要求t + e + l ； 4 、纠正t 个错误和p 个删除，则要求2 t + p + l 。 因此，构造尽可能大的九。以确保更好的纠错能力，这是任何时候设计信道 码字的通用规则。 8 第二章l d p c 码基本原理 2 2l d p c 码的基础知识 2 2 1l d p c 码的定义 l d p c 码是一种线性分组码，由它的校验矩阵来定义，设码长为，信息位 为k ，则校验位为m = n - k , 码率为r = k n ，校验码矩阵h 是一个m * n 的矩阵。 而l d p c 码又是一种特殊线性分组码，它的名字来源于其校验矩阵的稀疏性，即 其中只有少数元素为“l ”，其余为“0 ”。g a l l a g e r 最早给出了正则l d p c 码定义， 即其校验码矩阵h 满足： l 、h 的每行有p 个“1 ”； 2 、h 的每列有九个“1 ”； 3 、与码长和h 矩阵的行数相比，九和p 都很小。 矩阵h 的每列各自包含九个“1 ”，表示每个码元变量受到相同数目的校验约 束；每行也各自包含p 个“l ”，表示每个校验方程对相同数目的码元变量进行校 验约束。这样的校验矩阵h 对应的l d p c 码一般表述为( r ，免，p ) ，图2 1 给出了 一个( 2 0 ，3 ，4 ) 正则l d p c 码的校验矩阵。 图2 - 1 ( 2 0 ，3 ，4 ) l d p c 码校验矩阵 9 o 0 o 0 1 o 0 0 0 1 0 o o 0 1 0 o 0 0 l 0 0 0 1 0 0 0 0 l 0 0 0 o 1 o o o o 1 0 0 o 1 o o o o 1 o o o 0 l 0 0 0 o 1 o 0 o 1 0 0 0 0 1 0 0 o 0 1 o o o o 1 o o 0 1 0 0 o 0 1 0 0 0 0 1 0 0 0 o 1 0 0 0 0 0 0 0 o 1 o o 0 1 0 o o l o 0 o 1 0 o 0 1 0 0 0 o 0 0 o o 1 0 o 0 1 0 0 o l o 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 o o o 1 o 0 0 l 0 0 0 1 o 0 0 l o 0 0 0 o 0 0 0 l 0 0 0 l 0 0 o l 0 0 0 1 0 0 0 1 0 0 0 0 l 0 0 o 0 o 1 o 0 o 0 o l 0 o 0 0 o 1 0 0 0 o o 1 l o 0 o o o 1 0 0 0 o o 1 o 0 o 0 o 1 0 0 o o o l 1 0 0 0 0 o 1 o o 0 o o 1 o o 0 0 0 1 0 o o o 0 1 l o 0 0 o 0 l o 0 0 0 o 1 0 0 0 0 0 1 0 0 0 0 0 l 第二章l d p c 码基本原理 2 2 2l d p c 码的t a n n e r 图表示 设一个( ，kp ) 正则l d p c 码c 具有校验矩阵日= ( 红，) m ，则其相应的t a n n e r 图模型可以表示为一个二部图。图的上面有个节点，每个节点表示码字的信 息位，称为信息节点或变量节点 x ，j = l ，2 ，3 ，n ) ，对应于校验矩阵各列；而 校验约束则表示为一组校验节点 z ，i = l ，2 ，m ) ，对应于校验矩阵的各行。仅 当曩= 1 时，变量节点x ，与校验节点z ，之间有一条边相连，节点工，与五之间互称 邻接节点，其间的连接边称为两个节点的邻接边。 对于( ，kp ) 正则l d p c 码，每个变量节点与a 个校验节点相连，称该变量 节点的度为a ，每个校验节点与p 个变量节点相连，称该校验节点的度为p ，度 表示与节点相连的边的数目。 图2 2 给出了图2 1 所示的校验矩阵对应的t a n n e r 图结构。 而屯屯而9x 2 0 2 2 3 非正则l d p c 码 z 2z 3z 1 5 图2 - 2校验矩阵对应的t a n n e r 图 对于l d p c 码的每个变量节点来说，当它参与的校验式越多，即次数k 越大， 则它可以从更多的校验节点获取信息，也就可以更加准确的判断出它的正确值。 对于l d p c 码的每个校验节点来说，当它涉及的变量节点越少即次数越小，则 它可以更准确的估计相关变量节点的状态。这种情况对于正则l d p c 码来说是一 对不可克服的矛盾，于是l u b y ，m i t z e n m a c h e r l l 4 1 等人引入了非正则l d p c 的概 念。 1 0 第二章l d p c 码基本原理 j c l屯为毛毛氏 而墨x9 x l o z lz 2z 3z iz 5 图2 - 3 ( 1 0 ，5 ) 非规则码t a n n e r 图 对于非正则l d p c 码，相应的t a n n e r 图中各变量节点或校验节点的度并不 相同( 如图2 3 所示) ，通常用序列 九l ，沁，h i ) 和 p l ，p 2 ，p d r 来表示其中 边的度分布，其中乃表示与度为，的变量节点相连的边占总边数的比率，p ，表示 与度为f 的校验节点相连的边占总边数的比率，西和咖分别表示变量节点和校 验节点的最大度数。显然应有罗刎，五，= 1 ，罗咖，p = 1 ，即部分之和等于全部。 o j o 1 在非正则l d p c 码的编码二分图中，两个集合内部的节点次数不再保持相 同，即每个变量节点参与的校验式数目或每个校验式中含有的变量节点数目不再 保持均匀，而是有意设置部分突出的变量节点和校验节点。在译码过程中，那些 参与较多校验式的变量节点迅速得到它们的正确译码信息，这样它们就可以给相 邻的校验节点更加有效的概率信息，而这些校验节点又可以给与它们相邻的次数 少的变量节点更多的信息。整个译码的过程呈现出一种波状效应，次数越高的变 量节点首先获得正确信息，然后是次数较低的节点，然后依次往下，直到次数最 低的变量节点。正是这种波状效应，使得非正则l d p c 码获得比正则l d p c 更好 的译码性能。理论上的极限性能仅仅比香农限高0 0 0 4 5 d b 的非正则码次数分布 对已经找到。 虽然良好设计的非规则码的纠错性能优于规则码，但是规则码在硬件实现方 面较非规则码简单，且码长较短的非规则码码字距离过小的可能性较大。总之， 规则码和非规则码相比各有优势，因此，规则码在很多场合下还是得到应用。 2 2 4q 元l d p c 码 前面对l d p c 码的定义都是在二元域基础上的，如果定义中的域不限于二元 第二章l d p c 码基本原理 域就可以得到多元域g f ( q ) 上的l d p c 码。多元域上的l d p c 码具有较二进制 l d p c 码更好的性能，而且实践表明在越大的域上构造的l d p c 码，译码性能就 越好，比如在g f ( 1 6 ) 上构造的正则码性能己经和t u r b o 码相差无几。 多元域l d p c 码之所以拥有如此优异的性能，是因为它有比二元域l d p c 码更重的列重，同时还有和二元域l d p c 码相似的二分图结构。假设在域g f ( 2 ) 和域g f ( q ) ( q = 2 v ) 上构造的l d p c 码所对应的校验矩阵分别是日，和日。风中 的元素是0 或l ，而。是由元素0 ，l ，口1 构成，日。中的每个元素都是皿 中p 个元素的合成。如果设域g f ( q ) ( q = 2 v ) 上的一个值a 与一个1 p 的二进制 向量相关联，那么把这个向量代入以中，就可以得到亿的二进制表示。 m a c k e y 1 5 】已证明：对于二进制l d p c 码来说，如果它的校验矩阵h 的列重 量足够大，那么它可以任意地接近香农限，即大重量的列会有助于译码的快速纠 错，然而如果增加列重量会使得二分图中节点之间短圈的数目急剧增加从而使译 码算法的性能下降。而在g f ( q ) 域上构造的l d p c 码可以解决这个矛盾，所构造 的校验矩阵h ，可以增加与之对应的二进制校验矩阵只中列的平均重量，但它 的二分图结构并没有改变，不会造成节点之间短圈数目的增加，从而使得译码性 能得到显著的提高。这种多元域上的编码构造会增加译码复杂度，但是相对于译 码性能的提高来说这种增加是值得的。 2 3l d p c 码编码算法 l d p c 码所面临的一个主要问题是其较高的编码复杂度和编码时延，采用直 接的编码方法时编码复杂度与l d p c 码码长的二次方成正比，这在码长较长时是 难以接受的。幸运的是文献d 6 给出了一种新的编码算法，即e f f i c i e n t 编码算法， 可以有效的解决巨大的运算量和存储空间消耗的问题，实现了在线性时间内编 码，初步解决了l d p c 码应用所面临的一个主要问题。 2 3 。1 基于高斯消去的编码 对于一个给定的m * n 校验矩阵h ，编码后的码字x 应满足h x7 。= 0 7 。l d p c 码的直接编码方法就是利用高斯消去法，产生一个下三角矩阵，如图2 - 4 所示。 奖x 分成两部分萨和，p ) ，其中s 代表系统比特，p 代表校验比特，则系统编码可 以分为以下两个步骤： 1 ，将要传输的- m 个信息比特直接赋值给系统位s ； 2 ，对于第i ( i = l ，2 m ) 个校验比特p ，可通过式2 5 后向递推得到。 1 2 第二章l d p c 码基本原理 n mm ny 4、n， 融一。? ：j ?。 4 。 z i0 一、 。i5 0 叠 、 k j 器。j 一一二：、， 。 卅卜 n 图2 4下三角结构的校验矩阵 m ( 2 5 ) 将校验矩阵化成下三角结构后进行编码，复杂度计算包括两部分；一是校验 矩阵高斯消元运算复杂度为o ( n 3 ) ；二是编码复杂度为o ( n 2 ) 。实际上，稀疏校 验矩阵化成下三角结构后往往不满足稀疏特性，编码时需要r 1 2 r o r ) 2 次运算 ( 月是码率) 。如果直接构造出下三角形式的稀疏校验矩阵，则可实现线性编码， 但这样设计的码在性能上会有所损失，有时甚至会非常糟糕。 2 3 2l d p c 码有效编码算法 文献 1 6 】中证明给定校验矩阵h ，对于传输速率可达信道容量的l d p c 码， 线性编码是可能的，即使编码复杂度与码长平方成正比时，因为平方项的系数是 很小的常数因子，其编码复杂度仍是可以接受。 乃 m一 一 厶q h 一 + 一 矗， m 川 = 刃 第二章l d p c 码基本原理 m n m g m 叼 0 n 图2 - 5近似下三角校验矩阵 m g 将校验矩阵进行行列变换，变成如图2 - 5 所示的结构。由于在矩阵变换中 只有行列变换，因此变换后的校验矩阵仍是稀疏矩阵，设新生成的校验矩阵为式 2 - 6 h ：p 口丁l ( 2 - 6 ) = ii () lc 一ei - 一 a 、b 、c 、d 、e 、t 分别是( m - g ) 宰6 v - m ) ，( m - g ) 勺，g 木( n - m ) ，g * g ，g 木( m - g ) ， ( m - g ) 牛似舌) 维矩阵。h 中所有的子矩阵均是稀疏矩阵，并且t 是下三角矩阵。 矩阵h 左乘一矩阵得到式2 7 瞄i 牡瞄麓二赢矧 协7 ， 码字向量x 写成三部分，z = ( s ，p 。，p 2 ) ，s 定义为信息向量局，p 2 分别定义 为校验向量，s 长为m ，a 长为g ，仍长为m - g 。由h x 7 = 0 可得式2 - 8 和式 2 9 。 彳，+ 舰7 + 碾7 = 0 ( 2 - 8 ) ( 一j r l 1 a + c p7 + ( 一e 丁一1 b + d ) p l r = 0 ( 2 9 ) 设一e r 一1 b + d 可逆，令矽= 一e 丁一b + d ，则a7 = 1 ( - e t 1 a + c ) s 7 。求出 一1 ( 一e 丁_ 么+ c ) 后可得第一个校验向量p 。再根据式2 - 7 ，求出第二个校验向量 为p 2 r = - t 7 ( 加7 + 舰丁) 。为降低计算复杂度，在此并不求出妒一1 ( - e t - 1 彳+ c ) 然 后乘s 7 ，而是将求珐7 的计算分解成几步来进行，如表2 一l 所示。第1 、2 、4 步 1 4 第二章l d p c 码基本原理 是稀疏矩阵与向量相乘，复杂度为o ( n ) ，第5 步是向量加，复杂度也为o ( n ) ，第 3 步中由于丁- 1 a s 7 = y r a s r = r y 7 ，t 为下三角的稀疏矩阵，可以利用回归算 法求得y7 ，其复杂度仍为o ( n ) ，只有第6 步中1 是一个g g 的高密度矩阵，运 算复杂度为o ( 9 2 ) 。因此，计算a7 1 的总计算复杂度为o ( n + 9 2 ) 。同理计算仍7 的 复杂度如表2 2 所示，为o ( n ) 。 表2 - 1 计算a7 的步骤 么s 7 、 b p ： a 0 b p ： - t 1 a s 7 + 印1 7 】 d ( ”) d ( ”) d ( 珂) d ( ，? ) 稀疏矩阵和向量乘 稀疏矩阵和向量乘 向最加 一t - l a s 7 + 声p 1 7 】= y7 - a s r + 置既7 = t y r 不难发现，有效编码算法的复杂度是线性的。除了对上述编码复杂度的分析 之外，文献【1 6 】中还给出了将矩阵化成图2 - 2 的结构的四种算法，并且证明了线 性可编码的最优非规则l d p c 码的存在性。 2 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 码译码算法 l d p c 码的译码方法可以分为两大类：基于硬判决的译码和基于软判决的译 码。基于硬判决的译码运算量较小，比较实用。而软判决译码采用了后验概率信 息，并通过迭代运算，使得l d p c 码性能得以逼近香农限。近年来各种结合软判 决结果的硬判决算法在保持复杂度的情况下使译码性能进一步提高，从而推动了 l d p c 码的实用化。 3 1l d p c 码的译码思想 下面介绍l d p c 码通用的一类译码算法，即所谓的消息传递算法( m e s s a g e p a s s i n ga l g o r i t h m ) 。消息传递算法9 】是一种迭代译码算f k ( 1 t e r a t i v ea l g o r i t h m ) ， 它的名字来源于其运行机制，在该算法的每一次迭代译码过程中，关于各个节点 的置信信息需要在变量节点和校验节点之间传递。例如由变量节点向校验节点传 递的消息是基于变量节点对应的码元变量经过信道后的观察值和由邻接的校验 节点在上一次迭代过程中传递过来的消息联合计算的，其中需要特别注意的是由 某个变量节点v 向校验节点c 所传递消息的计算中不包含在上一次迭代中由校验 节点c 传递给变量节点v 的消息，对由校验节点向变量节点传递的消息也是同样 情况。 其中一类比较重要的消息传递算法称做置信传播算法( b e l i e fp r o p a g a t i o n a l g o r i t h m ) ，该算法在g a l l a g e r 的博士论文【2 】咩t 有具体的描述j 也经常在人工智 f l 皂( a r t i f i c i a li n t e l l i g e n c e ) 等领域内使用。在置信传播算法中，各个节点之间传递 的信息是概率域置信信息，比如由变量节点v 传递给校验节点c 的信息是v 取某 些特定值的概率信息，该信息的具体取值依赖于v 的观测值和其它所有与v 相连 的校验节点( 除c 以外) 在上一轮迭代中传递给v 的置信信息，同样由c 传递给v 的信息也是v 取某些特定值的概率信息，该信息的具体取值依赖于其它所有与c 相连的校验节点( 除v 以外) 在上一轮迭代中传递给c 的置信信息。 置信传播算法的迭代公式是在独立性假设( i n d e p e n d e n c ea s s u m p t i o n ) 下推导 得到的，这里仅考虑码元取自g f ( 2 ) 的情况。设某个二值随机变量x 取值为0 、1 的概率分别为( x = 0 ) 和e ( x = 1 ) ，为了使所传递的消息中能够同时包含x 的两 个取值概率信息，通常用两者的一个函数变量来表示该信息，如概率差 a ，= e ( x = 0 ) 一只 = 1 ) 、概率比l ( x ) = p a x = o ) e , ( x = 1 ) 或者对数似然比 1 6 第三章l d p c 码译码算法 l l r ( x ) = i n p , ( x = 0 ) e ( x = 1 ) 】，这些函数变量称做量度( m e t r i c ) 。可以证明，不 同量度下推导得到的迭代公式是等价的，这里仅给出对数似然比量度下的公式推 导【1 7 1 。 设x 为满足均匀分布的二值随机变量，即只 - m 0 ) = p a x = 1 ) = 1 2 ，y 为x 经过信道后的观测值，根据b a y e s 规则有： 儿尺( x iy ) 乩坐型塑：h a p ( x = o , y ) p ( y ) 一。p ( x = 1j ，) p ( x = l ，y ) 尸( y ) ：i n ! ! 兰! 兰三旦! ! ! 兰三1 2 ：i n 竺! 兰! 兰三竺2( 3 1 ) p ( y i x = 1 ) p ( x = 1 ) p ( y l x = 1 ) = l l r ( y x ) 根据独立性假设，若五，恐x e 为互相独立的二值随机变量，乃，儿儿是 五，屯x d 经过无记忆信道后的观测值，则有： l l r ( x 1 ，x , 2 x ey l ，y 2 儿) = ：。l l r ( x , i ) ( 3 2 ) 考虑两个二值随机变- 一- t 宣- x 。和x 2 ，y t 和儿为经过信道后的观测值，则： 儿r ( x 1 。x 2l y l 赐，= i n 筹粼 ：i n ! ! 兰! 三q ：兰三q ! 苎：丝! 竺垡三! ：垒三! ! 苎：丝2 尸( 五= 0 ，而= 1 i y l ，y 2 ) + p ( x j = 1 ，x 2 = 0 i y l ，y 2 ) ：i n ! ! 墨三竺! 筮! ! ! 兰三! l 丝! ! ! 苎三! ! 当2 璺兰三! ! 兰2 2 ( 3 3 ) p ( 五= 0