（通信与信息系统专业论文）低密度校验码结构优化及译码改进.pdf

重庆邮电大学硕士论文 摘要 摘要 低密度奇偶校验( l d p c ) 码是一种具有稀疏校验矩阵的线性分组码。 研究结果表明，采用迭代的概率译码算法，它能逼近香农容量限。由于 l d p c 码的诸多优点，它已经成为最具有应用潜力的下一代纠错码之一。 本文主要讨论了译码算法和码结构优化两个方面，分别提出了改进方 案。主要完成的工作包括： 1 利用t a n n e r 图模型详细阐述了l d p c 码的表示，从不同角度介绍了 l d p c 码的分类。 2 分析了影响码字性能的根本问题一围长，给出了直观实用的消去 小环的方法。 3 本文针对l d p c 码的结构优化问题，分析了随机化的构造，有限几 何构造等方法的优缺点，并指出准循环码的可实用性。提出了一种 利用相关函数值的方法来构造准循环码，消除了l d p c 码对应 t a n n e r 图上的小环，并使用计算机仿真了其性能，取得了较理想的 效果。 4 研究了在高斯白噪声信道下，l d p c 码的硬判决译码和软判决译码。 针对最小和积算法的误差，分析了归一化最小和积算法中归一化因 子的选取问题。 5 研究了硬判决译码的各种改进算法，提出了一种使用行重做权重因 子的硬判决译码方法。然后给出了l d p c 码在这些硬判决译码算法 下的仿真结果，结果显示新方法对于l d p c 码尤其是对短码具有较 好的改进作用。 关键词：l d p c ，围长，准循环码，比特翻转译码 重庆邮电大学硕士论文摘要 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 e k ( l d p c ) c o d e sa r eac l a s so fl i n e a rb l o c kc o d e s w i t h s p a r s ep a r i t y c h e c km a t r i x b yu s i n gi t e r a t i v eb e l i e fp r o p a g a t i o n d e c o d i n g ，t h i sc l a s so fc 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 g p e r f o r m a n c e d u et om a n ya d v a n t a g e s ，l d p cc o d e sh a v eb e c o m eo n eo ft h e m o s ta t t r a c t i v ea n di m p o r t a n tf i e l d si nc h a n n e lc o d i n gc o m m u n i t y a m o n gt h e m ，t h ed e c o d i n ga n dc o d ec o n s t r u c t i o ni m p l e m e n t a t i o na r et h e f o c u so ft h i st h e s i 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 c c o d e sa r ei n t r o d u c e da n dt h e ya r ec l a s s i f i e da c c o r d i n gt od i f f e r e n t s i d e s 2 t h em o s ti m p o r t a n tf a c t o ri n f l u e n c i n gl d p cc o d e s - g i r t h ，i st a l k e d a b o u t a n dp r a c t i c a lm e t h o d sf o rd e s t r o ys m a l lg i r t hc o n s t r u c t i o na r e r e s e a r c h e d 3 g o o da n db a da s p e c t so nm a n yc o d e sc o n s t r u c t i o n s ，s u c ha s r a n d o m i z a t i o na n ds y s t e m a t i z a t i o n ，a r ef o u n do u t a st h ep r a c t i c a l i t y o fq u a s i c y c l i cc o d e s ，an e wl d p cc o d ec o n s t r u c t i o nh a s b e e np r o p o s e d u s i n gc o r r e l a t i o nf u n c t i o n ，b a s e d o n q u a s i c y c l i cc o d e s t h i sn e w c o n s t r u c t i o nc a nd e s t r o yt h es m a l lc y c l ea n dr e a c hi d e a lp e r f o r m a n c e 4 i nt h i st h e s i s ，s e v e r a ld e c o d i n ga l g o r i t h m sf o rl d p cc o d e s ，s u c ha s b i tf l i p p i n g ( b f ) a l g o r i t h m ，b e l i e fp r o p a g a t i o n ( b p ) a l g o r i t h m ，a r e c o n s i d e r e d a tt h es a m et i m e ，t h ek e yp a r a m e t e r , n o r m a l i z e df a c t o r , h a sb e e na n a l y z e dc o n s i d e r i n gf o rt h ed i f f e r e n c e b e t w e e nb p a l g o r i t h ma n du n i f o r mm o s tp o w e r f u l ( u m p ) b p b a s e da l g o r i t h m 5 s e v e r a li m p r o v e db pd e c o d i n ga l g o r i t h ma r er e s e a r c h e d ，s u c ha s w e i g h t e db f ( w b f ) a l g o r i t h m a ni m p r o v e dd e c o d i n ga l g o r i t h m b a s e do nt h er o w sw e i g h ti sp r o p o s e d i nt h em e a n t i m e ，s i m u l a t i o n so f t h o s eb fa l g o r i t h m sa r eg i v e n ，t h en e wb fd e c o d i n ga l g o r i t h mh a s b e e np r o v e db eb a t t e rt h a no t h e r s k e yw o r d s ：l d p c ，g i r t h ，q u a s i - c y c l i cc o d e s ，b i tf l i p p i n gd e c o d e l l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重废 邮皇太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名： 签字日期：种7 年5 月了e l 学位论文版权使用授权书 本学位论文作者完全了解重庞邮鱼太堂有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权重麽邮电太坐 可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：主犯导师签名：审荔文学位论文作者签名：犯 导师签名：7 锣弋 签字日期 砷年5 月7 日 签字日期渺产 月7 日 1 1 重庆邮电大学硕士论文 第一章绪论 第一章绪论 本章首先简要介绍了低密度校验( l d p c ) 码的提出、发展和研究现状， 系统阐述了l d p c 码的定义及其t a n n e r 图表示。并且按照不同角度介绍了 l d p c 码的分类，最后给出了全文的内容安排。 1 1l d p c 码的研究现状 s h a n n o n 提出的有噪信道编码定理作为现代通信理论的基础，给出了 在有噪信道上实现可靠通信的理论极限。虽然该定理指出了可以通过差错 控制码在信息传输速率不大于信道容量的前提下实现可靠通信。但却没有 给出具体实现差错控制编码的方法。 1 9 9 3 年于瑞士日内瓦召开的国际通信会议上，c b e r r o u 、a g l a v i e u x 和p t h i t i m a j s h i m 首次提出了一种新型信道编码方案一t u r b o 码，由于它 们很好地应用了s h a n n o n 信道编码定理中的随机性编、译码条件，从而获 得了几乎接近s h a n n o n 理论极限的译码性能。 然而，虽然t u r b o 码标志着人们构造其性能接近s h a n n o n 限的好码的 开始，但t u r b o 码仍未将随机化思想真正贯穿于其编译码的始终，而且它 也有许多缺点： 1 ) 译码时延大，这就使t u r b o 码在某些对时延要求高的通信系统( 如 数字电话) 中的应用受到限制： 2 ) 计算量大，为达到高码率需要很大的交织器，这就增加了时延； 3 ) 有所谓的错误平层( e r r o r f l o o r ) 效应。 在深入研究t u r b o 码原理的过程中，1 9 9 6 年m a c k a y ，s p l e l m a n 和w i b e r g 几乎同时发现：g a l l a g e r 早在1 9 6 2 年提出的低密度校验码( l d p c ) 也是 一个好码，具有更低的线性译码复杂度。人们的进一步研究表明：基于非 规则t a n n e r 图的l d p c 长码的性能可以优于t u r b o 码，而且这样的码的性 能可以非常接近s h a n n o n 限。由于l d p c 码不仅具有良好的距离特性、小 的译码错误概率和较低的译码复杂度，而且适当码长( 比如大于2 0 0 ) 时， 不存在错误平层，其码率容易调整。实验结果中的错误几乎均为可检测错 误。所以l d p c 码无论在理论上还是在实际上都具有极其重要的价值。 l d p c 的重新发现是继t u r b o 码后在纠错编码领域又一重大进展。 在l d p c 码研究的初期，无论g a l l a g e r 还是m a c k a y 等都是用随机方 法构造，这样构造的码字参数选择灵活，但对于高码率、中短长度的l d p c 重庆邮电大学硕士论文第一章绪论 码，要避免t a n n e r 图中的四线循环是困难的。这些码都没有一定的码结构， 编码复杂度高。于是人们考虑用代数法构造l d p c 码。 l d p c 码代数构造可采用几何方法、图论方法、实验设计方法、置换 方法来设计。不同的构造方法都是为了实现以下几个目的：增大图中的环， 优化非规则码的节点分布，减小编码复杂度，构造的l d p c 码要有好的码 性能。 m g l u b y ! “5 】等指出，基于非规则图定义的码性能优于相应的基于规 则图定义的码，在非二元域中定义码和采用具有非均匀行、列重量的非规 则校验矩阵均可改善码的性能，在寻找好的码结构方面，m a c k a y l l 6 等提出 对非规则码采用先选择轮廓再选择结构的两步选择方法，验证了超泊松 ( s u p e rp o i s s o n ) 结构具有较好性能，并指出能快速编码的l d p c 矩阵通常 具有下三角形结构。 t j r i c h a r d s o n l l 7 1 等通过优化非规则图的次数结构来寻找逼近容量的 非规则l d p c 码。t j r i c h a r d s o n l l 8 1 探讨了要获得高效编码器如何确定校验 矩阵稀疏度的问题，以及如何构造码，使编码时间与码块长度实际上符合 线性关系( 线性时间编码) ，而非通常认为的平方关系。m g l u b y 1 9 1 等也提 出了一类基于级联t a n n e r 图的l d p c 码，用于可删除信道，称为可删除码。 它不仅是线性时间编码，而且也可实现线性时间译码。 d a s p i e l m a n t 2 0 1 开发了一种试探法来寻找非规则l d p c 码参数的好的 分布，据此构建了在很低信噪比下误码率( b i te r r o rr a t e ，b e r ) 低于t u r b o 码的码率为1 2 的l d p c 码。y m a o 等则基于性能准则，提出根据图中最 小环长的分布来设计好的l d p c 码的方法。 y k o u 和s l i n t 2 1 】等讨论了基于有限几何学的l d p c 码结构。s l i n 研 究团队的b a m m a r 等提出用均衡不完全区组设计方法( b a l a n c e d i n c o m p l e t eb l o c kd e s i g n ，b i b d ) 构造好的l d p c 码1 2 “。j i r o s e n t h a l 和 p v o n t o b e t 2 3 】研究了基于r a m a n u j a 图和按照m a r g u l l i s 的概念构建的规则 l d p c 码，其性能优于随机构造的( 3 ，6 ) 规则码。n v a n i c a ”1 等则对 t j r i c h a r d s o n d t 的优化方法作了修正，对存在符号间干扰的部分响应信道 中的l d p c 码进行了优化。 在译码算法的选择上，g a l l a g e r i 25 2 6 1 曾给出了两种l d p c 码的迭代译 码算法：硬判决和软判决算法。前者性能不是很理想，后者虽有好的性能， 但太复杂。消息传递算法可认为是二者的折衷。消息传递算法( m e s s a g e p r o p a g a t i o n ，m p ) 有时也称置信传播( b e l i e fp r o p a g a t i o n ，b p ) 算法。在b p 译 码算法中，节点到节点的消息是通过t a n n e r 图传递的。 2 重庆邮电人学硕士论文 第一章绪论 d b u r s h t e i n 和g m i l l e t ”j 利用扩展图的理论证明了消息传递算法具有 的某些特性。f r k s c h i c h a n g t 2 8 】等指出：作为一种通用的消息传递算法， 和积算法( s u m p r o d u c ta l g o r i t h m ) 实际上包含了大量的实际译码算法( 如前 向，后向算法、v b 算法、p e a r l s 传播算法等) ，它可应用于任何因子图( f a c t o r g r a p h ) ，众多的实际译码算法均可由和积算法框架导出。 m a c k a y 和c p h e s k t h 2 9 1 研究了l d p c 码采用b p 算法译码并假定某个 噪声电平时，译码性能随实际噪声变化的敏感程度，得出了实际与假定噪 声失配对译码性能影响的函数关系。 译码算法的改进和优化离不开译码性能的分析。在译码性能分析的研 究方面，m g l u b y 1 4 】等在文献中给出了一种新的基于弓形连线的 c o n c e n t r a t i o nb o u n d s 方法来分析l d p c 码。对于b p 译码器的收敛性能分 析，存在这样的情况：当码块长度有限时，分析十分困难；而当允许码长 趋于无限时则可大大简化分析。这可以理解为：给定迭代次数t ，从某个 随机构造的l d p c 图中随机选取某个信息( 比特) 节点，其成为长度小于t 的环的组成部分的概率。当码长无限时趋于0 ，因而可不考虑环，而将任 一节点上的消息视为独立的。t j r c h a r d s o n 等 1 5 1 将文献 1 4 1 中的方法 ( c o n c e n t r a t i o nt h e o r e m ) 从二元对称信道( b i n a r ys y m m e t r i c a lc h a n n e l ，b s c ) 和二元b p 译码算法的约束条件推广到各类信道模型，开发了一种假设在 码块无限长的条件下跟踪l d p c 码t a n n e r 图中消息概率的技术，称为“密 度进化”算法的数值程序，来近似估计噪声门限( 在该门限以下可望成功地 采用b p 算法) ，并提出了一种通用的方法来确定具有离散或连续输出字符 集的任何二元输入无记忆信道中采用b p 译码的l d p c 码的性能。特别对 于b p 译码算法，该方法可提供任何所需精度的性能估计。 s y c h u n g 3 0 】等利用消息分布的高斯近似( 即假设所有消息具有不变的 高斯概率密度函数( p r o b a b i l i t yd e n s i t yf u n c t i o n ) ) 简化了密度演进算法，可 在不降低精度前提下快速找到门限和快速、容易地优化密度的分布，有助 于了解和积算法译码器性能和优化非规则l d p c 码。s y c h u n 9 1 3 1 1 等将消 息离散化，通过计算机迭代搜索寻找最优的节点次数分布，特别适合于非 规则码的分析，在二进制输入a w g n 信道下，设计的码率1 2 ，码长1 0 7 的 非规则l d p c 码在错误概率1 0 6 时离s h a n n o n 限仅o 0 0 4 5 d b 。这是迄今为 止报道出的性能最接近s h a n n o n 限的信道编码。 m p c f o s s o r l o r 3 2 1 3 3 1 研究了降低复杂度的l d p c 码的基于信度传播的 迭代译码，提出了基于可靠性译码与信度传播译码相结合的l d p c 译码算 法，以获取译码性能和译码复杂性的折衷。“密度进化”应用于基于b p ( b p 重庆邮电大学硕士论文第一章绪论 b a s e d ) 的译码算法的还包括p e a r l s 3 4 3 5 】的最大积( m a xp r o d u c t ) 算法和 x w e i 【3 6 】的最大对数映射( m a xl o gm a p ) 算法等。为了改善b pb a s e d 算法因 在校验节点上作简化处理而导致性能的下降，j c h e n t 37 3 8 】提出了两种改进 算法：采用归一化的b pb a s e d 译码算法( 亦称为n o r m a l i z e d b p b a s e d 算法) 和通过降低可靠性值来改善信息精度的o f f s e tb pb a s e d 算法。 近年来，l d p c 码的很多研究成果表明l d p c 码是一类性能优异的好 码。l d p c 码比t u r b o 码在技术上更具有优势，更能适应未来系统高速数 据传输和高性能的要求。 1 2l d p c 码的定义及其t a n n e r 图表示 l d p c 码是一种线性分组码，它的名字来源于其校验矩阵的稀疏性， 即校验矩阵中只有数量很少的元素为”l ”，大部分都是0 。g a l l a g e r 最早 给出了正则l d p c 码的定义，具体来讲正则l d p c 码的校验矩阵h 满足下 面三个条件： ( 1 ) h 的每行有p 个”1 ”； ( 2 ) h 的每列有五个”1 ”，五3 ； ( 3 ) 与码长和h 矩阵的行数相比，p 和旯都很小。 矩阵h 的每列各自包含a 个“l ”，表示每个码元变量受到相同数目的 校验约束；每行也各自包含j d 个“l ”，表示每个校验方程对相同数目的码 元变量进行校验约束；由于p 和旯都很小，校验矩阵h 具有很低的“密度”， 因此由校验矩阵h 所确定的码称为l d p c 码。g a l l a g e r 证明了当五3 时， 这类码具有很好的汉明距离特性。正则l d p c 码通常用( n ，a ，p ) 来表示，其 中n 为码长，p 和五的含义不变，图1 1 给出了一个( 2 0 ，3 ，4 ) i e 则l d p c 码 的校验矩阵。 4 重庆邮电大学硕士论文第一章绪论 图1 1 ( 2 0 ，3 ，4 ) l d p c 码的校验矩阵 当校验矩阵h 各列( 行) 中“l ”的个数不全相同时，就得到了非正则 l d p c 码。非正则l d p c 码通常用度序列分布函数来表示，我们会在给出 l d p c 码的t a n n e r 图描述之后具体介绍非正则l d p c 码的度序列表示。 设一个( n ，a ，力正则l d p c 码具有校验矩阵h = ( h 1 j ) ，则其相应的 t a n n e r 图模型可以表示为一个二部图。其中码字向量x = ( x l ，x 2 ，x 。) 表示 为一组变量节点 工，j = 1 ，2 ，n ) ，分别对应于校验矩阵的各列，而校验约束 则表示为一组校验节点 = ，i = l ，2 ，m ) 对应于校验矩阵的各行。仅当h t ，= l 时，变量节点x i 与校验节点z i 之间有条边相连，节点x ；与z ；互相称为邻 接节点，其间的连接边称为两个节点的邻接边。对于( n ，五，力正则l d p c 码， 每个变量节点与五个校验节点相连，称该变量节点的度为五：每个校验节 点与p 个变量节点相连，称该校验节点的度为p ，度表示与节点相连的边 的数目。图1 2 给出了图1 1 所示的校验矩阵对应的t a n n e r 图结构。 o o o o l o l o 0 o o o 0 l o o o o 0 l o o 1 o o o 1 o o 0 o o o o l 1 o o o o l o o o o 0 o o 0 1 0 1 o o 0 o o 0 o l o o 0 1 o o o o 0 1 o o o o 0 o o ，o o o 1 o o o o o 0 o 0 o o o o o l o 0 o 0 o o o o 0 o o 0 1 o o o 0 o o o ，o o 0 o 0 o ，o o o o o o ，o o o o o o 0 0 o o 0 o ，o o o o l o o l 0 0 o o o o ，o o o o 0 o l 0 o o o 0 o o 0 o o o l o 0 0 o o o l o 0 0 l o o o o o o o l o o ，o o o o o o o l o o o 0 1 0 l o o o o o o 1 o o o o 0 o o o o ，o o o o o o o l o o 0 o o o o o o l o 0 o o ，o o o o o o o o o o o o ， l o o o o o l o o o o o o o 重庆邮电大学硕士论文第一章绪论 变量 节点 图1 2 ( 2 0 ，3 ，4 ) l d p c 码的t a n n e r 图表示 1 3l d p c 码的分类 1 。3 1 非规则l d p c 码和规则l d p c 码 若l d p c 码所对应的t a n n e r 图为规则t a n n e r 图，则此l d p c 码称为规 则l d p c 码：若对应的t a n n e r 图为非规则t a n n e r 图，则此l d p c 码称为 非规则l d p c 码。 对于非正则l d p c 码，相应的t a n n e r 图中各变量节点或校验节点的度 并不相同，通常用序列 2 ) 上的l d p c 码的性能可优于二进制的l d p c 码的性能，而 且更大域上构造的l d p c 码的性能可得到大的改善。下面给出一个直观性 解释： m a c k a y 1 0 】已证明：对给定的译码器，当校验矩阵h 的列重量( 固定常 数) 足够大，码长充分大时，l d p c 码的性能可以接近s h a n n o n 限，即大重 量的列有助于译码器的快速纠错，然而若增加列重量会造成相应的t a n n e r 图中的循环数目急剧地增加，从而导致迭代译码的性能下降。而在 g f ( 2 ，) ( q 2 ) 上构造的l d p c 码便可解决这个问题，增加它的校验矩阵h 。 的列重量( 即增加与它对应的二进制校验矩阵h ，的列重量) ，但它们进行译 码的t a n n e r 图是相同的，g f ( q ) 上不会造成结点之间循环路径数目的增加， 从而使译码性能得到显著的提高。 比较两个等价矩阵的一部分，可以看到q 进制码不包含长为4 的环， 而等价的二进制码含有长为4 的环。因此，在传输的二进制信息等价的情 况下，q 元l d p c 码译码性能得到显著的提高。 1 4 本文主要研究工作和内容 作者在深刻理解l d p c 码基本编、译码原理基础之上，提出了一种利 用准循环码的相关函数值来构造l d p c 码的方法，利用理论分析和计算机 仿真相结合的方法，获得了一定的研究成果。全文共分为五章，其它章节 安排如下： 第二章对影响l d p c 码性能的环进行了全面的分析，为深入研究l d p c 码的构造和译码算法提供了理论依据；研究了比较成熟的几种l d p c 码构 造以及译码方法。 8 重庆邮电大学硕士论文 第一章绪论 第三章首先分析了基于准循化码构造l d p c 码的优势；重点介绍了基 于光正交码构造的准循环l d p c 码( o o c l d p c 码) ，提出了一种利用相关 函数值，构造具有较大围长的l d p c 码设计方法。 第四章着重研究了硬判决译码改进算法，提出利用行重做为加权因子 的改进算法，提高了非规则l d p c 码性能。通过密度进化和仿真两种手段 得出，现有的最小和积算法对译码性能影响较大的结论；介绍了归一化的 b pb a s e d 方法，并给出采用不同归一化因子的仿真结果。 第五章对全文工作进行总结，并且提出了下一步的研究工作。 9 重庆邮电大学硕士论文第二章l d p c 码理论 第二章l d p c 码理论 本章首先分析影响l d p c 码性能的因素一一环，为后面的低密度校验 码构造和优化提供了理论依据，同时给出了较为直观的消去小环的方法。 随后研究了比较成熟的几种l d p c 码构造以及译码方法。 2 1l d p c 码的环分析 2 1 1l d p c 码的环分析例 一个l d p c 码的矩阵结构对码的性能有决定性的影响。在t a n n e r 图中， 我们这样定义环( c y c l e ) ：环是一些边与顶点的集合，从其中任意一个顶点 出发，经过所有的边及顶点又回到该初始顶点，而且在此过程中，除了初 始顶点，所有的顶点与边只经过一次。一个环上边的数目被称为环长。 在g a l l a g e r 推导l d p c 码的译码算法中，他是基于树图的，即图中没 有环的存在，这样在图中传递的消息之间是统计独立的。并且在推导置信 传播译码算法和密度进化理论的过程中，我们都假定所传递的消息之间是 统计独立的。然而，大部分l d p c 码在码长为有限时都不能满足该假设。 因子图中环的存在及数量影响l d p c 码的性能，尤其小环的存在及数量对 编码的码距和性能有着重要的影响。 通过一个例子我们可以直观地解释环长对译码性能的影响，如图2 1 所示的t a n n e r 图片段。在图2 1 中，存在环长为4 的环，如图中黑线所示。 显然，如果图示中3 个变量节点都发生错误，则5 个校验节点对应得约束 关系中只有一个能检测到有错误发生。在这种情况下，应用消息传递算法， 从检测到错误的一个检验约束关系来纠正3 个错误是困难的，译码性能受 到了较大的影响。 所以，此例t a n n e r 图结构的分析告诉我们，t a n n e r 图上的环特别是小 环对码的性能有很重要的影响，环的存在使得节点传递出去的信息几轮迭 代后，经过环又传递回到它本身，造成了信息的重复利用。因此，环尤其 是最小环的存在会降低迭代译码中传递消息的可靠性，从而影响了译码性 能。所以，我们在构造l d p c 码时，总是很关心怎样构造具有更大环长的 l d p c 码，或者说怎样消去小环。 1 0 重庆邮电大学硕士论文第二章l d p c 码理论 图2 1t a n n e r 图片段 一般地，长为4 的环很容易通过t a n n e r 图找到。但是对于长大于4 的 环的判定是很困难的。下面给出几种环路的检测方法。 2 1 2 根据校验矩阵检测环 t a n n e r 图可以根据l d p c 码的校验矩阵h 得到，其中h 是n x k 。前 面已经叙述过，如果单从校验矩阵来判断环个数是很困难的，因此要对 t a n n e r 图进行改造，将t a n n e r 图校验节点和信息节点合并成新的有向图， 合并后并没有改变l d p g 码的性质。 定理2 1l d p c 码的任意一个长为l 的环，满足l 4 ，且l 是2 的倍 数。 设集合q 表示节点集合 x t , z ；i i = 1 , 2 ，n ；j = 1 , 2 ，k ；这样q 中有n + k 个元素，则可以用矩阵s 来表达q 的内部关系。 s = i 三，习 ( 2 1 ) 也就是说，当s 中的元素s 。为l 的时候表示从i 到j 有连接，这里i ， j l ，2 ，n + k 。则根据图论知识，设s k ( k = l ，2 ，3 ) 是s 的k 次幂， 则s k ( k = 1 ，2 ，3 ) 的元素s 。；。的物理意义是经过k 步从节点i 到节点j 的路径 有s 。”条，对角线元素s i t k ) 表示节点i 经过k 步回到i ，这些回路与环是不 等价的，一条回路满足一个长为l 环的条件：( 1 ) l = k ；( 2 ) 经过的节点数也 是k 。 下面考虑s k ( k = 1 ，2 ，3 ) 的每个元素的值。 根据定理2 1 可知，当k 是奇数的时候s 。对角线上的元素为0 ，因此只 需要考虑s 的偶数次幕。 k s k = ( s 2 ) i 重庆邮电大学硕士论文第二章l i l p c 码理论 s 2 = b ，：0 三苫i = l 孑h 7h ，9 c 2 z ， 因此计算的简化形式 s t ：( h h t r ：l ( 2 - 3 ) 1 0( h 7 h ) ：i 由于一些病态路径的存在，也就是存在按原路折返的路径，比如存在 x l 寸z l 专x l ，x l 寸z l _ x 3 _ z l 专x i ，使得环的个数和路径数是不等价的。 下面给出一个计算这些路径中包含环的个数的方法，设为n t k ) ，定义 一个修正因子m “，使得： n - = s 譬一m ：” m ：”= l s , js j j j ，矗“b ，。s j 2 j , s ”l ( 2 4 ) 山，j 2 ，也i 2 2 ” i 以上得出的是经过任意一个节点i 所有回路中，包含环的回路个数， 但要精确的断定一个环的存在，这是不够的。 2 1 3 环路检测定理 定理2 2 假如i 和j 是一个周长为l 环的任意2 个节点，则从i 到j 的路径只有2 条，而且这2 条路径所经过步数和为l 。 定理2 3t a n n e r 图中2 个节点i 、j ，如果k 为偶数， s 。，元素s ：( i ，j l ，2 ，n + k ) ，满足 兰 ! 一2 s ；2 ，s , f = 0 矩阵s 的k 次幕 ( 2 - 5 ) 则存在一个长为k 的环，且这个环经过节点i 、j 。通过这个环路检测 定理可以精确地判定一个环的长和经过的所有节点。 2 1 4 根据t a n n e r 图的交换图直观检测和消去小环 l d p c 码校验矩阵的非零元素反映在t a n n e r 图上就是连接信息节点和 校验节点的一条线。为了形象的看出l d p c 码环路的性质，将如图2 2 所 示的t a n n e r 图变换成如图2 3 的形式，经此变换没有改变l d p c 码的内部 结构和约束关系。显然经过这种变换后，很容易得出该( 8 ，2 ，4 ) l d p c 1 2 重庆邮电大学硕士论文第二章l i n g 码理论 码存在的环路个数，环长以及经过的路径。 h = lo l0 ol ol l0 ol 1o 0l l0 ol ol lo lo ol l0 ol 图2 2 校验矩阵和t a n n e r 图中的环 图2 3 ( 8 ，2 ，4 ) l d p c 码转换后的t a n n e r 图 因此分析l d p c 码环路一种直观的办法就是： ( 1 ) 选取任意一个信息节点，作为第一层节点； ( 2 ) 选取和该节点相连接的节点作为第2 层节点； ( 3 ) 将除了第l 层节点外，和第2 层节点相关的节点作为第3 层； ( 4 ) 当t a n n e r 图通过如此变换后，考虑环路时，只要找到一个节点与多 个上层节点有关系，即可以断定存在一个环。 事实上，有些l d p c 码并不是每个节点之间都是相通的，也就是说可 以表示成好几个独立的这种树图形式。 重庆邮电大学硕士论文第二章l d p c 码理论 下面给出特定长度小环的消去方法。 如图2 4 所示，存在4 个节点v l ，v 2 ，v 3 ，v 4 和两条边e t 、e 2 ，其中e l 连接v l 、v 2 ，e 2 连接v 3 、v 4 。若交换它们的连接关系，即变成两条新边e l 、 e 2 ，其中e l 连接v l 、v 4 ，e 2 连接v 2 、v 3 ，对整个l d p c 码来说没有改变 校验关系。 图2 4 交换节点示例图 在消去短环前，先确定要消去的小环最大长度l 一，对于所有长度小 于l 的环采用这种小环消去方法，具体实现如下： ( 1 ) 将t a n n e r 图变换成本小节所述的树图形式。 ( 2 ) 遍历整个树图，找出第一个和上层节点构成环路的节点。 ( 3 ) 计算通过该节点和上层节点构成所有环路的周长，对于小于l 。的 环路，在该环中选择一条通过该节点的边，在环外随机选择没有公共节点 的一条边，交换两条边的节点，这样该环路就被消去，如图2 5 所示。 ( 4 ) 如此反复迭代，可以消去所有的特定小环。 v l v 3 v 5 口 v 2v l v 4 v 6 v 3 v 5 图2 5 小环消去的示例图 v 4 v 6 下面给出的定理2 4 ，说明消去环路的极限。 定理2 4 所有节点都连通的规则l d p c 码( n ，y ，p ) ，码率为r ，当， l 时，一定存在环，同时该规则码环个数m 满足：m n ( p 一2 + r ) + 1 。 一个所有节点都连通的无环l d p c 码的t a n n e r 图，可以看作是多叉树。 说明这个定理前，先构造一个信息节点个数和校验节点个数与规则 ( n ，n 力l d p c 码相同的无环l d p c 码，该l d p c 码总共应该有不多于n ( 2 - r ) 条边，若多于这个边数则存在环，也就是说在该t a n n e r 图上每增加一条边， 1 4 重庆邮电大学硕士论文 第二章l d p c 码理论 就至少增加一个环路。规则( n ，p ) l d p c 码的边数为n ，条，所以该规则 的l d p c 码至少有m n o 一2 + r ) + 1 个环路。这就说明了能消去的环是有 限的。这个极限是由码结构来决定的，可以通过节点个数和环个数定性地 确定一个范围。 2 2l d p c 码构造法介绍 在上小节中，我们给出了直观的消去小环的方法，但是构造高性能的 l d p c 码不可能仅通过以上手段得到。人们在研究过程中，围绕这一问题 作出了长时间的努力，发现了多种构造法。下面我们仅做部分介绍。 2 2 1 g a l l a g e r 的构造方法 假定需要构造的正则l d p c 码，列重为3 ，行重为4 。g a l l a g e r l 2 6 将校 验矩阵按行分成3 个大小相等的子矩阵，每个子矩阵行重为4 ，列重为1 。 子矩阵按照确定的方式构造，比如由单位阵排列而成。也可以这样，第一 个子矩阵的第i 行从第( i - 1 ) k + l 到i k 列均含有l 元素，这里k = 4 为行重， 其它的予矩阵，都是通过对第一个子矩阵的所有列做随机的排列组合而 成。 以下的校验矩阵就是g a l l g e r 构造的一个例子( 2 0 ，3 ，4 ) 码 l1ll000000000000 oo0 0l1ll00000000 oo0 0 0 000lll10000 000 000000000ll1l o o o 0 l o 1 o o o o o o l o o o o o 1 o o l o o o l 0 o o o o o o l l o o o o l o o o o o o o o l o l o o o o o 0 o l o o o o o 1 o o l o o o o o 1 o o o o l o o o o o o l o o o o 0 1 o o o o l o o 0 o 1 o o o l o o o 1 o o o o o 1 o o o 0 l o 0 o o o o o l o o l o o o 0 o o o 0 o 1 o l o o o o o o o l o 0 1 o o o o 1 0 o o o o o o l o o o o o o l o o o o l o o o o l o o o l 0 o o 1 o o 0 0 o o o l o o o o o o 1 o o l o o o o o 1 0 o o o o 0 l o 0 l o o o o 1 o o o 重庆邮电大学硕士论文第二章l o p e 码理论 2 2 2 m a c k a y 的构造方法 构造法1 ：这种方法是最基本的一种构造方法，它要求保证固定列重 为，而行的重量尽可能均匀的保持为p 。同时要求任意两列之间的交叠 重量不超过1 。图2 6 ( a ) 表示了按照此方法构造的一个l d p c 码( 3 ，6 ) 码【1 们。 o ( a ) m a c k a y 的构造法1( b ) m a c k a y 的构造法2 图2 6m a c k a y 的构造方法 构造法2 ：将m 2 的列，重量置为2 ，通常采用两个m 2 x m 2 的单位 矩阵，上下叠放。剩余的列依然保持法1 的构造方法。如图2 6 ( b ) 所示。 构造法3 在前面所说的法l 和法2 构造方法构造的矩阵中，挑出部分 使得t a n n e r 图中出现短圈的列，将其删除。再插入重新随机产生的列，使 得t a n n e r 图中不再存在小于某个长度的圈。 无论o a l l a g e r 还是m a c k a y 等都是用随机方法构造l d p c 码，用随机 法构造的l d p c 码的码字参数选择灵活，但对于高码率、中短长度的l d p c 码用随机法进行构造，要避免t a n n e r 图中的四线循环是困难的，其没有一 定的码结构，编码复杂度高。 除了随机化构造l d p c 码以外，还有系统化构造，包括利用欧氏几何 ( e g ) 和射影几何( p g ) 分别构造e g - l d p c 码和p g l d p c 码，可以对校验矩 阵按一定规则进行扩展与删减，进而对l d p c 码进行扩展或缩短，可以进 一步提高其性能。 系统化方法还包括利用均衡不完全区组设计( b a l a n c e di n c o m p l e t e b l o c kd e s i g n ，b i b d ) 构造的码字，这种方法已经有不少文献可供参考，但 是我们发现它们中有很大一部分性能没有人们想像的那样美好，即使在 i e e e 里与此相关的文章中描述的内容也只是给人留下仅仅有扎实理论的 感觉。随着代数学和几何学的不断向前发展，利用系统化的方法构造需要 的l d p c 码是一种趋势，例如正在发展的极空间的仁，) 几何等组合数学 新分支都可能是个构造l d p c 好码的新方法。鉴于篇幅和精力，本文不 再介绍系统化的构造方法。 1 6 重庆邮电大学硕士论文第二章l d p c 码理论 通过研究发现，具有大