（通信与信息系统专业论文）低密度校验码应用研究.pdf

摘要 低密度校验码是一种能逼近香农容量限的渐进好码，长码时其性能甚至超过 了t u r b o 码，其译码采用了具有线性复杂度的置信传播算法，复杂度低于t u r b o 码，并且几乎所有错误可检。由于低密度校验码的诸多优点，它在信息可靠传输 中的良好应用前景已经引起世界各国学术界和i t 业界的高度重视，成为当今信道 编码领域最受瞩目的研究热点之一，低密度校验码的应用也已经被提到日程上来， 被列为。4 g 关键技术。 作者认真学习了l d p c 码的基本原理，参与了重庆金美公司方案讨论，基于 l d p c 码的特征，提出一种改进型的l d p c 码与卷积码级联方案。此外，对于扩展 密度校验码作了一点探讨。 本论文主要完成的工作包括以下几个方面： 1 基于t a n n e r 图模型详细介绍了l d p c 码的表示和构造以及l d p c 码的硬 判决译i - 5 ( l l 特翻转算法) 和软判决迭代译码( 和积算法) 。 2 介绍了对l d p c 码性能影响的几个因素，特别关注了构造大围长的几种方 法。 3 研究了l d p c 码的级联方式，提出一种改进型的l d p c 码与卷积码级联方 案，该方案具有：编译码复杂度低，可并行译码，时延小、易于硬件实现， 纠错性能突出的特点。 4 对于g l d 码，介绍了构造方法和编译码的基本原理，性能仿真表明了其 良好的纠错性能。 许多优秀的l d p c 码级联方案已被提出，在具体方案中，应选择适当构造的 l d p c 码。l d p c 码的实用化还要有相当长的一段路，虽然长码时l d p c 码的性能 可以超越t u r b o 码，但是短码却比t u r b o 码差得很多，g l d 码在短码时的性能介 于l d p c 码和t u r b o 码之间，且g l d 码可并行译码，有利于集成电路的设计。 关键词：l d p c 码，二部图，置信传播算法，级联，g l d 码 a b s t r a c t 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 s a r 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 yb e l i e fp r o p a g a t i o na l g o r i t b a n ，l d p c c o d e sa r ea b l et og 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 i t ha l m o s ta l l e r r o r s d e t e c t a b l e f o rl o n gc o d el e n g t h s ，l d p cc o d e sc a ne v e no u t p e r f o r mt u r b oc o d e s d u e t ot h ea d v a n t a g e so fl d p cc o d e s ，t h e i ra p p l i c a t i o n si nr e l i a b l ec o m m u n i c a t i o n sh a v e r e c e i v e dg r e a ti n t e r e s t sa n dh a v eb e c o m eo n eo ft h em o s ta t t r a c t i v ef i e l d si nc h a n n e l c o d i n gc o m m u n i t y n o w , t h ea p p l i c a t i o no f l d p cc o d e sh a sb e e np u t0 1 1t h ea g e n d a l d p cc o d e sa r er e g a r d e da sa k e yt e c h n i q u e i nt h e4 g t h i st h e s i si n v e s t i g a t e ss o m ea s p e c t so fl d p cc o d e sw i t he l i l p h a s i so nm e s s a g e p a s s i n ga l g o r i t h m sa n dg i r t h s o fl d p cc o d e s a n o t h e rp a r to ft h ep a p e rt o u c h e so n g l dc o d e s t h em a i nc o n t e n t sa n dr e s u l t sa r ea sf o l l o w s 1 b a s e do nt a n n e rg r a p h ，t h er 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 s a r e i n t r o d u c e da n dt w o d e c o d i n ga l g o r i t h m s f o rl d p c c 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 ta l g o r i t h ma r ed i s c u s s e d 2 s e v e r a lf a c t o r si n f l u e n c i n gl d p cc o d e sa r et a l k e d a b o u t ，e m p h a s i s o n m e t h o d sf o rl a r g eg i r t hc o n s t r u c t i o n 3 t h ee f f i c i e n t e n c o d i n gp r o b l e mo fl d p cc o d e s i sm e n t i o n e da n da n i m p r o v e ds c h e m ea b o u tc o n c a t e n a t e dl d p ca n dc o n v o l u t i o n a lc o d e si s p r o p o s e d s e v e r a lc o d e sc a l lb ee n c o d e da n dd e c o d e da tt h es a m et i m ei n t h es c h e m e t h er e a l i z a t i o no ft h i ss c h e m eh a sl o wc o m p l e x i t ya n ds h o r t d e l a y t h es c h e m ea l s oh a se x c e l l e n tp e r f o r m a n c e 4 t h e t h e o r ya b o u tg l d c o d e si si n t r o d u c e d t h er e s u l t so fs i m u l a t i o n ss h o w t h ep e r f o n n a n c eo ft h e s ec o d e si so u t s t a n d i n g s e v e r a lg o o dc o n c a t e n a t e ds c h e m e sa b o u tl d p cc o d e sh a v e b e e n p u tf o r w a r d ，b u t i nr e a l i z a t i o n ，s e l e c t i n gp r o p e rl d p cc o d e sm u s tb es e r i o u s l yc o n s i d e r e da l t h o u g h l 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 rs h o r tl d p cc o d e s p e r f o r m a n c eo fg l dc o d e si sb e t w e e nt h e mi ns h o r tc o d el e n g t h s g l dd e c o d e rh a sa r e g u l a ra n dp a r a l l e ls t r u c t u r ew h i c h m a k e si tv e r ys u i t a b l ef o rp r a c t i c a li n t e g r a t e dc i r c u i t ( i c li m p l e m e n t a t i o n s k e y w o r d s ：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 s ，b i - p a r t i t eg r a p h ，m e s s a g e p a s s i n ga l g o r i t h m s ，c o n c a t e n a t i o n ，g e n e r a l i z e dl o w d e n s i t yp a r i t y c h e c k ( o l d ) c o d e s 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示了谢意。 b 本人签名： 盈虫殷 同期趔 丝：! 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名仍为西安电子科技大学。学校有 权保留送交论文的复印件，允许查阅和借阅论文；学校可以公和论文的全部或部 分内容，可以允许采用影印、缩印或其它复制手段保存论文。 本人签名：缢垒丛日期垒型：! ! ! k ： 导师签名： 彩卜 f l e a 趔生：f 乏：鲁一 第一章绪论 第一章绪论 本章中首先介绍数字通信系统的组成和几种常见信道的模型。简单回顾50 多 年来信道纠错编码技术的进步和发展，以及低密度校验码( l d p c ) 的提出、发展 的历程及研究现状，最后总结作者的主要i - 作，给出了全文的安排。 1 1 数字通信系统的组成及信道模型 1 1 1 数字通信系统的组成 通信的目的是要把对方不知道的信息及时、可靠、有时还需秘密安全的传给 对方。因此，一个通信系统传输信息必须可靠且快速，而实际系统中可靠与快速 往往是一对矛盾，可靠性用误比特率( b e r ) 衡量，有效性以信息传输速率r 来 度量。早期的人们普遍认为【l 】：通信系统的可靠性与有效性是一对不可调和的矛盾， 一方的改善总是以牺牲另一方为代价，要保证信息可靠的传输，只有两个自由度 可选择：一是提高系统的信噪比，二是选用不同的调制方式。当系统的功率受限 时，在有扰信道上实现以任意小错误概率的信息传输、唯一途径就是把信息传输 速率降低至零。1 9 4 8 年香农( s h a n n o n ) 发表了关于信息和编码理论的奠基性的论 文“通信的数学理论”，为通信的可靠传输提供了理论基础【2 1 。在这篇论文中，他 首次阐明了在有扰信道上实现可靠通信的方法，指出实现有效可靠地传输信息的 途径就是信道编码。 图1 - 1 显示了一个数字通信系统的功能框图和基本组成部分。信源输出可以是 模拟信号也可以是数字信号。数字信息本身不依赖于信源和信道的特性因而编码 可以分为信源编码和信道编码，香农证明了这种分离的合理性。在数字通信系统中， 寻求信源输出的有效表示方法，使之产生很少或不产生冗余，这种将模拟或数字信 源的输出有效地变换成数字序列的处理过程、称之为信源编码或数据压缩【3 1 0 固五园亟垂叵h 至函 i 调制信道_ 十于蒿鬲重 编码信道 j 墨h 磊 l i f ；i 固叫丕困叫互画习h 夏盏习 l 图1 1数字通信系统模型 两安电子科技大学硕士论文：低密度校验码应用研究 从信源编码器输出的二进制数字信号序列称为信息序列，被送入信道编码器。 信道编码就是在输入的二进制信息序列中人为控制的引入些冗余，使得接收机 能够用来克服信号在信道传输过程中受到噪声干扰的影响。冗余可以提高接收数 据的可靠性，有助于接收机译出期望的信息序列。本文主要关于信道编码，香农 的通信的数学理论一文也为信道编码技术的研究发展指明了方向。半个多世 纪以来，伴随通信技术的飞速发展及各种传输方式对可靠性要求的不断提高，信 道编码技术作为抗干扰技术的一种重要手段，在数字通信技术领域中和数字传输 领域中显示出愈来愈重要的作用。 1 1 2 信道模型 我们关心的是信道编码，故可以将数字调制、解调器与实际的物理信道整体 的看成编码信道( 图1 - 1 ) 。数字解调器中的检测器对信号作判决，检测器的判决 过程可看成量化，有q 元，如采用m 元信号，应有q m 。当q = m 时称硬判决， q m 时或在不作量化的极端过程情况下( q = o 。) ，称软判决。由于信道存在的 干扰引起码元接收错误，并且错误往往不是单独而是成串成群的出现，即是错误 之间具有相关性，这种错误称之为突发错误。出现突发错误的信道称有记忆信道 或突发信道，与之相对应的只存在随机错误的信道称之为无记忆信道或随机信道。 这里简单介绍几种常见的信道 4 j f5 j ： 二进制对称信道( b s c ) ：最简单的信道模型，对应于m = 2 、硬判决情况， 它具有离散时间的二进制输入与输出序列。该信道可以用输入值集x = o ，1 l 和输 出集y = o ，1 ) ，及一组表示输入与输出之间关系的条件概率来描述。如图1 2 ，这 种信道传输错误概率与输入无关。 p ( y = 0 | x = 1 ) = p ( r = 1 i x = o ) = p e ( r = 1 l x = 1 ) = p ( y = 0 l x = 0 ) = 1 一p 0 0 图1 2二进制对称信道( b s c ) 二进制高斯信道( b i a w g n ) ：在加性高斯白噪声信道中，信号受服从高斯分 布的噪声干扰，信道的输入x 和输出y 之间的关系为： y = x + g 第一章绪论 g 为零均值、方差盯2 的高斯随机变量。对于每个输入符号x k ，信道转移概率为 础悱咖去e 山叶一2 一 o 1 i y 图1 3二进制输入高斯信道 1 。2 信道编码定理与纠错码的发展 通信的数学理论一文中定义了信息的概念，指出在不可靠信道传输最大 信息量的界。一个给定的信道，香农证明存在一个值，称之为信道容量，记作c 。 如果信息传输速率小于或任意接近该容量，可靠通信是可达的；但一旦信息传输 速率超过该容量，可靠通信将变为不可达，下面给出几种常见的信道的容量。 二进制对称信道容量： c = m 。a x l ( x ；】，) = 毋许 日( 】，) 一日口l j ) ) 吩( j ) ( j ) 。 2 m 忡a x ) 日( y ) - 莓m ) 胛悱工) 斗h ( p ) h ( p ) = - p l o g p 一( 1 - p ) l o g ( 1 一p ) 是熵函数 加性高斯白噪声信道容量： c _ m a x h ( y ) 一h ( y i x ) = 1 一f p ( y l + 1 ) 1 。9 2 ( 1 + e - 2 y ：c & ) d y y p ( yl + 1 ) 为输k y 口+ l 时转移概率 定理1 1 有噪信道编码定理 4 ：设离散无记忆信道 ，p ( y l x ) ，y 】，p ( y ix ) 为 信道转移概率，信道容量为c 。当信息传输速率r ) = 1 3 p , ( s i = l ， y ) ) = n d 一1 1 + 兀( 卜2 p ，) ! 竺! 一 2 口一j 1 一兀( 1 2 p , f ) 土= l 一 2 ( 2 - 1 0 ) f 2 1 1 ) 将( 2 1 0 ) 和( 2 1 1 ) 代入( 2 9 ) ，可得到定理2 1 ，得证。 显然通过定理2 1 来计算某一比特d 关于两层或更多层的条件概率将是非常复 杂的，但可通过迭代的方式进行下去，即利用计算出的层结果来计算下一层、以 至多层节点概率。如：利用( 2 8 ) 式计算图2 4 中第一层节点关于第二层节点的概 率时，每个节点只计算五一1 个与之相关的校验方程，不包括比特d 参与的方程，得 型 鸳 西安 毡了科技大学顸上论文：低密度校验码成用研究 到的概率就可以代入( 2 8 ) 式计算节点d 的条件概率。若图2 4 中各层节点满足统 计独立，那么迭代就可进行下去。 下面简单总结整个译码过程：码字中的每一比特条件概率的计算，先通过( 2 8 ) 式计算出五个条件概率，其中每个条件概率的计算只使用五一1 个校验方程，不包括 浚比特参与的方程，然后再将获得的条件概率利用( 2 8 ) 式进行第二次计算。如果 比特统计独立的条件成立，这个过程就可持续进行，经多次迭代，如能成功译码， 码字中每一比特为1 的概率应趋向于1 或0 。 在实际运算过程中，采用对数形式可以简化计算，定义： i n 地：局 pd l i l 虹：嘞反 p , i - n 盟p , ( x a 裂1 溜= 西历= i y ，s ) 其中口= s g n ( x ) 是对数值的符号，= f x l 是对数值的绝对值。将上述定义代入( 2 8 ) 式可得： 以历= 届+ l 兀q ，矿i 厂( 屏) j (212)i l rp l、厂p 一、 ；= l f i f 乱， 其中( ) = l f l 菩等，式( 2 1 2 ) 的证明类似于下面的式( 2 - 2 2 ) 。 2 2 2 基于t a n n e r 图上l d p c 码译码算法 在t a n n e r 图上描述l d p c 码译码过程的称之为消息传播算法( m e s s a g ep a s s i n g a l g o r i t h m s ) ，其名称获得的原因为：该算法的每一轮计算过程中，关于各个节点的 置信消息需要在变量节点和校验节点之间传递。如图2 2 ，由变量节点向校验节点传 递的消息是基于收到的该变量节点观察值和与其邻接的校验节点在上一次迭代过程 中传递过来的消息联合计算的结果( 式2 8 ) ，其中需要特别注意的是由某个变量节 点工向校验节点z 所传递消息的计算中不包含在上一次迭代中由校验节点z 传递给 变量节点x 的消息，对由校验节点向变量节点传递的消息也有同样情况。基于t a n n e r 图描述的消息传播算法同基于树图描述g a l l a g e r 的概率译码算法是等价的。 置信传播算法( b e l i e fp r o p a g a t i o na l g o r i t h m ) 是消息传播算法中的种，其的 迭代公式也是基于独立性假设条件下推导的1 2 4 1 1 2 5 1 。设某个二进制随机变量x 取值 为0 、l 的概率分别为g ( x = 0 ) 和p a x = 1 ) ，可采用对数似然比l l r ( x ) 来度量x 的 第二章l d p c 码编译码原理1 7 两个取值概率信息。 l l r ( x ) = l n 5 ( x = o ) p , ( x = 1 ) 设x 为满足均匀分布的二值随机变量，即p ( x = o ) = p ( x = 1 ) = 1 2 ，y 为x 经 过信道后的观测值，根据b a y e s 公式有： l l r ( x jy ) ：i n 垫三! 丝：l n p ( x = o , y ) p ( y ) e ( x = 1 l y ) p ( x = l ，y ) p ( y ) ：l n ! 型兰三坐壁三! ! p ( y i 工= 1 ) p ( x = 1 )：k ! 剑兰三塑p ( y lx = 1 ) ( 2 1 3 ) = l l r ( yj 叫 根据独立性假设，若x i ，x 2 ，x d 为互相独立的二进制随机变量，m ，儿是 x i ，砭，经过无记忆信道后的观测值，则有： l l r ( x , ，x 2 ，l y l i 儿) = ：。l l r ( x ii 咒) ( 2 1 4 ) 现在考虑多个二进制随机变量x 1 ，x 2 ，以的联合取值的概率信息，首先由定义， 三l r ( ti 以，= n 蹦= h 三赭 可得： 再由式( 2 7 ) 可得出 p ( 葺= 1 l m ) = 而1 l l r ( x lo x 2o o x f y l ，y 2 ，y ) ：l n ! ! 兰! 叟兰里：里兰三竺! 兰! ：上2 ：羔! p ( 一ox 20 0 以= 1 iy i ，y 2 ，y i ) 1 + n ( 1 2 p ；( x = l l y ；) 凸吐二一 = h t 兰= i n 1 一兀( 1 2 异( z = 1 1 m ) 丘生 2 k 1 + n t a n h ( l l r ( x ； m ) 2 ) = i n j 一 1 一兀t a n h ( l l r ( x ；i ”) 2 ) 1 + 1 - i o 一 1 = 1 l 一兀( 1 一 ( 2 1 5 1 2 1 、 l + p l r 呻) 7 2 1 、 1 + e l l r x t j y j ) r 2 1 6 1 一一一一 。兀牛n闰 一一 。兀矧丁兀蚓 西安电予科技大学硕士论文：低密度技验妈应用研究 利用( 2 1 4 ) 式和( 2 一1 6 ) 式便可推导出置信传播算法的迭代公式。设发端为二进制 等概信源，即每个发送符号取0 和1 的概率均为1 2 ，发送码字为 x = “，码，矗) g f n ( 2 ) ，经过信道传输之后在接收端得到的码序列为 y = m ，款，咒 n ，对不同的信道输出，集合c ，的含义有所不同。首先，根据 信道观测值y 计算每个码元变量的后验概率信息，即一= l l r ( x s iy j ) ；在之后的 每一轮迭代中，每个校验节点i 根据( 2 1 6 ) 式计算出相应的对数似然信息r ：并传递给 相邻的变量节点，；每个变量节点j 也根据( 2 1 4 ) 式计算出相应的信息斜并传递给 相邻的校验节点i ，其中，为迭代次数。 通常，用m ( j ) 表示与变量节点，相连的所有校验节点所构成的集合，m ( j ) i 表示m ( ，) 中除去其中的校验节点f 后剩下的集合；用n ( i ) 表示与校验节点f 相连的 所有变量节点构成的集合，n ( i ) j 表示n ( i ) 中除去其中的变量节点- ，后剩下的集 合，则相应的迭代公式可表示为： f厂z = 0 ， g 2 协+ 乙、，掣， 2 。1 7 釉糍描 陋 注意到( 2 1 8 1 式还可以表示为： t a n h ( r 5 2 ) = ( 1 、，t a i l i l ( 贼2 ) ( 2 - 1 9 ) 可以发现第一个迭代公式主要采用求和运算，而第二个迭代公式则主要采用乘 积运算，因此置信传播算法也被称为和积译码算法( s u m - p r o d u c t a l g o r i t h m ) 。图2 5 给出了和积译码算法在t a n n e r 图上的具体描述。 t ：k 工k ( f ) 图2 5l d p c 码的译码算法示意图 由和积算法公式，即一步可得： 引理2 ：先定义： 娥= 。戳 第二章l d p c 码编译码原理 其中 此时有： 证明：由t a n h 定义 i f 珐 0 w w f i 砌t h p r o 。6 b 口a 揪b i i i 钞t y l l 2 2 蜴o f k = ：。0 ，彪= i 残w f f d 6 口6 f ，咖1 26 _ = “ i f 蛾 0 _ 2 1 1q i 的 l d p c 码而言，当码长趋于无穷时，图3 1 中的曲线逼近阶跃函数( 跃变点处是码最 小距离与码长的比值，为一个固定值，记为靠) 。因此，当码长”足够长时，l d p c 码的最小距离至少为n d j k 1 7 1 图3 1 最小距离分布函数 l d p c 码的译码采用迭代译码，这是其性能优越的原因之一。但迭代译码是基 于码间传递的信息是统计独立的假设下推导的，当t a n n e r 图中有环存在时，统计 独立的假设不再成立，码的性能将受到影响。环是从t a n n e r 图中任一节点出发， 经过一系列的边和节点后回到原节点的集合( 每个节点和边只经过一次) ，并且边 数等于节点数。因t a n n e r 图为二部图，故环长只能为偶数，最小的环长称之为围 长。由于小环对译码性能的影响很大，设计具有大围长( g i r t h ) 的t a n n e r 图便成为 研究的热点之一，然而研究表明并非围长越大、码的性能就越好。如果t a n n e r 图 是无环的，并且当对应l d p c 码的码率大于1 2 时，码的最小距离小于等于2 ；当 码率小于1 2 时，码可以由最小距离小于等于2 的码重复某些位生成。因此，无环 图对应的码并不是好码，相反地，环的存在改善了码的性能【2 0 】 2 8 。 围长和码最小距离是一对矛盾体，构造性能优越的l d p c 码就是要适当的折衷 tl p 西安电了科技大学预l 论文：低密度校验i i f 成用研究 这对矛盾体。m a c k a y 等指出消除4 环对码的性能有很大的提高，继续消环对码性 能提高的效果越来越不明显【27 。w i b e r g 对因子图的研究发现，对任意给定系统， 无环图的状态复杂度是最大的，有环图的状态复杂度则会大大降低，证明了基于 有环t a n n e r 图的l d p c 码具有较低的译码复杂度【1 9 1 。 3 1 2 构造具有较大围长l d p c 码的方法 构造具有较大围长l d p c 码的方法有很多种，本文主要介绍基于启发式搜索方 和代数构造的方法。 g a l l a g e r 构造的l d p c 码，如图3 1 ，校验矩阵h ( 如图2 1 ) 可分解为三个小 矩阵，_ ，乃是交织函数，对于h ，只进行一些列置换。如果对交织函数进行约束， 疗、( h ，) 保证与h ，相同的列不超过1 ，同样选择孔使得( h ，) 同时与h 。，丑( h 。) 相同 的列不超过1 ，这样构造的校验矩阵h 没有四环。 h i h 2 = 巧( h 1 ) h 3 = 码( h 1 ) 图3 1 校验矩阵h x i a o ，y uh u 采用“步步最优”的策略，提出了一种有效的构造具有较大围长的 l d p c 码的方法一渐进边增长( p e g ，p r o g r e s s i v ee d g e g r o w t h ) 算法，属于启发式 搜索方法i l “。该算法通过依次在t a n n e r 图上添加边进行构造，每次添加边都尽可能 减少对已有t a n n e r 图的围长的影响。该算法不但适用于正则l d p c 码的构造，也可 应用于非证则l d p c 码的构造。p e g 算法具有较好的实用性，采用该算法能构造出 围长为8 、码长为1 0 0 8 的( 3 ，6 ) 正则l d p c 码。 对于一个( ”，无p ) 的正则l d p c 码，可以分析出其上限f 2 3 】。如果该码的围长为 2 l ，则任意变量节点都有深度至少为卜1 个邻接树。图2 4 中树图中所有的奇数深 度节点( 全为校验节点) 的叶子数为p 一1 ，偶数深度节点( 全为变量节点) 的叶 子数为五一l ( 根节点的深度为0 ) 。由此可计算出树上各层的节点个数，偶数层为： 0 深度等于1 ，深度为2 节点有a ( p 一1 ) 个，深度为4 节点有d ( p 一1 ) d 个，深度为 6 节点有d ( p o d 2 个，由此类推( d = ( 五一1 ) ( p 一1 ) ) 。则偶数深度上的节点总数等 于： l ，+ l l l 旦j 百d l t j _ i 咖_ 1 ) 訾 树图上的偶数深度节点个数最多等于变量节点数n ，故有： 第三章l d p c 码的应用研究 d t j - 1 + ( p 一一1 ) 坐! 生n ( 3 1 )+ ( p j s nl j 。l ， d ld 一1 围长上限的数量级为l o g d 。 基于g f ( 2 ) 上的循环群，可构造具有较大围长的正则l d p c 码校验矩阵【2 9 】， 设h 为一个( 五，p ) 正则l d p c 码的校验矩阵，维数为7 p p p ，其中p 为一个素数。 将h 分裂为五x p 个维数为p x p 的小方阵，每一个方阵为一个单位阵或单位阵的行 循环移位。这种由多个循环移位的小矩阵构成的校验矩阵称之为循环矩阵，如式3 2 。 其中： h = e “oe “ e 1 o e e t t - i ，oe ，。 e “p 1 e “1 ： e p e = 矧 n 为m x m 的单位矩阵，p = m + l ，则= ( p 。) ，可表示为 ( 3 2 ) ( 3 3 ) 勺= 化怠黛! 。， f = ，卅+ ，( 口) = d r o o d p ， i , e ，e 2 ，f j 构成g f ( 2 ) 上的循环群。易得出，e 相当 于将n n 维数的单位矩阵经过各行循环左移f 位。 这种通过分裂矩阵的方法构造的校验矩阵，其围长的上限为1 2 图3 2 给出校 验矩阵上环长为1 2 的一种形式。下面给出证明，但须先引入几个引理。 ( ，、， 一 一 丫、 丫t 甲i l+ _ o 丫 rl j ，j， 、【 。 ，、 酗3 2 校验矩阵h 上的环 引理3 1 口9 1 ：设v ，屹，v 2 为校验矩阵上的一条路径，v 是矩阵中的非零元 素、对应t a n n e r 图中的节点，n 1 是一整数，且_ ，。在同一个小方阵中。则 v 11 7 2 ，v ! 。v ：。构成一个环，当且仅当 西安b 子科技大学硕士论文：低密度校验码应用研究 ( 黔n ，) = ( 纠 s ， ( ) = ( o ) ( 3 - 5 ) lp = i 成立。v 。在小方阵h 。= e 。中，s ，f 是小方阵h 。在校验矩阵h 中的坐标。 证明：令u 在小方阵e 。内的坐标为( 吒，t 。) 。由式( 3 - 4 ) 可得： = ( o + 吒) ( 3 - 6 ) 又设仉h 和v 2 ，在同一列，那么v ，和v 2 川则在同一行( 反过来设，具有同样的效果) ， 即有： 岛j - l = 岛， 和 嚏，= 也川 ( 3 7 ) 联合式( 3 - 6 ) ，( 3 - 7 ) 可得： ( k ：，+ 2 扣( 岛，+ + i 2 川) ( 3 - 8 ) 必要条件：设v l ，u ，v 2 。v 2 构成一个环，即有v 2 = u 。由式( 3 - 7 ) ( 3 - 8 ) 可以推出： 。= ( 宝t = l ( 如，一。一t ：，) = ( 主p - i ( 毛，一，一，) |l 即得到式( 3 5 ) ，得证。 充分条件：从式( 3 6 ) ( 3 7 ) ，可以得到：( 岛川- i 2 川) = ( 缟，一，) 即为： ( 3 - 9 ) ( 呜，一) = ( f 2 川- g ，) ( 3 - 1 0 ) 式( 3 5 ) 为已知，因而有： ( 言( 吃，一一吃，) 1 = ( 言( 屯，一。一t ，) 1 = 。 、i= 1 再联合式( 3 - 7 ) ，可得： = 岛。= 岛。 再由已知，u ，+ l 在同一个小方阵中，故v 2 = h 。则v l ，v 2 ，v 2 。，v 2 构成一个环。 下面再引入另外引理。 引理3 2 口9 1 ：令校验矩阵h 如式( 3 2 ) 由k 。p + d 、方阵构成，则存在长度为2 五p 的环。 证明：可以利用( j ，) 表示小方阵e “，j ，r 是小方阵e “在校验矩阵h 中的坐标。 ( j ，f ) 斗( j ，f + 1 ) 表示连接e 和e 。“l 中相同行非0 元素的边，p + 1 ，f ) j ( j ，r ) 表示 连接e “和e _ 7 中相同列非0 元素的边。j 等价于j m o d 2 ，等价于f r o o d p ，例 第三章l d p c 码的应用研究 如：( 五+ 1 ，p ) = ( 1 ，0 ) 。 在驴，上定义一个“序”，环经过的e “上非0 元素称之为环的顶点。存在一个路 径起始于( o ，0 ) ，即开始顶点位于e “中，则e “的“序”为0 。因而路径迭代可描 述为为： 和 ( s + 1 ，t ) _ ( s + 1 ，f + 1 ) 经过2 a p 个边，路经回到( o ，0 ) 。这个路径包括2 2 p 个边，每个( j ，) 被经过两次， 故具有两个“序”，一个为奇数，一个为偶数。由引理3 1 ，可得该路径构成一个环， 这个环可以有子环。 由引理3 1 、3 2 ，推出定理3 1 。 定理3 1 1 2 9 1 ：任何( n ， ，p ) 正则l d p c 循环矩阵，则围长的上限为1 2 ，2s 9 h ( p 一1 ) ( 3 - 1 2 ) 其中： f h ( 0 = g ( i ) h ( i 一1 ) ( o ) = o ； ( 1 ) = 1 ( 3 - 13 ) i g ( 0 g ( i 一1 ) 7 这是一个充分条件，事实上素整数p 可以小些，如：当矗( f ) = 7 ，g ( f ) = 3 ，p = 3 4 9 的( 3 ，6 ) 正则l d p c 码的围长为1 2 ，同时码的最小距离为2 4 。 在实际应用中，当满足围长为1 2 ，若再要求高码率，则码长将变得很大，随之 译码时延将增加，实用价值将会降低。这种构造的另外一个优点是：可快速编码和 并行译码。 3 2 西蜜电子科技大学硕十论文； 低密度校验码成用研究 槲 留 蝼 、 、 1 簇 墓囊萎喜 幽3 , 3 ( 1 0 0 8 ，3 ，6 ) 正则l d p c 码的性能图 3 2l d p c 码的快速编码 线性码的编码方式中，码的生成一般利用生成矩阵g 。，而l d p c 码的生成 矩阵g 一般不是稀疏矩阵，因此整个编码的复杂度取决于编码方程x = s g 的运算 复杂度，为仪珂：) 。文f 3 1 】给出实现l d p c 码的快速编码的方法，即通过列的置换 将校验矩阵变换成下三角或近似下三角形式，如图3 4 所示。 幽3 4 、l d p c 码校验矩阵f 三角形式和近似r 三角形式 此时矩阵斜线全为“l ”，其余的“l ”均在斜线的左边。若l d p c 码校验矩阵 具有下三角的形式，则可直接利用校验矩阵进行线性迭代编码，得到系统l d p c 码。 设码字向量为x f ”，将其分为两部分，即信息位向量s f 和校验位向量 p f “，即x = ( s ，p ) ，若l d p c 码校验矩阵具有下三角的形式，则l d p c 码的编 码过程可具体描述为： 1 ) 、对于码的前胛一m 位，直接将信息比特的值赋给信息位向量s 。 2 ) 、利用迭代方程来确定所有校验位的值，即对所有的， 1 ，掰 ，从小到大依 次计算下式： 第三章l d p c 码的应用研究 p i 书h l 。j s j + 前j p j ( 3 - 1 4 ) 其中岛，表示校验矩阵第，行、第列上的元素。设下三角形校验矩阵的平均行重 为p ，则整个编码约需要m p 次与运算，f m 一1 ) p 次异或运算，由于校验矩阵 是稀疏矩阵，p y 3 相对于胛是很小的常数，该编码方法可看成具有线性的复 杂度。 对于近似下三角矩阵，计算复杂度要高一些。如图3 4 可将h 进行分块。 r abt 、 h 。ij ( 3 - 1 5 cdf ) ij 7 a 、b 、c 、d 、f 、t 分别是( 掰一g ) ( n - m ) 、( m g ) g 、g ( n m ) 、g g 、g x ( 掰一g ) 、 ( m g ) 一g ) 维的矩阵，并且r 是下三角矩阵。矩阵h 左乘一矩阵得到 r l 0 、ra b t 、 i f t 。i j h 2 1 f t 。a + c f t “b + do j ( 3 - 1 6 ) 相应的码字向量x 也分成三部分，x = ( s ，p 。，p ：) ，s 为信息向量，p ，、p ：为校验向 量，s 长肝一m ，p j 长为g ，p 2 长为m g 。由h x = 0 可得： 月s 7 + 却j + r g = 0( 3 1 7 ) ( - f t 。a + c ) s + ( 一f t 。b + d ) p j = 0( 3 1 8 ) 设f t 。b + d 可逆，令中= - f t b + d ，则p j = ? - l ( - f t 。a + c ) s 。可单独计算出 矿( - f t 。1 a + c ) ，然后可求得校验向量p ，。再根据( 3 。j 7 ) 式，求出第二个校验向量 为p ；= 一t 7 ( a s 7 + 点秘；) 。计算过程中除一( 一f t 4 a + c ) 的计算复杂度为o ( 9 2 ) ，其 余计算复杂度都为o ( n ) 。 对于采用循环矩阵构造的正则l d p c 码，因其构造具有一定的规律，通过简单 的行列变换，h 也可变换到下三角形式。进行围长为1 2 的( n ，3 ，p ) 正则l d p c 码 编码需3 + 7 ) 叫p 次异或运算，因为p 相对于码长竹很小，故其复杂度可看作为 o ( n ) ，即具有线性复杂度。 3 , 3 一种改进的l d p c 码级联方案 i e e e 无线通信协议8 0 2 】6 标准建议，前向纠错( f e c ) 采用的是r s ( r e e d s o l o m o n ) 码和卷积( c o n v o l a t i o n a l ) 码的级联码1 。在小信噪比下，这种级联 码的性能较差。本节中采用l d p c 码代替r s 码，给出一种改进的l d p c 码与卷积 码级联方案。在编码时，选用校验矩阵h 具有下三角形式的l d p c 码为外码，h 矩阵无4 环，可以降低编码复杂度实现快速编码，同时又提高了系统的性能。采 西安t 乜了科技人学硕士论文：低密度校验码应用研究 用几组短码序列交织来代替长码，仿真结果表明两者在串行级联系统中具有相近 的性能，这样在保证系统性能的基础上，既能降低译码复杂度，又可实现并行译 码，进一步提高译码速度。 3 3 1 级联系统的构造 图3 5 给出级联系统的基本框图，类似于r s 码同卷积码的级联。外码为( ，z ，p ) l d p c 码，内码采用( n o ，) 的卷积码，此时整体码率为r = ( i - 2 p ) k o n 。卷 积码采用最大似然译码( v i t e r b i ) ，软输入硬输出：l d p c 编码采用快速编码，译 码采用b f 算法。l d p c 码和卷积码之间加入交织器，交织器采用按比特交织，不 同于r s 码按符号交织。整个级联系统于硬件实现都较为简单，复杂度较低，时延 较小。 0 区五卜痤 土 蹲35 、系统樽刮枢西 3 3 2l d p c 短码序列交织的构造 由s h a n n o n 信息论知，分组码的译码复杂度随码长呈指数增加，且时延长，而 采用短码抗突发错误能力较差。在级联系统中，由于卷积码的影响，错误主要表现 为突发错误，采用几组l d p c 短码序列交织的构造方式在性能上可逼近长码，且译 码硬件只具有短码序列的复杂度，其构造方式如图3 6 。 交织器是影响码的性能的关键因素，因而交织器的选择是级联系统的一个重要 方面。现常用的交织器有：分组型交织器、随机型交织器和c o d em a t c h e d 交织器。 这里采用是s 伪随机交织器p j 。 信息输入 图3 6 短码交织成长码模型 l d p c 码输出 第三章l d p c 码的应用研究 对于长度为_ 的交织器，交织数的产生方法是将每一个新生成的数与它之前 产生的s 位以内的随机数相比较，如果两者之差的绝对值大于正整数s ，那么它是 符合条件的，否则，再新产生一个随机数，继续比较，直到符合条件。当v