（应用数学专业论文）低密度校验码的围长提升研究.pdf

摘要 现代编码技术的终极目标是以逼近s h a n n o n 限的有效功耗实现可靠通信。 低密度校验码( l o w d e n s i t yp a r i t y - c h e c kc o d e s ，简称为l d p c 码) 的诞生和发 展使人们更加接近这一目标。结合现有的理论成果和实践经验，设计性能优良 且编译码复杂度低的l d p c 码是近年来人们研究的热点问题。本文对l d p c 码 围长进行了深入的研究，在以下几个方面获得了研究成果： 1 介绍数字通信系统的基本组成、信道编码技术的研究进展、加性高斯白噪 声信道模型及准循环l d p c 码拟循环l d p c 码( q u a s i c y c l i cl d p cc o d e s ， 简称为q c l d p c 码) 的研究现状。 2 研究l d p c 码的结构、介绍l d p c 码的校验矩阵的t a n n e r 图表示、校验 矩阵的围长。 3 总结了准循环低密度校验码关于围长的一些定理和性质，最后以表格的形 式给出了前人关于在给定围长时矩阵的最小扩张阶数的结论； 4 发展了一种贪婪搜索算法，极大的改进了前人得到的矩阵扩张阶数。利用 这种算法得到的一些性能较好的码字，最后对这些码字进行了仿真实验。 利用和积译码算法这种并行的有利于硬件实现的迭代译码算法，在加性高 斯白噪声信道中用b p s k 调制，译码性能曲线越来越趋近于s h a n n o n 限， 并且不会出现误码平层。 5 介绍了l d p c 码中平衡环的概念及定义，给出了平衡环的统一形式，指出 了如何在矩阵中找到平衡环的方法。 关键词：低密度校验码，准循环低密度校验码，t a n n e r 图，围长，环，贪婪算 法，平衡环 a b s tr a c t a c h i e v i n gr e l i a b l ec o m m u n i c a t i o na p p r o a c h i n gs h a n n o n sc a p a c i t yl i m i ta t e f f e c t i v ep o w e rc o s ti st h eu l t i m a t eo b j e c to fm o d e r nc h a n n e lc o d i n gt e c h n i q u e i ti sp o s s i b l et oc o m ec l o s et ot h eo b j e c t s i n c et h ed i s c o v e r ya n dt h ed e v e l o p m e n t o 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 e s c o m b i n i n gt h ee x i s t i n gt h e o r ya n d p r a c t i c a lr e s u l t s ，c o n s t r u c t i o n so fl d p cc o d e sw i t he x c e l l e n tp e r f o r m a n c ea n d l o we n c o d i n gc o m p l e x i t yh a v eb e e nr e s e a r c hf o c u s i nt h i sd i s s e r t a t i o n ，t h eg i r t h o fl d p cc o d e sa r ei n v e s t i g a t e d 。t h em a i nf r u i t sa r es u m m a r i z e da sf o l l o w s ： 1 w ei n t r o d u c et h eb a s i cc o m p o s i t i o n so fd i g i t a lc o m m u n i c a t i o ns y s t e m ， t h ed e v e l o p m e n to fc h a n n e le n c o d i n gt e c h n i q u e ，t h em o d e lo fa d d i t i v e g a u s s i a nw h i t en o i s ec h a n n e la n dc u r r e n tr e s e a r c hs i t u a t i o no fq u a s i c y c l i c l d p c ( q c l d p c ) c o d e s 2 w ei n t r o d u c et h es t r c t u r eo ft h el d p cc o d e s ，t h et a n n e rg r a p hr e p r e s e n t a t i o na n dt h eg i r t ho fl d p cc o d e s 。 3 w es u m m a r i z es o m ei m p o r t a n tt h e o r e m sa n dp r o p e r t i e sa b o u tt h eg i r t ho f l d p cc o d e s ，a n dp r s e n tt h ef o r m e rr e s u l t sb yt a b l e s ，i nw h i c ht h em i n i m a l o r d e ro fc i r c u l a n tp e r m u t a t i o nm a t r i c e st oa c h e i v eg i v e ng i r t ha r eg i v e n 4 w ed e v e l o pag r e e d ys e a r c ha l g o r i t h mw h i c hg r e a t l yi m p r o v et h ef o r m e rr 争 s u l t so fm i n i m u mm a t r i xe x t e n s i o no r d e r w eg e ts o m ec o d e sb yu s i n gt h i s a l g o r i t h m s i m u l a t i o nr e s u l t sp r e s e n tf o rt h e s ec o d e s u s i n gb p s km o d u l a t i n gi na d d i t i v eg a u s s i a nw h i t en o i s ec h a n n e l ，t h ec h a r a c t e r i s t i cc u r v eo f d e c i p h e rh a s t e n sa n db o r d e r so ns h a n n o n sl i m i tm o r ea n dm o r e ，a n dw i l l n o ta p p e a re r r o rf l o o r 5 w ep r o p o s et h ec o n c e p ta n dd e f i n i t i o no fb a l a n c e d c y c l e s ，p r o v i d eau n i f o r m l v扬州大学硕十学位论文 f o r mo fb a l a n c e d c y c l e s ，p o i n to u tt h ew a yt of i n db a l a n c e d c y c l e si nt h e p a r i t y - c h e c km a t r i x 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 kc o d e s ，q u a s i c y c l i cl o w - d e n s i t yp a r i t y c h e c kc o d e s ，t a n n e rg r a p h ，g i r t h ，c y c l e s ，g r e e d ya l g o r i t h m ，b a l a n c e d - c y c l e s 扬州大学学位论文原创性声明和版权使用授权书 作者： 题目： 院系： 学位： 王进利 低密度校验码的围长提升研究 数学科学学院 硕士 日期：2 0 0 9 年5 月 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工 作所取得的研究成果除文中已经标明引用的内容外，本论文不包含 其他个人或集体已经发表的研究成果对本文的研究做出贡献的个 人和集体，均已在文中以明确方式标明本声明的法律结果由本人承 担 作者签名：兰望左：1 签- 7 - 日期：丛坌! ：星 j 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交学位论文的复印件和电子文档， 允许论文被查阅和借阅本人授权扬州大学可以将学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文同时授权中国科学技术信息研究所 将本学位论文收录到中国学位论文全文数据库，并通过网络向社 会公众提供信息服务 作者签名：墨叁叠i 签字目期：丛雩- 乙丑一 ( 本页为学位论文末页如论文为密件可不授权，但论文原创必须声明) 毕 名期签日师字导签 1 绪论 1 1数字通信系统的组成 如今，通信已经渗透到我们日常生活的每一个角落，这可以很容易的从许 多方面发现：如我们手中的电话、办公室和家中的电脑、报纸等等。最基本的通 信意味着通过一系列过程从一点向另一个点传输信息。 通信真正地成为一门学科是在1 9 4 8 年。在s h a n n o n 发表的著名论文通信 的数学原理1 1 中，他从研究通信系统的实质出发，对信息做了科学的定义，并 进行了定性和定量的分析，在论文中给出一个统一的通信系统模型。他的模型 分为五个部分： 1 信源 顾名思义，信源就是产生消息和消息序列的源。它可以是人、生物、机器 或其他事物。它是事物各种运动状态或存在状态和集合。信源的输出是消 息，消息是具体的，但它不是信息本身，消息携带着消息，消息是信息的 表达者。 2 编码器 编码是把消息变换成信息的措施，而译码就是编码的反变换。编码器输出 的也是适合信道传输的信号，信号携带着消息，它是消息的载荷者。 3 信道 信道是指通信系统把载荷消息的信号从发射者传输到接收者的媒介或通 道。在狭义的通信系统中，它可能是电缆、无线电波或光纤。 4 译码器 译码就是编码的反变换，把信息从信号中重构出来。 2扬l i 大学硕十学位论文 5 信宿 信宿就是消息传输的目的地。 上述的通信系统可以用图1 1 来表示。在本文中，我们仅考虑编码器到译码 器的这两个过程，即信道编码部分。 图1 1 ：数字通信系统的模型 s h a n n o n 在通信的数学理论中除了给出了统一的通信系统模型外，还 用概率测度和数理统计的方法系统地讨论了通信的基本问题，得出了几个重要 而带有普遍意义的结论。其中之一是著名的信道编码定理，即对任意一类信道， 都存在着一定的信道容量，记做c 。它是信道的最大极限传输能力。只要信息 的传输速率低于信道容量，就必然存在一种编码方式，使得信息出现差错的概 率随码长的增加趋于任意小；反之，当信息传输速率超过信道容量时，则不存在 这样的编码方法。它给出了特定信道上信息传输速率的上确界。 定理1 1 1 ( 信道编码定理【1 】) 任意离散无记忆平稳信道存在信道容量c ，对预 期的任一数据速率r 0 ，都存在编译码器，以保证该 信道中速率为r 的数据传输具有小于p 的译码错误概率。 信道编码定理指出，在有扰信道中，只要信息传输速率小于信道容量，就 有可能实现任意可靠的信息传输。这个存在性定理告诉我们可以以接近信道容 量的数据传输速率进行通信。但遗憾的是该定理采用的是非构造性的证明方法， 其中并没有给出逼近信道容量的具体编译码方法。 王进利低密度校验码的同长提升研究 3 1 2低密度校验码的提出、发展和现状 自信道编码理论提出以来，如何构造一个逼近信道容量限的实用好码成了 众多学竞相研究的课题，并逐渐形成信息论的一个重要分支信道编码理论。五 十多来，人们构造实用好码的探索基本一卜是按照香农所提m 的基本条件的后两 条为主展开的。 1 9 6 2 年，g a l l a g e r 在他的博士论文l o wd e n s i t yp a r i t yc h e c kc o d e s 2 中 提出了二元正则l d p c 码。g a l l a g e r 证明了这类码具有很好的汉明距离特性， 经过迭代译码可以获得接近香农限的性能，但限于当时的计算能力，l d p c 码 被认为不是实用码，在很长一段时间没有受到人们的重视。 1 9 8 1 年，t a n n e r 3 首次提出用图的模型描述线性分组码，将线性分组码的 校验矩阵用二部图( t a n n e r 图) 来表示。 1 9 9 6 年，m a c k a y 和n e a l 4 利用随机构造的t a n n e r 图来研究了线性分组码 的性能的时候重新发现了l d p c 码。他们发现采用和积译码算法的正则l d p c 码具有与t u r b o 码相似的译码性能，在码长较长时性能甚至超过了t u r b o 码， 这一结果引起了信道编码界的极大关注。 在l d p c 码的构造中，校验矩阵日不仅决定了l d p c 编码的复杂性而且 决定了l d p c 码译码复杂性。校验矩阵的构造可以分成两个大类：随机构造矩 阵和结构化构造。g m l g e r 、m a c k a y 构造的校验矩阵都是随机生成的，虽然纠 错性能好，但由于校验矩阵的随机性，编码的复杂度比较高，而且要存储大量的 数据。结构化校验矩阵可以分成两个主要的类别。第一种是基于有限几何学的， 第二种是基于循环置换矩阵的。在码长较长的情况下，随机或伪随机的构造方 法构造的非规则l d p c 码在效果上接近了加性白色高斯信道( a w g n ) 的理论极 限值。一般来说，这些码比代数方法构造的l d p c 码的性能要好。而另一方面， 在中等长度( 几千比特左右，比特率为1 2 ) 的l d p c 时，情况截然相反。这种 长度下非规则构造方法不比规则构造方法要好，基于图或代数的构造方法都比 随机构造方法要好。近年来有多种新的方法提出如，何善宝等人 5 提出的利用 循环差集的方法。z l i u 6 提出的利用多边形构造l d p c 码，f a nz h a n g 等人 提出的3 d 格的方法 7 】以及1 9 9 7 年开始出现的量子码 8 】， 9 ， 1 0 】， 1 1 】等。 g a l l a g e r 也给出了一种所需的资源和时间复杂性与码长呈线性关系的信息 4 扬州大学硕士学位论文 传递的算法。近来的研究结果表明，非规则的l d p c 码的译码的复杂性也与码 长成线性关系f 1 2 1 。由于非规则的l d p c 码可以很好的利用变量节点与校验方 程之间的关系，因此可以在译码的时候达到很好的效果。一些作者证明了精心 设计的规则码可以有效的解码，其性能可以在不同信道各种码率下接近香农 限 1 3 】， 1 4 】， 1 5 】。l u b y 1 6 】等人设计的非规则l p d c 码可以达到删除信道的信道 容量。r i c h a r d s o n 和u r b a n k e 发明了密度进化的方法来分析在二进输入对称信 道下置信传播算法译码的性能，他们还最优化了二进删除信道和二进输入加性 白噪声( b i a w g n ) 下的码字 1 4 】。h o u 等人 1 7 1 在瑞利衰弱信道中优化了非规 则l d p c 码并证明了l d p c 码可以达到极好的性能，优化后的码字甚至能在 瑞利相关衰弱信道中比t u r b o 码拥有更好的性能。鉴于l d p c 码的译码很好 的利用了变量节点与校验方程之间的信息，即使在不知道信道信息的情况下， l d p c 也能达到非常好的性能。c , u o p 8 等人为瑞利衰弱信道提出了l d p c 一 辅助块码调制( l d p c - a s s i s t e db l o c k c o d e sm o d u l a t i o n ，l d p c b c m ) 也可以比 t h r b o 网格调制的性能要好。l u l l 9 等人提出了一种空时编码( s t c ) 的多输入 多输出( m i m o ) 的正交频分复用( o f d m ) 的系统也是基于l d p c 码。这种系 统能比一般的空时系统要好得多，这种系统的另外一个好处就是编译码的复杂 度比t u r b o 码低得多。 1 3 本文内容安排 本文将分成一下几个章节：第二章介绍准循环l d p c 码的概念，以及一些 重要的定理，并介绍了如何利用循环矩阵的扩张的方法并消除小围长来构好码； 第三章介绍平衡环的定义、其最短平衡环的最小矩阵表示以及如何找到所有的 平衡环，最后对全文内容进行总结。 2 准循环l d p c 码的构造 近年来，人们提出了很多通信容量接近信道容量的l d p c 码。但其中的大 多数码的编码的复杂度非常高，这就要求我们设计出高效编码的l d p c 码。而 q c l d p c 码由于其特殊的准循环结构，这种码与用其它方法构造的码相比具 有很大优越性：一是这种码可用简单线性移位寄存器完成编码：二是这种码只 需存储校验矩阵的指数矩阵，可节约很多存储空间【2 0 。 l d p c 码的最小环长是影响其译码性能的关键因素之。本文致力于提高 l d p c 码的围长来提高其译码的性能。 2 1准循环低密度校验码的介绍与定义 2 1 1环和t a n n e r 图 l d p c 码的校验矩阵日可以与称为t a n n e r 图的二部图相对应。 设校验矩阵 h 4 52 所对应的t a n n e r 图如图2 1 所示。 11 01 01 10 图2 1 ：l d p c 码的校验矩阵与t a n n e r 图 上面的实心节点是变量节点，各对应一个比特或者是校验矩阵中的一列； 下边的空心节点是校验节点，各对应一个校验方程或者是校验矩阵中的一行。 0 1 1 1 0 0 1 1 0 1 0 1 6 扬州大学硕：学位论文 当某一比特包含在某一校验方程中即校验矩阵相应的位为1 时，对应的变量节 点和校验节点之间存在连线。对于每个节点与之相连的边数称为这个节点的度 数。这种二部图可以比较直观地表现l d p c 码的译码过程。 t a n n e r 图中的环是指连接变量节点和校验节点的起始和结束于同一节点 并且不重复包括中间同一节点的路径，t a n n e r 图的围长是其最短的环的长 度 2 1 】。 在图2 1 中，k _ g k _ 瓯_ k 构成一个长度为4 的环，_ g _ k _ 岛_ k _ g _ 构成一个长度为6 的环。任何t a n n e r 图的围 长都是偶数并且大于等于4 。 2 1 2 q c l d p c 码的基本介绍 ( zl ) 一正则准循环l d p c 码可用列重恒为j ，行重恒为l 的校验矩阵日 来定义。当构造一个码长为n = l p 的( l ) 一正则准循环l d p c 的校验矩阵 时，通常把p p 阶的循环置换矩阵记成一个元素以简化这含校验矩阵 2 2 】， 2 3 h = i p o ，0 i m 。o i v ：一1 ，0 i v o ，1 i m ，1 i p j 一1 1 其中p j ，z ( o ，1 ，2 ，p 一1 ，。) ，0 歹j 一1 ，0 l l 一1 ，且 i = 010 0 0 1 0 00 100 0 0 ： 1 0 l l 一 一 一 l 工 工 ； l p p t j 王进利低密度校验码的同长提升研究 7 不失一般性，我们可以令日为 h = i qi q i op 1 1 i oi p j 1 1 ( 2 1 1 ) 为了后面章节的叙述方便，我们再引入一些记号： 1 ) 母矩阵：一个jxl 阶的的二进制矩阵m ( 日) 通过置换0 和1 为循环置 换矩阵可以唯一得到日，那么我们把这个m ( 日) 称为日的母矩阵。 2 ) 指数矩阵：我们把矩阵 e ( h ) = p o ，0 p i ，0 p j 一1 o p o ，l 一1 p i ，l 一1 p j 一1 ，l 一1 称为式( 2 1 1 ) 中校验矩阵日的指数矩阵。 3 ) 循环置换矩阵：乃，z 表示，o 个循环置换矩阵，相乘后得到的矩阵，o 为p p 阶单位矩阵，j 为p p 阶全零矩阵。 4 ) 矩阵的复合：日可以由指数矩阵e ( h ) 与循环置换矩阵，的复合得到， 则校验矩阵日可表示为h = e ( h ) oi 。 5 ) 块环：母矩阵t a n n e r 图中长为2 佗的环为块环。若舰表示该长为2 n 的 块环中的点，则该块环可以由有序序列m o _ 尬一_ m 2 。一1 _ m o 来表 不o 6 ) 指数链：母矩阵m ( h ) 中长为2 佗的块环所对应的有序数组 ( p o ，p i ，p 2 几一1 ) 称为该块环的指数链。其中置换矩阵p 的指数矶对应块环中第i 个点尬。 2 2 关于q c l d p c 码围长的理论上界 2 2 1l d p c 码的围长的定义 若( p j o f 0 ，岛“。，乃“l 一，功。_ h f t - ，p j o 一，) 是一个长为2 i 的指数链，则这个 纳m 阻 8 扬州大学硕士学位论文 指数链会导致日中一个长为2 i 环的充要条件为 由上述环的定义，我们可以得到以下结论： 定理2 2 1 ( 2 2 】) 校验矩阵日的围- 长a - l - i f - l - 2 ( + 1 ) 的充要条件是 其中l m i ，0 j j 一1 ，0 l l 一1 。 由定理2 2 1 可以得到一个推论。 ( 2 2 1 ) 推论2 2 2 对于j = 2 的准循环低密度校验码( q c - l d p c ) 而言，围长只可能 是g = 4 i 。 2 2 2 关于围长的结论 a 围长大于等于6 的情形 以下的定理给出了围长大于等于6 的一个必要条件： 定理2 2 3 围长大于等于6 的一个必要条件是岛“。p j 。f l ，j l 歹2 且 1 1 ，f 1 p j l ，z 2 ，1 产1 2 。 由定n 2 2 3 就可以得到9 6 时，循环置换矩阵阶p 的一个下界。 推论2 2 4 i f - 9 1 0q d l d p c 码的围长大于等于6 的一个必要条件是p l 。 以下的定理是由f o s s o r i e r 在文献 2 2 1 中给出并证明的，但他的证明有错误。 经他人指出后，他在 2 4 d p 给出了补充证明。 定理2 2 5 ( 2 2 1 1 2 3 1 ) 正则q d l d p c 码的围长大于等于6 的一个必要条件 是当l 为奇数时，p l ；当l 为偶数时，p l 十1 。 p dom0 l i k 蚪 融 一 k办 “脚 王进利低密度校验码的同长提升研究 9 b 围长大于等于8 的情形 以上的方法可以直接用于g 8 的情形 定理2 2 6 ( 2 2 ) 正则q c - l d p c 码 围长大于等于8 的一个必要条件是 殇1 ，z 1 岛2 ，f 2 ，0 j l 歹2 ，0 葡世器赫潜潜幂娜争哔岽琴潜 王进利低密度校验码的同长提升研究1 3 一般的随机算法重复度很大，得到较小p 的概率很低。贪婪搜索算法是通 过检验p 阶扩张矩阵的是否找到满足定理2 2 1 的条件的指数矩阵，这种算法 很大程度上避免了多次重复，能很快的得到最优或较小的p 。 a l g o r i t h m3 贪婪搜索算法 1 ：初始化指数矩阵e ( g ) 所有的点为o ，并将第0 行和第0 列的全部点加入到 已取点集中； 2 ：找出m ( h ) 中所有的环； 3 ：在未取点中取出一个点( 歹，z ) ； 4 ：找出的所有过( j ，2 ) 且其他点在已取点集中的块环； 5 ：求出乃，l 的取值范围，即满足( 功。，f 。一胁。+ h z 。) 0 ( m o d p ) ； 6 ：对阻z 的所有可能取值，均执行7 ； 7 ：更新指数矩阵e ( h ) 中胁，f 的值为岛，l 的可能取值z ： 8 ：复制现有取点集到临时的已取点集，在临时的己取点集加上( 歹，f ) 点； 9 ：若临时的已取点集不为全点集，则执行3 。 2 6 贪婪搜索算法的性能分析 以下给出了利用贪婪搜索算法用c + + 编程以及进一步的利用高性能计算 机长时间运算搜索得到的最优结果。逐步减小预期p 的值，直到p 达到理论最 小值，或较长时间计算使p 逼近最小值。f o s s o r i e r 在文献2 2 】中给出了利用计 算机搜索的方法得到的围长大于等于6 和围长大于等于8 的p 的一些最小值。 这里要指出的是在( 4 ，8 ) 和( 5 ，8 ) 时，f o s s o r i e r 搜出的p = 9 即使用遍历搜索算 法，也是无法找到合适的指数矩阵。在围长大于等于8 的p 的最小值，贪婪搜索 算法较大的缩小矩阵最小扩张阶数的值，分别见表2 2 和表2 3 。 下面为我们利用贪婪搜索法得到的一些指数矩阵的结果，再利用矩阵的复 合便可以得到相应的校验矩阵。 准循环低密度校验码最小环长g 6 1 4 扬州大学硕：1 j 学位论文 卜_ ) b 0 亡l 肆 岽 琴 c 九a aa c 丌c 兀c 兀 - 4c bo qq - 4 一 k - j o oo k i - j o oo l - o - 一 l 一k 一 l j l j_- j - 一 j- j - 4- j- j 时时 l 一 l l c o0 0 l l j- - j c 兀aa k l j c n明 l 一 - - j o - 一 l j n、l l jl 。o o o - 一 l oq o h 3卜3 k o - 一 卜)卜3 k ol j 时h 3 时时 卜3时 厶3 h )时 c 兀c 九 t 、3卜3 c 丌九 卜)时 j- - 4 时 时 - 4- j 时时 。o nh 0 q )o c oc o l jk - j c o0 0 - j - 一 c oc o c oc o c )0 0 0 0 c - o 啦k c 八 c b 、j o 。 q o l o o l l j l j 时 l c o l a - _ c 九 k o b l j 、j l j o o - j o b 3 o h ) l 一 卜3 时 t 、3 。 b 3 a 时 c 丌 b , 9 h _ ) _ 时 0 0 时 o o j o c o l _ c o 时 c o c o 望器圃术汁吨嘏咄赫潜高幂如 王进利低密度校验码的同长提升研究1 5 今 34567891 01 11 2 391 3 1 8 2 1 2 5 3 23 74 15 0 表2 3 ：得到的围长大于等于8 指数矩阵最小扩张阶数 1 当( zl ) = ( 5 ，1 4 ) ，p = 1 5 时，检验矩阵h 的指数矩阵e ( h ) 如下： e ( h ) = o 坞7 2 挖 o 他1 4 1 o n m 6 7 0 加3 8 坞 0 9 6 m 2 0 8 4 7 6 0 7 坞挖m 0 6 n 9 3 0 5 挖m 加 0 4 8 l 5 0 3 5 n 9 0 2 1 埒4 o l 2 3 n) d ) d ) 1 6扬州大学硕：卜学位论文 p 婶 的 趣 h o o o o 嚣o _ o 墨品1 , 0 。 茜器o 长霉a 。 qo a 誉ao 譬gq 。 接口o 高o 。骂吕。 誉a = o ”= 磊。 吕譬晶。 譬若墨o = 吕。 譬= 高。 昌笛；。 c o 吕磊。 口g 茜。 驾譬g 。 若端譬。 譬一芯。 留器o = n 鐾。 茹c ，i 臻。 q 磊譬。 器墨骂。 一譬笛。 接器譬o ；= 答。 器譬譬o = 譬恩。 咔 ，、 一 瞽器一o o 时。 苫基o 譬ao ；c 九o x 吕oo 写芯qo 祷时0 0o p = c 。0 a 吕go q舡=o n 吕高o = 暑i r a , o 譬p墨o g 茹吕0 若q高。 墨墨= 。 磊接。c o o 夏蹬茜o 0 0 c 。瞽。 器= 罡。 吕0 0 。譬 怒。 器o 。明注0 a o按0 c 九。c o 譬o i _ j 咔 ，、 - 一 詈了一 (4吣qy毽i吣q 4。藤器苗幂鱼墨手旨肄温幂两一趣一昔爿 i(4)1毽i墨。薜嚣高蒋屯器赫嫦潜幂圆一雹一甘叫。 千进利低密度校验码的同长提升研究 1 7 准循环低密度校验码最小环长g 8 4 当( zl ) = ( 3 ，5 ) ，p = 1 3 时，检验矩阵h 的指数矩阵e ( h ) 女n - - f 5 ，当( zl ) = ( 3 ，8 ) ，p = 2 5 时，检验矩阵h 的指数矩阵e ( h ) 如下： 6 当( z 三) = ( 3 ，9 ) ，p = 3 2 时，检验矩阵日的指数矩阵e ( h ) 如下： 7 当( zl ) = ( 3 ，1 0 ) ，p = 3 7 时，检验矩阵h 的指数矩阵e ( h ) 如下： 8 当( zl ) = ( 3 ，1 1 ) ，p = 4 1 时，检验矩阵h 的指数矩阵e ( h ) 如下： 9 当( zl ) = ( 3 ，1 2 ) ，p = 5 0 时，检验矩阵h 的指数矩阵e ( h ) 如下： 1j 0 n 6 o 7 5 0 3 4 0 1 m 0 0 0 _。l = 日e 1j o 均90 竭7o 璩殂 0 m 您 0 5 毖 0 3 娼 0 1 2 o 0 o _。l = 日e 1j 0 勰丝 0 卯毖o 10 坫60 埒殂 0 7 幻 0 3 5 0 2 m 0 o o -。l | 1 日 酞 1，j 0 弱7 o 幻4 o 螺驼o 硌30 您弱 o 9 孔 o 8 5 o 2 n 0 l 垮 o o 0 。l = 玎 ，、 g 1，j o 鼹4 0；5弓30 憋卵0 均盟o 6 0 璩嬲 o 抡娩 0 5 堪 o 2 殂 o 1 o o 0 -。l l l 巧 ，fk g 0 2 均 0 鹊媚o 髂嚣o 鹳u o 丝 o 钾 0 3 8 0 绣鼹 0 四0 毖殂 o 5 筋 o o 0 。l = 日 ，t g 1 8扬州大学硕? 卜学位论文 和积译码算法是一种并行的有利于硬件实现的迭代译码算法，下面在加性 高斯白噪声信道中b p s k 调制下用和积迭代译码算法，最大迭代次数为1 0 0 ， 借助计算机模拟用完备循环差集构造的q c l d p c 码，译码性能曲线越来越趋 近于香农限，并且不会出现误码平层f 6 1 0 图2 2 是我们由( 8 ) ，( 9 ) 中的指数矩阵构造出的长度分别是4 5 1 和6 0 0 的正 则( 3 ，1 1 ) 一l d p c 码和正则( 3 ，1 2 ) 一l d p c 码( 最小环长夕8 ) ，在加性高斯白 噪声信道中的误比特率( b e r ) 性能曲线比较图，其中它们的码率均大于0 7 3 3 ， 可以看到它们的性能良好，在信噪比4 5d b 时，误比特率可达1 0 _ 。 叱 。 o 匕 w 怠 图2 2 ：比特率性能曲线图 3 q c l d p c 中平衡环的统一形式 在上一章节中，我们利用多种方法构造的准循环的l d p c 码，并且这些码 字都可以具有较大的围长。 3 1平衡环的发展 利用循环置换矩阵扩张的方法，我们可以构造围长比较大的l d p c 码， 但若要进一步的提升围长就不可能了。因为f o r s s i o r 和t a n n e r 都指出传 统q c l 。p c 的围长不可能超过1 2 ，因为有母矩阵中存在 ： 和 ：小 s u l l i v a n 【2 8 等人先对衡环进行了研究。m y u n g 等人在给出了如图3 1 所示 的胶囊型平衡环 2 9 】，后来又给出了如图3 2 所示的哑铃型平衡环 3 0 。 图3 1 ：胶囊型平衡环 为了进一步提高l d p c 码的围长，我们希望找到所有的最短平衡环，然后 利用仿射变换或一般置换消去平衡环的方法来提升围长。所以在一个矩阵中找 到所有的最短平衡环就非常有必要了。 下面我们来介绍一些重要的定义和定理。 ， 广 ； 、j 厂、 2 0 扬州大学硕：卜学位论文 广”、。1 i、 ， ，、 ， 图3 2 ：哑铃型平衡环 3 2平衡环的定义与定理 一个二进制的矩阵中非零的元素称为m 的点。若两个点在同一行或同一列， 我们称为两个点相匹配。对于任意的集合qcm ，一个点列，y 是一条路指它满 足以下的两个条件： 1 任意两个连续的点是不同的，而且是相匹配的。 2 被一个点分隔开的两个点是不匹配的。 点列7 上点的个数称为长度，并记为。为了简单起介，我们把d 看成为长度 为0 的空列，r ( q ) 代表了q 中所有路径的集合。 下面的引理可以很显然的得到。 引理3 2 i 以下是关于最短路的一些结论： j 任意集合q 中的点在m 中，则r ( q ) 中的最短环一定是最简的。 2 若，y r ( q ) 不是最简路，则一定存在着路饷，y 1 ，他，使得7 = 1 7 0 7 2 ，且 怕是最简路。 3 假设q 1 与q 2 是m 中没有交点的两个点集，若有一条路从q 1 出发，终止 于q 2 ，令日7 p 2 就是其中的一条最短路，则7 就是一条最短路且7 中的点 除首未两点外，都不和q 1uq 2 中的点相匹配。 彳假设q 是m 中的一个非空点集，若有一条首未都在q 中的r ( m ) r ( q ) 中 的路，令尸1 7 岛就是其中的一条最短路，则，y 就是一条最短路且，y 中的点 除首未两点外，都不和q 中的点相匹配。 王进利低密度校验码的围长提升研究2 1 我们再给出平衡环存在的充要条件。 定理3 2 2 矩阵m 中存在平衡环当且仅当以下的条件至少有一个被满足： ! m 有三条长度大于零简单路7 1 ，能，7 3 ，7 1 筲1 ，7 2 7 ；- 1 ，佻百1 是简单路。 2 m 有三条路7 0 ，7 1 ，7 2 和两个点p l ，恳，且r 7 1 ，岛他是一个简单环， 7 1 7 0 7 2 是简单路。 定理3 2 3 矩阵m 中存在平衡环当且仅当m 中存在一条最简路7 和两个点p 1 ，恳， 使得只7 ，7 岛都不是最简路。 引理3 2 4 对于整数a ，b ，c 满足 m a xa ，6 i 【a + b + c 一1 ) 2 j 我们定义矩阵s ( a ，b ，c ) = ( s t j ) j 若a + b + c = 2 n + 1 为奇数，s ( n ，b ，c ) 是佗行n + 1 列的矩阵 i 1 0 歹一i 1 或_ ( 口，1 ) ，( n ，他+ 1