（通信与信息系统专业论文）多元ldpc编码调制系统的低复杂度译码算法研究.pdf

摘要 信道编码足提高信息传输可靠性的垂要手段，而寻找性能优越、实现复杂度低的 编译码方案是编码界的研究热点。最近的二十年问，t u r b o 码的诞生引起了巨大的轰 动，进而引发了人们对低密度校验( l o w - d e n s i t yp a r i t y - c h e c k ，l d p c ) 码的重新发现。 近几年的研究结果表明，多元l d p c 码在中短码长时具有比二元l d p c 码更出色的纠 错性能，尤其在与高阶调制相结合时，这一点引起了人们的广泛关注。然而多元l d p c 码相对较高的译码复杂度削弱了它在性能上的优势。过去的十多年间，有关t u r b o 码二 元l d p c 码的研究与认知已渐趋成熟，然而有关多元l d p c 码的理论和应用研究仍亟 待深入。 本文主要研究多元l d p c 编码调制系统，并着重讨论了多元l d p c 编码调制系统 的低复杂度译码算法。其中针对编码调制系统中采用的基于有限域有限几何构造的多 元l d p c 码，研究了基于可靠度的消息传递算法，获得了一点成果。本文主要完成的 工作有以下几个方面： ( 1 ) 介绍了多元l d p c 码的定义和因子图表示，描述了经典的和积算法以及扩展最小 和( e x t e n d e dm i n s u m ，e m s ) 算法。通过性能仿真对比了多元l d p c 码、优化 设计的二元l d p c 码以及t u r b o 码。验证了多元l d p c 码在中短码长时的优越性 能； ( 2 ) 介绍了多元l d p c 编码调制系统，仿真结果验证了多元l d p c 编码调制系统是一 种逼近容量限的编码调制方案； ( 3 ) 针对多元l d p c 编码调制系统，我们从联合检测器与译码器操作的角度，引 入了一种新的低复杂度联合迭代检测一译码f i t e r a t i v ej o i n td e t e c t i o n - d e c o d i n g ， i j d d ) 算法。在迭代模式下，i j d d 算法将硬判决译码和最大似然信号硬检测联 合在一起工作，其中硬判决译码器基于码约束和大数逻辑规则产生的外信息传递 至检测器被用于纠正接收信号，以不断改进译码可靠度量。这不同于传统的检测 器一译码器工作模式，且只有硬信息在各节点间传播。性能仿真验证了i j d d 算 法的有效性，而复杂度分析表明，i j d d 算法对于多元l d p c 编码调制系统具有 潜在的应用价值。 关键词：多元l d p c 码和积算法编码调制系统联合迭代检测一译码 低 复杂度 a b s t r a c t c i l a n n e lc o ( 1 i n gi san e c e s s a r yt e c h n i q u e f o rr e l i a b l ec o m m u n i c a t i o no v e rn o i s yc h a r t - n e l s a n dt h es e a r c hf o rc a p a c i t y - a p p r o a c h i n gc h a n n e lc o d i n gs c h e m e sw i t hp r a c t i c a l c o m p l e x i t yh a sb e e nt h ef o c a lp o i n ta m o n g t h ec o d i n gc o m m u n i t y l a s t2 0y e a r sw i t n e s s t h ed h e n o m e n a ls u c c e s so ft u r b oc o d e s ，w h i c hl e a d st o t h er e d i s c o v e r yo fl o w - d e n s i t y p a r i t y - c h e c k ( l d p c ) c o d e s r e c e n t l y ，i th a sb e e ns h o w nt h a tn o n b i n a r yl d p cc o d e s c a no 行研b e t t e re r r o r - c o r r e c t i n gp e r f o r m a n c et h a nt h e i rb i n a r yc o u n t e r p a r t s ，e s p e c i a l l y w h e nc o m b i n e dw i t hh i g h e r o r d e rm o d u l a t i o n s h o w e v e r ，t h ea d v a n t a g e so fn o n b i n a x y l d p cc o d e sa r eb a l a n c e db yt h e i rh i g h e rd e c o d i n gc o m p l e x i t y o v e rad e c a d e ，a l b e i tt h e r e s e a r c ha n dk n o w l e d g eb a s ef o rt u r b oc o d e sa n dl d p cc o d e sh a v eb e e nq u i t em a t u r e ， m o r ei n t e n s i v er e s e a r c ho nt h e o r ya n da p p l i c a t i o n so fn o n b i n a r yl d p c c o d e sa r er e q u i r e d t h i st h e s i si n v e s t i g a t e s t h ed e c o d i n ga l g o r i t h m sf o rn o n b i n a r yl d p cc o d e d - m o d u l a t i o ns y s t e h l s ，w i t ht h ee m p h a s i so ns o m el o w - c o m p l e x i t yd e c o d i n gm e t h o d s a n d w m a i n l va d d r e s st h er e l i a b i l i t y - b a s e dm e s s a g ep a s s i n ga l g o r i t h mf o rd e c o d i n gn o n b i - n a r yl d p c c o d e sc o n s t r u c t e db a s e do nf i n i t ef i e l d s g e o m e t r y 。t h em a i nc o n t e n t sa r ea s f o l l o w s ， ( 1 ) t h ed e f t n i t i o na n d f a c t o rg r a p hr e p r e s e n t a t i o no fn o n b i n a r yl d p c c o d e sa r ei n t r o - ( 2 ) ( 3 ) ( 4 ) d u c e d t h ee r r o r c o r r e c t i n gp e r f o r m a n c eo fn o n b i n a r yl d p c c o d e sd e c o d e dw i t h s u m p r o d u c ta l g o r i t h mi sc o n f i r m e dw i t hs i m u l a t i o n s c o m p a r i s o n sa r ep e r f o r m e d w i t hb i n a r yl d p cc o d e sa n dt u r b oc o d e s ； e x t e n d e dm i n o s u m ( e m s ) a l g o r i t h m ，w h i c hr e d u c e st h ed e c o d i n gc o m p l e x i t yo f n o n 。 b i n a r vl d p cc o ( 1 e sw i t hn e g l i g i b l ep e r f o r m a n c el o s s i sa d d r e s s e d t h ee f f e c t i v e n e s s a n df e a s i b i l i t yo fe m sa l g o r i t h ma r ec o n f i r m e dw i t hs i m u l a t i o n sa n dc o m p l e x i t y a n a l y s i s ； t h en o n b i n a r yl d p cc o d e d - m o d u l a t i o ns y s t e m sa x ei n t r o d u c e d t h ec a p a c i t y a d p r o a c h i n gp e r f o r m a n c eo ft h en o n b i n a r y l d p cc o d e d m o d u l a t i o ns y s t e m si sv e r - i f i e db ys i m u l a t i o n s ； al o w - c o m p l e x i t yi t e r a t i v ej o i n td e t e c t i o n - d e c o d i n g ( i j d d ) a l g o r i t h mf o rn o n b i n a r y l d p cc o d e d m o d u l a t i o ns y s t e m si sd e v e l o p e d i nt h ep r o p o s e ds c h e m e ，s i g n a ld e - t e c t i o na n dd e c o d i n ga r ei n t e g r a t e da sa w h o l e a n dt h er e c e i v e ds i g n a l sa r eu p d a t e d b vt h ed e t e c t o rb a s e do ne x t r i n s i ci n f o r m a t i o np r o d u c e db yh a r dd e c o d e r i na ni t e r 。 a t i v em a n n e r i ti ss h o w nt h a tt h ep r o p o s es c h e m ec a l lo f f e rg o o de r r o r - c o r r e c t i n g p e r f o r m a n c eo re v e no u t p e r f o r mq s p a w i t hl o w e rc o m p u t a t i o n a lc o m p l e x i t y 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 u m - p r o d u c ta l g o r i t h mc o d e d - m o d u l a t i o ns y s t e m s i t e r a t i v ej o i n td e t e c t i o n - d e c o d i n gl o wc o m p l e x i t y 第一章绪论 第一章绪论 本章简要介绍了数字通信与信道编码的关系，回顾了信道编码理论与技术的发展历 程；结合稀疏图码和迭代译码，概述了l d p c 码的历史和现状，o 最后总结了作者 在攻读硕士期间所做的主要工作并给出了本文内容安排 1 1信道编码理论及技术的发展 通信系统设计的核心问题即在信道噪声的干扰下，如何将信源发出的信息可靠且 有效地传输到信宿。一般地，通信系统中采用误比特率( b i te r r o rp r o b a b i l i t y , b e r ) 来 衡量可靠性，而有效性则使用传输速率r 比特信道符号表征。早期的通信界普遍认为 【1 】，若要实现任意小错误概率的信息传输，唯一途径便是将r 降低到零。1 9 4 8 年，贝 尔实验室的工程师c l a u d ee s h a n n o n 在b e l ls y s t e mt e c h n i c a lj o u r n a l 上发表了一篇 题为am a t h e m a t i c a lt h e o r yo fc o m m u n i c a t i o n 的论文 2 】颠覆了通信系统可靠性与有 效性彼此互为矛盾的传统认知，同时开辟了信息与编码理论的崭新篇章。 根据s h a n n o n 的信息理论，数字通信系统的基本组成如图1 1 所示。 + i 数字调制器畔 姻 _ 数字解调器h r ) 删觥 图1 1数字通信系统基本框图 定理1 1 ( 信道编码定理)任意离散输入无记忆平稳信道存在信道容量c ，对于预 期的任一信息速率r g ，那么对任意的码长 n ，系统的译码误比特率r 的下界由下式给出： p b 何1 ( 1 一页c ) ，( i - i ) 其中风 ) = 一a l 0 9 2 ) 一( 1 一口) l 0 9 2 ( 1 一口) 为熵函数【2 j ，何1 ( ) 为其逆函数。 s h a n n o n 的信道编码定理阐明了，只要以不高于信道容量的速率传输信息，总存 在一种编码方案，使得系统的差错概率降至任意低；反之，则系统无法实现可靠通 多元l d p c 编码调制系统的低复杂度译码算法研究 信。s h a n n o n 在文献【2 】中证明此存在性定理时采用了随机编码和典型序列译码的思 想。但这种证明方法不具有指导意义：既没有指出如何构造出逼近容量限的好码，也 没有给出切实可行的译码方法。自此之后，人们便以信道编码定理为圭臬，在漫长的 几十年里不懈地探索着性能优良的编译码方案。在此，我们简略地回顾一下这段历 史。 在s h a n n o n 的论文发表后两年，同在贝尔实验室工作的h a m m i n g 发现了第一类用 于纠错的线性分组码- - h a m m i n g 码 3 1 。其后，r m 码【4 ，5 】、g o l a y 码【6 】和循环码【7 】 也相继涌现，这些码与h a m m i n g 码一起组成了线性分组码的早期成员。当时的研究 人员在设计纠错码时，着眼于构造具有较大最小码字距离的码，并运用码的代数结构 设计出限定距离译码算法( b o u n d e d - d i s t a n c ed e c o d i n g ，b d d ) 。其中值得一提的是循环 码，它蕴含着优美的代数理论，编译码过程简单便捷，尤其是在b c h 码【8 ，9 】和r s 码 1 0 1 诞生后，更是获得了广泛而深入的研究。b c h 码和r s 码可以使用基于有限域算术 的代数译码算法进行快速有效地译码1 1 ，1 2 】。由于r s 码还具有出色的纠突发错误的 能力，因而在通信及存储领域获得了持久广泛的应用。六十年代初，纠错码的一个重 要成员诞生在m i t r g g a l l a g e r 博士在其博士论文 1 3 】中详细阐释了一类具有稀疏 校验矩阵结构的线性分组码，即低密度校验( 1 0 w - d e n s i t yp a r i t y c h e c k ，l d p c ) 码，并第 一次给出了相应的迭代译码算法。然而，受限于当时的硬件水平，这一重要的工作被 人们遗忘在历史的角落里。 1 9 5 5 年，e l i a s 在文【1 4 1 中证明了使用线性码可以在二进制对称信道( b i n a r y s y m m e t r i cc h a n n e l ，b s c ) 上达到容量，并最早引入了不同于分组码的卷积码。稍 后，w o z e n c r a f t 和r e i f f e n 提出了卷积码的序列译码方法f 1 5 1 ，开启了一股研究序列译 码的热潮，并以f a n o 算法1 6 1 和堆栈算法【1 7 ，1 8 】的出现而告终。虽然采用序列译码 的卷积码被首先应用于深空通信中，但序列译码算法却从未在实际应用中广获青睐。 接着，m a s s e y 给出了一种效率不高但易于实现的译码方案一门限译码 1 9 l ，这一进展 使得卷积码得到了大量的实际应用。1 9 6 7 年，v i t e r b i 在文【2 0 】中为了证明错误指数 界引入了一种“渐进最优”的算法，即v i t e r b i 算法。不久，f o r n e y 【2 1 ，2 2 和o m u r a 2 3 1 意识到v i t e r b i 算法实际上是卷积码的最大似然( m a x i m u ml i k e l i h o o d ，m l ) 译码算 法，即译码器总是输出使接收序列条件概率最人化的码字序列。上世纪七十年代，在 l i n k a b i t 公司和j p l 的主导下，v i t e r b i 算法成为了n a s a 深空通信标准的一部分，其 应用日益广泛。1 9 7 4 年，b a h l 、c o c k e 、j e l i n e k 以及r a v i v 等四人给出了卷积码以及具 有网格结构的分组码的最大后验概率( m a x i m u map o s t e r i o r i ，m a p ) 译码算法【2 4 】，也 称为b c j r 算法。原则上，卷积码可以随着约束长度的增加而逼近s h a n n o n 限，但 v i t e r b i 译码算法的复杂度却随着k 指数增长，在k 较大时难以实施。 第一章绪论 3 按照m a c k a y 给出的码的分类f 2 5 1 ，上述的分组码和卷积码属于实| j 码的范畴， 然而在可接受的复杂度范围内，其性能相比于s h a n n o n 限尚有很人的距离。因此，人 们围绕着如何构造出好的长码以及复杂度可接受的的译码算法，设计出了许多编码方 案，如e l i a s 的乘积码【2 6 】和f o r n e yf 2 7 】的级连码。目标都是通过短分量码构造出具有 强纠错能力的k 码，并在接收端将最大似然译码分解成几个较简单的译码步骤，这样 就得到一个次优可行的策略，一个典型的级连编码系统如图1 。2 所示。 i 一一一一t l 墅墨堕墨垫丝堂一一j 图1 2 级连编码系统框图 f o r n e y 的分析表明，与传统的分组码和卷秋码相比，级连码可以获得较大的性能 改善，而译码复杂度并不显著增加。例如，美国空间数据系统顾问委员会( c c s d s ) 在 “行星标准”中采用了g f ( 2 5 6 ) 上的r s ( 2 5 5 ，2 2 3 ) 码和( 2 ，l ，7 ) 卷积码的级连。若内外 编码器之间选用2 8 个r s 码字大小的分组交织器，则当b e r = i o 一5 时，b p s k 信号 所需单位信息比特信噪比岛n o = 2 6 2 3 5 d bf 2 8 1 。 。 无论是乘积码，还是r s 码和卷积码的级连编码，都具有强大的纠随机和突发错误 的能力。然而由于早期硬件水平的限制，两种级连编码方案的译码通常采用硬输入硬 输出译码算法，因此其潜在的纠错性能并没有得到充分利用。 一般地，根据译码器处理的输入信息序列的格式不同，译码可以分为硬判决译码 ( h a r d d e c i s i o nd e c o d i n g ) 和软判决译码( s o f t d e c i s i o nd e c o d i n g ) 。硬判决译码是基于传 统纠错码观点的译码方法：解调器首先对信道接收值进行最佳硬判决，再将硬判决序 列送入译码器，而译码器基于h a m m i n g 度量依照一定的代数译码方法处理此硬判决序 列。根据数据处理定理( d a t ap r o c e s s i n gt h e o r e m ) 【2 9 ，对一个接收信号进行硬判决会 导致信息的丢失，进而降低译码性能。软判决译码则充分利用了信道输出信息：匹配 滤波器输出的软判决接收序列送入译码器进行处理，由于在译码时利用到了额外的信 息，因此软判决译码提供了比硬判决译码更好的纠错性能。一般地，与硬判决译码相 比较，软判决译码在a w g n 信道上有2 - 3 d b 的编码增益。 迄今为止，人们设计出的软判决译码算法大致可分为两类：一类是基于最小码字 错误概率( 误字率或误帧率) 准则的逐帧软判决译码，如广义最小距离( g m d ) 译码算 4多元l d p c 编码调制系统的低复杂度译码算法研究 法f 3 0 1 ，c h a s e 算法3 1 1 和v i t e r b i 算法等。另类是基于最小符号错误概率( 误比特 率) 准则的逐位软判决译码，如b c j r 算法，l e e 的前向m a p 译码 3 2 1 算法等。原 则上，b c j r 适用于任何可以使用网格进行描述的码。但由于它是一种软输入软输出 ( s o f t i ns o f t o u t p u t ，s i s o ) 译码算法，计算较为复杂，当时并朱引起足够的重视。直至 t u r b o 码出现后，b c j r 算法才逐渐成为迭代译码方案的首选【3 3 ，3 4 】。 1 2稀疏图码及迭代译码的繁荣 在上世纪九十年代以前，由于真正逼近s h a n n o n 限的纠错码迟迟未被发现，人们 习惯于将信道截止速率作为信道的实际容量。然而在1 9 9 3 年，随着c b e r r o u 等在i c c 会议上提出t u r b o 码f 3 5 1 ，沉寂许久的编码界迎来了一场疾进的变革人们第一次看到 码的纠错性能距离s h a n n o n 限如此之近。从编码角度来看，t u r b o 码将伪随机交织器 和卷积码结合在一起，实现了类随机编码方案；而在接收端，t u r b o 码通过两个低复 杂度的s i s o 译码器间的迭代操作来逼近最大似然译码。大量的结果表明，这种简单、 次优的迭代译码算法几乎总是收敛到最大似然译码的结果。这一革命性的进展引爆了 编码界对于迭代可译码的研究热情 3 6 1 。在t u r b o 问世后不久，剑桥大学的m a c k a y 和 m i t 的s p i e l m a n 几乎同时发现，g a l l a g e r 早在1 9 6 2 年提出的l d p c 码也是好码，在 中等码长时可以像t u r b o 码那样逼近s h a n n o n 限【2 5 ，3 7 ，3 8 】，且具有更低的线性译码 复杂度3 9 - 4 2 】。稍后，r i c h a r d s o n 等人的研究表明 4 3 】，当分组长度较很大时，精心 设计的非规则l d p c 码的性能优于同等码长和码率的t u r b o 码。理论分析表明，在二 进制输入a w g n 信道上使用码率1 2 的l d p c 码，当其的分组长度趋于无穷时，进行 可靠通信所需的信噪比门限值离s h a n n o n 限在0 0 0 4 5 d b 以内，而文【4 4 ，4 5 】中的仿真 结果表明，基于密度进化( d e n s i t ye v o l u t i o n ) f 4 3 1 设计出的码长为1 0 7 的非规则l d p c 码，在b e r = 1 0 _ 6 时所需的既o 距离s h a n n o n 限不到o 0 4 d b 。这些研究成果轰动了 当时的编码界，继t u r b o 码之后引发了又一轮迭代译码研究的热潮。不久之后，第一 个商用的l d p c 码一t o r n a d o 码【4 6 】也问世了。 回顾l d p c 码从诞生到被重新发现的近三十年，期间只有少数几篇论文进行了进 一步研究f 4 7 _ 4 9 1 。其中最引人注目的是r m t a n n e r 【4 9 】关于图模型的工作：t a n n e r 引入一种规范的图表示l d p c 码，即把码校验约束建立在局部码元集合上的t a n n e r 图。1 9 9 5 年，w i b e r g 在他的论文【5 0 ，5 1 1 中推广了t a n n e r 图模型，扩展后的二部 图可以表示网格码。这样，t u r b o 码和l d p c 码等迭代可译码都可视作稀疏图码 ( c o d e so ns p a r s eg r a p h s ) 的特例，且它们的迭代译码算法均可归结于迭代后验概率( a p o s t e r i o r ip r o b a b i l i t y , a p p ) 译码，即和积算法( s u m - p r o d u c ta l g o r i t h m ，s p a ) 。w i b e r g 还证明了在无环( c y c l e - f r e e ) 图上，最小和算法( r a i n s u ma l g o r i t h m ，m s a ) 准确实现 了最大似然译码，s p a 则实现了最大后验概率译码。特别地，在t r e l l i s 图上二者分 第一章绪论5 别简化为v i t e r b i 算法和b c j r 算法。此外，w i b e r g 的图模犁还允许使用更般性的 量度( m e t r i c ) 作为成本函数，从而适用丁二非均匀先验概率分布模型或有记忆信道模 型。f o r n e y 赞誉w i b e r g 的论文为“一次成功的统一( 即将码统一用图模型来表示) ，为 该领域( 即稀疏图码的研究) 奠定了理论的基石”。后来基于w i b e r g 的工作，人们又引 入了因子图( f a c t o rg r a p h ) 5 2 ，5 3 】以及f o r n e y 型凶子图( f o r n e y - s t y l ef a c t o rg r a p h ) 【5 4 】 的概念。一个由如下校验矩阵h 定义的( 8 ，4 ，4 ) r m 码的t a n n e r 图和f o r n e y 型因子图 如图1 3 所示。 h = lll 100oo 010110l0 oo1 l11o0 00oo111 1 ( a ) t a n n e r 图表示( b ) f o m e y 型因子图表示 图1 3 ( 8 ，4 ，4 ) r m 码的图表示 关于图码及迭代译码的其它研究成果，可参考文献f 5 5 ，5 6 】。除了v i t e r b i 算 法、b c j r 算法以及t u r b o 码和l d p c 码的译码算法以外，下列算法也已被证明是和 积算法操作在相应图表示上的特例f 5 7 1 ： 1 ) 用于在贝叶斯网络上进行统计推理的置信度传播( b e l i e fp r o p a g a t i o n ) 算法【5 8 】 2 ) 在信号处理尤其是语音识别中用于检测隐m a r k o v 模型的前向后向( f o r w a r d b a c k w a r d ) 算法【5 9 】； 3 ) m a r k o v 随机域上的联结树( j u n c t i o nt r e e ) 算法【5 5 】； 4 ) 基于广义高斯图的k a l m a n 滤波器。 在t u r b o 码、l d p c 码等t u r b o - l i k e 码 6 0 逐渐成为编码界研究热点的十多年中， 洳 确 娩池 妇 枷 断 o 1 2 3 4 5 b 7 肋 慰慰 勋 躬 胎 勋 6 多元l d p c 编码调制系统的低复杂度译码筛法研究 人们对稀疏图码和迭代译码的认识也逐步深入，理论上的主要成果可以归结为两大 部分：一是t a n n e r 、k s c h i c h a n g 、f r e y 、l o e l i g e r 、w i b e r g 和f o r n e y 等人关于图模型 的工作；二是r i c h a r d s o n 、c h u n g 、t e nb r i n k 等人关于迭代译码性能分析方面所作的 工作，即密度进化理论【6 1 】、高斯近似【6 2 】以及e x i tc h a r tf 6 3 6 6 】分析。此外，还 有许多研究涉及l d p c 码的有效编译码、在不同环境下的应用等问题，可参考文献 6 7 ，6 8 】o 毫无疑问，迭代译码思想的诞生对于通信领域的影响是深远而巨大的。如今，通 信的各个环节几乎都可以纳入到迭代处理的框架下：信源编码，信道编码，调制，均 衡，多址接入以及多天线技术等，无一不受到了迭代信号处理技术带来的冲击【6 9 】。 1 3多元l d p c 码的研究现状和展望 事实上，在二元l d p c 码研究进行得如火如荼时，多元l d p c 码的研究也已悄 然展开。多元l d p c 码最早由g a l l a g e r 在文【1 3 】中基于模算术引入。1 9 9 8 年，d a v e y 和m a c k a y 基于有限域g f ( q ) ( q 2 ) 引入了一类多元l d p c 码【7 0 】，并给出了译q 元 l d p c 码的和积算法，被称为q s p a 。现有的研究成果表明，相较于二元l d p c 码， 多元l d p c 码具有如下优点： i 更好的纠错性能：由于多元l d p c 码将多个比特合并成一个多元符号，从而具有 消除l d p c 码二部图表示中小环的潜力，在迭代译码下可以获得更好的纠错性能 【7 0 7 2 】 i i 抗突发错误能力强：实际信道中产生的错误往往是突发错误或突发错误与随机错 误并存。而二元l d p c 码并不具有很强的抗突发错误能力，在实际系统中往往需 要同r s 码或b c h 码级联。多元l d p c 码由于可以将多个突发比特错误合并成数 量较少的较少的多元符号错误，因而纠错性能优于二元l d p c 码，研究结果也已 验证了这一点f 7 3 1 ； i i i 适合高速率传输：多元l d p c 码是基于高阶有限域设计的，因此非常适宜与高阶 调制方案及多天线系统结合从而提供更高的数据传输速率和频谱效率f 7 4 - 8 0 。研 究发现，与高阶调制相结合时，采用多元l d p c 码要优于二元的l d p c 码。 基于上述优点，多元l d p c 码的研究具有很大的实际应用价值。如欧洲的e n s e a 联合三星、意法半导体等诸多公司进行的“达芬奇计划”( d a v i n c ip r o j e c t ) ，便是以多 元l d p c 码为核心展开的关于多元编码调制系统的研究，旨在为下一代移动通信系统 的高频谱效率要求提供可靠、低复杂度的解决方案。近几年来，针对多元l d p c 码的 构造，s h u “n 等在文f 8 1 - 8 6 1 中基于有限域及有限几何等代数工具给出了系统的构造方 法，其他构造方法可参见文献【8 7 8 9 】等。理论分析方面可参看文【7 5 ，7 6 ，9 0 ，9 1 】。 在多元l d p c 码的译码方面，文【7 0 】给出的q s p a 的运算复杂度高达o ( q 2 ) ( q 为 第一章绪论 有限域的阶数) 。为了有效地降低的译码复杂度，d a v e y 和b a r n a u l t 等在q s p a 的校验 节点的更新步骤中采用快速傅立叶变换( f a s tf o u r i e rt r a n s f o r m ，f f t ) 技术7 2 ，9 2 1 ，即 f f t - q s p a ，从而将运算复杂度降低至o ( ql o g 。( q ) ) ，但前提是有限域阶数q 必须是2 的 整数幂次。然面，大量的实数乘法运算以及概率域上的量化问题导致该算法难以应用 到实际中。随后s o n g 等将消息的表示推广到了概率和对数似然比( 1 0 9 - l i k e l i h o o dr a t i o ， l l r ) 的混合域上【7 3 ，在保留校验节点f f t 运算的同时避免了大量的实数乘法运算， 但消息形式的频繁转换以及大量查表运算仍制约着其实际应用。2 0 0 7 年，d e c l e r c q 和 f o s s o r i e r 等提出了一种扩展最小和算法( e x t e n d e dr a i n s u m ，e m s ) f 9 3 ，9 4 1 ，通过将l l r 消息向量长度截短为扎m ( n m 3 2 ) ，e m s 的译码复杂度仍然相当高。最近，b o u t i l l o n 等又针对e m s 算法中校验节点的信息更新 提出了检泡( b u b b l ec h e c k ，b c ) 算法 9 5 ，9 6 1 ，进一步降低了译码复杂度。 以上有关多元l d p c 码的研究现状的介绍比较粗略，相比于已经很成熟的二元 l d p c 码，多元l d p c 码的理论和实际研究尚有很多内容，比如门限分析、迭代译码 分析、低复杂度译码算法研究、降低错误平层等方面，需要投入更多的研究力量。 。 1 4本文的研究内容及论文安排 本文结合国家重大专项和国家8 6 3 计划项目，研究了多元l d p c 码的译码算法， 引入了一种低复杂度的联合迭代检测一译码算法，详细讨论了提出的算法与经典算法 在性能、复杂度上的对比。全文共分为四章，其他章节安排如下： ? 。 第二章详细描述了多元l d p c 码的经典和积译码算法以及扩展最小和译码算法； 第三章介绍了编码调制系统的基本原理、容量限，并重点介绍了多元l d p c 编码调制 系统；在第四章中本文给出一种针对多元l d p c 编码调制系统的联合迭代检测一译码 算法，探讨低复杂度的译码方案。 第四章是本文的核心内容，从解调器和译码器联合迭代的角度入手，探索解调器 与译码器在硬检测及硬判决译码的工作方式下的纠错性能。传统译码观点认为解调器 只需一次性地输出软解调信息即可，本文第四章给出了一种新的框架，即解调器基于 信道接收符号给出最大似然硬判决序列输入到译码器，译码器基于大数逻辑规则和码 约束关系给出发送符号的硬估计值和相应的整数可靠度。然后解调器利用硬估计值及 可靠度对接收符号进行更新，更新的规则是将受噪声污染而偏离原发送信号点逐步修 正到原始的发送信号。本文结合性能仿真和复杂度分析，对该方案进行了综合的评 述。 最后对全文工作进行总结，并给出了下一步的研究方向。 第j 二章多元l d p c 码及其译码算法 第二章多元l d p c 码及其译码算法 多元l d p c 码是一种逼近s h a n n o n 容量限的编码方案本章简略地介绍了多元 l d p c 码的一些基本概念，讨论了多元l d p c 码的经典译码算法和积译码以及 扩展最小和译码算法，并通过性能仿真与二元l d p c 码及3 g p p 标准中采用的 t u r b o 码作了比较结果证明，在中短码长时，多元l d p c 码具有更优良的纠错 性能 2 1 线性分组码 2 1 1 定义 一个g f ( q ) 上的( 竹，k ) 线性分组码c 是g f ( q ) 上所有礼元组组成的向量空间的k 维子空间 67 】。如果一个码c 是g f ( 2 ) 上的，那么它就是一个二进制码，其码字的的每 个元素被称为一个码比特。反之，若码c 基于g f ( q ) 且q 2 ，那么就称c 为多元或者 q 元码。假如g 是p 的幂次，即q = p 8 ，其中5 为一正整数，那么g f ( q ) 上的每个元素 都可以用一个g f ( p ) 上的s 元组等效表示。因此，每个g f ( q ) 上的( n q ，k q ) g 元线性分 组码岛都可以映射成g f ( p ) 上的( t t q 8 ，k q s ) p 元线性分组码c p 。并且这种映射是一一对 应的满射。 通常，一个( 礼，k ) 线性分组码c 将信息序列划分成k 长的信息块，即每个信息块包 含了g f ( q ) 上的k 个符号。然后编码器逐一地将信息块映射成c 中的1 7 , 长码字，此映 射也应是一对一的。比例r 兰后佗被称为c 的码率。 假定c l 是( 佗，k ) 线性分组码c 中的一个码字，那么c 的h a m m i n g 重量叫( c 1 ) 定 义为c i 中的非零元素个数。令c j ( j i ) 是c 中的另外一个码字，那么c i 与c j 的 h a m m i n g 距离d ( c f ，c j ) 定义为二者相应位置不相等的元素的个数。由h a m m i n g 重量和 h a m m i n g 距离的定义可知： d ( c i ，勺) = w ( c i + c j ) ( 2 1 ) 现在我们引入一个线性分组码的重要参数：最小距离，它决定了线性分组码的检 错和纠错的能力。线性分组码的最小距离定义如下： d , n i n 全m i n d ( c i ，c 1 ) ：c i ，c j c ，c i q ( 2 - 2 ) 基于式2 1 和式2 2 ，我们可以得到如下关系： d m 饥= m i n w ( c i + 勺) ：c i ，c j c ，c i q ) = m i n w ( c ) ：c t + c j = c c ，c 0 ) 全w m t n( 2 - 3 ) 1 0多元l d p c 编码调制系统的低复杂度译码算法研究 其中w m 讯被称为线性分组码c 的最小h a m m i n g 重量。一般来说，采用硬判决译码的 纠错性能由其最小距离决定，而采用软判决最大似然译码的纠错性能则由码重量分布 决定。 2 l 2生成矩阵和校验矩阵 由于g f ( q ) 上的线性分组码c 是g f ( q ) 上所有礼元组张成的空间的k 维子空间， 那么就有o - l - e 。”, 从c 中找出k 个相互线性独立的码字g o ，9 1 ，g 七一1 形成一组基向量，使 得任意码字c 都可这k 个码字的线性组合来表示，即： c = u o g o + u t g t + + u 七一l g k 一1( 2 4 ) 其中u 0 ，u l ，u k 一1 g f ( q ) 。如果我们使用基 g o ，g l ，g k l 当作一个矩阵的行，那 么我们可以得到一个g f ( q 1 上的k n 矩阵： c = 其中g l = ( g i ，0 ，g i ，1 ，g i , n - - 1 ) ，0s 信息块，编码操作可表示为： 憾一引协5 ， 卸俨。小 g = c i k p，=(妻三；手i妻i。主j，。j；三i：_二i。 c 2 7 ， 第：二章多元l d p c 码及其译码算法 其l li 是一后七的译位矩阵，p 是一个后( n 一庇) 的矩阵，p i ，j c v ( q ) 。由系统矩阵 g 编出的码被称为系统码，因为其中的码字都具有图2 1 所示的结构，其中第一部分足 包含k 个信息符号的信息块，第二部分为包含佗一k 个校验符号的冗余校验部分。 例如，假设u = ( u o ，u l ，u k 一1 ) 是信息块，v = ( 口o ，口1 ，一1 ) 是编码后的码字， 则有： 忱= 。山f o r r 后0 三i i 三 k 一- 1 ( 2 - 8 ) 除了上述的定义方法外，一个g f ( q ) 上的( 他，k ) 线性分组码c 还可以由其校验矩阵 h 完全定义。h 的维数是m n ，其中m 扎一k 。一个校验矩阵h 满足条件：任一 由g 生成的礼元组v 是一个码字当今当v h t = 0 ，或等效地 ( 2 - 9 ) 其中乘法和加法操作都定义在有限域g f ( q ) 上。因此，一个( n ，七) 线性分组码的校验矩 阵h 包含佗一k 个线性独立的行。这一条件也意味着：g h t = 0 。 由于矩阵h 的行空间形成一个g f ( q ) 上所有n 元组张成空间的7 7 , 一k 维子空间， 它定义了一个g f ( q ) 上的( n ，n 一) 线性分组码q 。我们称白为c 的对倡码，因为。 是c 的零字间。换言之，任意c 中的码字都正交于岛中的任意码字。 如果一个( 死，惫) 线性分组码c 的生成矩阵是如式2 7 的系统形式，那么其校验矩阵 h 可以表示为： f p o ，op l ，op k - 1 ，oi 10 01 h = ( p t i n - k ) = 卜p 1 ；1 ：0 1 1 * 引 浯 p o ，t l 一惫一1p l ，n 一七一1 p k 一1 ，n 一七一1l 00 1 其中p t 是矩阵p 的转置。特别地，下面的定理给出了一个( n ，七) 二元线性分组码的最 小距离与其校验矩阵之间的关系： 定理2 1 令c 为一个( 扎，k ) 二元线性分组码，其校验矩阵为h 。对每个h a m m i n g i 信息部分冗余校验部分 图2 1系统形式的码字 l ml0 | i o = 吩 玩 “瑚 1 2多元l d p c 编码调制系统的低复杂度译码算法研究 重量为z 的码字，h