（通信与信息系统专业论文）准循环低密度奇偶校验码的研究.pdf

原创性声明 filll1 11i i i iil ll ll ll iii y 17 9 2 2 9 8 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：錾盛盈日论文作者签名：肇盛盈日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名蜘师签名：皿日 期：蛐 山东大学硕士学位论文 目录 摘要1 a b s t r a c t 2 符号说明3 第一章绪论4 1 1 差错控制编码4 1 1 1 线性分组码4 1 1 2 信道模型5 1 1 3 硬判决译码和软判决译码5 1 1 4 最大后验概率译码和最大似然译码6 1 2l d p c 码的发展6 1 3 本文的主要内容7 第二章l d p c 码的基本原理8 2 1 有限域的基本概念8 2 1 1 群8 2 1 2 有限域8 2 1 3 有限域扩展9 2 1 4 g f ( 2 m ) 域的构造10 2 1 5 g f ( 2 m ) 域的表示10 2 2 l d p c 码的基本概念一1l 2 3 l d p c 码的译码算法一13 2 3 1l d p c 码的译码算法13 2 3 2 多进制l d p c 码的译码原理1 6 第三章q c l d p c 码的构造18 3 1q c - l d p c 码的特点18 3 2p e g 算法构造q c l d p c 码19 3 2 1 p e g 算法19 i 山东大学硕士学位论文 曼! ! ! 曼曼曼曼詈i m i i 曼詈曼詈曼曼! ! 曼! 詈! ! ! 曼詈! 曼! ! 曼! 皇! ! ! 暑! ! ! 皇墨! 曼鼍皇葛曼曼皇! ! 皇皇詈! ! ! 詈曼皇皇寰 3 2 2 p e g 算法构造q c l d p c 码2 1 3 2 3 仿真性能分析2 4 3 3 多迸制q c l d p c 码的构造2 6 3 3 1基于循环群的构造方法2 6 3 3 2 基于p e g 算法的构造方法2 8 3 3 3 仿真性能分析2 9 第四章q c l d p c 码的译码器设计3 3 4 1 全并行译码结构。3 3 4 2 部分并行译码结构。3 4 4 2 1 部分并行译码结构框图3 4 4 2 2 存储器的访问3 6 4 3 重叠译码结构3 8 第五章l d p c 码的应用研究4 3 5 1l d p c 码在网络编码中的异或译码4 3 5 1 1 蝶形多播网络一4 3 5 1 2 概率域的异或运算。4 4 5 1 3 译码方案4 5 5 1 4 仿真性能分析4 6 5 2l d p c 码在m i m o o f d m 系统中的性能4 8 5 2 1m i m o o f d m 系统4 8 5 2 2 仿真性能分析5 0 总结与展望一5 1 参考文献5 3 致谢5 7 攻读学位期间发表的学术论文5 8 i l 山东大学硕士学位论文 c o n t e n t s c h i n e s ea b s t r a c t 1 e n g l i s ha b s t r a c t 2 s y m b o l s 3 c h a p t e r1i n t r o d u c t i o n 4 1 1e r r o rc o n t r o lc o d i n g 4 1 1 il i n e a rb l o c kc o d e s 4 1 1 2c h a n n e lm o d e l s 5 1 1 3h a r dd e t e c t i o na n ds o f td e t e c t i o n 5 1 1 4m a p d e c o d i n ga n dm ld e c o d i n g 6 1 2h i s t o r yo fl d p cc o d e s 6 1 3c o n t e n t so f t h i st h e s i s 7 c h a p t e r2f u n d a m e n t a l so fl d p cc o d e s 8 2 1 p r i n c i p l eo f f i n i t ef i e l d 。8 2 1 1g r o u p 8 2 1 2f i n i t ef i e l d 8 2 1 3f i n i t ef i e l de x t e n s i o n 9 2 1 4g f ( 2 小1c o n s t r u c t i o n 10 2 1 5g f ( 2 用) d e s c r i p t i o n 1 0 2 2p r i n c i p l eo fl d p cc o d e s i1 2 3d e c o d i n ga l g o r i t h m so fl d p cc o d e s 13 2 3 1 d e c o d i n g a l g o r i t h m so f l d p cc o d e s 1 3 2 3 2 d e c o d i n ga l g o r i t h m so f n o n b i n a r yl d p c c o d e s 1 6 c h a p t e r3c o n s t r u c t i o no fq c l d p cc o d e s 18 3 1p r i n c i p l eo f q c l d p cc o d e s 1 8 3 2q c 。l d p cc o d e sc o n s t r u c t i o nb yp e ga l g o r i t h m 1 9 3 2 1p e g a l g o r i t h m 1 9 3 2 2q c l d p cc o d e sc o n s t r u c t i o nb yp e ga l g o r i t h m 2 1 3 2 3s i m u l a t i o na n da n a l y s i s 2 4 3 3n o n b i n a r yq c l d p cc o d e sc o n s t r u c t i o n 2 6 3 3 1c o n s t r u c t i o nb yc y c l i cg r o u p 2 6 3 3 2c o n s t r u c t i o nb yp e ga l g o r i t h m 2 8 1 1 i 山东大学硕士学位论文 ! i i ；i i 皇詈鼍詈毫詈皇曼鲁皇鼍詈詈曼! ! 皇曼皇曼! ! 曼! ! ! ! ! ! ! ! 曼兰! 曼曼曼皇! ! 詈皇暑! 曼鼍曼皇皇暑! 毫篁曼! 詈詈曼曼鼍曼詈曼皇皇詈曼! 曼! 量鼍毫 3 3 3s i m u l a t i o na n da n a l y s i s 2 9 c h a p t e r4d e s i g no fq c l d p cd e c o d e r 3 3 4 1f u l l yp a r a l l e ld e c o d i n gs c h e m e 3 3 4 2p a r t i a l l yp a r a l l e ld e c o d i n gs c h e m e 3 4 4 2 1d e c o d e rs c h e m e 3 4 4 2 2r e f e r e n c et os t o r a g e 3 6 4 3o v e r l a p p e dd e c o d i n gs c h e m e 3 8 c h a p t e r5a p p l i c a t i o n s o fl d p cc o d e s 4 3 5 1x o rd e c o d i n go fl d p cc o d e sf o rp h y s i c a ln e t w o r kc o d i n g 4 3 5 1 1b u t t e r f l ym u l t i c a s tn e t w o r k 4 3 5 1 2x o r o p e r a t i o no np r o b a b i l i t yd e n s i t y f u n c t i o n 4 4 5 1 3d e c o d i n gs c h e m e s 。4 5 5 1 4s i m u l a t i o na n da n a l y s i s 4 6 5 2p e r f o r m a n c eo f l d p cc o d e so v e rm i m o o f d ms y s t e m 4 8 5 2 1l d p cc o d e dm i m o o f d ms y s t e m 4 8 5 2 2s i m u l a t i o na n da n a l y s i s 5 0 c o n c l u s i o n sa n df u t u r ew o r k 5 l b i b l i o g r a p h y 5 3 a c k n o w l e d g e m e n t 5 7 p u b l i c a t i o n s 5 8 i v 山东大学硕士学位论文 摘要 低密度奇偶校验码是一类逼近香农限( 信道容量) 的线性分组码。随着对高 速并行编译码器设计的重视，相对于非结构化的随机l d p c 码，结构化的准循环 l d p c ( q c l d p c ) 码以其良好的性能和灵活的硬件可实现性，成为当前的一个研 究热点。本文在介绍l d p c 码和有限域的基本原理的基础上，重点研究了有限域 上的q c l d p c 码的构造及译码器的设计，主要工作包括： 1 、基于构造校验矩阵的p e g 算法，加入准循环的限制条件，构造参数灵活的 q c l d p c 码。a w g n 信道下的仿真结果表明，本文构造的q c l d p c 码与原始 p e g 算法构造的非结构化l d p c 码性能基本一致。 2 、针对多进制l d p c 码，基于p e g 算法，构造出结构化和非结构化的多进 制l d p c 码。在a w g n 信道下，分别采用b p s k 调制和高阶调制( 8 p s k ) 进行了 性能仿真。同时，与等价编码速率的二进制l d p c 码进行了性能比较，分析了多 进制l d p c 码的纠错性能和译码复杂度。 3 、研究了q c l d p c 码译码器的并行实现和部分并行实现，特别是部分并行 译码器的外部消息存储、路由算法和重叠译码方法，设计了一种可接近1 0 0 硬件 资源利用率的译码器结构。 4 、将l d p c 码应用于物理层网络编码中，在蝶形多播网络中，提出了l d p c 码异或译码的四种方法，对译码性能和实现复杂度进行了对比。 5 、研究l d p c 码编码的m i m o o f d m 系统，考查了l d p c 码在该系统下的 编码增益。 关键词：l d p c 码：准循环：多进制；有限域；p e g 算法；l d p c 译码器；重 叠译码；网络编码；异或运算；m i m o o f d m 系统； 山东大学硕士学位论文 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 sa r eac l a s so fl i n e a rb l o c kc o d e sw h i c ha p p r o a c h s h a n n o nl i m i t w i t ht h ed e v e l o p m e n to fl d p ce n c o d e r d e c o d e rd e s i g na n dr e s e a r c h ， q u a s i - c y c l i c ( q c ) l d p cc o d e sa r ew i d e l ys t u d i e df o rt h e i rc o m p a r a b l ep e r f o r m a n c e a n dh a r d w a r e f r i e n d l yc h a r a c t e r i s t i c t h i st h e s i sf i r s ti n t r o d u c e st h ep r i n c i p l e so ff i n i t e f i e l dl d p cc o d e s ，a n dt h e nf o c u s e so nt h ec o n s t r u c t i o no fq c l d p cc o d e sa n dt h e d e s i g no fl d p c d e c o d e r 1 1 1 em a i n w o r ki n c l u d e s ： 1 m o d i f i e dp r o g r e s s i v ee d g eg r o w t h ( p e g ) a l g o r i t h mi ss t u d i e dt oc o n s t r u c t q c - l d p cc o d e sw i t hf l e x i b l es t r u c t u r ep a r a m e t e r s t h es i m u l a t i o nr e s u l t ss h o wt h a t t h ep e r f o r m a n c eo fq c l d p cc o d e si sc o m p a r a b l ew i t ht h a to fn o n s t r u c t u r e dl d p c c o n s t r u c t e db yp e g a l g o r i t h mo v e ra w g n c h a n n e l 2 n o n b i n a r ys t r u c t u r e da n dn o n - s t r u c t u r e dl d p cc o e sa r ec o n s t r u c t e db yp e g a l g o r i t h m t h e i rp e r f o r m a n c ei sc o m p a r e dw i t ht h a to fb i n a r yl d p cc o d e sw i t hs a m e c o d i n gr a t e so v e ra w g nc h a n n e lb yb p s km o d u l a t i o na n d8 p s km o d u l a t i o n t h e p e r f o r m a n c ea n dd e c o d i n gc o m p l e x i t yo fn o n b i n a r yl d p cc o d e sa r ea n a l y z e d ， r e s p e c t i v e l y 3 t h ep a r a l l e la n d p a r t i a l l yp a r a l l e ld e c o d e rs c h e m e sa r ei n t r o d u c e d ，r e s p e c t i v e l y f o r p a r t i a l l yp a r a l l e ld e c o d e rs c h e m e s ，t h es t o r a g i n ga n dr o u t i n ga l g o r i t h mf o re x t r i n s i c m e s s a g e ，勰w e l la st h eo v e r l a p p e dd e c o d i n ga l g o r i t h ma r es t u d i e d o n eo v e r l a p p e d d e c o d i n gs c h e m e i sp r o p o s e d ，w h i c hp e r f o r m sa p p r o x i m a t e10 0 h a r d w a r eu t i l i z a t i o n 4 l d p cc o d i n gi si n t r o d u c e dt op h y s i c a ln e t w o r kc o d i n g f o u rd e c o d i n gw a y s a r ep r e s e n t e da n da n a l y z e df o rx o r d e c o d i n gi nt h eb u t t e r f l ym u l t i c a s tn e t w o r k 5 l d p cc o d e dm i m o - o f d ms y s t e mi ss t u d i e d n l ec o d i n gg a i no fl d p c c o d e so v e rm u l t i p a t hc h a n n e li sp r e s e n t e db ys i m u l a t i o n k e yw o r d s ：q c l d p cc o d e s ，f i n i t ef i e l d ，n o n b i n a r yl d p cc o d e s ，p e ga l g o r i t h m s ， l d p cd e c o d e r , p a r t i a l l yp a r a l l e l d e c o d i n g , o v e r l a p p e dd e c o d i n g , p h y s i c a ln e t w o r kc o d i n g ，x o r ，m i m o o f d m 2 山东大学硕士学位论文 以x ) p ( x ) g f ( q ) g f ( 2 研) h g a w g n b e c b p b s c c n u g d s c e e c m a p m i m o m l o f d m p e g q c - l d p c v n u g v - b l a s t z f 符号说明 生成多项式 本原多项式 包含g 个元素的有限域 二元域的扩展 分组码的校验矩阵 分组码的生成矩阵 加性高斯噪声 二进制可擦除信道 置信度传播 二进制对称信道 校验节点处理单元 分布式信源编码 差错控制编码 最大后验概率 多输入输出 最大似然 正交频分复用 渐进边增长 准循环低密度奇偶校验 变量节点处理单元 贝尔实验室垂直分层空时 迫零 3 山东大学硕士学位论文 1 1 差错控制编码 第一章绪论 差错控制编码( e r r o rc o n t r o lc o d i n g , e c c ) 是数据传输和存储领域罩的重要 技术，它通过增加冗余信息提高信息传输的可靠性。1 9 4 8 年，c l a u d ee s h a n n o n 弓 入 了信息熵的测度概念，提出了信道编码定理 1 】。该定理指出在任一噪声信道都存 在一个最大传输速率，当传输速率低于这个最大传输速率时，信息能够可靠传输。 这个最大传输速率称作信道容量，如何构造出达到信道容量的e c c ，随之成为香 农留给后来学者的重要工作。 图1 1 描述了一个典型的数字通信系统框图，信道编码器在发送端对信源增加 适当冗余，信道译码器在接收端依靠冗余信息来恢复被噪声干扰的信息。编码方 式、信道模型和译码方式是信道编码研究的三个基本问题。 1 1 1 线性分组码 图1 1 典型的数字通信系统框图 一个线性分组码( n ，k ) 表示将k 个码元分为一组通过编码器生成一个含有n 个码元的码字。假定码元在g f ( q ) 域上取值，则矿个n 维数组构成一个g f ( g ) 域上 的n 维线性3 芑f j ，若其中q k 个码字构成一个k 维线性子空间，则这个码字就是线 性性分组码。 4 山东大学硕士学位论文 1 1 2 信道模型 图1 1 的数字通信系统可简化成编码、信道和译码三部分。编码部分包括信源、 信道编码过程，信道部分包括调制、噪声信道和解调过程，译码部分包括信源、 信道解码过程。 信源s 可以是连续波形也可以是离散的符号序列，信源编码器将s 转换为二进 制信息序列u 。对连续信源，该过程还包括模数转换。信源编码器以两个条件为设 计目标【2 】：( i ) 为表示信源输出所要求的比特数最低；( i i ) 信源s 可以从信息序列 u 确切的重现。 信道编码器将信息序列u 转换成离散的编码序列c ，称之为码字。离散的符号 不适合在物理信道上传输。调制器将信道编码器输出的每个符号转换成持续时间 为t 秒的适合传输的波形。 这些波形进入信道并受到噪声的干扰。系统仿真时，一般采用二进制对称输 入的离散无记忆信道( d i s c r e t em e m o r i l e s sc h a n n e l ，d m c ) 考查信道编码增益。它 主要包括三类：二进制可擦除信道( b i n a r ye r a s u r ec h a n n e l ，b e c ) ，二进制对称信 道( b i n a r ys y m m e t r i cc h a n n e l ，b s c ) 和二进制输入的加性高斯信道( b i n a r yi n p u t a d d i t i v ew h i t eg a u s s i a nn o i s ec h a n n e l ，b i a w g n ) 。 接收端，解调器直接进行码元判决或输出表示码元可靠性的软消息，解码器 进行相应的硬判决译码或软判决译码。 1 1 3 硬判决译码和软判决译码 假设二进制码字c = ( c o ，q ，口，c 州) ，在发送端c 被映射调制，通过噪声信道，接 收端对受损调制符号解调得到码元序列y = ( ，m ，只一，) 。如果y 被直接量化为 0 1 两级序列，则称解调器硬判决，相应的译码方式称作硬判决译码；如果y 的每 个元素信息多级( 大于两级) 量化，或者未被量化，则称解调器软判决，相应的 译码方式称作软判决译码。很明显，硬判决丢掉了信道的一些有用信息，降低了 译码精确度。但是，由于译码器只需进行进行简单的0 1 运算，复杂度和时间延迟 较低，适合高速率传输译码。软判决译码精确度和复杂度都比硬判决高，随着集 成电路技术的发展，软判决译码开始受到越来越多的关注。 5 山东大学硕士学位论文 1 1 4 最大后验概率译码和最大似然译码 g f ( q ) 域线性分组码( n ，k ) ，信n u = ( ，u l ，u 川) ，码字c = ( c o ，c l ，q 一。) ，经 过信道后解调序列y = ( ，y ，只一。) 。译码器的目的是最大化后验概率 p ( u i = u ii y ) ，0 i k ，满足a m = a k ，即a m - k = l 。这个等式进一步 说明必定存在一个使得a n = l 的最小正整数n 。这个整数n 称为域元素a 的阶。 定义2 5 在有限域g f ( g ) 中，如果非零元素a 的阶为g l ，则a 称为本原元 ( p r i m i t i v ee l e m e n t ) 。 9 山东大学硕士学位论文 可简单证明，本原元的幂生成g f ( g ) 中的所有元素。任何一个有限域都有一个 本原元。 2 1 4g f ( 2 肼) 域的构造 数字通信和存储系统中，信息一般采用二进制码的形式表示，所以我们只关 心二进制码和g f ( 2 研) 中的符号生成的码。g f ( 2 m ) 的元素可以用g f ( 2 ) 上的m 1 次多 项式a x ) 表示，这个多项式以x 为变量，以g f ( 2 ) 中元素为系数，表示如下： f ( x ) = f o + f , x + l x 2 + + 正q x 剃 g f ( 2 ) 上的m 次多项式p ( x ) 若不能被g f ( 2 ) 上的任意次数小于m 大于0 的多项 式整除，则称p ( x ) 在g f ( 2 ) 上是不可约( i r r e d u c i b l e ) 的。 定义2 5m 次不可约多项式p ( x ) 若满足能被p ( x ) 整除的x n + 1 的最小正整数 n 为n = 2 m 1 ，则称p ( x ) 为本原多项式( p r i m i t i v ep o l y n o m i a l ) 。 判断一个本原多项式比较困难，文献提供了一些常用本原多项式。 g f ( 2 朋) 的构造流程如下： ( 1 ) 确定了一个m 次本原多项式烈x ) 。 ( 2 ) 令o f 满足烈口) = o ，由本原多项式的性质可推出，2 m 一1 是使o r 2 对- i - 1 的最小 正整数，根据本原元的定义，可以把o r 看作一个有限域g f ( 2 册) 的本原元。 ( 3 ) 以口为本原元构造有限域集合f + = o ，l ，口，口2 ，口2 。_ 2 ) ， 可以证 明f + 在乘法下和加法下均为交换群，从而得到一个g f ( 2 用) 。 由于烈x ) 不唯一，g f ( 2 小) 也不唯一。 2 1 5g f ( 2 肼) 域的表示 g f ( 2 埘) 中的元素主要用三种形式表示：本原元的幂形式，多项式形式以及m 维二元向量形式。本节以p ( x ) = l + x + x 4 生成的g f ( 2 4 ) 为例，表2 1 描述它的三种 表示形式： 1 0 山东大学硕士学位论文 表2 1g f ( 2 ”) 域的三种表示方式 幂表示多项式表示4 维向量表示 00 ( 0 0 0 0 ) l l ( 1 0 0 0 ) 口 口 ( 0 1 0 0 ) 口2口2 ( 0 0 1 0 ) o y 3口3 ( 0 0 0 1 ) 1 2 4 l + 口 ( 1 1 0 0 ) 口1 21 + 口+ 口2 + 口3 ( 11 11 ) 口1 31+ 口2 + 口3 ( 1 0 1 1 ) 口1 41+ 口3( 1 0 0 1 ) 一 2 2l d p c 码的基本概念 g f ( 2 ) 域上的l d p c 【3 】码c 是一种线性分组码( ，k ) ，码长为，信息序列 长度为k ，可以由其校验矩阵h 唯一定义。h 的维数是m n ，每一行对应一个 校验方程，每- n 对应码字的一位。每一行中非零元素的个数称为行重，每一列 中非零元素的个数称为列重。 l d p c 码的名称来源于其校验矩阵是一种稀疏矩阵，即矩阵中非0 元素的个数 远远小于0 元素的个数，或者矩阵的行重和列重与码长相比是很小的数值。 构造一个维数为m n 的矩阵h ，通过高斯消元法将其变成如下形式 h ：fp i 一髟) x 丘l ( n - x ) 。f 一k jl l o o j 如果h 是满秩的，变换后不存在全0 的行。由以上变换可以得到系统形式的生成 矩阵g = 【l 足。置攻。( 一k ) 】，信g 序：nu = 【”l ，“2 ，】通过c = u g 映射为码字c 。虽 然h 是稀疏的，但是矩阵p 通常不是稀疏的，编码过程中需要存储p 的元素，存 储量较大。同时，编码的运算量是码长的二次方的形式，在码长较大时，需要采 取措施降低复杂度。 山东大学硕士学位论文 除了用校验矩阵表示l d p c 以外，还可以用双向的图模型表示l d p c 码，其 中t a n n e r 图【4 】表示是比较方便的一种，可以形象地刻画l d p c 码的编译码特性。 t a n n e r 图是一种双向图，可以用 ( 矿，e ) ) 表示，其中矿是节点的集合，矿= 圪u 圪。 对维数为m xn 的校验矩阵，k = ( m ，屹，h ) 称为变量节点( 或位节点、左节点) ， 对应校验矩阵的列，同时对应码字中的位；圪= ( c i 乞，) 是校验节点( c h e c k n o d e ，函数节点、右节点) ，对应校验矩阵的行，也就是校验方程。e 是节点之间 相连的边的集合e c _ r v 圪，同类节点之间没有边相连，只有在两类节点之间有边 存在。e 还可以表示成毛u & u ue v 。的形式，其中气是变量节点_ 上所有 边的集合。如果校验矩阵的第i 行第歹列元素为是非零的，则t a n n e r 图的第，个位 节点与第f 个校验节点有一条边相连。即当h i ，= 1 时，节点g 与v ，之间有一条边相 连，边( q ，) e 。与节点的相连的边数目称为节点的度( d e g r e e ) 。参照图2 - l ， ( a ) 中校验方程组确定的一个( 6 ，2 ) 线性分组码，可以表示成( b ) 中的t a n n e r 图形式。 佣v lv ，_忧v 4伏 h = l o l 0 1 0 1 0 0 1 0 1 0 ll0 0l 0 lol l0 斗 场手哆手巧= 0 略+ 吩手吩= 0 m + + v j = 0 巧手吩十均= d c 0c igc3 ( a ) 校验方程和方程组( b ) t a n n e r 图表示 图2 1 ( 6 ，2 ) 线性分组码t a n n e r 图 如果校验矩阵的各行中非零元素的个数是相同的，各列中非零元素的个数也 是相同的，此时l d p c 码为规则码。对应t a n n e r 图中所有变量节点具有相同的度 以，所有校验节点具有相同的度d 。，可简记为( ，巩，d 。) 码。 与规则码对照，如果校验矩阵的各行中非零元素的个数不相同，各列中非零 元素的个数也不相同，此时l d p c 码为非规则码。 规则码和非规则码相比各有优势。良好设计的非规则码的纠错性能优于规则 码，但是规则码在硬件实现方面较非规则码简单，且码长较短的非规则码具有相 1 2 山东大学硕士学位论文 对较小的最小距离的可能性较大。因此，规则码在很多场合下还是得到应用。 多进制l d p c 码 2 4 】的码元取自有限域g f ( q ) ，其中g 矿，p 为素数，r n 为正整 数。考虑到数字信息的二元特性，实际中我们一般只研究扩展域g f ( 2 m ) 上的多进 制l d p c 码。图2 2 给出了g f ( 2 册) 域l d p c 码和j p lt u r b o 码在二进制a w g n 信 道下的仿真性能。l d p c 码的码率均为1 3 ，码长从左到右依次为6 0 0 0 ，6 0 0 0 ，9 0 0 0 和1 8 0 0 0 ，两个j p l t u r b o 码的码率分别为1 4 码和1 3 ，码长分别为6 5 5 3 6 和4 9 1 5 2 。 图2 2 的结果显示，g f ( 1 6 ) 域l d p c 码的编码增益也明显超过了同等码率的j p l t u r b o 码。而且，随着有限域阶数的提高，g f ( 2 m ) 域l d p c 码的译码性能也明显提 升。遗憾的是，其译码复杂度也随阶数呈指数级增加。因此，如何在译码复杂度 和性能之间进行折中，成为多进制l d p c 码研究的重要问题。 图2 - 2g f ( q ) 域上l d p c 码与j p lt u r b o 码性能比较【2 4 】 为了行文方便，如不做特别说明，本文提到的l d p c 码均指二进制l d p c 码。 2 3l d p c 码的译码算法 2 3 1l d p c 码的译码算法 l d p c 码的译码原理可以通过消息在t a n n e r 图的边上传递过程来分析，所以 我们把l d p c 译码算法看作一种消息传递算法。同时，它也常被称作迭代算法， 1 3 空凳受暑麦b星盖杀le茹兽盘暑山 山东大学硕士学位论文 因为译码消息在变量节点和校验节点间来回传递。根据消息传递的方式和节点的 运算模式不同，消息传递算法演变出多种类型，它们基本以降低译码复杂度和运 算量为目标。 在常见的算法中，比特翻转算法的消息是二进制的形式，而置信传播算法的 消息是代表码字比特信息可信度的概率值形式。为了计算方便，通常把概率消息 表示成对数似然比的形式，这样校验节点和变量节点主要进行和、积运算，所以 置信传播算法又称和积( s u m p r o d u c t ) 算法。近年来，结合硬件实现的特点，一些 基于和积算法的改进算法不断提出。本小节简要回顾一下和积算法、最小和算法 2 5 】 和一种平衡变量节点和校验节点运算量的算法 2 6 】。 1 和积算法 首先，定义二进制码字c = ( c 1 q ，c 。) ， b p s k 映射后通过a w g n 信道，接收 端未解调的符号序列y = ( y 。y 以) ，译码后的序列为。定义消息变量如下： 信道初始消息 三) - l o g 鬻1 0 9 雨p r c , = 丽o l y , ( 2 - 1 ) 校验节点传向变量节点的消息 三( ) = l 。g 笔等 ( 2 2 ) 变量节点传向校验节点的消息 l ( ) = l 。g 老等 ( 2 3 ) 变量节点收集到的所有消息 l ( q i ) = l o g 考罟 ( 2 4 ) 算法流程：- 1 ) 信道消息初始化 计算信道传递给变量节点的初始概率似然比消息三) ，i = 1 ，2 ， 。然后对 每一个变量节点i 和与其相邻的校验节点j ( f ) ，设定变量节点传向校验节 点的初始消息 ( ) = ( p ) 2 ) 迭代处理 s t e p l 校验节点消息处理： 1 4 对所有的校验节点和与其相邻的变量节点i n ( j ) ，计算第个校验节点传 向第i 个变量节点的消息 t a n h ( 圭( 白) ) = 飘，t 柚( 圭三q i - ) ) p 5 ， 或 如) = 2 蛐叫b 1 - i 肼，鼬( 托一) ) ) ( 2 - 6 ) ( ) = 2 t 飙h 叫l鼬愕三( ) 】l f t ( ，) f 厶 s t e p 2 变量节点消息处理 对所有的节点变量i 和与其相邻的校验节点j m ( i ) ，计算第i 个变量节点传 向第，个校验节点的消息 l ( q 驴) = ( 只) + ( o ，) ( 2 7 ) s t e p 3 译码判决 对所有变量节点计算硬判决消息 l ( q ，) = ( 只) + ( o ) ( 2 8 ) 若己( 仍) o ，则乞= 0 ，否则6 ，= l 。 3 ) 停止 若m7 = 0 或者达到最大迭代次数，则结束运算，否则从s t e p l 继续迭代。 2 最小和算法【2 5 】 最小和算法将和积算法中校验节点的复杂的函数查表运算进行近似处理，即 将式子( 2 6 ) 近似为： ( 像) _ 取s 印( 地) ) 。洲r a i n 、f ( | q i 川) 仁9 ) 3 一种平衡复杂度的算法【2 6 】 由于和积算法中校验