（信息与通信工程专业论文）基于图模型的ldpc码译码算法研究.pdf

国防科学技术大学研究生院工学硕士学位论文 摘要 l d p c 码( 低密度校验码) 是一类可以用非常稀疏的奇偶校验矩阵定义的线性分 组纠错码，具有逼近香农限的性能。消息传递机制是影响l d p c 码译码性能的重要 因素之一，寻找不同的消息传递机制以改进译码性能一个很有意义的课题。 本文主要研究内容如下： ( 1 ) 首先，简要概述了纠错编码的发展情况；并分析了信道容量的计算；对 l d p c 码的产生和研究现状进行了论述，指出对l d p c 码的深入研究，有助于我们朝 着s h a n n o n 限所在的方向迈出更大的步伐。 ( 2 ) 介绍了l d p c 码图模型理论；分析环对l d p c 码性能的影响；并讨论了如何 构造l d p e 码校验矩阵。这为后面的深入研究奠定了必备的理论基础。 ( 3 ) 结合概率论知识，介绍了消息传递算法的基本原理；并在此基础上分析 和推导了各种l d p c 码经典译码算法，包括概率测度和积译码算法、对数似然比测 度和积译码算法和最小和译码算法。 ( 4 ) 研究了和积译码算法在树上的消息传递过程：在l d p c 码经典译码算法基 础上，将洪水消息传递机制转换成基于校验节点的串行消息传递机制和基于变量 节点的消息传递机制，分别对应串行译码算法i 和串行译码算法i i ，并对密度进 化和译码复杂度等方面进行分析；仿真结果表明，两种串行译码算法都使译码性 能得到明显提高，改善了消息收敛特性，降低了译码复杂度。串行译码算法i i 极 大的提高了译码性能；串行译码算法i 在译码性能和复杂度之间找到了更好的平 衡点，是一种应用价值较高的译码算法。 ( 5 ) 介绍了量化译码的背景和量化原理，分析了量化译码对译码器实现的重 要作用，基于串行译码算法i ，以消息种类的不同分别研究了有限长量化对译码 性能的影响，并提出可行的串行量化译码方案，其性能接近连续译码性能。 【关键词】：l d p c 码，图模型，消息传递算法，洪水消息传递机制，串行消息传递 机制，量化译码 第1 页 国防科学技术大学研究生院工学硕十学位论文 a b s t r a c t l o wd e n s i t yp a r i t yc h e c kc o d e s 盯eac l a s so fi i n e a rb i o c ke r m r c o r r c c t i n gc o d e s t 1 1 a tc a nb ed e f 协e db y 虹1 ev e r ys p a r s ep 州t y - c h e c km a 缸x 1 1 1 e i re r m rp e r f o r n l 赫c e a p p r o a c hs h a 衄o nl i r n i t s m e s s a g e p a s s i n gs c h e d u l e i sa 1 1i m p o r t a l l tf 她t o rw h i c h a 圩e c t sm ep e r f b 姗a 玎c eo fd e c o d i n g a ns i g i l i f i c a t i v eq u e s t i o ni sw h e m e rd i 旋r e n t s c h e i i u l e sc o u l di n l p r o v ed e c o d i n gp e r r ) n n a i l c e t l l i sp a p e rm 血l yc o n t a i i l sm ef o l l o w i n ga s p e c t s ： ( 1 ) f i r s t ，s i m p l yi n 血o d u c et h ed e v e l o p m e mo fe r r o r c o r r e c t 讪gc o d e s ；a n a l y s e1 l l e c a p a c 埘o fc h a 加e l s ；a n di n t r o d u c et 1 1 eb a c k g r o u n do fl d p cc o d e s ，p o i mo u t 恤t r e s e a r c l l i n g0 nl d p c c o d e sw i l ll l e l pu sg e tt ot h es h a n n o n1 i m i t ( 2 ) i n 舡o d u c et h eg r a p ht h e o r yo fl d p cc o d e s ；8 n a l y s et h eh p a c to fc y c l e ；a n d r e s e a r c hh o wt oc o n 曲r u c t l ep a r i t yc h e c km 枷x ，t h e s ea r et 1 1 eb a s i cn l e o r yf o r f o l l o w i n gr e s e a r c h ( 3 ) c o m b i n e dv v i t hp m b a b i l 时s 锄s t i ck n o w l e d g e ，i n 仃o d u c et 1 1 eb a s i ct h e o r yo f m e s s a g ep a s s i n ga l g o r i t h m ；a n a l y s et h ec l a s s i c a ld e c o d i n ga l g o r i t l mo fl 冱) p cc o d e s ， i n c l u d i n gs mp r o d u c t 舢g o m h m d l i c hb a s e do np r o b a b i l 蚵a j l dl l r ，a 1 1 dm i ns 啪 a l g o r j t l l l l l ( 4 ) r e s e 鲫c hm e s s a g ep a s s i n gp r o c e s so n 饥en e e ；a c c o r d i n gs p a ，t l l mm e n o o d i n gs c h e d u l et o s e r i a is c h e d u l eb a s e do nc n o d e sa 1 1 dv n o d e s ，n 锄e l ys e r i a l a i g o r i t h mi a n di i ，a n a l y s ed ea n dc o m p l e x i t y ；s i m u l a t i o n ss h o wt h a t 廿l eb o t hs e r i a l a l g 谢蛔sc o u l di m p r o v ed e c o d i n gp 耐a m 硷n c e ，i m p f o v ec o n v e 曙e n c ep r o p e n y ，r e d u c e c o m p l e x i 砂 s e r i a l a l g o r “hi ii m p r o v e sd e c o d i n gp e r f o r m a n c eg r e a y ； s e r i a l a l g o r i t 硒i f i n d st 1 1 eb e t t e rt m d e o 行b e t w e e np e r f o m a l l c ea n dc o m p l e x i t y ，i ti sag o o d d e c o d i n ga l g o r i 也mw i t hh 培h 印p l i c a t i o nv a l u e ( 5 ) i n 乜d d u c et h cb a c k g r o u n do fq u 趾t i z e dd e c o d i l 喀a n db a s i c l e o r y a n a l y s e e f f b c to f q u a n t i z e dd e c o d i n g ，r e s e a r c hm ei m p a c to f l i r i l i t c dq u a n t i z c dt os e r i a ld e c o d i n g i ，a n dp r e s e n tf e a s i b l ep r o j e c tf o rq u a n t i z e dd e c o d i n g 【k e yw o r d s 】：l d p cc o d e s ，g r a p h i c a lm o d e l s ，m e s s a g ep a s s i n ga l g o r i t l l i n ，n o o d i n g s c h e d u l e ，s e r i a ls c h e d u l e ，q u a l l t i z e dd e c o d i n g 第1 i 页 国防科学技术大学研究生院工学硕士学位论文 图目录 图2 1 ( 1 0 ，2 ，4 1 规贝4l d p c 码一1 1 图2 2 二分图存在长度为4 的环1 3 图2 3 二分图存在长度为6 的环1 3 图2 4 校验矩阵存在长度为4 的环1 4 图2 5 校验矩阵存在长度为6 的环1 4 图2 6 ( 2 0 ，3 ，4 1 l d p c 码校验矩阵1 6 图2 7m a c k a ) r 构造法示意图1 7 图3 1t a n n e r 图上的迭代过程2 4 图3 2 描述消息传递的局部t a n n e r 图2 4 图3 3 庐“) 函数特性曲线3 4 图4 1 变量节点展开的树3 9 图4 2 变量节点展开的多层树4 0 图4 3m a x = 1 0 0 时的误比特率5 1 图4 4m a x = 1 0 0 时的误帧率5 1 图4 5m a x = 2 0 时的误比特率5 l 图4 6m a x = 2 0 时的误帧率5 1 图4 7 洪水译码算法性能随迭代次数变化曲线5 2 图4 8 最小和译码算法性能随迭代次数变化曲线5 2 图4 9 串行译码算法i 性能随迭代次数变化曲线5 2 图4 1 0 串行译码算法i i 性能随迭代次数变化曲线5 2 图4 1 1m a x = 1 0 0 时的平均迭代次数5 3 图4 1 2m a x = 2 0 时的平均迭代次数5 3 图4 1 3 不同码长时的误比特率5 4 图4 1 4 不同码长时的误帧率5 4 图5 1e 0 = ld b 接收信号概率密度曲线5 9 图5 2e 0 = 2 d b 接收信号概率密度曲线5 9 图5 3e ，0 = 3 d b 接收信号概率密度曲线5 9 图5 4 接收信号量化处理后的误比特率6 0 图5 5 接收信号量化处理后的误帧率6 0 l 圉5 6 庐( 曲= 饿+ 6 6 1 图5 7 使用查找表后的误比特率6 2 国防科学技术大学研究生院工学硕士学位论文 图5 8 使用查找表后的误帧率6 2 图5 9e b n o = l d b 变量消息的统计特性6 3 图5 1 0e b n o = 2 d b 变量消息的统计特性6 3 图5 1 1e b n o = 3 d b 变量消息的统计特性6 3 图5 1 2e b n o = 1 d b 校验消息的统计特性6 3 图5 1 3e b n o = 2 d b 校验消息的统计特性6 3 图5 1 4e b n o = 3 d b 校验消息的统计特性6 3 图5 1 5 量化译码后的误码率6 4 图5 1 6 量化译码后的误帧率6 4 v 国防科学技术大学研究生院工学硕士学位论文 表目录 表4 1 洪水译码算法一次迭代的运算量4 8 表4 2 最小和算法一次迭代的运算量4 8 表4 3 串行译码算法i 一次迭代的运算量4 8 表4 4 串行译码算法i i 一次迭代的运算量4 9 表5 1 与最，。( 如) 的关系6 0 表5 2 妒( x ) 量化实现表6 2 表5 3 量化方案表6 4 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：基王里搓型盟k ! 匹丑竖塑篡洼盈塞 学位论文作者签名受磊日期：口j 口厂年，月，护日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：基王圈搓型煎l ! 堕璺堡盟篡洼班窒 学位论文作者签名：垦益 日期：一j ，年，r 月口日 作者指导教师签名 壁蓑 日期：2 耕，f 月口日 国防科学技术大学研究生院工学硕士学位论文 第一章绪论 1 1纠错编码发展概述 所有的数字通信系统，包括通信、雷达、遥控遥测、数字计算机内部及数字 计算机之间的数据传输，以及数据存储系统都是把信源发出的信息，经过某些变 换和传输路径送给收端用户。数字通信中的一个主要问题是可靠性问题。信息理 论从通信系统的整体最佳化来研究信息的传输和处理。任意给定的信道都有一个 固有的量，称之为信道容量，正好是信息传输速率的上确界n 1 。纠错编码是以特 定的控制手段，引入适量冗余比特，克服信息传输中受到的噪声和干扰影响。纠 错编码技术是保证传输可靠性的一项关键技术。在数字移动通信、数字卫星通信 等应用中，传播环境较为恶劣，而纠错码技术是这些系统中用来维持系统性能的 一个重要手段。分组码是最早应用的信道编码技术，在分组码每个码字中，监督 元仅与本组的信息元有关，而与别组的信息元无关。汉明码是h 锄i n g 在1 9 5 0 年 提出的分组码，这也是第一个纠错码。1 9 5 7 年p r a n g e 首先开始研究循环码，这是 线性分组码的一个重要子类，由于它具有循环特性和优良的代数结构，使得可用 简单的反馈移存器实现编码和伴随式计算，并可使用多种简单而有效的方法进行 译码。1 9 5 9 年h o c g e n g h e m 与1 9 6 0 年b o s e 及c h a u h u r i 分别提出了纠正多个随机 错误的循环码，称为b c h 码。这是一类纠错能力强，构造方便的好码。1 9 6 0 年 p e l e r s o n 找到了二元b c h 码的第一个有效算法，从而将b c h 码由理论研究推向实 际应用阶段。r e e d s d o m o n ( r s ) 是多元b c h 码的一个特殊子类，是应用广泛而有 效的一类线性码。它是一类g f ( q ) ( q 2 ) 域上的码长为q l 的循环码，它既可以纠 随机错误，也可以纠正突发错误，是m s d 码( 最大距离可分码) 中的纠错能力最 强的编码。定义在g f ( 2 a ) 域上的非二元r s 码，通常用来做二元内码的外码。信息 首先用r s 码编码，然后再用二进制码( 例如卷积码) 再次编码，这就是f o r n e y 的级联码。卷积码是由麻省理工学院e l i a s 提出的，和分组码一样，卷积码也是 将长度为k 的输入信息组映射成长度为n 的输出编码组。所不同的是，输出码组 不仅和对应输入有关，还依赖以前的m 个输入信息。我们称k ( m + 1 ) 为该卷积码的 第l 页 国防科学技术大学研究生院工学硕士学位论文 卷积深度。在编码存储较大时，可以得到较低的译码错误概率。在1 9 9 3 年t u r b o 码出现之前，高斯白噪信道性能最好的编码是f o m e y 提出的用r e e d s d o m o n 码做 外码，卷积码做内码的级联码。用移位寄存器可以很方便的实现卷积码，其译码 方法有两种：v i t e r b i 译码和序列译码。卷积码理论的发展与译码的两个最主要的 方法密切关连。这两个译码方法分别为代数译码和概率译码。代数译码从码的代 数结构出发，以一个约束长度的接收序列为单位，对该接收序列的信息码组进行 译码。这是基于码的代数结构的译码方法。而概率译码不仅考虑码的结构，还考 虑信道的统计特性，使译码的性能更好。序列译码与v i t e r b i 最大似然译码都是 概率译码。v i t e r b i 最大似然译码的运算时间是固定的，其译码复杂性均与约束长 度成指数增长。而序列译码时延是随机的，它与信道干扰情况有关，尽管译码复 杂度与约束长度无关，但其纠错能力有限。只有在速率小于某个低于信道容量c 的门限r 的条件下，序列译码才能够有效纠错。在门限r 点计算量将变得非常大。 在1 9 4 8 年，s h a n n o n 就提出了信道编码定理，界定了纠错编码的性能。b e r r o u 等 在1 9 9 3 年提出的t u r b o 码，性能接近了s h a n n o n 限，这标志着信道编码理论进入 了一个新的阶段，是近年来纠错编码领域的一个突破。特别地，t u r b o 码采用的 s i s o 迭代译码技术能够在许多情况下相当接近于s h a n n o n 极限，同时其复杂度远 低于最大似然译码算法，因此迅速在实际系统中得到了广泛的采用。两年后， m a c k a y 和n e a l 重新发现l d p c 码和t u r b o 码有着相似的优秀性能，而且在某些方 面已经超过了t u r b o 码，之后l d p c 码得到大家的关注，称为新的研究热点。本文 就主要对基于图模型的l d p c 码译码算法进行研究。 1 2 信道容量 在信道编码领域，学者们一直在寻找接近s h a n n o n 界的实用的编码。在这一 节中，我们将简单地回顾一下关于s h a n n o n 界的理论，作为论文后面章节的理论 基础n “。 信道容量定义为信道输入与信道输出的互信息，它表现了信道能够可靠传输 的最大速率。最常见的信道容量计算式就是带宽、功率受限下的加性高斯白噪声 ( a w g n ) 信道容量计算公式。设a w g n 信道带宽受限于卜，矿1 ，噪声双边功率谱密 第2 页 国防科学技术大学研冗生院工学坝士字位论文 度为掣，信号功率为p ，则 c 胡l o g ( 专肛州 ( 1 _ - ? 这个容量仅在输入服从高斯分布的情况下可以达到。如果输入信号调制受限， 那么容量将会小于上面这个值。考虑一个d m c ( 离散无记忆信道) ，它的输入符号 集为x = ，墨，一i ) ，输出符号集为y = ，儿，。，y 口- l ，并且转移概率为 p ( mi 一) 。假定传输符号为即接收到符号为m ，则事件x = _ 和事件】，= m 的互 信息如g 制濮中 p ( ”) = 尸( y = m ) = p ( 坼) p ( mi ) 因此，输入集x 和输出集y 之间的平均互信息为 邪；y ) = 善霎p ( _ ) p ( 小) b s 铡 ，( x ；y ) = p ( _ ) p ( mj - ) l o g 裂 ，；0j = oo 、，f ， 由上式可知，( ；】，) 的值取决于输入符号集的概率分布 尸( o ) 。令( j ；l ，) 在所有输入分布 p ( _ ) ) 中取得最大值，则这个最大值只与信道的特性 _ p ( 以i - ) 有关，它标志着信道的传输能力，称为信道容量，记为c 。这样我们就得到了离 散无记忆信道的容量计算式： c = 黼肛= 臀芸喜p ( _ m 椭掣”z ) 对转移概率为p 的二进制对称信道而言，当输入等概时，互信息取得最大值， 信道容量为 c = 1 + p l 0 9 2 p + ( 1 一p ) 1 0 9 2 ( 1 一p ) = 1 一日( p ) 其中，h ( p ) 是二元熵函数。 对于离散输入连续输出信道，记输入符号集为x = ，墨。，一0 ，输出符号集 第3 页 日阴付予仅小人于研九，土阮j 一子坝i 子1 丝w 义 为y = ( 一，佃) 。在式( 卜2 ) 中，将对输出符号的求和换成积分，相应的概率 ，( 只l _ ) 换成概率密度p i t ) ，这样就得到了离散输入连续输出信道的容量计算 式： c = 翁喜亡m 盹) l o s ：篇粤 ( 1 _ 。) 对照式( 卜3 ) ，对二元输入高斯白噪声信道而言，信道容量为 c = 斟y l 同嵫帮砂啦卅同k 钾砂 其中e 为每符号能量。 若对二元输入高斯信道输出做硬判决，则信道等效为一个b s c ，其转移概率为 吖寿e 坤 _ 粤b 叮击e 冲 - 华p ：r 去。坤 _ 掣b 厕) = 去e 坤 一净c 扯( y + 厄) ，厕， = q ( 而) ( 1 4 其中q ( 垆f 击e 冲( 卜 给定信道容量c ，由信道编码定理可知，只要传输码率r 低于c ，就可以获 得任意小的误比特率岛。但是如果允许a 大于零，那么可获得更大的编码增益。 一个编码调制系统方案的“编码增益”是指达到一定的目标错误率所需的眠璃与 相应的无编码方案的肼氓比较所减少的数值。 第4 页 国防科学技术大学研究生院工学硕士学位论文 1 3l d p c 码的产生和研究现状 l d p c 码( 低密度校验码) 的起源最早可以追溯到2 0 世纪6 0 年代g a l l a g e r 的博 士论文l o w d e n s i t yp a r i t y c h e c kc o d e s “1 。g a l l a g e r 在其博士论文中提出舯 二元l d p c 码是一类可以用非常稀疏的奇偶校验矩阵定义的线性分组纠错码。l d p c 码具有非常稀疏的校验矩阵，即矩阵中“l ”的数量很小。矩阵每列各自包含相同 小数目的“1 ”，表示每个码元比特受到相同数目的校验约束：每行也都各自包含 相同小数目的“1 ”，表示每个校验集对相同数目的码元比特进行校验约束；同时， 行和列所包含的“1 ”的数目不同。g a l l a g e r 证明了这类码具有很好的汉明距离特 性，在计算树上进行多次迭代后验概率译码可以获得依码字长度呈指数降低的比 特错误概率，后来人们把这类码称为g a l l a g e r 码。由于当时计算机水平和人们对 这种形式非常简单的码的认识不足，l d p c 码的出现并没有引起人们的重视，接下 来的几十年一直无人问津，只有寥寥几篇文章对其进行了研究，其中一篇是1 9 8 1 年r m i c h a e lt a n n e r 发表的ar e c u r s i v ea p p r o a c ht o1 0 wc o m p l e x i t yc o d e s 嘲。在这篇文章中，t a n n e r 为基于图模型的码奠定了基石，引入了l d p c 码的二分 图( b i p a r t i t eg r a p h i c a lm o d e l ，又称t a n n e r 图) ，还提出了最小和( m i n s u m ) 算法与和积( s u m p r o d u c t ) 算法两种消息传递算法，证明基于有限无环 ( c y c l e f r e e ) t a n n e r 图时，最小和算法准确实现了最小码字错误概率的最佳最 大似然译码，和积算法实现了最小符号错误概率的最大边界后验概率算法。但是， 无环图上的消息传递算法对每个中间成本函数只计算一次，导致译码复杂度依约 束长度指数增长。低结构复杂度的有环t a n n e r 图使译码复杂度显著降低，但是无 法保证迭代算法的收敛性，只能实现次优译码。直到1 9 9 3 年t u r b o 码出现以后，研 究者们才发现t u r b o 码迭代译码的方法和码集合的概念与l d p c 码有异曲同工之妙。 9 0 年代后期，l d p c 码被s p i e l m a n 和m a c k a y “1 等人再度发现，唤起了人们对l d p c 码 的研究热潮。m a c k a y 和n e a l 关于稀疏随机图上定义的l d p c 码能够接近容量限的结 果以及s i p s e r 和s p i e l m a n “1 的线性复杂度扩展图码使人们重新认识到g a l l a g e r 工 作内在的巨大潜力。研究结果表明，非规则图上的和非二元的l d f c 码具有更好的 收敛性，r i e h a r d s o n “等示范的性能已经相当接近s h a n n o n 容量限。l d p c 码在给定 误码率情况下的信息传输速率可以非常接近s h a n n o n 限，对于一些中长码长的l d p c 第5 页 国防科学技术大学研究生院i _ _ f = 学硕士学位论文 码，其纠错性能甚至已经超过t u r b o 码。l d p c 码以其优越的纠错性能和译码的低复 杂度而越来越得到人们的重视。l d p c 码研究的兴起，除了t u r b o 码的研究热潮为它 提供了契机，还有两方面的原因：一方面是由于s p i e l m a n 、m a c k a y 等几位学者独 立研究了低密度校验码，发现l d p c 码有杰出的纠错能力”；而另一方面是由于 w i b e r g 在他的关于基于图模型码的论文中作了拓荒性的研究工作。w i b e r g 结合对 t u r b o 码和网格的研究，把t a n n e r 图推广到具有隐含状态变量的码图( w i b e r g 图) 上，使网格型结构作为其特殊情况，从而使消息传递算法包容了基于网格的译码 算法。他的图模型还允许使用更一般性的量度( m e t r i c ) 作为成本函数，从而适用 于非均匀先验概率分布模型或有记忆信道模型。 此后，经过众多学者的研究，l d p c 码的理论研究得到了蓬勃发展。w i b e r g 图 的理论分析技术被r i c h a r d s o n 、u r b a n k e 等学者发展后，可以应用到a w g n 信道中非 规则l d p c 码的长码设计当中以满足各种不同应用目的。给定一个具有任意度分布 的二元l d p c 码，这几位学者指出在对称信道中采用和积译码算法时概率密度的进 化可以精确计算出来。此外，他们还证明了当码长足够大、迭代次数足够多时， 存在一个门限值，如果噪声低于这个门限就可以实现无差错传输。而这个门限值 可以通过选择度分布序列进行优化。仿真结果表明用这种方法设计的码，当码长 达到1 0 5 时其性能要优于t u r b o 码。c h u n g 等人设计了1 2 码率的l d p c 码，其门限值 离s h a n n o n 限在o 0 0 4 5 d b 之内。1 ，并应用高斯逼近原理，用单一参数分析了l d p c 码 的密度进化问题。密度进化的不动点概念与方法在t u r b o l i k e 码的分析中，一方 面指导建立迭代终止准则，另一方面也指导码的设计准则。e e l e f t h e r i o u 等提出 基于二元l d p c 码的多电平编码，并研究了用于宽带接入网中不对称数字用户线 ( a d s l ) 的传输性能“”。h s o n g 研究了在磁记录信道中应用l d p c 码的情况“。e y e o 等提出了用于磁记录的2 类l d p c 码的译码方案和相应的串行结构，它们具有高的吞 吐率和低的计算复杂度“”。m c h i a n i 等对l d p c 码用于有记忆块衰落( b l o c k f a d i n g ) 信道时的性能进行了评估n ”。j h o u 等研究了用于瑞利衰落信道l d p c 码的优化和性 能分析，认为移动通信终端在宽范围移动速度情况下，优化的非规则码( 块长为 3 0 7 2 ) 性能优于相应的t u r b o 码“”。b m y h r e 提出一种速率自适应l d p c 编码调制的方 案用于慢变化平坦衰落信道，经推广还可应用于f e ca r q 系统“”。t w a d a y a a 针对 第6 页 国防科学技术大学研究生院工学硕士学位论文 l d p c 码应用于突发信道( 包括衰落信道) 的情况，提出了适合于隐马尔可夫噪声信 道模型的由和积算法和前后向似然估计构成的迭代译码算法“”。f l a r i o n 开发的集 成了l d p c 的f 1 a s ho f d m 移动无线芯片组已可用于基于i p 的移动宽带网，以期增大传 输距离和在无线信道中的坚韧性，其数据速率可达3 m b p s 。v o c a lt e c h n o l o g i e s ，n d 推出了一种用于w l a n 的l d p c t u r b o 不对称解决方案，即下行链路采用l d p c ，上行链 路采用t u r b o 码，目的在于节能。据称，采用该方案后用于i e e e 8 0 2 1 1 a b gw l a n 移 动终端的电池寿命可延长至原来的4 倍。l d p c 码还广泛应用于数字电视传输网络， 如欧洲第二代数字电视卫星传输标准就使用了2 种码长、1 1 种可变码率的l d p c 码作 为信道编码。l d p c 码具有巨大的应用潜力，将在深空通信、光纤通信、卫星数字视 频和声频广播、磁光全息存储、移动和固定无线通信、电缆调制解调器和数字 用户线( d s l ) 中得到广泛应用。 总之，l d p c 码的出现掀开了纠错编码研究领域的新篇章。对l d p c 码的深入研 究，有助于我们朝着s h a n n o n 限所在的方向迈出更大的步伐。 1 4 本文的主要工作 作者结合国家自然科学基金调研和数字电视传输标准等科研项目，在对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 码性能所产生的影响，并介绍了常用的几种 l d p c 码的构造方法，为后续深入研究奠定了基础。 第三章介绍了与译码算法相关的概率论知识，详细说明消息传递算法的原理。 在此基础之上，对l d p c 码的各种经典译码算法进行了推导和分析，包括概率测度 和积译码算法、对数似然比测度和积译码算法和最小和译码算法。 第四章介绍了树的相关概念和性质，将和积译码算法在树上的消息传递过程 第7 页 国防科学技术大学研究生院工学硕士学位论文 进行了描述，由此引入消息传递机制，说明其对译码性能的重要作用。在l d p c 码 经典译码算法基础上，使洪水消息传递机制分别转换为基于校验节点的串行消息 传递机制和基于变量节点的串行消息传递机制，分别对应文中的串行译码算法i 和串行译码算法i i ，并对其特性进行分析。然后结合l d p c 码构造方法，构造出校 验矩阵和生成矩阵对各种译码算法进行计算机仿真。仿真结果表明相对于洪水译 码算法，两种串行译码算法均能提高译码性能，改善收敛特性，而且串行译码算 法i 在简化译码复杂度方面具有更大的优势。 第五章介绍了量化译码背景，基于量化原理，针对l d p c 码串行译码算法i 的 量化译码进行了深入分析，分别研究了接收信号、查找表和中间变量的有限长量 化处理对译码性能所产生的影响，结合计算机仿真提出可行的串行量化译码方案。 第六章为结论，并指出进一步的研究方向。 第8 页 国防科学技术大学研究生院工学硕士学位论文 第二章l d p c 码图模型及校验矩阵构造方法 2 1l d p c 码的图模型 l d p c 码( l o wd e n s i t yp a r i t yc h e c kc o d e s ) 是一种线性分组码，可由低密 度稀疏奇偶校验矩阵月的零空间来定义。所谓“稀疏性”指的是( 在卵f 2 ) 域上) 矩阵h 中包含o 的个数远大于1 的个数，而“低密度”指的是矩阵h 中含1 的密度很低。 众所周知线性分组码可以由它的生成矩阵g = 岛 。决定，给定生成矩阵g ，码字 集合可以表示为 r1 c = x 胃i x = ，q l j 其中，品为生成矩阵g 的第f 行。等价地，线性分组码也可以由校验矩阵日来 决定。给定校验矩阵，码字集合可以表示为 c = x 胃i ( x ，囊) = o ，f _ 1 ，2 ，n 一_ i 危为校验矩阵日的第f 行。因此选定了校验矩阵，那么这个线性分组码也就确定了。 根据校验矩阵的不同，l d p c 码分为两大类：规则l d p c 码( r e g u l a rl o wd e n s i t y p a r i t yc h e c kc o d e s ) 和非规则l d p c 再马( i r r e g u l a rl o wd e n s i t yp a r i t yc h e c k c o d e s ) 。规则l d p c 码校验矩阵每行( 列) 中的非零元素个数是相同的，而非规则 l p d c 码校验矩阵每行( 列) 中的非零元素个数未必相同。规则l d p c 码用( ，j ，k ) 表 示，其中，为校验矩阵每列非零元素个数( 称为列权重) 。足为校验矩阵每行非零 西以 元素个数( 称为行权重) 。非规则l d p c 码用多项式z ( x ) = x 1 和p ( x ) = 乃x 川 f _ l j = 1 表示，其中五为列权重为f 所占的比例，p ，为行权重为_ ，所占的比例，和吃分 别代表列权重和行权重的最大值。当多项式转化为五( x ) = 一。1 和p ( x ) = 并“1 时，列 权重和行权重均为常数，此时即为规则码。 第一章曾指出，l d p c 码的发展与图模型的发展紧密相关，l d p c 码的构造和译 码均可通过图模型来表示。因此在介绍l d p c 码的构造之前，先介绍有关的图模型。 第9 页 国防科学技术大学研究生院工学硕士学位论文 定义2 1 “ 图( g r a p h ) g 可以用一个三重组g = ( 矿，e ，中) 来表示，其中矿是 一个非空节点集，e 是边的集合，巾是从边集e 到节点偶对集y 矿上的函数。 令边p 对应节点偶对( 口，6 ) ，若( d ，6 ) 是有序的则称边p 为有向边，否则称p 为 无向边。存在有向边的图称为有向图，每条边都是无向边的图称为无向图。在无 向图g = ( 矿，e ，m ) 中，与节点v e y 相连的边数称为节点v 的度数，记为巩。 定义2 2 。1 若无向图g = ( y ，e ，中) 的节点集y 可以划分为两个子集巧和吃， 使得v e e ，p 的一个端点属于k ，另一个端点属于k ，则称g 为二分图 ( b i p a r t i t eg r a p h ) 。若节点集k 中所有节点的度数都相同并且节点集k 中所有 节点的度数也都相同，则称g 为规则二分图( r e g u l a rb i p a r t i t eg r a p h ) ，否则 称为非规则二分图( i r r e g u l a rb i p a r t i t eg r a p h ) 。 定义2 3 “”二分图g 的邻接矩阵( a d j a e e n c y 珥a t r i x ) ：设二分图的节点集 矿可以划分为两个子集k 和k ，使得v e e ，p 的一个端点属于k ，另一个端点属 于k 。将k 中的节点依次排成一行，并将k 中的节点排成一列。若节点v l k 和 k 之间有边相连，则在v 1 所在列，v ，所在行的交点位置上填l ，否则填0 。这样 构造的矩阵日称为二分图g 的邻接矩阵。 如前所述，规则l d p c 码的行权重和列权重均为常数，其校验矩阵即为一个规 则二分图的邻接矩阵，而非规则l d p c 码的校验矩阵是一个非规则二分图的邻接矩 阵。由于t a n n e r 首先将l d p c 码用二分图来表示，因此在编码理论界通常把表示l d p c 码的二分图称为t a n n e r 图。图2 1 ( a ) 和( b ) 分别给出了f l o ，2 ，4 1 规则l d p c 码的校验 矩阵和它对应的t a n n e r 图。 t a n n e r 图由变量节点( v a r i a b l en o d e s ) 、校验节点( c h e c kn o d e s ) 以及连接它 们的边( e d g e s ) 组成。图2 一l ( b ) 的t a n n e r 图中，下面的节点为变量节点，代表了编 码后的比特位，对应校验矩阵中相应的列：上面的节点为校验节点，代表了编码 比特组成的校验方程，对应校验矩阵中相应的行；图中的边则表示下面的某个节 点出现在上面的某个校验方程中，对应了校验矩阵中的非o 元素。上述例子是一个 二元域上的l d p c 码，其编码的校验矩阵中，每一列有2 个非零元，每一行有4 个非 零元。即编码码字中的每个比特参加2 个校验约束，而每个校验约束包括4 个比特。 第1 0 页 国防科学技术大学研究生院工学硕士学位论文 11lloooo o o l0 0o111o o o 01oo10 011o 0 0loo1o101 0 0 01oo10 11 ( a ) ( 1 0 ，2 ，4 ) l d p c 码的校验矩阵 ( b ) ( 1 0 ，2 ，4 ) l d p c 码的t a n n e r 图 图2 1 ( 1 0 ，2 ，4 ) 规则l d p c 码 从变量节点的角度看，其度数越高越好，因为对它进行监督的校验节点越多， 提供的译码信息越准确，使得它能更快更准确地被译码。但是从校验节点角度看， 则是度数越低越好，因为这样它对与之相邻变量节点的校验约束更有效，变量节 点所获得的校验信息就更准确。针对这一矛盾，非规则码显然比规则码能够更好 地实现两者的平衡。在非规则码中，度数高的变量节点迅速得到它们的正确译码， 这样它们就可以给相邻的校验节点更加有效的概率信息，而这些校验节点又可以 给与它们相连的度数低的变量节点更多的信息，从而产生“波浪效应”( w a v e e f f e c t ) ：度数高的变量节点首先得到它们的正确译码，接着是度数稍低的变量 节点，然后是度数更低的变量节点，如此继续下去，直到译出所有的变量节点。 正是这种波浪效应，使不规则码可以获得较规则码更好的性能。 2 2 环对l d p c 码影响的分析 2 2 1 环的定义 我们已经知道l d p c 码校验矩阵的图形表示形式是t a n n e r 图，t a n n e r 图和校验 第1 1 页 国防科学技术大学研究生院工学硕士学位论文 矩阵之间是唯一确定的关系。一个m 的校验矩阵h 定义了每个具有比特的 码字满足m 个奇偶校验集的约束。一个t a n n e r 图包括个变量节点，每个节点对 应日中一个比特位；还包括m 个校验节点，每个节点对应一个中的奇偶校验。 校验节点将连到将要得到校验的变量节点上：具体的说，当第m 个校验涉及到第月 个比特位，即只。= 1 的时候，将有一条边连接校验节点m 和变量节点n 。t a n n e r 图名称的由来就是因为它包括两类节点：变量节点和校验节点。其中，任何同一 类的节点之间都不会有连接，并且t a n n e r 图中的总边数和校验矩阵