（通信与信息系统专业论文）高性能非规则ldpc码的研究.pdf

( - c l a s s i f i e di n d e x ： u d c ： 4d i s s e r t a t i o nf o rt h ed e g r e e o f m e n g r e s e a r c ho n h i g hp e r f o r m a n c e i r r e g u l a rl d p cc o d e s c a n d i d a t e ：j i a n gx i s u p e r v i s o r ：p r o f e s s o rz h a od a n f e n g a c a d e m i cd e g r e ea p p li e df o r ：m a s t e ro f e n g i n e e r i n g s p e c i a l t y ：c o m m u n i c a t i o na n di n f o r m a t i o ns y s t e m s d a t eo fs u b m is s i o n ：m a r c h ，2 0 1 0 d a t eo f0 r a le x a m i n a t i o n ：m a r c h ，2 0 1 0 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y a k l i , 继l 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：互奄 日期： 纠。年月7 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ： 善年 日期： 劬f o 年月f 7 日 导师( 签字) ： 油f 口年月7 7 k l 二 继， 哈尔滨t 程大学硕十学位论文 摘要 l d p c 码在近些年越来越受到人们的重视，不仅各种通信标准对l d p c 码青睐有加，纷纷将其纳入自己的信道编码方案：l d p c 码在军事和民事的 应用领域也引起了人们的广泛关注，本文试图根据水声信道的特点提出一 种l d p c 码联合扩频技术的水声通信系统方案。 论文的工作首先集中在对二进制l d p c 码校验矩阵构造方法的研究， 提出了l d p c 码的图论和s c 构造两种算法；然后研究了多进制l d p c 码的 译码算法，主要分析了多进制l d p c 码的对数域译码算法和基于二进制思 想的b p 译码算法。 最后重点研究了l d p c 码在水声通信中的应用：通过对水声信道环境 的分析，建立信道模型和“l d p c + 直接序列扩频+ b p s k 的通信系统模型， 并通过对不同码长，码率，译码迭代次数，扩频序列长度的仿真确定该通 信方案的参数；最后与r s 码和卷积码为信道编码的水声通信系统方案进行 了仿真性能对比，结果表明“l d p c + 直接序列扩频+ b p s k 水声通信模型 比其他编码水声通信方案可以更有效得抵抗水声通信中的多径衰落，多普 勒频移，时延等因素的影响，具有更好的系统性能。 关键词：l d p c 码；多进制译码；水声通信 e x t e n s i v ea t t e n t i o ni nt h em i l i t a r ya n dc i v i la p p l i c a t i o n s t h i sp a p e ra t t e m p t st o p r e s e n tak i n do fa c o u s t i cc o m m u n i c a t i o ns y s t e mw h i c hh a sb o t hl d p cc o d e s a n ds p r e a ds p e c t r u mt e c h n o l o g y t h ep a p e rf i r s tf o c u s e so nt h ec h e c km a t r i xc o n s t r u c t i o no fb i n a r yl d p c c o d e s ，p r o p o s i n gl d p cg r a p ht h e o r ya n ds cl d p c ；t h e np a p e rs t u d i e st h e d e c o d i n ga l g o r i t h mo fn o nb i n a r yl d p cc o d e s ，m a n l ya n a l y z i n gd e c o d i n g a l g o r i t h mo nt h el o g d o m a i na n da l g o r i t h mb a s e do nb i n a r yt h i n k i n go f t h eb e f i n a l l yp a p e rf o c u s o nt h e a p p l i c a t i o no fl d p cc o d e s i na c o u s t i c c o m m u n i c a t i o n ：t h ec o m m u n i c a t i o ns y s t e mm o d e l l d p c + d s s s + b p s k c a l l b eb u i l tt h r o u g ht h ea n a l y s i so fa c o u s t i cc h a n n e l ，a n dt h e ns i m u l a t i o no f d i f f e r e n tc o d el e n g t h ，c o d er a t e ，d e c o d i n gi t e r a t i o n sa n ds p r e a d i n gs e q u e n c e l e n g t hi sn e e d e dt od e t e r m i n et h ep a r a m e t e r so ft h ep r o g r a m t h r o u g ht h e p e r f o r m a n c ec o m p a r i s o na m o n gl d p cc o d e s ，r sc o d e sa n dc o n v o l u t i o n a l c o d e s ，w ec a ng e tt h ec o n c l u s i o nm a t “l d p c + d s s s + b p s k ”c o u l dh a v eam o r e e f f e c t i v er e s i s t a n c et om u l t i p a t hf a d i n g ，d o p p l e rf r e q u e n c ys h i f t ，d e l a ya n do t h e r f a c t o r si nt h ea c o u s t i cc o m m u n i c a t i o ns y s t e m k e yw o r d s ：l d p cc o d e s ；n o nb i n a r yd e c o d i n g ；a c o u s t i cc o m m u n i c a t i o n ， 咯 kl l ， 哈尔滨t 科人学硕十学何论文 目录 第1 章绪论1 1 1 课题研究背景1 1 2l d p c 码的发展现状2 1 2 1l d p c 码理论研究发展现状2 1 2 2l d p c 码实际应用发展现状5 1 3 论文结构安排7 第2 章l d p c 码基本原理9 2 1l d p c 码的定义及相关概念9 2 1 1l d p c 码的定义9 2 1 2l d p c 码的t a n n e r 图描述9 2 2l d p c 码的校验矩阵构造1 0 2 2 1l d p c 码的图论构造10 2 2 2l d p c 码的s c 构造1 4 2 3l d p c 码的编码算法16 2 3 1l d p c 码的编码原理16 2 3 2 基于高斯消去的直接编码方法16 2 4l d p c 码的译码算法17 2 4 1 置信传播算法( b p ) 1 7 2 4 2 对数域l o g b p 译码算法1 9 2 5 本章小结2 0 第3 章多进制l d p c 码2 l 3 1g a l o i s 域2 l 3 1 1g a l o i s 域定义2 l 3 1 2 6 f ( p ”) 的构造2 1 3 2 多进制l d p c 码的校验矩阵构造2 3 1 ； k ， f k ， 哈尔滨t 稃火学硕十学何论文 3 2 1 多进制l d p c 码2 3 3 2 2 基于矩阵分裂的q c 多进制l d p c 码构造2 4 3 3 多进制l d p c 码的译码算法2 5 3 3 1 对数域译码算法2 6 3 3 2 基于二进制思想的b p 译码算法2 9 3 3 3 译码算法的性能仿真31 3 4 多进制l d p c 码的e x i t 图分析3 2 3 5 本章小结3 6 第4 章l d p c 码在水声通信中的应用3 7 4 1 水声信道简介3 7 4 1 1 衰减3 7 4 1 2 噪声3 9 4 1 3 信噪比s n r 4 0 4 2 水声通信系统模型4 0 4 3 水声通信系统仿真4 3 4 3 1 不同码长的l d p c + d s s s + b p s k 系统方案比对4 3 4 3 2 不同码率的l d p c + d s s s + b p s k 系统方案比对4 4 4 3 3 不同迭代次数的l d p c + d s s s + b p s k 系统方案比对4 5 4 3 4 不同扩频码长的l d p c + d s s s + b p s k 系统方案比对4 6 4 3 5 不同编码方案的性能比对4 6 4 4 本章小结5 0 结论51 参考文献5 2 攻读硕士期间发表论文和取得的科研成果5 8 致谢5 9 l f 分： 哈尔滨。t ：科大学硕十学位论文 第1 章绪论 1 1 课题研究背景 3 g 时代的到来证明移动通信发展到了一个更为成熟的层次，信 道编码技术作为物理层通信的核心技术之一也越来越受到关注和重 视。无论是t d s c d m a 、w c d m a 、c d m a 2 0 0 0 标准中的卷积码、 t u r b o 码，还是i e e e 8 0 2 系列标准中的l d p c 码，都是为了更为有效 的检测和纠正出信道传输过程中产生的误码，以提高信息传输的可 靠性。信道编码技术不仅在民用通信领域中有不俗的表现，军用领 域中对信道编码技术的研究也在紧锣密鼓的进行，其中有代表性的 水声通信系统中早已将编码技术与高效率调制技术结合，使得在信 道环境恶劣的水下进行远距离可靠通信成为现实。 l d p c 码于l9 6 2 年提出，经过一段时间的沉寂，、近些年又引起 了人们的关注。l d p c 码再一次掀起编码界的热潮源于其可以逼近香 浓限的性能，通过理论研究可知1 3 7 1 ：码率为1 2 的l d p c 码，选择 b p s k 调制，其性能可与s h a n n o n 限仅差0 0 0 4 5 d b ，是目前的编码 中距s h a n n o n 最近的纠错码0 7 1 ：此外与t u r b o 码相比，l d p c 码具有 长码、高码率优势1 3 7 ；因此姗姗来迟的l d p c 码已被列为未来通信 领域重点备选的编码方案。 二进制l d p c 码的优良性能引起了人们对多进制l d p c 码的研 究和探寻，这种从理论上同样可以逼近香农限的好码可以更好的节 约带宽，提高数据传输率，但因为多进制l d p c 码是基于有限域g f ( q ) 的，因此随着g 的增大而引起的译码复杂度的骤增问题成为了阻碍多 元域l d p c 码发展的关键之一。 ， ， 性 哈尔滨t 稃人学硕十学位论文 1 2l d p c 码的发展现状 1 2 1l d p c 码理论研究发展现状 近几年对于l d p c 码理论的研究日趋成熟和完善，比较突出的 研究主要是针对l d p c 码校验矩阵的构造、译码算法等方面进行的， 通过仿真实验的验证，这些新兴的理论将会对l d p c 码的发展起到 很大的推动作用。对2 0 0 6 年至2 0 0 9 年具有代表性的l d p c 码理论 研究总结如下： 2 0 0 6 年，针对结构化构造q c l d p c 的性能不如随机构造l d p c 码，但随机构造l d p c 码又不利于硬件存储这一问题，x i a oy a n g ， l e e ，m o o nh o 提出了一种更优的q c l d p c 构造方法，利用索引 矩阵，增大了校验矩阵的环长，使得最小码间距离变大，可以得到 更好的误码率性能。 l d p c 码中存在的短环是影响l d p c 码性能的关键所在，通过分 析校验矩阵的t a n n e r 图中的短环形态，j u nf a n 等人提出了一种可以 有效判断短环分布带来影响的方法1 2 l ，这种方法可以有效的检测出随 机构造和结构化q c 构造中存在的短环。 g a b i d u l i n e 等人提出了一种基于矩阵置换的通用q c l d p c 码 构造方法【3 1 ，该算法可以构造不带4 环的校验矩阵，从而编码后可以 获得优异的性能，g a b i d u l i n e 同时也阐述了另一种通用的可以适用 于l d p c 码码群的构造方法。 l u j 和m o u r a j m f 提出了p s l d p c 码，一种可以获得任意大 的最小距离的规则l d p c 码 4 1 。这种码可以被设计成任意列重，并且 具有灵活的码率设计，通过仿真表明这种p s l d p c 码在高信噪比的 条件下性能优于随机构造的l d p c 码，并且减轻了地板效应。 c o l e c a 等人提出了一种中码长低误码率的规则l d p c 码构造方 法i ，】。该方法虽然同时适用于规则和非规则l d p c 码，但其特别适用 2 协 哈尔滨t 稃大学硕十学何论文 于规则 3 ，6 l d p c 中码长的情况。 k y u h y u kc h u n g 等人提出了一种改进的b p 译码算法 6 1 ，这种算 法主要针对的就是具有大量短环的l d p c 码。 2 0 0 7 年，a b e m a t s u 等人提出了一种可适用于任意码长的高码率 l d p c 码构造方法s c a r r a yl d p c 码【7 1 ，并对其在高斯白噪声信道下 进行了性能仿真，其结果表明：在高斯白噪声信道下，s c a r r a yl d p c 码比常规构造方法下的高码率l d p c 码具有更优异的性能。 k e l l e y c a 提出了一种基于树理论的l d p c 码构造方法1 8 1 ，这种 构造方法可以获得最小的伪码重，等于或几乎等于其最小距离，并 且迭代译码后的性能优异。在构造的过程中涉及列举出一个d 一规则 树和一个固定数目的层数，运用的是基于置换或相互正交的树算法。 r o n g h u ip e n g 等人提出了一种多进制l d p c 码的准循环构造方 法i9 1 。在构造过程中使用了循环消去理论以保证在构造校验矩阵的过 程中尽可能地避免短环产生，以减少低重量码字的生成，这种优化 后的并行稀疏码字称为p s e ，它由q c l d p c 码和一个简单的树码构 成，不仅可以进行线性编码，还可以显著地减少编码时间。 p i s h r o n i k h 等人提出了一种适用于二进制均衡无记忆信道的 l d p c 译码改进算法1 1 0 1 。 2 0 0 8 年，r e f a e y a h m e d a 等人将密度进化理论与译码算法相结 合i ，从e x i t 图的角度出发，对b p ，l o g b p ，m a x l o g b p 等译 码算法进行了比较，得出了对于规则l d p c 码在二进输入高斯信道 下的三种译码算法的性能依次为b p 最优，l o g b p 其次，m a x l o g b p 最末的结论。 y a nc u i 等人提出了一种新的结构化l d p c 码构造方法1 12 1 ，通过 检测校验节点的关联矩阵来避免构造过程中短环的产生，这种基于 图论中双向图理论的构造方法经仿真表明：对于达到1 0 3 误码率，可 以比随机构造p e g 方法节约0 1d b 。 知 分 哈尔滨t 程人学硕十学位论文 x uh u a 提出了一种基于o p t p s o 环长理论的q c l d p c 码构造 算法1 1 3 l 。这种算法不仅从性能上优于t a n n e r 图编码和阵列编码，并 且可以进行更加灵活的码长和码率设计。 r o u n h u ip e n q 等人对多进制l d p c 码在m i m o 系统中的应用进 行了研究1 14 ，并基于系统的角度将多进制和二进制l d p c 码从性能 和复杂度方面进行了对比。仿真结果表明，多进制l d p c 码系统的 性能表现甚至要优于二进制l d p c 码在i e e e 8 0 2 16 标准中的表现， 而且通过e x i t 优化的效果也好于二进制l d p c 码。 h a i y a nc a o 等人提出了一种适用于瑞利衰落信道的多进制 l d p c 码对数域迭代译码算法，并将这种算法与u s t m 调制技术相 联合1 15 1 。仿真结果表明这种方案性能优异，多进制l d p c 码与u s t m 调制联合的系统性能要比采用二进制l d p c 码情况下多出5 6 d b 的 编码增益。 z a h c e r s f 等人提出了一种有效的码率兼容r c l d p c 码，针对 半随机r c l d p c 码，z a h e e r s f 等人在文中也提出了基于截取和扩 展两种途径的系统构造算法 1 6 l 。对于应用了半随机r c l d p c 码的 a r q 系统，其性能明显要好于一般的规则l d p c 码a r q 系统。 k o b a y a s h i m 等人提出了一种利用g e 信道下的参数来设计非 规则l d p c 码的方法【1 7 l 。首先通过高斯分布下的密度进化，从变量 节点到校验节点的信息中获得精确的概率密度函数，然后利用g e 信道下的参数和概率密度函数一起完成非规则l d p c 码的设计。 m a t a r a c i o q l u t 等人针对非规则l d p c 码提出了一种性能优化设 计算法，该算法除了在编码和译码部分使用的是比特填充和置信传 播算法l i7 i ，还联合了微分优化技术，使得码的性能最大可能的提高， 经仿真论证这种优化后的非规则l d p c 码在码率为1 2 时可与信道容 量仅相差0 0 2 d b 。 c h i h y u a ny a n g 等人将l d p c 码与o f d m 调制技术相结合应用 4 k 哈尔滨- r n 大学硕十学何论文 于无线环境，在系统中尝试了将l d p c 码与双重格雷码联合，r s 码 与l d p c 码联合等编码技术，以达到优于传统l d p c 编码方案的目 的1 18 1 。仿真证明达到性能1 0 。时，r s l c m 系统可以节约o 4 d b 。 2 0 0 9 年，b o c h a r o v a i e 等人利用卷积码的思想提出了一种短 q c l d p c 码的构造方法 1 9 1 ，用修正后的b e a s t 算法找到卷积码和 l d p c 码的基矩阵的最小距离和环长，然后基于t b 卷积码有限几何 思想的l d p c 码就可以构造完成了。 b h a r d w a i v 等人提出了_ 种线性复杂度编码方法，这种方法将 t u r b o 码和l d p c 码的结构特点融合在一起称为t s l d p c 码 2 0 1 。这 是一种规则l d p c 码，其t a n n e r 图由两种树通过交织器组成。因为 限制了t u r b o 的t a n n e r 图结构，从而获得了线性编码复杂度。 应用于二进输入高斯白噪声信道( b i a w g n ) 的b p 译码算法需 要在接收端加入信噪比s n r 才可以获得最终的译码性能，为了避免 信噪比不匹配带来的性能下降，s a e e d i h 等人于2 0 0 9 年利用e x i t 图设计了一种非规则l d p c 码1 2 t i ，这种码即使在出现信噪比不匹配 的情况下性能也可以优于通常意义设计下的非规则l d p c 码。 s h e b l s 等人利用计算搜索算法根据误码率提出了一种l d p c 码 构造方法。这种针对校验矩阵的构造方法是逐列构造的1 2 2 1 ，并且要 考虑列重和环长的限制，构造后的校验矩阵可以改善l d p c 码的环 长和码率。 1 2 2l d p c 码实际应用发展现状 l d p c 码的发展不仅体现在其理论方面，对于l d p c 码的硬件实 现等实际应用发展也是很热门的研究方向。针对l d p c 的迭代译码 复杂度较高，硬件实现困难度大等特点，大量的专家学者提出了各 种利于硬件实现的算法和编译码器结构，现对近四年的l d p c 码实 际应用发展现状总结如下： 0 厶 哈尔滨丁稃人学硕十学何论文 2 0 0 6 年，g u n n a m k k 等人提出了一种基于o n t h e f l y 算法1 2 3 1 适用于q c l d p c 码的译码算法，这种算法可以有效地将译码器的信 息存储降低5 5 8 0 。 m o i n i a na b d i 等人将l d p c 码应用于无线数据传输f 2 4 l ，并对其 进行了充分的论证：l d p c 码的许多码长，码率，构造方法的组合编 码方案都很适用于无线信道。 2 0 0 7 年，b r a c k t 等人针对u w b 系统提出了一种名为u l t r a s p a r s el d p c 的新码1 2 5 1 ，并综合w i m a x ，w i f i 等译码器的特点提出一 种改进译码器，这种译码器的译码复杂度可以降低5 5 。 多进制l d p c 码是对二进制l d p c 码研究的一个扩展，从理论 上也证明了多进制l d p c 码具有比二进制更不俗的性能表现，但是 其编译码的复杂度却要比二进制l d p c 码高出许多，因此2 0 0 7 年， s p a q n o lc h r i s t a i n 等人利用f p g a 对多进制的两种译码算法进行了硬 件尝试 2 6 1 ，结果表明，其优异的性能表现是可以平衡由于进制数的 增大带来的额外的复杂度的。 2 0 0 8 年，y o n g m e id a i 等人提出了一种针对q c l d p c 码对最佳 迭代信息译码算法o m p 进行了改进，提出了一种部分并行o m p 译 码器结构1 2 7 1 ，这种译码器结构可以将q c l d p c 码的吞吐量增益最优 化，提高硬件利用效率h e u 。 n o s a t o h 等人设计一种系统来完成l d p c 码的设计工作1 2 s i ，系 统用到了一个多用途的群集和一个硬件加速器，这个系统解决了长 码设计需要耗费大量时间并且需要反复试验的问题。 y a n gs u n ，c a v a l l a r o j r 提出了一种标准化结构的译码器，可以 同时完成l d p c 码和t u r b o 码的译码 2 9 1 。译码器利用m a p 算法作为 l d p c 码与t u r b o 码之间的译码算法桥梁，这种算法可以获得两部的 收敛速度。 d a s e s u no h 等人提出了一种利用控制器有效地重构l d p c 码的 6 a 哈尔滨t 稗人学硕十学何论文 译码器t 3 0 l ，这种设计可以降低译码器的复杂度。 c h e n z h o uz h a n 等人提出了一种高性能部分并行译码器t 3 1 l 。这 种l d p c 部分并行译码结构就是用来降低译码过程中的单元区域消 耗，增大h u e ，通过实际验证，对于( 19 4 4 ，9 7 2 ) 长度的非规则l d p c 码，在没有任何性能损失的情况下可以获得6 0 的平均吞吐量： b e u s c h e l c 等人提出了一种结构灵活的可适用于任何结构化和 非结构化l d p c 码的译码器 3 2 1 ，同时还针对校验矩阵的生成提出了 一种映射算法，这种算法可以保证迅速可靠的生成需要的校验矩阵。 通过利用x i l i n x 、x c 4 l x l 6 0 、f p g a ，b e u s c h e l c 等人对这种译码 器结构和映射算法进行了验证，结果表明这种设计可以将译码码长 提高3 0 倍。 2 0 0 9 年，g u o c h u nw a n 等人针对d m b t h 标准对l d p c 码译 码算法进行了研究，提出了一种基于t u r b o 码译码思想的t d m p 算 法【3 3 l ，这种算法的提出不仅基于硬件实现的考虑，其最大的优点是 这种译码算法改进了编码增益，降低了译码复杂度。 1 3 论文结构安排 论文首先对二进制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 码的编译码理论，在构造编码方 7 0 a 哈尔滨下稃大学硕十学何论文 面主要介绍了基于结构化构造的q c 方法，在译码方面介绍了对数 域和积译码算法和基于二进制思想的b p 译码算法，并在最后介绍了 用以优化多进制l d p c 码的e x i t 图。 第四章，分析了水声通信的信道模型，将二进制l d p c 码应用 于实际信道，针对不同码长，不同码率，不同译码迭代次数进行仿 真，拟定了基于水声通信的l d p c 编码初步方案，并与r s 码和卷积 码作为编码方案的水声系统进行性能对比，为接下来的课题提供依 据。 8 0 和 哈尔滨t 程人学硕十学何论文 第2 章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 码是一种线性分组码( 聆，七) ，其校验矩阵日是一个具有很 多0 ，很少1 的稀疏矩阵。每行1 的个数被定义为行重w ，每列1 的个数则定义为列重心，因为为0 一七) n 矩阵，易于证明m 和心的 关系为嵋= w e n ( n k ) ，码率，可计算为1 3 4 1 ： ，：鱼：l 一丝 ( 2 1 )，= 一= l 一2 iz il 刀 w ， 如果日是稀疏的，但是每列或者每行的l 的数目不是常数，所 得到的码称为不规则l d p c 码。 2 1 2l d p c 码的t a n n e r 图描述 t a n n e r 研究了用二部图表示l d p c 码的方法，因此称之为t a n n e r 图。二部图是一个节点由无向分支连接的图，且其节点可以分为两 类，分支只能连接处于不同类中的节点1 3 4 1 。在t a n n e r 图中，两类节 点分别为珂个变量节点和i = 刀一k 个校验节点。当且仅当啊，= l 时，在 校验节点f 和变量节点，间存在一个分支连接【34 1 。这样对( 刀，。，c o ，) 规 则l d p c 码，其中有，( 刀一k ) = 。刀个分支，每个变量节点有。条分 支连接，每个校验节点有c o ，条分支连接 3 4 1 。图2 1 表示的就是一个 含有5 个校验节点，lo 个变量节点的校验矩阵的t a n n e r 图。图中黑 色的粗实线表示的是在这个t a n n e r 图中所形成的环路，这是一个长 9 k a 哈尔滨一：稃人学硕十学仲论文 度为6 的环，这就意味着从变量节点f 0 出发，经过六条边后再度回 到了f 0 。 ) 【ox l x 2 x 3x 4 x 5 ，( 6x 7 x 8) 【9 图2 1 ( 1 0 ，5 ) 线形分组码h 矩阵的t a n n e r 图 2 2l d p c 码的校验矩阵构造 2 2 1l 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 码的图论构造【3 5 】就是从校验矩阵的校验节点入手，通过与 数学中的几何概念相结合来完成校验矩阵的构造，这样构造可以增 大l d p c 码的码间距离，提升编码性能。 以下面这个校验矩阵为例，在这个矩阵中存在着长度为4 ，6 ，8 ， 10 等长度不等的环： 1 0 山 o o 0 l 图2 2 具有环长为4 ，6 ，8 ，10 的矩阵( a ) 若以矩阵中长度为6 的环为例，通过观察可以将其在校验矩阵 中圈划出来，这个长度为6 的环中相关的校验节点一共有3 个，分 别为q ，c 3 ，q c o c 1 c 2 c 3 c 4 c 5 00lol 图2 3 具有环长为4 ，6 ，8 ，1 0 的矩阵( b ) 然后可以用一个三角关系来表示这三个节点： 图2 4 环长为6 的三角结构图 两个校验节点相连表示在矩阵中这两个校验节点所在的行中某 列元素同时为1 ，那么如果三个节点同时相连，则正是符合了六环的 结构，由此环与校验节点的关系就建立了，对于其他环长其对应的 校验节点几何图形分别为 3 5 1 ： 印q 吻哆钰哆 、卜 和 哈尔滨一t ：n 人学硕十学何论文 o口仑 ( a ) 4 环( b ) 8 环 ( c ) 10 环 图2 5c a ) 环长为4 的几何结构图 ( b ) 环长为8 的几何结构图( c ) 环长为10 的几何结构图 这些表示环长的几何图形形状并不是唯一的，以8 环为例，下 面两种情况表示的均是环长为8 的情况，虽然这些表示8 环的校验 节点图不同，但它们之间都是同构的，并且满足彼此是同构的欧拉 图1 3 5 1 。 口 图2 6 环长为8 的同构欧拉图 分析了校验矩阵中的校验节点关系后，就可以把校验节点之间 的关系也用一个矩阵表示出来，这个矩阵在数学中称为邻接矩阵s ， 通过判断由校验节点生成的邻接矩阵，便可以很快的判断在原校验 矩阵中是否构成了相应的短环1 3 5 1 。上述校验矩阵的邻接矩阵为： qc 2 1 01 1 c 3c 4c 5 011 通过邻接矩阵可以观察出由c l ，c 3 ，c 4 构成的6 环的位置关系如 下，正如之前分析，此时三个校验节点构成了一个直角三角形： 1 2 1 1 1 l o ) 。o。 瞅 l l o l l 矩接自、 o 0 1 1 1 b 0 o l 1 1 72 、图 彩向如白以以 k 哈尔滨t 程火学硕十学何论文 c 1 o l l 0 1 1 c 2白c 4巳 1011 、 图2 8 邻接矩阵( b ) 总结邻接矩阵的成环规律，可以得出以下结论 3 5 1 ：若在邻接矩 阵中某一位置的元素为“l ”，则代表该位置所对应的两个校验节点之 间相连，即一定是有4 环存在；若在邻接矩阵中存在直角三角形， 并且满足( ( ，) ，( 屯，f c ) ，( ，f f ) ) ，其中屯 i b 0 ，则6 ，= 0 ，否则a = l ；若h e7 = 0 或者达到最大迭代 次数，则译码结束，否则继续上述第二和第三步骤 3 9 1 。 2 5 本章小结 本章对二进制l d p c 码的基础理论进行了介绍，首先简要介绍 了l d p c 码的定义和t a n n e r 图的概念，接下来阐述了基于图论的校 验矩阵构造方法和基于几何构造的s c l d p c 构造方法，最后对 l d p c 码的经典编译码算法给出了介绍，为接下来多进制l d p c 码的 引入做好准备。 哈尔滨。i ：科人学硕十学何论文 第3 章多进韦i jl d p c 码 多进制l d p c 码，又名多元l d p c 码，其特点便是其码元是取 自g f ( q ) 域，每个码元都可以用l o g ：q 个二元制符号表示，因此二进 制l d p c 码可以看做是多进制l d p c 码的特殊情况。 3 1g a l o i s 域 3 1 1g a l o i s 、域定义 域是元素的集合，如果域中的元素个数q 有限，就称之为有限域， 也称为g a l o i s 域，记为g f ( g ) p 6 1 。任何域都必须有一个加法恒元0 和乘法单位元l ，所以 0 ，1 ) 就构成了最简单的有限域g f ( 2 ) ，也就是 通常所说的二元域 3 6 1 。如果g 为素数i o ，l ，q l 在模g 乘法和加法 下也构成域，并且只有g 为素数或者是素数幂的情况下才能构成有限 域g f ( q ) 36 1 。当口为素数，乘和加基于模q 算术。如果q = p ”，p 为素 数而朋为正整数，则可以由域g f ( q ) 扩展到域g f ( p ”) ，称为g f ( p ) 的 扩域，乘和加都基于模p 算术1 3 6 1 。 3 1 2 g f ( p 肘) 的构造 一般g f ( p ”) 是通过g f ( p ) 上的多项式来构造的【36 1 。考虑系数取 自g f ( p ) 上多项式 厂( x ) = 口o + 口l x + + c t l n x ”( 3 - 1 ) 其中g f ( p ) ，f - 0 ，疗。若0 ，称f ( x ) 为刀次多项式且记作 a 。f ( x ) = r l ，口。称为首相系数3 酣。若g n = l ，称为首一多项式。常数可 以看做是o 次多项式。0 多项式的次数认为是一0 0 。多项式加法和乘 法定义如下 3 6 1 。若 ( x ) = y 吼x 。，g ( x ) = p , x 。 ( 3 2 ) 2 1 哈尔滨t 程人学硕十学位论文 加法定义为 m a x ( m 。打 厂( x ) + g ( x ) = ( + 屈) x 。 ( 3 - 3 ) 如果m 丹，则f n 时认为t ；t ，= 0 。若n m ，则f m 时认为屈= 0 。 乘法定义为 3 6 1 厂( z ) g ( x ) = c ，x 。 ( 3 - 4 ) i = 0 其中 f c l = 口屈一 ( 3 - 5 ) j = 0 与整数类似，多项式除法采用带余除法 口( x ) = q ( x ) b ( x ) + 厂( x ) ，a 。r ( x ) a 。6 ( x ) ( 3 - 6 ) 记做a ( x ) m o d b ( x ) = r ( x ) 。多项式模运算也有下列性质 3 6 1 口i ( x ) m o d b ( x ) + a 2 ( x ) m o d b ( x ) = 【a l ( x ) + 0 2 ( x ) m o d b ( x ) ( 3 - 7 ) 【口l ( x ) m o d b ( x ) a 2 ( x ) m o d b ( x ) 】= 【a l ( x ) 口2 ( x ) m o d b ( x )( 3 - 8 ) 如果有f ( x )