（通信与信息系统专业论文）基于有限几何ldpc编码的研究及其fpga实现.pdf

独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：专豁年宴l i 一 日期：塑! ：；：! 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生在校 攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国家有关部 门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 7 本人签名： 导师签名： 日期： 一 吣舟 p吖l 基于有限几何l d p c 编码的研究及其f p g a 实现 摘要 l d p c 码由g a l l a g e r 于1 9 6 2 年首次提出，只是限于当时的技术 发展水平这方面的研究在接下来的3 0 多年里沉寂了，直到上世纪九 十年代中期，m a c k a y ，n e a l 等人重新发现l d p c 码与t u r b o 码一样 也是一种能够逼近香农限的非常好码，过去几年l d p c 码有了很大发 展。 本文以欧氏几何空间、循环码、线性分组码为理论背景对l d p c 码做了研究，并设计了d v b s 2 标准中l d p c 编码在硬件f p g a 上的 实现方案。主要工作如下： 1 研究了l d p c 码奇偶校验矩阵的构造方法，基于置信度传播 的译码算法，一般编码算法和快速编码算法。重点研究了欧氏空间 l d p c 码和基于奇偶校验矩阵编码的算法。 2 设计了构造第一类二维循环( 2 ，0 ，s ) 阶e g l d p c 码的的具体实 现步骤；提出一种直接从奇偶校验矩阵经过简单计算即可获得循环 e g l d p c 码的生成多项式的方法。 3 设计了构造第一类多维准循环( 朋，0 ，j ) 阶e g l d p c 码的的具体 实现方法，提出基于准循环矩阵实现q ( q 2 ) 进制l d p c 编码的思路， 并给出了硬件编码电路。 4 针对l d p c 码通用编码算法的复杂度与码长的平方成正比的 问题重点研究了l d p c 码的快速编码方法。根据d v b s 2 标准中给出 的l d p c 码的奇偶校验矩阵为非规则校验矩阵，此矩阵可以看成由一 个稀疏矩阵和一个双对角线矩阵组成，符合利用校验矩阵直接进行编 码的条件，并且编码复杂度为线性。给出了在f p g a 上实现的编码器 的方案，针对设计中的乘法运算提出了累加的改进方法，节约了存储 空间，利用硬件描述语言完成了编码器设计。 关键词低密度校验码有限几何置信传播算法第二代卫星数字视 频广播标准 i l 一 f ，j r e s e a r c ho fe g l d p ca n dd 衄l e n n t a t i o no n f p g a a b s t r a c t t h el o wd e n s i t yp a r i t y - c h e c k ( l d p c ) c o d ew a sf i r s tp r o p o s e db y g a l l a g e ri n19 6 2 o fw h i c ht h er e s e a r c hh a db e e nh a l t e dd u e t oc o n s t r a i n t o ft h et e c h n o l o g yd e v e l o p m e n ti nt h ef o l l o w i n gm o r et h a n3 0y e a r s i n t h e19 9 0 s m a c k a ya n dn e a lf o u n dt h a tl d p ci so n ek i n do fg o o dc o d e s a sw e l la st u r b oa n dn e a rt os h a n n o nl i m i t b a s e do nt h i sd i s c o v e r y , t h e r e s e a r c ha b o u tl d p ch a sg r o w na n dg o tab i gd e v e l o p m e n ti nt h ep a s t s e v e r a ly e a r s b a s e du p o ne u c l i d e a ng e o m e t r y c y c l i cc o d e sa n dl i n e a rb l o c k c o d e ss c h e m e ，t h i sd i s s e r t a t i o ni s t r y i n gt or e s e a r c ho nl d p ca n d ，p r e s e n t i n g ap r o p o s a lf o rh o wt o i m p l e m e n tt h el d p ce n c o d e r o n h a r d w a r ea c c o r d i n gt od v b - s 2s t a n d a r d t h ed e t a i l sa r ea sb e l o w ： 1 t h es t r u c t u r em e t h o do fl d p cp a r i t yc h e c km a t r i xh a sb e e n s t u d i e di nd e t a i l ，a sw e l la sb e l i e f - p r o p a g a t i o nd e c o d i n ga l g o r i t h m s ， g e n e r a le n c o d i n ga n df a s te n c o d i n ga l g o r i t h m s e u c l i d e a ng e o m e t r y l d p ca n de n c o d i n ga l g o r i t h m sb a s e do nt h ep a r i t yc h e c km a t r i xa r e m a i n l yr e s e a r c h e d 2 an e wm e t h o df o rc o n s t r u c t i n gt h ef i r s tc l a s s2 d i m e n t i o n ( 2 ，0 ，j ) o r d e re g - l d p ci sp r e s e n t e d ；a n dan e wm e t h o df o rg e r i n gg e n e r a t e d p o l y n o m i a lf r o mp a r i t yc h e c km a t r i xo fc y c l i ce g - l d p cb ys i m p l e c a l c u l a t i o ni sp r o p o s e d 3 am e t h o df o rc o n s t r u c t i n gt h ef i r s tc l a s sm u l t i d i m e n s i o n ( m ，0 ，s ) o r d e rc y c l i ce g l d p ci sp r e s e n t e d ；a n da ni m p l e m e n t a t i o no fn o nb i n a r y l d p ce n c o d i n gf r o mq c u ) p ci sp r o p o s e d ，w i t ht h eh a r d w a r ee n c o d e r c i r c u i ti n t r o d u c e d 4 o nt h eq u e s t i o nt h a tt h ec o m p l e x i t ya n dt h eq u a d r a t i co fc o d e l e n g t ha r ep r o p o r t i o n a lb yg e n e r a la l g o r i t h m s ，t h ef a s te n c o d i n gm e t h o d o fl d p ci s m a i n l ys t u d i e d a ne n c o d e ri sp r e s e n t e do nf p g aw i t h h a r d w a r el a n g u a g ea c c o r d i n gt od v b s 2s t a n d a r d t h el d p cp a r i t y c h e c km a t r i xi nd v b s 2s t a n d a r di s i r r e g u l a ra n di sc o m p o s e do fo n e s p a r s em a t r i xa n do n ed o u b l ed i a g o n a lm a t r i xa n dh a sc o n d i t i o nt ob e e n c o d e dd i r e c t l yi nl i n e a rt i m e b yc o r r e c t i v em e t h o do fa c c u m u l a t i o nt o r e p l a c em u l t i p l yo p e r a t i o n ，t h ep r o p o s a lg i v e sam e t h o dt os a v em e m o r y s p a c e k e yw o r d s ：l o w d e n s i t yp a r i t y c h e c kc o d e sf i n i t e g e o m e t r y b e l i e f - p r o p a g a t i o na l g o r i t h md v b s 2 i i i 1 。 一 r 。j 北京邮电大学硕十论文 目录 第一章绪论1 1 1 数字通信与信道编码l 1 1 1 数字通信1 1 1 2 信道编码理论及其发展历程1 1 2l d p c 码的发展历史和现状3 1 2 1l d p c 码的发展历史3 1 2 2l d p c 码的发展现状4 1 2 3l d p c 码的应用4 1 3 本文主要研究工作与内容安排5 第二章l d p c 码的结构7 2 1l d p c 码的表示方法。7 2 1 1l d p c 码的校验矩阵表示7 2 1 2l d p c 码的t a n n e r 图表示9 2 2 正则l d p c 码和非正则l d p c 码9 2 3 本章小结1 0 第三章l d p c 校验矩阵的构造二12 3 1 随机构造法1 2 3 1 1g a l l a g e r 的构造方法1 2 3 1 2m a c k a y 构造法1 3 3 1 3d a v e y 超轻构造法1 4 3 1 4 比特填充和扩展的比特填充构造法1 5 3 2 代数几何构造法1 6 3 2 1 有限几何构造法1 6 3 2 2 基于组合设计的均衡不完全区组构造法2 2 3 3 本章小结2 3 第四章l d p c 码的译码2 4 4 1 一步大数逻辑译码算法2 4 4 2 基于置信度传播的和积译码算法2 6 4 2 1 概率b p 算法2 6 4 2 2 对数似然b p 算法2 8 4 2 3a w a n 信道下的译码算法3 0 i v 北京邮电大学硕i ：论文 4 3 软判决和硬判决结合算法31 4 4 本章小结31 第五章l d p c 码的编码3 2 5 1 普通编码方法3 2 5 2 有效编码方法3 2 5 2 1 下三角矩阵编码3 3 5 2 2 近似下三角矩阵编码3 4 5 2 3d v b s 2 中重复累积编码方法3 5 5 3 本章小结3 6 第六章基于有限几何空间的e g l d p c 码3 7 6 1 循环e g l d p c 码3 7 6 1 1e g l d p c 码的结构特征分析3 7 6 1 2 基于欧式几何校验矩阵的循环l d p c 码的生成多项式的新方法3 9 6 2 准循环e g - l d p c 码4 2 6 3d v b s 2 中的编码分析及其硬件实现4 6 6 3 1d v b s 2 标准中的编码方案4 6 6 3 2 编码器硬件实现方案4 9 6 4 本章小结5 2 第七章结束语5 3 至i 【谢5 9 参考文献5 5 攻读学位期间发表的学术论文目录5 9 v 北京邮电大学硕士论文 1 1 数字通信与信道编码 第一章绪论 1 1 1 数字通信 通信系统的目的在于将信息由信源高效、可靠、有时还需安全地传送到信宿。 而有扰通信信道中的噪声会不可避免地对传输信息产生不同程度的干扰，从而可 能降低通信可靠性。所以通信系统设计的关键问题就是在存在随机噪声的信道中 如何克服干扰，保证不降低信息传输的效率的前提下减小信息传输的差错。一般 地，通信系统的可靠性通常用误码率描述，其有效性则用信息传输速率r 比特 信道符号来衡量。早期的人们普遍认为：通信系统的可靠性与有效性是一对不可 调和的矛盾，只有把传输速率降低至零【l 】，才能在有扰通信信道上实现任意小错 误概率的信息传输。而事实上并非如此，s h a n n o n 证明【2 】，只要信息传输速率低 于信道容量，通过对信息适当进行编码，可以在不牺牲信息传输或存储速率的情 况下，将有噪信道或存储介质引入的差错减到任意低的程度。通信系统要完成的 任务就是把数据从信源传到信宿，一个典型的传输系统可以用图1 1 所示的框图 来表示。 图1 - 1 数据传输系统模型 1 1 2 信道编码理论及其发展历程 图1 1 中的信道编译码部分是以某种规则引入适量冗余比特，以克服信息在 北京邮电人学硕： ：论文 传输过程中受到的噪声和干扰影响。根据s h a n n o n 提出的信道编码定理【2 】，对任 意一个平稳离散无记忆有噪声信源，都有一个固定的量，称之为信道容量，记做 c 。只要信息的传输速率低于信道容量，就必然存在一种编码方法，使得信息出 现差错的概率随码长的增加趋于任意小；反之，当信息传输速率超过信道容量时， 则不存在这样的编码方法。这就是著名的信道编码定理，它给出了特定信道上信 息传输速率的上界。 定理1 - 1 ( 信道编码定理) ：任意离散输入无记忆平稳信道存在信道容量， 对预期的任一数据速率和任一错误概率，有可能设计一对编译码器，以保证该信 道中速率为r 的数据传输具有小于c 的译码错误概率。 信道编码定理指出，在有扰信道中，只要信息传输速率小于信道容量，就有 可能实现任意可靠的信息传输。这个存在性定理提醒我们可以实现以接近信道容 量的传输速率进行通信。但遗憾的是该定理采用的是非构造性的证明方法，其中 并没有给出逼近信道容量的码的具体编译码方法。 s h a n n o n 在信道编码定理的证明中引用了三个基本条件，即： ( 1 ) 采用随机的编码方式； ( 2 ) 码字长度趋近于无穷大； ( 3 ) 译码采用最佳的最大似然译码。 自信道编码定理提出以来，众多研究学者都对如何构造一个逼近信道容量限 的实用好码做了研究。下面对其进行简要概述。 纠错码【3 西】【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 f 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 码。事实上，r s 码可以看作 是b c h 码的特例，b c h 码又可以看作是某个r s 码的予域子码。其后发现的分 组码主要有1 9 7 0 年的g o p p a 码和1 9 8 2 年发现的代数几何码。 卷积码最早由e l i a s 提出，卷积码具有动态格图结构，可用有限状态机来描 述其状态。由于缺乏有效的理论研究工具，对卷积码的有效研究成果不是很多， 目前性能好的卷积码的构造方法主要借助于计算机搜索来获得。卷积码的译码一 般采用概率译码，由于译码算法简单、实用和易于实现，卷积码被广泛应用于实 际中。 1 9 6 6 年，f o m e y 将分组码和卷积码结合起来，提出了级联码( c o n c a t e n a t e d 北京邮电人学硕士论文 c o d e s ) 的概念。 1 9 9 3 年t u r b o 剐7 】【9 】的提出被看作是信道编码理论研究的重要里程碑。 b e r r o u 等人将卷积码和随机交织器相结合，同时采用软输出迭代译码来逼近最大 似然译码，取得了超乎寻常的优异性能，直接逼近s h a n n o n 提出的信道容量限。 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 年提出的低密 度奇偶校验码【1 1 】【1 2 】( 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 信道容量限 【l 弘1 6 j 。而且在中长码长时l d p c 码具有超过t u r b o 码的性能，并且具有译码复杂 度更低，能够并行译码及译码错误可检测等特点，成为目前信道编码理论的研究 热点。研究表明，t u r b o 码只是l d p c 码的一个特例【协1 9 1 ，两者都是基于图构造 的低密度码，译码算法具有等价性，从而使两者在基于图模型的编译码研究中得 到了统一。 1 2l d p c 码的发展历史和现状 1 2 1l d p c 码的发展历史 1 9 6 2 年，g a l l a g e r 在他的博士论文中提出了二元正则l d p c 码，也被称做 g a l l a g e r 码【i 。g a l l a g e r 证明了这类码具有很好的汉明距离特性，是满足g v 限 的渐进好码，在计算树上进行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 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 码 3 北京邮电人学硕十论文 【1 6 】【2 1 1 1 2 3 1 ，这一结果引起了信道编码界的极大关注。 在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 铊7 1 。在对扩展码的研究中，他们证明了一个随 机构造的t a n n e r 图以很大的概率为好码的扩展图，而由好的扩展图构造的线性 纠错码是渐进好码，从而证明了采用随机t a n n e r 图构造的l d p c 码以很大概率 是渐进好码。l u h y 等人将采用非正则t a n n e r 图构造的扩展图用于删除信道，称 之为t o r n a d o 码【2 睨9 1 。由于采用了非j 下则的t a n n e r 图，t o r n a d o 码具有更大的扩 展性和更好的收敛性，纠删性能更强。此后，采用优化度序列设计的非正则t a n n e r 图被用于构造l d p c 码，称为非j 下则l d p c 码，与j 下则l d p c 码相比，非正则 l d p c 码的性能得到显著的提高【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 】【2 2 】【3 5 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 译码算法。 1 2 2l d p c 码的发展现状 近两年，r i c h a r d s o n 等人应用密度进化理论来测度l d p c 码的性能【3 2 】【3 6 1 。 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 码性 能的模型由多参数动态系统的密度进化理论模型简化为单一参数动态系统的高 斯逼近模型【3 0 】【3 3 】。 1 2 3l d p c 码的应用 l d p c 码理论的深入发展推动了其实用化进程。l o e l i g e r 等学者认识到和积 算法非常适合模拟v l s i 实现【3 7 】。l d p c 码的图模型表示可以用于电路实现，而 且和积算法的运算也非常适合用晶体管的非线性物理特性实现。用模拟v l s i 实 4 ( 北京邮电大学硕士论文 现和积算法比用数字v l s i 在速度、功率方面大概能提高1 0 0 倍，主要的瓶颈在 于同通用数字电路的接口上。 在c c s d s 【3 副标准中，近地轨道通信与深空通信都采用了l d p c 码的方案。 深空通信中采用了准循环分块形式的并行结构，信息位码长分别为1 0 2 4 ，4 0 9 6 ， 1 6 3 8 4 ，码率为1 2 ，2 3 ，4 5 三种，通过对l d p c 码校验矩阵的分块和其特殊的 并行结构完美地解决了l d p c 长码优异的性能和高的实现复杂度之间的矛盾，为 人类探索未知的宇宙提供了一种有效的通信解决方案。 为达到数字高清标准，第二代卫星数字电视广播( d v b s 2 ) 中采用了b c h 码和l d p c 码级联的方案【3 9 1 。其中，l d p c 码长度分别为6 4 8 0 0 和1 6 2 0 0 ，最低 码率为1 4 ，最高码率为9 1 0 。 在无线城域网的i e e e 8 0 2 1 6 e 删草案中，l d p c 码与t u r b o 码一起作为编码 调制的备选方案。草案中，采用矩阵分块技术( 码长从2 0 3 4 到5 7 6 ，码率为1 2 ， 2 3 ，3 4 ) ，将大规模的矩阵乘运算分解为小规模矩阵乘的并行结构，有效的解 决了l d p c 码编码复杂度高的问题。 c c s d c 、d v b s 2 和i e e e 8 0 2 1 6 e 标志着l d p c 码实用化进程的开始。随着 l d p c 码理论的同趋完善，实现方式的不断改善和v l s i 技术的进步，l d p c 码 将应用到更多的通信系统中。 1 3 本文主要研究工作与内容安排 本文对低密度校验码( l d p c ) 的理论、设计和应用进行了研究，主要内容 包括码的定义、结构、码校验矩阵的构造、译码、编码和实现等方面。主要工作 和内容安排如下： 第一章介绍了数字通信信道模型，信道编码理论发展历程，l d p c 码发展历 史，现状和应用。并概括了本文的主要工作和章节安排。 第二章介绍了低密奇偶校验码的结构，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 码的编码理论，分别介绍了普通编码方法和快速编码方 法。介绍了直接通过校验矩阵得到生成矩阵的编码方法，基于全下三角矩阵编码 算法，近似下三角矩阵编码算法，重复累积编码算法，并比较了这几种算法的复 5 北京邮电大学硕士论文 杂度。 第六章介绍了第一类循环有限几何e g l d p c 和第二类准循环e g - l d p c 码。 分析了具有循环特性的校验矩阵节点度的特征；提出一种计算二维第一类 e g l d p c 码的生成多项式的方法；提出构造准循环l d p c 码校验矩阵的具体方 法和基于准循环l d p c 码校验矩阵进行多进制编码的方法；在硬件上设计实现 d v b s 2 标准中采用的l d p c 编码，提出一种节省存储空间的方案，并在 q u a r t u s 6 0 中仿真实现。 第七章对全文工作进行总结，提出下一步的研究内容。 6 北京邮电大学硕上论文 第二章l d p c 码的结构 2 1l d p c 码的表示方法 长度为n 的线性分组码c 由生成矩阵g 或奇偶校验矩阵h 唯一确定。如 果是由奇偶校验矩阵确定的，码c 就是日的零空间。l d p c 码就是通过奇偶校 验矩阵定义的。 定义2 1l d p c 码定义为具有如下结构特性的奇偶校验矩阵日的零空间：( 1 ) 每一行含有p 个l ；( 2 ) 每一列含有厂个1 ；( 3 ) 任何两列之间位置相同的1 的个数 ( 以五表示) 不大于l ，即1 = 0 或者1 = 1 ；( 4 ) 与码长和h 的行数相比，p 和y 都较 小。 由于p 和y 都小于码长和日中的行数，因此日中1 的密度很小。因此日称 为低密度奇偶校验矩阵，由日所确定的码称为低密度奇偶校验码，即l d p c 码。 定义l d p c 码的密度，为日中l 的总数与日中的元素总数的比值。显然， ，= p n = y ，其中，是矩阵日的行数。日是一个稀疏矩阵。定义2 - 1 给出的l d p c 码被称为( 厂，p ) 规贝i jl d p c 码。如果奇偶校验矩阵的各行或各 列具有不同的重量，则l d p c 码被称为非规则l d p c 码【4 。4 2 1 。 2 1 1l d p c 码的校验矩阵表示 图2 1 给出了校验矩阵，该矩阵每一行和每一列分别含有4 个1 。且没有 哪两列( 或两行) 相同位置1 的个数大于l 。该矩阵的密度是0 2 6 7 。因此，它 是一个低密度矩阵。该矩阵的零空间给出了一种( 1 5 ，7 ) l d p c 码，最小距离为 5 。在后面的章节中，我们还要进一步分析该矩阵。 令k 为大于l 的正整数，对于给定的p 和y ，g a l l a g e r 给出了由奇偶校验矩阵确定 的一类线性码的如下构造方法【3 9 4 0 1 。构造由y 个后印的子矩阵 日。，日：，日7 组成的k rx 助矩阵日。子矩阵的每行有p 个l ，每列只有一 个1 。对于1 f k ，h 。的第所于的p 个1 都分布在o 一1 ) p + l 到护中。其他子矩 阵只是日的列置换。 7 北京邮电大学硕十论文 那么 h = 0 o o 0 0 o11o1o0 0 o o0 oo ol1olo lo oo0o o 0l10l o1o ooo o o o1l0 0olo0oo0o o11 o o01oo 0o0o01 lo0o1 oo000oo o1o0 o10ooo0 0 lo1o o o1o oooo 11o1o o 01o 0 0 0 01101o 0 olo 00 oo ll01ooo10 o 0 00110lo0 0lo o 0oo1lo10 0 01 0 oo0 01lo100 0 图2 - 1 一种0 5 ，7 ) l d p c 码的奇偶校验矩阵 h = 纠 这样构造的矩阵满足定义2 1 给出的前两个条件，日是否具备定义中定义 的第三条性质( 即日的任意两列对应元素同时为l 的个数至多为1 ) ，取决于 对子矩阵日。中7 1 个列的置换的选择。但是g a l l a g e r 没有给出这种构造方法 的子矩阵日。的置换方法，以构成其他子矩阵日：，h ，h y ，使得由完整的 日生成的l d p c 码具有最小的距离和定义2 1 要求的结构特性。因此，要通过 g a l l a g e r 提出的方法构造好的l d p c 码需要用计算机搜索得到。 例如，令k = 5 ，p - - 4 ，y = 3 。图2 2 所示为由g a l l a g e r 方法构造的1 5 2 0 的 矩阵日，日的零空间给出一种( 2 0 ，7 ) 的l d p c 码，最小距离为6 。 8 1 o 0 0 1 o l l o o 0 0 o o o 0 0 0 l o 1 1 0 o o 0 o o o 1 北京邮电人学硕十论文 h = 11o 0 0oo0o 0 00o 0 o 011l 1 o0o0 0 o 0 o 0 0o 0oo 1111o oo o 0 0 0 0ooo 00ol111 0 0 o o o o o 0 0 o o o 0o 0 0 1o o o1 oo o looo o0 o1o o 0l0oo o oo 1oo o10 0 o 0 0 oloo 01o o o 0 o 01o 0010 0ooo o o10 ol0o 01 o 0 01o o o o o100 oo oo0 o 1o o 01 o0 0 0 l 10 0 ool0 o o 0lo0o olo oo0lo0 o o1oo 0 o10oo 010 o o o1o 图2 - 2g a l l a g e rl d p c 码的奇偶校验矩阵。 2 1 2l d p c 码的t a n n e r 图表示 设l d p c 码具有校验矩阵h = ( 乃) 。，则其相应的t a n n e r 图模型可以 表示为一个二分图【4 l 】。其中码字向量x = ( x ”x ：，x 。) 表示为一组变量节 点 工，j = l ，2 ，刀 ，分别对应于校验矩阵的各列，而校验约束则表示为一组 校验节点 c ，i = 1 ，2 ，m ) ，对应于校验矩阵的各行。仅当h = l 时，变量 节点x ，与校验节点c ，之问有一条边相连，节点j ，与c ，之间互称邻接节点，其 间的连接边称为两个节点的邻接边。对于正则l d p c 码，每个变量节点与y 个校 验节点相连，称该变量节点的度为厂；每个校验节点与p 个变量节点相连，称该 校验节点的度为p ，度表示与节点相连的边的数目。图2 3 给出了图2 - 2 所示的 校验矩阵对应的t a n n e r 图结构。 2 2 正则l d p c 码和非正则l d p c 码 如果校验矩阵的各行中非零元素的个数是相同的，各列中非零元素的个数也 是相同的，该码为规则码。此时，t a n n e r 图中所有变量节点具有相同的度d ， 所有校验节点具有相同的度d 。此时，t a n n e r 图的度数分布为 9 0 o o 0 1 0 0 0 o l o 0 o 0 1 0 0 0 o 1 0 o o l 0 0 0 1 0 o 0 0 0 0 1 0 0 l 0 0 1 0 0 o 0 0 o o o l 0 l 0 0 0 0 0 o l 0 l o 0 0 0 o l o 0 o o 1 o o o l o o 0 0 1 o 0 o 0 1 0 o o o 北京邮电人学硕：i ：论文 图2 - 3 ( 2 0 ，7 ) 的l d p c 码的t a n n e r 图表示 r ( x ) = x d r 1式( 2 1 ) 翮= 一 式( 2 2 ) 而非规则l d p c 码由具有不同行重和不同列重的奇偶校验矩阵日所确定。 从t a n n e r 图上来看，变量节点和校验节点都具有不同的度，观察一种非规则 l d p c 码的t a n n e r 图q 和校验矩阵日。q 的变量节点对应日中的列，q 的 校验节点则对应日中的行。定义与q 中一个节点相连接的边的数量为该点的 度，那么，q 中一个变量节点的度等于其对应的日中列的重量，而q 中一个 校验节点的度等于其对应的日中行的重量。令 正 y ( x ) = 乃x 卜1 式( 2 3 ) f = l 式( 2 - 3 ) 表示q 中变量节点的度分布，其中厂，代表q 中度为f 的变量节 点所占的比例，d 。表示变量节点的度的最大值。令 d p ( x ) = 岛x 卜1 式( 2 4 ) i = 1 式( 2 - 4 ) 表示q 中校验节点的度分布，其中p ，代表q 中度为i 的校验节 点所占的比例，d ，表示校验节点的度的最大值。 f , 纽i e n t 4 3 1 ，长随机非规则码的性能可任意逼近香农限。非规则l d p c 码 通常由其泰纳图来设计和构造。 2 3 本章小结 本章介绍了低密奇偶校验码的结构，l d p c 码的校验矩阵表示和t a n n e r 图 表示方法，介绍了规则和非规则l d p c 码及两者性能比较。l d p c 码称为好码的 1 0 - _ _ _ _ _ - _ _ _ _ _ _ _ 。 北京邮电大学硕七论文 原因和其结构特性是分不开的，稀疏的奇偶校验矩阵使得编码具有随机性，奇偶 校验矩阵行列数目较大又使得该码具有长码特性。这样都符合s h a n n o n 编码定理 提出的前两个条件。 北京邮电人学硕i ：论文 3 1 随机构造法 第三章l d p c 校验矩阵的构造 3 1 1g a l l a g e r 的构造方法 g a l l a g e r 构造法如前面2 1 1 节已经叙述过，在这里不再说明。由于g a l l a g e r 并没有给出具体的构造方法，所以一般都是通过计算机搜索方法得到。根据欧式 几何空间可以构造出一种g a l l a g e r 构造矩阵【4 3 1 ，这种方法以平行线簇为基础。考 虑在g f ( 25 ) 上的m 维欧氏几何e g ( m ，25 ) ，e g ( m ，25 ) 中的直线可以划 分为( 2 ”_ 1 ) ( 25 1 ) 个平行线簇，每个平行线簇包含2 - 1 条彼此平行的直 线。在每个平行线簇中，平行线包含了e g ( m ，25 ) 中所有2 琊个点，且每个点 在且仅在一条这些平行线中的一条上。用p l ，p 2 ，兄表示这 ( 2 脚- 1 ) ( 25 1 ) 个平行线簇，其中k = ( 2 椰_ 1 ) “25 一1 ) 。 对于 0 i ( 2 船- 1 ) ( 25 1 ) ，构造一个2 一1 。2 ”的矩阵日；，其列对应于 e g ( m ，25 ) 中所有2 船个点，行对应于平行线簇中的只中的直线的关联向量。 称该矩阵为平行线簇的关联矩阵。日，的行重为25 ，由于平行线簇中直线互不 相交，日，中每- - y o 的列重为1 。日，中的列数等于其行数的25 倍。所以，矩阵 圩，满足g a l l a g e r 形式。对于0 7 ( 2 脚_ 1 ) “25 一1 ) ，我们构造如下矩阵： h 略j g = 日1 日2 ： h