（通信与信息系统专业论文）多进制ldpc码与rs码的性能比较研究.pdf

摘要 本论文主要对多进制l d p c 码( q l d p c ，n o n - b i n a r yl o wd e n s i t yp a r i t y c h e c kc o d e s ) 的性能进行了深入的研究，并与二进制l d p c 码( b l d p c ) 、r s 码( r c e d o s o l o m o nc o d e s ) 进行了全面的比较分析。仿真结果表明，q l d p c 码 具有优良的抗突发噪声和抗衰落性能，尤其在高码率下的性能更为突出。在突发 噪声长度高达1 4 4 b i t s 的情况下，误帧率达到1 0 。4 水平时，q - l d p c 码比r s 码多 出2 7 d b 的编码增益；在瑞利衰落信道下，误帧率为l 酽时，q - l d p c 码甚至比 采用软判决译码的r s 码多出7 1 d b 的编码增益。这对于o l d p c 码在未来数字 通信系统当中的应用具有重要的实际意义。 本文第一章对l d p c 码进行了概述，阐述了l d p c 码的历史及其基本原理。 第二章论述了b l d p c 码的编译码原理，包括校验矩阵h 的构造、古典译码算 法、以及利用消息传递的信度传播译码算法等。第三章在b u ) p c 码的基础上， 详细而全面地分析了q l d p c 码在突发噪声信道下性能良好的原因，并对 q l d p c 码的校验矩阵h 进行了优化设计，同时针对q l d p c 码的特性，引进 了傅立叶变换一信度传播译码算法以降低译码复杂度。第四章对r s 码的编译码 算法进行了简要介绍。第五章重点论证了一种新的优化方法- - e x i t 图 ( e x t r i n s i ci n f o r m a t i o nt r a n s f e r ) 在l d p c 码优化设计当中的应用。第六章为仿 真分析部分，不仅考察了q l d p c 码在a w g n 信道下不同帧长、不同码率的纠 错性能，而且对q l d p c 码与b l d p c 码、r s 码在高斯白噪声( a w g n ，a d & f i v e w h i t eg a u s s i a n n o i s e ) 信道、突发噪声信道、以及瑞利衰落信道下的性能进行了 全面的、公平的对比研究。文章末尾指出了q l d p c 码广泛的应用前景和下一步 工作方向。 关键词：多进制l d p c 码；香农限；信度传播译码 a b s t r a c t n o n b i n a r yl o wd e n s i t yp a r i t yc h e c k ( q l d p c ) c o d e sa r ei n v e s t i g a t e da n d c o m p a r e dw i t hb i n a r yl d p cr b l d p c ) c o d e sa n dr s ( r e e d - s o l o m o n ) c o d e si nt h i s t h e s i s s i m u l a t i o nr e s u l t si n d i c a t et h a tq - l d p cc o d e sa l ev e r ye f f e c t i v ea g a i n s tn o i s e b u r s t sa n df a d i n g ，e s p e c i a l l yw i t hh i g hr a t e s q - l d p cc o d e sp e r f o r m2 7 d bb e t t e r t h a nt h ec o n v e n t i o n a lr sc o d e sa taf t a m ee r r o rr a t e ( f e r ) o ff e r = i o 4o v e rn o i s e b u r s t sc h a n n e l sw i t hb u r s tl e n g t hu pt o1 4 4 b i t s ，a n de v e no u t p e r f o r mt h e s o f t - d e c o d i n gr sc o d e sb y7 1 d ba tf e r = i 旷o v e r f a s tr a y l e i g hf a d i n gc h a n n e l s i t i so f s i g n i f i c a n t v a l u ef o rq l d p cc o d e st ob e a p p l i e d i nf u t u r e d i g i t a l c o m m u n i c a t i o ns y s t e m s t h i st h e s i si so r g a n i z e da sf o l l o w s s e c t i o nig i v e sab r i e fi n t r o d u c t i o no f l d p cc o d e s s e c t i o ni ip r e s e n t st h ee n c o d i n ga n dd e c o d i n ga l g o r i t h mo fb l d p c c o d e s ，i n c l u d i n gt h ec o n s t r u c t i o no f p a r i t yc h e c km a t r i xh ，c l a s s i cd e c o d i n ga l g o r i t h m a n dm o d e mb e l i e fp r o p a g a t i o nd e c o d i n ga l g o r i t h m s e c t i o ni i ii n t r o d u c e san e w d e c o d i n ga l g o r i t h mw i t hr e d u c e d c o m p l e x i t ya n d a l lo p t i m i z e de n c o d i n gs c h e m ef o r q l d p cc o d e s ，a n dt h ep e r f o r m a n c e so fq l d p cc o d e so v e rn o i s eb u r s t sc h a n n e l s a r ea l s od i s c u s s e d t h ee n c o d i n ga n dd e c o d i n gs c h e m eo fr sc o d e si si n t r o d u c e di n s e c t i o n1 v s e c t i o nvd i s c u s s e st h ea p p l i c a t i o no fe x t r i n s i ci n f o r m a t i o nt r a n s f e r ( e x i t ) c h a r tf o rl d p cc o d e s s e c t i o nv ip r o v i d e st h es i m u l a t i o nr e s u l t so fq l d p c c o d e s ，b l d p cc o d e sa n dr sc o d e so v e ra d d i t i v ew h i t eg a u s s i a nn o i s e ( a w g n ) c h a n n e l s ，n o i s eb u r s t sc h a n n e l s ，a n df a s tr a y l e i g hf a d i n gc h a n n e l s c o n c l u s i o na n d f u t u r ew o r ka r es h o w e di ns e c t i o nv i i k e y w o r d s ：n o n b i n a r yl d p cc o d e s ；s h a n n o nl i m i t ； b e l i e f p r o p a g a t i o nd e c o d i n g 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成 果。本人在论文写作中参考的其他个人或集体的研究成果，均在 文中以明确方式标明。本人依法享有和承担由此论文产生的权利 和责任。 声明人( 签名) ：叶瓤馋纵 上占年，月矽日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦 门大学有权保留并向国家主管部门或其指定机构送交论文的纸 质版和电子版，有权将学位论文用于非赢利目的的少量复制并允 许论文进入学校图书馆被查阅，有权将学位论文的内容编入有关 数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密 的学位论文在解密后适用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( ) ( 请在以上相应括号内打“4 ”) 作者签名：玲斑他弓拼 导师签名：- ? i 彬 日期：阿2 ；年f 月甥日 日期：z ，祝年厂月1 日 第一章缭谂 1警l 言 第一章绪论 1 9 4 8 年，美国贝尔实验室的c l a u d ee ，s h a n n o n 在贝尔技术杂志上发表了题 为“am a t h e m a t i c a lt h e o r yo f c o m m u n i c a t i o n 的论文，这是篇关于现代信息和编 璃遴谂的奠基往论文，它的发表标恚羞臻健僚爨与编码理论学辩的创立。s h a n n o n 谯该论文中提出歹僖邋编码理论，即每个信邋嶷有确定的傣道容基c ，对任侮，j 、 于c 的码率r ，存在一种编码方法，若采用最大似然译码，则随着码长的增加其 译褐镂误概率p 可任意小。在a w g n 僖滋下，债道容量裘达式为： r p1 艮彤魄2 轴赢| ( b i t s ) q 1 d 荩中，矿是信道所能提供的带宽，冀一嚣。t 是信号功率，最是信号能量， f 楚分组码信号的持续时间即信号宽度，e w 是单位频带的信号功率，0 是单 缎频带瓣噪声功率，( w n o ) 是镶噪魄。 懿s h a n n o n 绘国的只是个存在栏定联，并没毒给蹬g 够遮刘香农限的码鼙 的舆体构造方法。此蔚，寻找靠近香农限的“好鹤”成为编码科研工作者们不懈遣 求的目标。 谯上拿墼纪5 0 年代爨6 0 每代，萃摹攀家裁拳鋈骚究嚣秘毒效瓣编、译妈方案， 这个瓣瀚羹定了线犍分缀鹨懿纂磴。蘩：1 9 5 0 年h a m m i n g 发明了h a m m i n g 码， h a m m i n g 码是种能纠正一个错误的完备线性分组码；此后又如现了b c h 码的 编译码方法，b c h 码魁循环码的一个予炎，懿肖较好的码特性；同时还出现了 卷积鹳及序列译码方法，其中卷积码不同于上丽提到的分组码，它是类非分组 鼹；瓣且关予绸锩秘豹墓搴鹳羧等在这一辩麓瞧褥到了深入瓣骥究。 遴入6 0 年代到7 0 年代，入髓越来麓熬横编鹤在实际系统中的应趱磺究。这 个时期不仅出现了许多有效的编码方案，而且还出现了门限译码、迭代译码、较 判决译码、卷积码的绒特比译码等。特别是黜e d 和s o l o m o n 于1 9 6 0 年应用m s 多瑗式稳逶窭采豹一类多避割b c h 秘，潮r s ( r e e d - s o l o m o n ) 弱，具有缀强麓鲻 镶髓力，莲慕仍j 泛& 箱子各类数字透信系缀孛；与鼗露辩，g a l l a g e f l 子1 9 6 2 多进制l d p c 码与r s 码的性能比较研究 年提出了低密度奇偶校验码( l d p c ，l o wd e n s i t yp a r i t y - c h e c kc o d e s ) ，首次提出 了迭代译码的方法。但是由于当时计算机仿真水平的限制，这种码字的性能没有 得到完全的体现。当时g a l l a g e r 主要从理论的角度分析了l d p c 码的性能，如码 字的重量分布、译码错误概率和不可检测概率的计算，以及信道的模型化等。 进入9 0 年代，应用迭代译码的t u r b o 硎2 】表现出优异的纠错性能，同时也 使得科研工作者们将目光重新聚焦在l d p c 码上，掀起了研究l d p c 码新的一轮 热潮。1 9 9 6 年d m a c k a y 从现代编码理论观点出发，证明利用迭代译码的l d p c 码具有逼近香农限的性斛3 ；1 9 9 8 年由d m a c k a y 和s p i e l m a n 提出了l d p c 码 的不规则编码方式【4 】，这是l d p c 码发展过程中跨出的非常重要一步；2 0 0 1 年美 国麻省理工的研究成果则进一步表明，不规则l d p c 码的理论门限值在a w g n 信道下距离香农限只有o 0 0 4 5 d b ，而仿真结果也只距离香农限o 0 4 d b ”。针对 b l d p c 码如此优异的纠错性能，m d a v e y 和d m a c k a y 进一步将b l d p c 码一 般化到多进制域上，并且研究结果表明q l d p c 码在低码率( r 5 _ 1 2 ) ，a w g n 信道下比b l d p c 码的纠错性能还要优越【6 】【7 1 ，q l d p c 码的出现为l d p c 码的 研究开拓了一个全新的领域。在理论研究方面，则先后出现了密度进化算法 ( d e n s i t ye v o l u t i o n ) 和e x i t 图( e x t r i n s i ci n f o r m a t i o nt r a n s f e r ) 优化设计方法。 密度进化算法通过分析l d p c 码的渐进性能，计算其精确的门限值，从而寻找优 秀的度的分布对【8 ：与密度进化算法相比较，e x i t 图优化设计方法也是从分析 码的渐进性能入手，但运算更为简便与直观 9 1 ，并且运用的领域也更为广泛。为 l d p c 码的优化设计与分析提供了新的方法和理论依据。 1 2l d p c 码概述 不同于其他的线性分组码，l d p c 码并不是由其生成矩阵来表示，而是由其 校验矩阵来表示的。作为一种典型的奇偶校验码，它的校验矩阵h 具有非常稀 疏的形式：矩阵中绝大多数的元素均为0 ，只有很少数的元素为l 。这是l d p c 码低密度性的直接表现。对于规则的l d p c 码，其校验矩阵h 中每一列1 的个 数都相等，同时，每一行1 的个数也相等。因此可以用( n j k ) 来描述规则的 l d p c 码，其中n 表示分组长度，j 表示校验矩阵h 中每- y u1 的个数，k 表示 校验矩阵h 中每一行1 的个数。 第一章绪论 根据线性分组码的性质，如果已知校验矩阵h ，可推知其生成矩阵g ，从而 得到对应的码字。由此可以看出，l d p c 码的生成矩阵g 并没有简洁、规律的表 达形式。u ) p c 码校验矩阵h 的物理意义如下：h 的每一行表示一个校验方程； h 的每一列则表示一个变量点受到哪些校验方程的约束。式( 1 2 1 ) 为( 1 2 ，3 a ) l d p c 码的校验矩阵，其中第一行可以表示为：为o k o 而x g = 0 ，o 表示模 2 加，其物理意义为：第一个校验方程约束着为、这4 个变量点：第 一列的物理意义则为：变量点五受到第2 、第5 、第7 这三个校验方程的约束。 h 0 0 l 0 0 l1l00 00 ll0 0 10 0000 0 1 o o o l0 0 0 0 11lo 0 1000 1l00 l0 0 l0 l000 0 1 0 0 l0 00 0 1l0 0 0 100 l 100 110 1000 0 0 00 00 0 10 10 0 ll o ll0 00 0 0 l10 0 ( 1 2 1 ) 为了更加清晰地反映l d p c 码中变量点与校验方程之间的关系，九十年代中 期，科学家开始用因子图来表示l d p c 码。在因子图中有两类节点，其中一类是 变量节点，另一类为函数节点。变量节点所代表的变量是函数节点的自变量。并 且同一类节点问无边的直接连接。 根据代数学中的分布法则，任意一个函数都可以进行因式分解。现假定函数 g ( _ ，屯，屯，- ，屯) 可以分解成几个“局部函数”之积的形式，如式( 1 2 2 ) 所示： 烈薯，屹，鼍，) ：= 正( 珑也墉瓴，恐，毛m ，如，珑如，恐) ( 1 2 2 ) 如果在因子图中用圆圈表示变量节点，用方框表示函数节点，则式( 1 2 2 ) 的因子图如图1 1 所示。局部函数节点与它相关联的变量节点用边进行连接。 b c d b 图1 1 函数g “，t ，_ ，- ，) 的因子图表示 多进制l d p c 码与r s 码的性能比较研究 相对应的，可以将l d p c 码中的变量点对应于图1 1 中的自变量节点，将 l d p c 码中的校验方程对应于图1 1 中的函数节点。那么对于规则l d p c 码( n j ，k ) 而言，每个变量点都受到j 个校验方程的约束，因此每个变量点都应该连接j 个 校验方程；每个校验方程有k 个变量点参与，因此每个校验方程都应该与k 个变 量点相连接。式( 1 2 1 ) 所示的规则l d p c 码( 1 2 ，3 ，4 ) 的因子图表示如图1 2 所示。从图1 2 中可以看到，由于l d p c 码是一种线性码，使得它的因子图一边 为变量点，一边为校验点。其中，我们定义每个点发出的边的个数为这个点的度。 另外，u ) p c 码的因子图表示在部分文献中也称为二部图。 图1 2( 1 2 , 3 ，4 ) l d p c 码的因子图表示 从l d p c 码的因子图表示中可以看到，所有变量点发出的边的数目必然等于 所有校验方程所接收的边的总数。那么对于l d p c 码( n j ，k ) ，若假设m 为校验方 程的个数，即校验矩阵h 的行数，则以下等式必然成立： r x ，= m x k ( 1 2 3 ) 对于不规则l d p c 码，顾名思义，就是每个变量点受到约束的校验方程数目 不同，每个校验方程所约束的变量点的个数也不相同。反映在因子图中就是每个 点( 变量点和校验方程点) 所连接的边的数量并不是完全相同的。 那为什么这样一种不规则的l d p c 码在码长很大的时候，性能要比规则的 l d p c 码好呢? 这是由于“波浪效应”( w a v e e f f e c t ) 【1 0 1 所致。一部分变量点受到 约束的校验方程数目比较多，即受到的约束度比较高，那么其f 确译码的速度也 相对比较快；与此同时，这些约束度比较高的点也为其他约束度比较低的点提供 了更为准确的译码外信息，最终使得所有变量点正确译码的速度得以加快。这个 原理和我国的一项基本经济政策具有异曲同工之处：先让一部分人通过诚实劳动 富裕起来，从而带动其余人后富起来，最终实现共同富裕。 对于不规则l d p c 码的情况，因为校验矩阵h 中每行和每列1 的个数都不 4 第一章绪论 相同，所以不能再用( n j ，k ) 的方式进行表示。为了准确地表达一个非规则的l d p c 码，我们引入如下表达式： 2 ( x ) = 彬，p ( x ) = 一x 1 ( 1 2 4 ) 其中a 卜) 表示变量点的度的分布，p ( z ) 表示校验方程点的度的分布；丑( n ) 表 示从度为i + 1 ( ，+ 1 ) 的变量点( 校验方程点) 所发出的边数占总边数的比例。很 显然a ( 1 ) = 1 ，p ( t ) = 1 。 对于规则的l d p c 码，也可以用这样的方式进行表示。例如，对于规则的 l d p c 码 3 ，6 ) ，则五( x ) = x 2 ，p ( x ) = x 5 。已知一个度的分布对( 五，p ) 后， 可以确定一系列码字集合c ”( 五，p ) ，其中校验方程个数川以及码率r 如下式所 示： m ：”擎鲨( 1 ：5 ) f z ( x ) 出 。 呻纠= 等斗雠n z 卸 第二章二进制l d p c 码 第二章二进制l d p c 码 l d p c 码于1 9 6 2 年就由g a l l a g e r 所提出，但一直到上世纪9 0 年代，随着采 用迭代译码的t u r b o 码所表现出来的优异纠错性能，l d p c 码才重新被世人所关 注，随后各项研究成果也表明，l d p c 码的性能比t u r b o 码更为靠近香农限。在 本章中，将主要介绍二进制l d p c 码的编译码原理，重点说明构造l d p c 码校验 矩阵h 的基本原则以及l d p c 码的现代译码算法，信度传播( b p ， b e l i e f - p r o p a g a t i o n ) 译码算法。 2 1 二进制l d p c 码的编码原理 由于l d p c 码是以校验矩阵h 为特征的，不同的校验矩阵h 对应了不同的 码字集合。因此，l d p c 码的编码首先需要设计校验矩阵h ，同时这也是l d p c 码编码的关键。 对于规则的l d p c 码( n j 固，在码长n 一定的情况下，主要的参数选择为j 与k 。目前的研究结果表明，性能最好的规则l d p c 码是( n ，3 ，6 ) 码。根据式( 1 2 3 ) 得知，参数n , j , k 确定后，则可以得到校验方程的数目m ，那么校验矩阵h 的大 小就可确认为所h 。l d p c 码校验矩阵h 的一般构造步骤如下：首先生成一个 川竹的全0 矩阵，然后随机地将每列当中的j 个0 换成1 ，每行当中的k 个0 换 成1 。但在随机置l 的过程中，必须避免以下两种情况的出现【l l 】： ( 1 ) 出现长度为4 的环 如图2 1 所示，当校验矩阵h 当中出现长度为4 的环时，对应的因子图如图 2 2 所示。这种长度为4 的短环结构会导致消息在两组节点之间的反复传递，而 难以得到更新，与迭代译码思想的初衷所违背，是必须清除的一种结构。理论分 析表明，最小环的长度为6 的情况下，码字的最小距离为4 。而随机构造的l d p c 码的最小距离是随着分组长度，即码长的增加而线性增加的。 ( 2 ) 变量点所连接的校验方程过于集中 当变量点所连接的校验方程过于集中时，常常导致l d p c 码错误地板的发 生。例如在图2 3 中，变量点的度为3 ，但其中三个带阴影的变量点总共只连接 多进制l d 耕e 码与r 8 码豹牲能撼鞍研究 o 霆2 。l 出现长渡为4 鹣繇麴校验矩黪珏 妇谶 餮2 2 螽有长度淹4 靛环的凌子强 了5 个校验方程；除了最右边静个校骏方程骏井，其它4 个校验方程中，每个 都连接了两个阴影的变量点。因此，如粜这三个阴影的变量点都出错时，左边4 个校验方程都不能检测到错误的存在。当分组长度增大时，出现这种拓扑结构的 掰缝牲也箍之减少。 c h e c k s b i t s 纛一 圈2 3 交量点胬连接校骏方程i 窭子集孛瀚因子圈 对予不瓶剐的l d p c 码h 矩阵酶褥造也同样需要遵循殴上静两个舔剃，餐 因为校骏矩阵h 中不再楚每列和每行l 的个数都相同，构造的过程要稍微复杂 嫂。在最早提出的不规则l d p c 码中，变量点和校验方程点的度都是不均匀的， 鞠校验艇瘁珏中每到，每行l 魏个数都不相同；毽实繇获真结荣表臻，这静双 边不均匀的情况并非最佳方案。实际的应用方案是，让变量点的度( 即校验矩阵 秘中每列 懿个数) 交纯琵较大，蠢臻持校验方程点懿菠( 帮校验矩箨瓣中每 第二章_ 二进制l d p c 码 行1 的个数) 比较平均。其中约束度比较大的变量点称为优先点。在迭代译码过 程中，优先点酋先被正确译码的概率是最大的。如何分配这些优先点，让哪些校 验方程点连接更多的优先点，是不规则l d p c 码的一个研究方向。目前常用的分 配方式主要有三种：泊松方式( p o i s s o n ) ，完全随机控制1 的位置；次泊松方式 ( s u b p o i s s o n ) 每行中较重的列的分布比泊松分布变化更小；超泊松方式 ( s u p c r - p o i s s o n ) ，每行中较重的列的分布比泊松分布变化更大。 以上部分说明了构造校验矩阵h 的基本流程和原理，在获得校验矩阵h 后， 就可以根据校验矩阵h 来进行编码，从而得到相应的码字。 ( 1 ) 常规编码 根据校验矩阵h 得到相应的生成矩阵g ，假设信息源为s ，则编码生成码字 为u = s g 。这种编码方式是以牺牲运算复杂度为代价的。当分组长度为n 时， 其编码复杂度为o ( n 21 ，若应用在移动通信当中，这种传播时延对于语音通信而 言是无法忍受的。同时计算复杂度也会使得存储器的数量过多，从而提高通信设 备的成本。为了简化运算复杂度，科研工作者们提出了很多简便算法。但是这些 算法均要求校验矩阵h 具有一定的特殊形式，因此在实际应用当中，应根据实 际应用条件来进行选择。 ( 2 ) 具有系统形式的h 矩阵的快速编码 由编码理论可知，具有系统形式的校验矩阵h 对应的生成矩阵g 也具有系 统形式，得到的码字u 也是具有系统形式的码字。现假设编码前的信息源为s ， 编码后的校验位为c ，编码后信息位s 位于码字u 的后部，即u = 【c i s 】；假设 校验矩阵h 的大小为m n ，并具有系统形式h = a i b 】，其中a 是一个m x m 的 单位矩阵，b 是一个m x 0 一所) 的矩阵。运用编码理论及矩阵运算可得下式： u 日7 = 0 j c a 7 + s b 7 = 0( 2 1 1 ) 由此等式可得到：c = s b 7 ( 爿7 ) 一，因为a 为单位矩阵，故又可简化为： c = s b 7 。 这种编码方式要求校验矩阵h 具有系统形式，简化了运算复杂度，但却是 以牺牲l d p c 码的稀疏特性为代价的。因为系统形式的校验矩阵h 要求具有一 个聊m 的单位矩阵，这必然使得校验矩阵h 的其余部分必须承担余下的所有1 元素，从而使得这部分显得相对比较密集，并不能很好地达到l d p c 码原本所要 多进制l d p c 码与r s 码的性能比较研究 求的稀疏特性。 2 2 二进制l d p c 码的古典译码算法 最大似然概率译码无疑是二进制信道的最佳译码方案。译码错误率也是使用 最大似然概率译码来分析的。但是在实际的应用当中，尤其是码长比较大的情况 下，采用最大似然概率译码所需要的硬件复杂度，存储器个数和时延等是难以承 受的。因此如何在运算复杂度与译码性能之间取得平衡是评价一个译码算法优劣 的标准。 作为l d p c 码的首创者，g a l l a g e r 于1 9 6 2 年提出了两种古典的译码算法， 前者基于硬判决，后者基于软判决。 ( 1 ) 硬判决古典译码算法 译码器的输入为硬判决所获得的初始值1 或0 ，译码器计算所有的校验矩阵， 如果某个变量点参与的校验方程出现了错误，并且错误的数目超过一个预定值， 就改变这个变量点的值。计算完整个分组的所有变量点后，再利用改变后的值进 行下一轮的计算，直到所有的校验方程都满足为止。 在校验方程的监督点比较少的情况下，这个方案还是比较可行的。因为大多 数校验方程都只会含有一个或者没有传输错误，所以当一个变量点参与的大多数 校验方程都出错时，这个变量点错误的可能性就非常大了。 ( 2 ) 软判决古典译码算法 在硬判决译码当中，变量点在进入译码器之前先进行了一次判决，译码器输 入的是某个变量点为l 或者为0 的值；而软判决译码则不同，变量点在进入译码 器之前并不进行判决，译码器输入的是某个变量点为0 或者为1 的概率。假设某 个变量点在经过信道以后存在两种情况，一种为1 0 的可能判决为0 ，9 0 的可 能判决为1 ；另一种为5 0 的可能判决为0 ，5 0 的可能判决为1 。硬判决译码 对这两种情况的区别是视而不见的，它只根据预先设定的判决门限进行判决；而 软判决译码则很好地保留了这两种情况的区别，为译码器的成功译码提供了更多 的外信息。 阐述此古典软判决译码时，首先引入一个g a l l a g e r 定理。 定理1 ：只代表经过信道传输后，第d 个变量点为1 的初始概率( 跟信道自 第二章二进制l d p c 码 身的特性有关) 。对于规则的l d p c 码( n j ，k ) ，b 代表第i 个校验方程中第z 个燹 量点为l 的概率，那么 篝糕= 警斜糍 ( 2 2 - ， 为了证明这个定理，需要用到如下的引理： 引理1 ：一个独立的川个比特的序列，第z 个比特为1 的概率为曰，则整个 序列中出现偶数个l 的概率为：旦i 二堕，出现奇数个1 的概率为： l 一兀：。1 2 日 了一。 此引理在此直接引用，不予证明。现对定理1 证明如下： p r x 。= ll y ，跚= p r x 。= 1 】_ = 1 时满足j 个校验方程的概率 ：b i j i 硝：1 时满足第i 个校验方程的概率 ：只血i = l 第i 个校验方程的其它k l 变量还有奇数个1 的概率 嘶c 1 1 皿学卜 同理可得：p r c 劫：。i t y ，s ，= c 一弓，垂11 学l c z z 。， 将式( 2 2 2 ) 与( 2 2 3 ) 相除，则得到了式( 2 2 1 ) ，定理1 得证。 通过定理l 的运算可以得到每个变量点为0 和为1 的概率比值，如果这个比 值大于1 ，则这个变量点在本次迭代中判为0 ；如果这个值小于1 ，则判为1 。经 过一次迭代以后，每个变量点的概率比值都会得到更新，并得到一组新的结果 f x 。用此新的结果与校验矩阵h 进行相乘，如果为0 ，则代表着译码成功，否 则转入下一次迭代。同时系统也设定一最大迭代次数，如果超过这个次数仍无法 译码成功，则放弃继续译码，输出最后一次迭代译码结果。 g a l l a g e r 为了表示这样一种迭代译码的思想，采用了图2 4 所示的树形图来 表示。图中d 点表示译码的起始点，为了计算d 点的条件概率，需要计算j 个校 多进制l d p c 码与r s 码的性能比较研究 验方程。图中的实线表示的正是校验方程。第一层的每条横线有k 一1 个点，代 表这个校验方程的其他k 一1 个变量点。 是一lo t h 盯 d 啦怡妇矗y 啦， p 越矗p 吧h o 噍嘲 d 图2 4 迭代译码的树形图表示 2 3 二进制l d p c 码的现代译码算法 o n d 进入9 0 年代，通过引入因子图来表示l d p c 码的结构，并引用人工智能中 的b p 算法，发展成为了l d p c 码的现代译码算法，信度传播( b p ，b e l i e f p r o p a g a t i o n ) 算法。 如图2 5 所示，因子图与信度传播算法是紧密结合的。在因子图中，仍用圆 圈表示变量点，用方框表示校验方程点；边上所传递的信息定义为m e s s a g e ，分 为从校验方程点到变量点，与从变量点到校验方程点两种。因此l d p c 码的现代 译码在部分文献中也称作m e s s a g e p a s s i n g 方法。 图2 5 因子图与信度传播算法 其中从校验方程点到变量点传递的信息为。( ) ，其物理意义为：第n 个变量点为0 ( 或1 ) 时满足第m 个校验方程的概率；从变量点到校验方程点传 递的信息为q ：。( q l m ) ，其物理意义为：通过除了第m 个校验方程以外的其它 第二章二进制l d p c 码 i 1 个校验方程所得到的第n 个变量点为0 ( 或1 ) 的概率。 信度传播算法延续了古典算法中的迭代思想，它的主要改进为：在计算变量 点满足校验方程的概率时，不再采用奇数个或者偶数个1 的方式，而是采用了全 概率的公式。因为当分组很大，通常有达到1 0 7 时，不可排除的总会有某个变量 点出错，如果它受约束的所有校验方程都产生了偶数个错误，就会使得译码无效。 采用全概率公式后就不会出现这样的问题。 下面详细介绍信度传播译码算法中的各个步骤： ( 1 ) 计算初始概率 信度传播译码算法为软判决译码，所以在进入译码器之前，需要根据信道状 态信息( c s i ，c h a n n e ls t a t ei n f o r m a t i o n ) 对变量点的初始概率进行估计，同时 也对q ：。( q ：。) 进行初始化。下面以a w g n 信道为例进行说明。 假设经过a w g n 信道后的接收信号如式( 2 3 1 ) 所示： 只= 薯+ q ( 2 3 1 ) 其中y 为经过信道传输后接收到的信号：x i 为发射端的信号，对于二进制信 源，采用b p s k 调制而言，假设p ( t = + 1 ) p r ( x ,1 ) = 1 2 ：n i 为加性高斯白 噪声，其均值为0 ，方差为占2 。由此，可以得到变量点的初始概率为： p ( t 爿l y a 2 方，( x e 1 ) ) 3 2 对式( 2 3 2 ) 的证明如下： 刮炉盟皆 ! p 山叫2 2 ：i ! 一 三e 一( m l p m 2 + l e - y , + l 】2 m 2 22 e q f 5 ； e h ，5 2 + e - y , ，s 2 1 砂( ，d 2 + e h ( 1 + j ) d 2 1 1 + p 2 h f 3 2 对于采用b p s k 调制的情况( 0 调制到+ l ，1 调制到一1 ) ，便可得到变量点 多进制l d p c 码与r s 码的性能比较研究 的初始概率砖= e ( = + 1 1 只) ；一= 只( = 一1 i 儿) 。并将此初始值赋给q ：。 ( q l m ) ，作为q o 。( q ：。) 的初始值。 需要注意，此初始概率对于l d p c 码的正确译码起到重要的作用；或从另一 个角度进行考察，可以认为l d p c 码是一类需要知道信道状态信息的码字。 ( 2 ) 计算从校验方程点到变量点的信息：。( ) 假设第m 个校验方程为：x 2x 3x 5 = 0 。现以计算r l ( x 2 = o 时满足第m 个校验方程的概率) 为例进行说明： 2 = p r x 2x 3 0 鼍= o l x 2 = o ，x 3 = o ，墨= 0 q 0 3 - q 0 5 + p r x 2 x 3 0 = 0 i x 2 = o ，x 3 = o ，x s = 1 q ：3 g ：5 + p r x 2 0 墨。毛= 0 l x 2 = o ，x 3 = 1 ，x 5 = 0 g ：3 q 0 5 + p r 恐。黾o = 0 i x 2 = o ，x 3 = 1 ，x 5 = l 以3 以5 这是一个典型的全概率计算方法。其中的条件概率函数p r ，如果满足校 验方程则为1 ，不满足则为o 。利用同样的方法，也可以得到t ：。对于计算e 。o ( t 。) 更为一般化的表达式如( 2 3 3 ) 、( 2 3 4 ) 所示。 0 = p r 满足校验m i x n = o ，x ，： 7e ( ) ”) n9 2 ， ( 2 3 3 ) h 一e ( ) 叫 “叫l “灿 t 。= p r 满足校验聊i _ = 1 ， ，：”7e | ( m ) n ) 兀g ( 2 3 4 ) h ：s 州m ) 、一j “5 ”【”灿 其中 n ( m ) 表示参加第m 个校验方程的所有变量点；疗7 ( m ) ”表示 除了第r 1 个变量点以外，参加第m 个校验方程的所有变量点。在这两式中条件 概率函数p r 1 的取值方式与冲激函数8 ( x ) 的取值相似，只有在校验方程满足时 取值为1 ，其余情况取值为0 。 ( 3 ) 计算从变量点到校验方程点的信息：q o 。( q ：。) 这一步的计算和古典方式是相同的，都是计算某个变量点为0 或为1 时满足 除了第m 个校验方程以外所有校验方程的概率，如式( 2 3 5 ) 、( 2 3 6 ) 所示。 g ：= 。睇兀r “o ：卅7 m ( h ) 珊 ( 2 3 5 ) q 二= 口。成兀t k ：m 7 m ( n ) 聊 ( 2 3 6 ) 其中口。为归一化参数，保址, g 。o1 - g 。i = 1 ；m 肘( 珂) 表示第n 个变量点所连 第二章二进制l d p c 码 接的所有校验方程；m 7 m ( n 1 m 表示除了第1 t 1 个校验方程以外，第n 个变量 点所连接的所有校验方程。注意到式( 2 3 5 ) 和( 2 3 6 ) 中均使用到了初始概率 p o ( 一) 。 ( 4 ) 计算后验概率，并进行判决 变量点后验概率的计算如式( 2 3 7 ) 、( 2 3 8 ) 所示： q o = 。群兀匕：卅吖( ”) ( 2 3 7 ) 巩= 。一兀：埘m ( 珂) ( 2 3 8 ) 其中口。仍为归一化参数，保证g ：+ 以= l 。得到后验概率后即可对码字进行 判决，如果吼o q ：，则判定吒= o ；如果q o 矗，则判定吒= 1 。至此，完成了 一次迭代过程，同时也得到了一个新的码字序列x ，如果h 7 = 0 ，则代表着 译码成功，停止迭代，并输出码字x ；否则跳转到步骤( 2 ) ，开始下一轮的迭 代过程。在实际操作过程中应设置一个最大的迭代次数，如果达到最大迭代次数 仍未能成功译码，则放弃译码，输出最后一次迭代译码的结果。 第三章多进制l d p c 码 第三章多进制l d p c 码 上一章介绍了b l d p c 的编译码原理，而且目前国内外的科研成果均表明 b l d p c 码具有很好的纠错性锹1 2 】 1 3 】。而b l d p c 码又可以一般化为q l d p c ， 并且目前国际上的研究结果表明【1 4 l 【5 】 1 6 1 ，具有特定列重的q l d p c 码在低码率的 情况下( r 1 2 ) ，在a w g n 信道下的性能甚至要优于b l d p c 码。在本章当中， 将详细介绍q l d p c 码的编译码算法，特别是针对q l d p c 码的特性所引进的 傅立叶变换一信度传播译码算法以及q l d p c 码的纠错性能分析。 3 1有限域 为了理解q l d p c 码的编译码原理，有必要深入到称为加罗瓦域( g a l o i s f i e l d ，g f ) 的有限域中。对于任何质数p ，存在一个有限域，表示为o f ( p ) ，其 中包含有p 个元素。可以将g f ( p ) 延伸为一个含有p “个元素的域，这称为g f ( p ) 的扩展域，表示为g f ( p ) ，r n 是一个非零整数。注意，g f ( p ) 是g f ( p m ) 的子集。扩展域o f ( 2 ”) 中的码元用于构造q l d p c 码。 二进制域g f ( 2 ) 是扩展域o f ( 2 “) 的一个子域，类似于实数域是复数域的一个 子域一样。除了数字0 和l ，在扩展域中还有特殊的元素，用一个新的符号7 表 示。g f ( 2 “冲任何非0 元素都可由7 的幂次表示。元素的无限集f ，就是根据元 素集 o ，1 ，7 而形成的，后一个元素通过前一项乘以口而得： f = o ，1 ，口，7 2 c , 7 ， = o ，口。，口，口2 ，一，口， ( 3 1 1 ) 为了从f 中得到有限元素的集合g f ( 2 “) ，必须对f 域施加一个条件，使它 只能含有2 “个元素并且对乘法封闭。域元素集对乘法封闭的条件可由下面的不 可约多项式表示： 7 ( 2 。1 1 + 1 = 0或等同于 口( 2 。1 ) ：1 ：7 0 ( 3 1 2 ) 根据这个多项式限制条件，任何幂次等于或超过2 “一1 的域元素都可降阶为 如下所示的幂次小于2 ”一l 的元素： 口( 2 4 + ”) ：7 ( 2 ”一1 ) 7 ”“：口“( 3 1 3 ) 因此，式( 3 1 2 ) 可用于从无限序列f 中形成有限序列，+ ，如下所示 多进制l d p c 码与r s 的性能比较研究 f = o ，l ，口，口2 ，口( 2 m - 2 ) 口口“。1 ，口7 ， = o ，l ，口1 ，口2 ，口( 2 m - 2 ) 窿。，口1 ，口2 ，1 ( 3 1 4 ) 所以，由式( 3 1 4 ) 可以看出有限域g f ( 2 ) 的元素由下式给出： o f ( 2 ”) = o ，口。，口1 ，口2 ，口r 。2 1 ) ( 3 1 5 ) 在有限域g f ( 2 “) 中，2 “个元素中的任意一个都可由阶数小于或等于m 1 的 不同多项式来表示。多项式的阶数是它的最高幂指数。将g f ( 2 “) 中每个非0 元 素用多项式q ( x ) 表示，其系数至少有一个不为0 。对于j - 0 ，1 ，2 ，2 “一2 ，有 口1 = q ( x ) = q 一- i a i ，l x + a j ，2 x 2 + + q ，。一i x “一1 ( 3 1 6 ) 考虑