（通信与信息系统专业论文）基于ldpc码的联合信源信道译码算法研究及其应用.pdf

摘要 摘要 低密度奇偶校验码( l o w - d e n s i t ) ，p 撕t y c h e c kc o d e s ，l d p c 码) 是由g a l l a g e r 在19 6 2 年提出的一种基于稀疏校验矩阵的线性分组纠错码，因其具有逼近香农限的优秀性能， 而成为了当前信道编码领域最受瞩目的热点之一。信源信道联合编译码是由m c e l i e n c e 于1 9 7 7 年首先提出来，被用于提高通信系统的整体优化，取得了预期效果。本文采用 理论分析和计算机仿真相结合的方法，对基于l d p c 码的联合信源信道译码算法及其在 数字水印系统中的应用展开研究。论文主要工作包括： ( 1 ) 系统地论述了l d p c 码的基本原理，l d p c 码的结构和校验矩阵的构造方法。 详细分析了l d p c 码的编译码原理和影响l d p c 码性能的几个因素，在此基础之上进行 了l d p c 码编译码器的结构设计。 ( 2 ) 研究了基于隐马尔可夫信源估计和l d p c 码的联合信源信道译码算法。从隐马 尔可夫信源估计算法入手，利用它与l d p c 码进行联合译码，对该联合译码算法进行了 改进，并对信源模型的阶数进行了更新，对各种译码算法的性能进行了全面的仿真分析。 ，( 3 ) 将基于l d p c 码的联合译码算法应用到数字图像水印系统。在该系统中先对数 字水印进行l d p c 纠错编码，然后在d c t 域将编码后的序列嵌入到原始图像中，提取 水印时，用隐马尔可夫模型来描述水印图像，利用信源信道联合迭代译码算法进行提取， 从而降低了水印在传输过程中的误码率。 a w g n 信道的仿真结果表明，采用联合的信源信道译码算法能够改善l d p c 码的 译码性能。将此联合算法应用到图像数字水印系统中，可以提高水印传输的可靠性，增 强水印的抗攻击能力。 关键词：l d p c 码；置信传播算法；隐马尔可夫模型；信源信道联合译码；数字水印 a b s t r a c t 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 kc o d e ，i n n d d u c e db yg a l l a g e ri n19 6 2 ，i so n eo fl i n e a rb l o c k e 仃o r c o r r e c t i n gc o d e s b a s e do nt 1 1 es p a r s ep 撕够一c h e c km a t r i xa n di t sp e 疵- 珏n a n c ei sc l o s et o s h a i l l l o nl i m i t d u et os u c hg o o dp e r f o m a i l c e ，l d p ch a sb e c o m em o r ea i l dm o r ea c 缸a c t i v ei n c h a n n e le n c o d i n gf i e l d j o i n ts o u r c e c h a n n e le n c o d i n ga n dd e c o d i n gw a s f i r s t l yi n t r o d u c e db y m c e l i e n c ei n19 7 7a n dt h e nu s e di 1 10 p t i m i z i l l gc o n l i l l u l l i c a t i o ns y s t e m i nt 王l i sp 印e r w e f o c u so nj o i n ts o u r c e c h a n n e l d e c o d m ga l g o r i t i m l s b a s e do nl d p cc o d e sa r l dt 1 1 e i r a p p l i c a t i o n st od i g i t a lw a t e 撇砌( s y s t e m s n l em a j nw o r ki sa sf o l l o w s ： ( 1 ) t l l i sp a p e rg i v e sas y s t e m a t i ci n v e s t i g a t i o no fl d p cc o d e s f i r s t l y ，h o wt 0c o n s t m c t n l el d p cc h e c km a t r i xi sm t r o d u c e d ；a n dn l e nt h ee n c o d i n ga i l dd e c o d i n gt l l e o 巧o fl d p c c o d e si sd e s 嘶b l e di nd e t a i l e d b e s i d e s ，s e v e r a lf a c t o r si n n u e i l c 吨l d p cc o d e sa r eg i v e n o n n l eb a s i s ，t 1 1 ee n c o d e ra n dd e c o d e ro fl d p ca r ed e s i g n e d ( 2 ) r e s e a r c ho nj o i n ts o u 】伦e - c h 锄e ld e c o d i n gb a s e do nh i d d e nm 破o vs o u r c em o d e l 锄dl d p cc o d e s s t a n i n g 谢t l lr e - e s t i m a t e da l g o r i t h mo fh i d d e nm a r k o vm o d e l ，廿l i sp 印e r d e s c r i b e sm ej o i n td e c o d i n ga j g o r i t h m ，t 1 1 ei m p r 0 v e da l g o r i t l l ma i l dt l l e 甜g o r i m m 州m c h a n g e ds t e p so fs o u r c e ，a i s og i v e st h es h u l a t i o nr e s u l t so fe a c ha l g o r i t l l i l l ( 3 ) t h ej o i n ts o u r c e c h a n n e ld e c o d i n ga l g o r i t h mb a s e do nl d p ci sa p p l i e dt 0d i g i t a l w a t e m i a r ks y s t e m mt h es y s t e m ，m e 、v a t e 肌a r ki sf i r s t l yc o d e d ，a n dt l l e ne m b e d d e di n t ot l l e d c tf i e l do f t h e 硫a g e i i l 也ed e c o d e r ，也ew a t e n n 酞c a i lb ed e s c 曲l e da sh i d d e nm a r k 0 v m o d e l ，e x t r a c t e dw i t hj o i n ts o u r c e c h a n n e li t e r a t i v ed e c o d i n ga l g o r i t i u n n l e e x p e 曲l e n t b a s e do na w g nc h a 肌e 1s h o w st h a tt h e a l g o r i t h mo fj o i n t s o u r c e c h a n n e ld e c o d i n gc a l li l n p r o v et h ep e f f i o 肌a l l c eo fl d p cc o d e s w h e nt h ea l g o r i t h mi s a p p l i e dt o t h ed i g i t a li n l a g ew a t e m a r k ，i tc a i ls u c c e s s m l l yi m p r o v et h er e l i a b i l i t ) ，o f w a t e r n l a r ka j l de r l l l a n c ei t sa n t i a t t a c “n ga b i l i 批 k e y w o r d ： l d p c ； b e l i e f p r o p a g a t i o na l g o r i t h m ； h i d d e nm a r k o vm o d e l ；j o i n t s o u r c e c h a n n e ld e c o d i n g ；d i g i t a lw r a t e 硼a r k i n g 河北大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽 我所知除了文中特别加以标注和致谢的地方外论文中不包含其他人已经发表或撰写的研究成果也不 包含为获得河北大学或其他教育机构的学位或证书所使用过的材科。与我一同工作的同志对本研究 所做的任何贡献均已在论文中作了明确的说明并表示了致谢。 作者签名：量盔盔日期：j 生年鱼月l 日 学位论文使用授权声明 本人完全了解河北大学有关保留、使刚学位论文的规定即：学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版允许论文被查阅和借阅。学校可以公布论文的全部或部分内容可以 采用影印、缩印或其他复制手段保存论文。 本学位论文属于 1 、保密口在年月日解密后适用本授权声明。 2 、不保密留。 ( 请在以上相应方格内打“ ) 作者签名：星盔盘 导师签名：易乏勋导师签名： 参乞放一一 日期：趔 年月二鱼_ 一同 日期：兰! 竺翌年笪一月卫同 保护知识产权声明 懒黻黼为c 善戮薯鬻黼， 的学位论文，是我个人在导师指导并与导师合作下取得的研究成果，研 究工作及取得的研究成果是在河北大学所提供的研究经费及导师的研究经费资 助下完成的。本人完全了解并严格遵守中华人民共和国为保护知识产权所制定的 各项法律、行政法规以及河北大学的相关规定。 本人声明如下：本论文的成果归河北大学所有，未经征得指导教师和河北大 学的书面同意和授权，本人保证不以任何形式公开和传播科研成果和科研工作内 容。如果违反本声明，本人愿意承担相应法律责任。 声明入：量盔盔日期：翘：年月上日 作者签名：量盔盘 导师签名：羔圣墼 日期：逆星年月上同 日期：塑呈年l 月卫r 第l 章绪论 第l 章绪论 人类社会的生存和发展，每时每刻都离不开信息。因此，信息的传输即通信在现代 社会中扮演着极为重要的角色。一个数字通信系统的基本组成如下图所示： 图1 1 数字通信系统模跫 通信的基本目的在于将信息由信源及时可靠地传送到信宿。但在数字通信系统中， 可靠和快速往往是一对矛盾，纠错编码正是在解决这对矛盾的过程中不断发展起来的。 提高信息传输的速度和有效性，始终是通信工作所追求的目标，因此，对纠错码的研究 也越来越受到人们的重视。 1 1 纠错编码的发展 1 9 4 8 年s h a i l l l o n 在其发表的“通信的数学理论一文中i l 】，提出了著名的有扰信道 编码定理，奠定了纠错码的基石，为通信的可靠性传输提供了理论基础，也为信道编码 技术的发展指明了方向。半个多世纪以来，信道编码界的学者正是沿着香农所指引的方 向，向可靠性极限( 香农限) 逼近，并不断取得可喜的成果。 上世纪五十年代到六十年代初，人们通过代数的方法构造了许多纠错码，例如汉明 码、格雷码、循环码和b c h 码【2 l ，这些码字主要以代数中的群论、域论等理论为数学 基础，属线性分组码，译码方法通常是采用大数逻辑和捕错译码。同一时期，还有另外 一种纠错编码被提出，那就是卷积耐3 1 。它在编码过程中引入了寄存器，增加了码元之 恻的相关性，在相同复杂度的条件下可以获得比线性分组码更高的编码增益。但是这种 相关性同时也增加了分析和设计卷积码的复杂性。卷积码的译码算法主要有序列译码算 洞北人学- 1 i 学硕十学何论文 法和维特比算法。 进入七十年代，纠错码进入了它的第二个大的发展时期。这一时期有两种优异的编 码方案，一种是由f o m e y 提出的将分组码和卷积码结合起来的级联码。研究表明，级 联码的性能比分组码或卷积码有较大提高，而译码复杂度没有明显增减。另一种是网格 编码方案( t c m ) ，它是将纠错码和调制技术相结合，通过对信号空间的不同分配，来 最大化信号相点间的最小欧式距离，以此达到抗干扰的目的。 到了上世纪八十年代到九十年代，经过几十年的研究和实践，纠错编码理论和技术 取得了突飞猛进的发展。其中最具有历史意义的是n 曲。码【4 j 的提出。1 9 9 3 年在世界著 名的正e e 国际通信会议上，法国学者c b e 仃o u 提出了一种新的编码结构t u 加码， 该码巧妙的将卷积码和随机交织器结合在一起，性能非常接近香农限，同时复杂度较低， 容易实现，为信道编码领域带来了一场革命。 m b o 码的出现引发了基于图的迭代译码算法研究的热潮。1 9 9 5 年m a c k a y 和n e a l 重新发现，早在1 9 6 2 年g a l l a g e r 提出的低密度校验码【5 l 也是一种性能接近香农限而且可 以实现的编码方案，其性能甚至可以超过t u r b o 码。这一优越性被发现后，越来越多的 研究者将注意力集中到l d p c 码上，并将其作为未来高速宽带移动通信中信道编码的主 要备选方案之一。 1 2 研究l d p c 码的意义 l d p c 码的重新发现是继1 、曲。码后在纠错编码领域的又一重大进展，它向逼近香 农的目标又跨进了一步，因此，对l d p c 码的研究有着重要的意义： l d p c 码不仅具有良好的距离特性、小的译码错误概率和较低的译码复杂度，而且码 率容易调整，错误平台极低，译码错误几乎均为可检测错误，中、长码的性能超过t u r b o 码，无论在理论上还是实际中都具有重要的研究和应用价值。 l d p c 码作为一种线性分组码，具有描述简单、并行译码等显著优点，与t l l 舭码相 比，没有内在的交织问题，系统实现更为简单，所以l d p c 码在大数据量通信，特别是 图像、视频通信领域，有着广泛的应用。 l d p c 码的优异性能及其在信息可靠传输中的良好应用前景( 例如光通信、卫星通信、 深空通信、第4 代移动通信系统、高速与甚高速率数字用户线、光和磁记录系统等) ， 2 第l 苹绪论 已引起世界各国学术界和i t 业界的高度重视，成为当今信道编码领域最受瞩目的研究 热点之。 l d p c 码与通信系统其它技术相结合的研究也有着重要意义，例如：l d p c 码应用于 c d m a 系统将大大提高通信系统容量；l d p c 码与调制技术相结合可增大通信流量； l d p c o f d m 系统在多径衰落信道等移动信道下具有惊人的抗衰落性能；把l d p c 码应 用在数字图像水印系统中，联合使用m l 检测器，能够极大地增加原始图像嵌入水印的 容量。 1 3l d p c 码的研究现状与进展 自从l d p c 码被重新认识以来，许多研究人员都投入到l d p c 码的研究之中，从 1 9 9 9 年开始这方面的研究文献大量出现。目前，对l d p c 码的研究主要集中在以下几 个方面： ( 1 ) 对l d p c 码的属性进行分析。包括l d p c 码的性能界和码率界、最小环长、码 重分布、节点次数分布等理论上的研究。 ( 2 ) 构造性能优异的l d p c 码。l d p c 码的结构可采用几何方法、图论方法、实验 设计方法、置换等方法来设计。m g l u b y 等【6 】指出基于非正则图定义的码性能优于相应 的基于正则图定义的码。m c d a v e y 【7 j 指出，在非二元有限域中定义码和采用具有非均 匀行、列重量的非正则奇偶矩阵均可改善码的性能。m g l u b y l 8 】等提出了一类基于级联 二分图的l d p c 码，称为e r a l s u r ec o 玎e c t i n g 码。j c 锄p e l l o 【9 】等提出采用扩展的b i t f i l l i n g 算法来设计具有高码率、高g i n h 和误码性能良好的l d p c 码。y k o u ，s l i n 和 m f o s s 耐e r i 旧】探讨了基于有限几何学的l d p c 码结构。 ( 3 ) 简化译码算法。g 2 l l l a g e r 】曾给出了两种l d p c 码的迭代译码算法：硬判决和软 判决算法。前者计算复杂度很低，但译码性能不理想。后者虽有好的性能，但比较复杂。 为了平衡性能和计算复杂度，文献 1 2 】提出了消息传递算法( m e s s a g e r p a s s i n ga l g o r i t h m ) ， 也称信度传播( b p ) 算法。m p c f o s s o r i e r 对低复杂度的b p 算法作了进一步研究，提出 了基于可靠性译码与信度传播译码相结合的b p b a s e d 译码算法。为了改善b p - b a s e d 算 法因在校验节点上作简化处理而导致性能的下降，j c h e n i b 】提出了2 种改进算法：采用 归一化的近似最佳通用b p - b a s e d 译码算法和通过降低可靠性来改善外信息精度的 3 河北人学t 学硕十学位论文 o 侬e tb p - b a s e d 算法。这些译码方法本质上都是基于t a n n e r 图的消息迭代译码算法，各 种简化算法的目的就是在计算复杂度、译码性能及译码时延等方面取得最优的折中。 ( 4 ) 研究和开发有效的编译码器实现方法。t b h 撒等尝试性地提出了采用定点 d s p ( 数字信号处理器) 实现l d p c 码的方案f j 4 j 。t z h a n g 和k k p a r h j 提出了一种与译码 器联合设计，适合执行部分并行译码的面向v l s i 实现的方法。f l 撕o n 技术公司已开发 了l d p c 编译码器产品，称为v e c t o r - l d p c ，可分别采用f p g a 和a s i c 实现，此外， 该公司还开发了v - l d p c 集成至o f d m 的芯片组。 ( 5 ) 研究l d p c 码的实际应用。l d p c 码具有巨大的潜力，在很多领域的应用都取 得了显著成效。把基于l d p c 码的m l c ( 多级编码) 和准比特交织编码调制( b l c m ) 方案 应用于c d m a 系统中，在8 p s k 调制方式下，能够同时提供2 5 6 k w s 的语言信道传输和 l m b s 的高速率传输，且误码率低，延时短。在我国地面数字电视传输标准建设备选方 案中，广电总局广科院的百m i 方案性能较好，最大技术亮点就是采用l d p c 码信道编 码技术，最优的解决了保持l d p c 编解码性能最佳的状况下实现复杂的难题。据此， i e e e 8 0 2 s a n 工作小组全体通过，在面向双绞线的1 0 g b i 佻以太网标准1 0 g b a s e 草案 中采用l d p c 码。 尽管l d p c 码有着卓越的性能，对它的研究也取得了丰硕的成果，但仍然存在需要 探讨的问题，主要包括：寻找更好的编译码方法；分析l d p c 码在复杂信道中的性能； 与信源编码进行联合实现通信系统的整体优化；研究低复杂度的l d p c 码编译码器的硬 件实现；研究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 码的编译码算法进行了研究，推导了b p 译码算法的具体步骤，分 4 第1 章绪论 析了影响l d p c 码性能的几个因素，并给出了简单的l d p c 码编译码器的设计方案。 第四章介绍了一种基于隐马尔可夫模型估计和l d p c 码的联合信源信道译码算法， 对该算法进行了改进；并更新了信源模型阶数，进行了新算法的讨论：最后针对各种算 法，给出了相应的计算机仿真结果。 第五章对基于l d p c 码的联合信源信道译码算法在数字水印系统中的应用进行了 探索。仿真结果表明，采用l d p c 码对水印图像进行编码，并采用联合译码的方法提取 水印，可以降低水印在传输过程中的误码率，提高水印的抗攻击能力。 第六章总结全文的主要内容，对进步的研究工作做出展望。 河北大学_ i j 学硕十学位论文 第2 章l d p c 码的基础知识 l d p c 码是一种特殊的线性分组码，可以用生成矩阵和校验矩阵来表征，其校验矩 阵具有低密度的特殊性，并且可以用与之对应的二分图( t a n n e r ) 来表示。本章从线性 分组码的概念出发，介绍了l d p c 码的定义及其二分图表示，并对l d p c 码的结构，校 验矩阵的构造方法进行了分析。 2 1l d p c 码的定义及二分图表示 2 1 1 线性分组码 法而言。我们通常在有限域上讨论码的构造，具有g 个元素的有限域通常称为伽罗华域， 用舒( g ) 表示。最简单的域是只有一个零元素和一个单位元的二元域凹( 2 ) 。一个( 刀，j j ) 分组码是将| j 长信息序列甜= ( ，咋一。) 映射为胛长序列c = ( c 0 ，q ，q 一。) 。设q ，巳是某 ( ，l ，足) 分组码的任意两个码字，q ，n ：是码元符号集中的元素，当c ，q + c ，a ：也是码字时， 凹( 2 ) 上的门维向量空间s 的元素共有2 ”个。而( 刀，后) 线性分组码的码字只有2 个， 量岛，蜀，断一。组成。岛，蜀，一。是c 的一组基底。某一码字c 和其对应的信息序列“的 写成矩阵形式即f = ”g ，其中g = ( 耋一 ，g 矩阵就称为生成矩阵，经过行运算和 写成矩阵形式即f = ”g ，其中g = 1 l ，g 矩阵就称为生成矩阵，经过行运算和 l 轧j 6 第2 章l d p c 码的基础知识 必要的列交换，该矩阵可以转换为系统形式：g = 【l 尸】。根据线性代数知识可知，在s 中必存在一个空间c 的零空间c 上，c 上由疗一元个线性无关的 维向量，矗，吃小。张成， 写成矩阵形式，即 日= 仁1 k ，j 由于这些向量属于c 上，故有础t = o 或册t = o 。当且仅当c c 时，有 胡t = 0 ( 2 2 ) 称日为校验矩阵。式( 2 2 ) 可在接收端用于判断一个矢量是否是c 中的码字。 从线性空间及其物理含义看，线性分组码实质上是利用线性空间的扩展，即由七维 的扩展成，? 维，利用被扩展的刀一忌维来发现、纠正信道传输中的差错。 2 1 2l d p c 码定义 根据g a l l a g e r 在其论文中的论述，一个长度为的l d p c 码由它的校验矩阵来定 义，该矩阵的特点是除很少一部分元素非零外，其他大部分的元素都是零，即所谓的“低 密度”。一个参数为( ，f ，) 的表示该矩阵中每列有f 个1 ，称为列重；每行有个l ， 称为行重。矩阵大小为k ，代表码字长度，k 代表校验子的个数。定义满足 日x t = 0 的矢量z = ( 五，h ) 的集合为相应的l d p c 码。 g a l l a g e r 的论文以及后来一些文献中提到的l d p c 码校验矩阵日的一些性质如下： 1 每列有f 个1 ，f 为任意取值的整数值，且，3 ； 2 每行有，个l ，为任意取值的整数值，且f ； 3 任何两列的元素同为1 的行数( 称为重叠数) 不超过1 ，即矩阵中找不到四个角都 是1 的矩形，也即没有所谓的“四线循环”； 4 i k 。 n 。 2 1 3 二分图( t a i m e r ) 表示 同北大学j r 学硕十学位论文 l d p c 码可用二分图来表示，它是与校验矩阵直接对应的。式( 2 3 ) 给出了 ( 8 ，2 ，4 ) l d p c 码校验矩阵h 的示例，图2 1 给出了其二分图表示。图中上面的节点称为 变量节点，可以认为是一个码字中的一个比特，对应着日中的一列；下面的节点称为校 验节点，每个节点相当于一个奇偶校验等式，对应着h 中的一行。每个变量节点称为相 邻校验节点的父节点，每个校验节点称为相邻变量节点的子节点，节点间的连接表征了 相应的比特参与了对应校验的计算，与校验矩阵中的非零元素相对应。与每个节点相连 的边数称为该节点的度数( d e g r e e ) 。由变量节点、校验节点和边首尾相连组成的闭合 环路称为环( c y c l e ) 。二分图中最短环的周长，称为围长( g i n h ) 。 2 2l d p c 码的结构 h = 1 1 1 0 0 0 1 0 l 0 0 0 l l o l 0 1 0 1 1 0 1 0 0 0 11 0 1 0 l 图2 - l ( 8 ，2 ，4 ) l d p c 码的二分图 2 2 1 正则与非正则的l d p c 码 在l d p c 码的校验矩阵中，如果行列重量均固定，即相同类型的节点的度相同，我 们称之为正则l d p c 码。如果各变量节点与各校验节点的度数不完全相等，而是服从一 个度分布函数，则称之为非规则l d p c 码。其编译码方法与规则码相似，但性能却优于 规则码，这是因为非规则码的“波浪效应”【1 5 】：在l d p c 码的随机双向图中，对变量 节点来说，其度数越高，它从校验节点所获得的信息也就越多，也就能更准确的判断其 校验值；反之，从校验节点的角度来看，希望度数低，其度数越低，那么传播到相邻节 点的有用信息也就越多。而非规则码的随机双向图就很好的平衡了变量节点与校验节点 3 oq o 0 o o = = l l = 仰魄n 魄 o o 0 0 吻仇 o o 0 0 吮吩n n o o o o h u 屹屹 第2 章l d p c 码的基础知谚! 二者对度数的要求。而所谓的“波浪效应”就是度数大的变量节点首先获得正确值，然 后将更多的有效信息提供给度数较小的变量节点，如此循环，直到所有变量节点都被译 出。 对于非规则码，非规则图的设计是重要的，在一个好的非规则图上构造的码字，它 能纠正更多的错误。因此设计非规则码就是找到序列九= ，九，九 和 p = 岛，p ：，岛) ，其中九和n 分别表示的是非规则图上与度为f 的信息节点和校验节点 相连的边占总边数的比例，z 和4 分别表示的是信息节点和校验节点的最大度数。序列 d ld a 和p 分别满足等式九= 1 ，b = 1 。如何找到合适的序列九和p ，成为非规则码设 ，- l，- l 计的主要问题。目前有多种方法来寻找序列a 和p ，主要有l u b y 等提出的前后向算法 和d m a c k a y 等提出的几何算法。 2 2 2 二元域与多元域的l d p c 码 根据校验矩阵日中的元素是属于甜( 2 ) 还是钟( g ) ( g = 2 ，) ，我们可以将l d p c 码 分为二元域或多元域的l d p c 码。前面对l d p c 码的定义都是在二元域基础上的， m a c k a y 对上述二元域的l d p c 码又进行了推广，如果定义中的域不限于二元域就可以 得到多元域卵( g ) 上的l d p c 码。m a c k a y 同时指出，在g ，( g ) 域上构造的l d p c 规则 码能显著地提高性能。 甜( 9 ) 域上有9 个元素，g = 2 ，夕是一个整数。g ，( 9 ) 域上构造的l d p c 规则码 与g 尸( 2 ) 上的l d p c 规则码是一样的。它的校验矩阵日的行和列中非0 的个数也是固定 的，只是对于校验矩阵中的每个非0 元素，不一定是1 ，它可以有g 一1 个值作为选择。 由于g j f l ( 9 ) 域上的每个元素可以有p 个二进制( ，而，z p ) 表示。如果g ，( 2 户) 域上的值 口与一个p p 的二进制矩阵相关联，那么把这个矩阵代入( q ，) 中对应的值，可以得 到生成矩阵和校验矩阵的二进制表示( g ，：) ，这种变化可以让运算变得简单方便，通 9 河北人学i ：学硕十学位论文 过这种变化还可以将g f ( g ) 域上构造的非规则码转换为在g f ( 2 ) 上构造的非规则码。在 g f ( 9 ) 域上构造的规则l d p c 码比在二进制中构造的性能要好，这是因为在g f ( 9 ) 域 上构造的l d p c 码其校验矩阵域可以增加与之对应的二进制校验矩阵丝中列的平均重 量，但它的二分图并没有改变，不会造成节点之间循环数目的增加，也不会降低译码算 法的性能。在g f ( g ) 域上构造的非规则码性能最好，因为它在具有上述优点后还有自身 的“波浪效应”，能够使译码性能得到显著提高。 2 3 校验矩阵的构造 一个码完全由它的校验矩阵确定，很明显矩阵的结构对于码的性能有决定性的作 用。对于l d p c 码来说，主要问题在于如何构造没有短长度的圈或圈的平均长度尽可能 大的校验矩阵。 2 3 1g a l l a g e r 的构造方法 假定需要构造的正则l d p c 码，列重为九，行重为p 。g 址i a g e r 将校验矩阵阿分成 a 个大小相等的子矩阵( 日。，日：，羁一) t ，每个子矩阵e ! 行重为p ，列重为1 。子矩 阵q 按照确定的方式构造，比如由p 个单位阵排列而成。子矩阵必，马蜴都是通过 对q 的所有列做随机的排列组合而成。图2 2 说明了一种g a l l a g e r 构造l d p c 码的规则。 凰= 【巨：乞】( 2 - 4 ) 娜= 瞳 oo 、 i l 0i = i 。l q 7 r 2 ( 且) 乃( 日。) 或= 7 r 1 ( q ) 7 r 2 ( ) 乃( h ) 其中日为第一个子矩阵，刀表示矩阵。的列置换。 i o 第2 章l d p c 码的基础知识 图2 - 2g a l l a g e t 的构造方法 按照g a l l a g e r 的规则构造码字，可以保证固定列重和行重，但因为随机构造的原因， 编码二分图可能会出现较短的圈。随着码长的增加，短圈出现的概率也会变得很小。所 以这样构造的l d p c 码在中短码长的情况下，需要考虑消除短长度的圈以获得较好的误 码率性能。 2 3 2m a c k a y 的构造方法 m a c k a y 在构造l d p c 码的时候为了减少短圈数目，引入了一些列重仅为2 的列。 降低了整个校验矩阵的重量，可以提高译码性能，但引入重量为2 的列会导致低重量码 字的出现，需要采取措施减小其出现概率。m a c k a y 给出了如下几种构造模式【16 1 ： 构造方法1 a ：要求保证固定列重为a ，而行的重量尽可能均匀的保持为p 。同时要 求任意两列之间的交叠重量不超过1 。图2 3 ( a ) 表示了按照此方法构造的一个l d p c 码 ( p = 6 ，a = 3 ) 。 构造方法2 a ：将m 2 的列，重量置为2 ，通常采用两个等等的单位矩阵，上下 叠放。剩余的列依然保持1 a 的构造方法。如图2 3 ( b ) 所示。 ( a ) 1 a( b ) 2 a 幽2 3m a c k a y 的构造方法 构造方法1 b ，2 b ：在前面所说的1 a 和2 a 构造方法构造的矩阵中，挑出部分使得二 河北人学：r 学硕十学位论文 分图中出现短圈的列，将其删除。再插入重新随机产生的列，使得二分图中不再存在小 于某个长度的圈。 2 3 3d a v e y 的构造方法 d a v e y 给出了一种不规则l d p c 码的构造方法，他把每个节点按照他们的度数d 复 制成d 个节点，然后构造二部图。 设校验矩阵中所有非零元素的个数为丁。则有 丁= ，2 沈= 珑f 成 ( 2 - 5 ) 一 j 、 j， 其中刀是分组码长( 矩阵列数) ，肌是校验式个数( 矩阵行数) ，丑和a 分别表示的是 非规则图上度为f 的信息节点和校验节点的相邻边所占的比例。按如下方法构造二部图： 图右半部有丁个节点( u ，) ，左半部也有丁个节点( d 1 ，砬岛) 。把列重为f 的列用f 个左节点表示，用其列号为这些节点命名。例如：若第j 列列重为3 ，则有三个 左节点用j 命名，分别是五，歹：，五。同样的把行重为j 的行用j 个右节点表示。之后，对 右节点做随机排列来构造校验式。为保证不出现双边，也就是一个右节点的两条边参与 同一个校验式，我们在排列时要保证同名的右节点分属于名字不同的左节点。 2 3 4 几何构造法 由于此种构造方法是基于有限几何基础之上的，所以我们首先介绍有限几何。设q 是一个有月个点、，条直线的有限几何，而且满足( 1 ) 每条直线上恰有尸个点；( 2 ) 任意两 点之间有且仅有一条直线相连；( 3 ) 每个点恰好在a 条直线上；( 4 ) 两条直线要么平行，要 么相交并且交于一点。有两类具有上述结构的有限几何，称为有限域上的射影几何和欧 氏几何 1 7 18 1 。 在g f ( 2 ) 构造一个，x ，维矩阵磁_ 矗，】，矩阵的每一行对应q 中的一条直线，每 一列对应q 中的一点。当且仅当f 条直线包含第歹个点时，忍，= 1 。矩阵的每一行的行重 第2 章l d p c 码的基础知识 为p ，表示此行对应直线包含p 个点；与之对应，矩阵的每列的列重为a ，表示此列 对应点在旯条直线上。这样构造的校验矩阵，因为两条直线之间最多只有一个交点，所 以任意两行之间没有一个以上的“l ”在相同的列出现；同样的原因，任意两列之间也没 有一个以上的“l ”在相同的行出现。矩阵砩的密度为，= p 疗= a ，如果d 和a 相对于 刀和，很小，那么砚是一个低密度矩阵。以砩为校验矩阵，其零空间给出了一个l d p c 码，码长为，z 。该码对应的因子图中没有长度为4 的环，其汉明距离至少为a + l 。 令磁为磁的转置矩阵，即磁= 【心】t ，那么磁也是一个低密度矩阵，行重为九， 列重为p 。以砩为检验矩阵，其零空间也给出了一个l d p c 码，码长为，。同样，该码 对应的因子图中也没有长度为4 的环，其汉明距离至少为p + l 。 除了上述构造方法，我们还可以利用欧氏几何( e g ) 和射影几何( p g ) 分别构造 e g l d p c 码和p g l d p c 码，对应于其中每种几何，均可构造两种l d p c 码。还可对校验 矩阵按一定规则进行扩展与删减，进而对该码进行扩展或缩短，进一步提高其性能。 2 3 5 图论方法构造 基于图的扩张的观点，可以构造具有良好扩展特性的扩张图( e x p a n d e rg r a p h ) 来得到 具有良好特性的l d p c 码，图的可扩展性影响码的译码性能。基于扩展图上扩展码的构 造可参看文献 1 9 】，这里我们不作详细介绍。另外，可以通过计算机统计出给定度序列 分布的l d p c 码码集的因子图中环的长度的分布情况，搜索出具有最大平均环长度的因 子图，并认为这样的因子图对应的l d p c 码具有较优的性能，可以将其作为构造结果进 行编码。 2 3 6 群论方法 以群的元素作为图的顶点，利用满足某些性质的群的子集s ，用该子集中元素与群 中其他元素的乘积关系构造顶点之间的连接关系，我们可以完成因子图的构造。如果s 中任意7 个元素蜀，g ：蜀的乘积蜀g ：g 都不为单位元p ，那么构造的图中没有长度小 河北大学j l i 学硕十学位论文 于，+ 1 的环。将构造的图进行适当的变换，就可得到所需的构造结果。如c a y l e y 图以及 m a r g u i i s 在此基础上给出的l d p c 码构造方法2 0 1 ，此外，还可利用陆n a n 吗a i l 图来构造 l d p c 码【2 1 2 2 】。 2 4 本章小结 本章从线性分组码的基础理论出发，引出l d p c 码的定义，介绍了稀疏校验矩阵和 t a r u l e r 图这两种表述方式，给出了l d p c 码的节点度分布描述；对规则l d p c 码、非规 则l d p c 码、多进制l d p c 码的特性做了较为详细地阐述。接着讨论了l d p c 码校验矩 阵的几种构造方法，包括随机构造法、图论构造法、群论构造法等。目前这方面的研究 还在进行，l u b y ，m i t z e m a c h e r ，s k o k r 0 1 l a h i 和s p i e h n a n 在【2 3 】中还给了构造非正则 l d p c 码的方法。不同的构造方法产生的l d p c 码，不仅译码性能有较大差别，而且编 码复杂度也有很大的差异。 1 4 第3 章l d p c 码的编泽码算法及性能仿真 第3 章l d p c 码的编译码算法及性能仿真 l d p c 码属于线性分组码，其通用编码方法即由校验矩阵求得生成矩阵，然后通过 生成矩阵生成码字，具有二次方的编码复杂度。l d p c 码所面临的一个主要问题是其较 高的编码复杂度和编码时延，幸运的是校验矩阵的稀疏性使得l d p c 码的线性编码成为 可能。 l d p c 码有很多种译码方法，本质上都是基于t a n n e r 图的消息传递译码算法。根据 消息迭代过程中传送消息的不同形式，可以将l d p c 的译码方法分为硬判决译码和软判 决译码。如果在译码过程中传送的消息是比特值，称之为硬判决译码；如果在译码过程 中传送的消息是与后验概率相关的消息，称之为软判决译码。主要的硬判译码算法有比 特翻转算法( b f ) 、加权的比特翻转算法( w b f ) 1 2 4 1 等；软译码算法主要有迭代结构的置信 传播算法( b e l i e fp r o p a g a t i o n ) 、简化的最小和积算法( m i i l - s u m ) 、归一化的最小和算法 ( n o 锄础i z e dm i n s u m ) 以及基于迭代可靠性的译码算法( o 凰e tb p b a s e d ) 等。 本章介绍了几种有效的编码方法，对基础的置信传播译码算法进行了分析与性能仿 真，并给出了l d p c 码编译码器的实现方案。 3 1l d p c 码的编码 3 1 1l d p c 码的直接编码 l d p c 码传统编码算法和一般的线性分组码十分类似，需要求出生成矩阵。若已知 长度为j i 的输入信息向量朋，以及七刀的生成矩阵g ，码字c 就可以容易的得到： c = 掰g 。 在获得校验矩阵圩后，利用日和g 之间的正交性可以用高斯消元法来得到生成矩 阵g 。假设稀疏校验矩阵曰有如下形式：= 蚂f c 2 】，其中c 2 是一个辫撒的稀疏方阵， 并且在二元域上是非奇异阵，那么g 就可以给出： 儿 p ， 河北大学j r 学硕十学伊论文 很容易验证，这样的g 满足册t = 0 。其中，厶是一个七阶的单位矩阵，这样得到 的码具有系统码的形式。l d p c 码一般都具有系统码的形式，否则由码字来恢复信息比 特是一个十分困难的过程。如果在二元域上日的秩是尺，而且c 2 是奇异矩阵( r m ，结束。 3 、如果该列中还有其他不为o 的元素，将该元素所在的行与第行j 二相加，然后将功口 1 ，返回上个步骤。 这样得到的日的前尺列是线性独立的，因此g 也能方便的求解出。 图3 1 与h 矩阵等价的下三角矩阵g 通过上面的编码方法我们可以看出，在对校验矩阵乩。作高斯消去的时候，主要 的操作包括与运算和异或运算( 模二加) ，其运算量大约为码长的三次方d ( 3 ) 。经过高 1 6 第3 章l d p c 码的编译码算法及性能仿真 斯消去而获得的矩阵g ，通常已经不再具有稀疏的特性，所以在按照递推方式获得校验 位的时候，编码运算量大概是o ( 2 ) ，即l d p c 码编码器的直接实现具有码长的二次方 复杂度。 3 1 2l d p c 码的简化编码 直接编码的方法具有码长的二次方复杂度，主要原因是由于高斯消去法破坏了原有 奇偶校验矩阵的稀疏性。针对l d p c 码的编码问题，融c h a r d s o n 和u r b a n k e 提出了一种 基于近似下三角矩阵的有效地编码方法【2 5 】，即对原有的奇偶校验矩阵做预处理，就能有 效地使编码复杂度控制到接近线性复杂度。 首先对矩阵的列做重排，这样虽然不能得到一个完全的下三角形式的矩阵，但可以 获得一个近似的下三角矩阵，如图3 2 所示。并将何分成六个分块的稀疏矩阵，其中矩 阵间隙g 是一个相当小的数。 图3 2 重排h 矩阵的列获得近似下三角阵 对于要发送的信息序列，直接作为l d p c 码码字的前一时个信息位比特输出，对 于其生成的