（通信与信息系统专业论文）ldpc码联合bicmid系统的研究.pdf

重庆大学硕士学位论文 中文摘要 摘要 联合低密度奇偶校验( l o w d e n s i t yp a r i t y c h e e k ，l d p c ) 码的比特交织编码 调制迭代译码( b i t i n t e r l e a v e dc o d e dm o d u l a t i o ni t e r a t i v ed e m o d u l a t i o n d e c o d i n g ， b i c m i d ) 技术，由于具有频谱利用率高、结构灵活性强、实现复杂度低和译码性 能优异等优点，而受到广泛关注。现阶段对l d p c b i c m i d 的研究主要集中在映 射方式的选择、交织器的设计及迭代译码算法的设计和改进等方面，虽然已经取 得了显著的成果，但仍存在一些问题需要继续深入研究，尤其是针对不存在研a y 映射的l d p c b i c m i d 系统映射标识的选择以及如何提高系统中解调器和译码器 之间的迭代译码增益。本论文针对上述指出的问题开展研究，并得出相应的结论， 主要工作如下： 1 ) 总结分析l d p c 码的编译码方法以及b i c m i d 技术，并通过仿真验证了 b i c m 性能优于t c m ，而b i c m i d 性能又优于b i c m 的结论，证明了迭代译码可 以改善系统误码性能。 2 ) 针对l d p c b i c m i d 系统结构，用互信息理论研究星座映射方式对 l d p c b i c m i d 系统性能的影响，重点对不存在格雷( g r a y ) 映射的星形1 6 q a m 映射方式的设计进行分析，结合欧氏平方重量最大化原则( m s e w ) 和最d , n 决 区域最大化原则，提出一种适合此系统的优化设计准则，并给出相应的星座映射 方式，仿真验证系统性能的优越性，从而为不存在g r a y 映射的l d p c b i c m i d 系 统提供了一种设计星座映射的准则。并通过仿真分析了a w g n 信道下，码长、列 重、交织、迭代次数等参数对l d p c b i c m i d 系统性能的影响。 3 ) 研究一种分析迭代译码收敛性能的有效方法外部信息传递图( e x i t ) ， 可以准确、直观的描述迭代译码的过程，通过绘制各星座映射方式随着信噪比的 提高e x i t 图的变化曲线，验证了论文提出的星座映射设计准则的正确性。此外， 本文给出了一种改进结构以改善l d p c b i c m i d 系统外迭代译码增益不大这一缺 点，通过把外迭代、解交织及解调插入到l d p c 码自身的迭代译码过程中来提高 译码准确度和收敛速度。 关键词：比特交织编码调制迭代译码，低密度奇偶校验码，星座映射，外部信息 传递图，互信息 重庆大学硕士学位论文 一一 一一一 茎塞塑墨 _ _ - 一 a b s t r a c t m o t i v a t e db yi t sl o wc o m p l e x i t y , s t r o n ga g i l i t y , h i g hs p e c t r u me f f i c i e n c y , a n d e x c e l l e n tp e r f o r m a n c e ，l o wd e n s i t yp a r i t yc h e c k ( l d p c ) c o d e db i t i n t e r l e a v ec o d e d m o d u l a t i o nw i t hi t e r a t i v ed e c o d i n g ( b i c m i d ) h a sb e e nak e yt e c h n i q u eo fn e x t g e n e r a t i o no fw i r e l e s sc o m m u n i c a t i o n a n di t h a sb e e nw i d e l yu s e di nm o d e m c o m m u n i c a t i o ns y s t e m s t h ec u r r e n tr e s e a r c h e so fl d p c - b i c m i ds y s t e m ，w h i c h i n c l u d et h em a p p i n gc o n s t e l l a t i o nd e s i g n ，i n t e r l e a v i n gs c h e m ea n di t e r a t i v ed e c o d i n g a l g o r i t h m ，h a v eb e e ns t u d i e dr i g o r o u s l y h o w e v e r , t h e r ea r es t i l lm a n yp r o b l e m sn e e d t o b er e s o l v e d ，e s p e c i a l l yf o rt h ec h o i c eo fs i g n a lm a p p i n gi nl d p c - b i c m i ds y s t e m w h i c hd o e sn o te x i s tg r a ym a p p i n ga n dh o wt oi m p r o v ed e c o d i n gg a i nb e t w e e nt h e m o d u l a t o ra n dt h ed e c o d e r t h i sd i s s e r t a t i o nf o c u so na b o v et w ot o p i c s ，t h e nd of u r t h e r i n v e s t i g a t i o no nb i c m - i ds y s t e mb a s e do nl d p c c o d e s 1 ) t h i sp a p e rd oas y s t e m a t i cs t u d yo nt h eb a s i cp r i n c i p l e so ft h el d p cc o d e s ， e n c o d i n gm e t h o do fl d p cc o d e s ，d e c o d i n gm e t h o d o fl d p cc o d e sa n dt h et e c h n o l o g y o fb i c m i d t h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft w ol d p cc o d e se n c o d i n gm e t h o d s a r ea n a l y z e da n dc o m p a r e d ；p r o b a b i l i t yo fb e l i e f - p r o p a g a t i o n ( b p ) d e c o d i n ga l g o r i t h m a n dt h el l rb pd e c o d i n ga l g o r i t h ma r ed e r i v e d t h es t r u c t u r ea n dw o r k i n gp r i n c i p l eo f b i c m i di sr e s e a r c h e d a n dt h es i m u l a t i o nr e s u l t si n d i c a t et h a tt h es y s t e mw i t hi t e r a t i v e d e c o d i n gh a sb e t t e rb i te r r o rp e r f o r m a n c et h a nb i c m a n dt c m 2 ) b i t i n t e r l e a v e dl d p cc o d e dm o d u l a t i o ni t e r a t i v ed e c o d i n g ，w h i c hc o m b i n e s l d p cc o d e sa n db i c m i d ，i sr e s e a r c h e da sa ne m p h a s i sp a r t ，i n c l u d i n gb u i l tt h e a r c h i t e c t u r eo fl d p c b i c m i ds y s t e m ，d e r i v et h ep r o c e s so fj o i n td e m o d u l a t i o nw i t h i t e r a t i v ed e c o d i n ga n dg i v ea ne f f i c i e n ts o f td e m o d u l a t i o na l g o r i t h m b a s e do nt h e i m p a c to fs i g n a ll a b e l i n g ，v e r i f i e dc o n s t e l l a t i o nm a p p i n gb a s e do nm u t u a li n f o r m a t i o n c r i t e r i o na r es i m u l a t e d ，a n dan e ws i g n a ll a b e l i n gd e s i g n e dc r i t e r i o ni sp r o p o s e df o rb i t i n t e r l e a v e dl d p cc o d e ds t a r - 16 q a mm o d u l a t i o nw i t hi t e r a t i v e l yd e c o d i n gi nt h i s d i s s e r t a t i o n ，i ti si no r d e rt om a x i m i z et h ee u c l i d e a ns q u a r ea n dm i n i m u md e c i s i o n r e g i o nf o rt h i ss y s t e m an e ws t a r - 16 q a ms i g n a ll a b e l i n gi sd e s i g n e db a s e do ni t c o m p a r a t i v es t u d y o fd i f f e r e n t l a b e l i n gi s d o n et h r o u g ha n a l y s i sa n dc o m p u t e r s i m u l a t i o n ，t h er e s u l t su n d e ra w g n c h a n n e ls h o wt h a tt h en e wd e s i g n e ds i g n a ll a b e l i n g a c h i e v e sab i gg a i n a l s o ，t h ei n f l u e n c eo fo t h e rp a r a m e t e r so ns y s t e mp e r f o r m a n c ea r e r e s e a r c h e d ，s u c ha sc o d el e n g t ha n dc o l u m nh e a v yo fl d p cc o d e s ，i n t e r l e a v i n ga n dt h e i i n u m b e ro fi t e r a t i o n so fl d p c b i c m i ds y s t e m 3 ) r e s e a r c ho nt h ee f f e c t i v em e t h o da n a l y z i n gc o n v e r g e n c eo fi t e r a t i v e d e c o d i n g 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 rc h a r t ( e x i t ) a n a l y z e dt h ei t e r a t i v ep r o c e s so f b i c m i db a s e dl d p cc o d e sa n dt h ei n f l u e n c eo fs o m el a b e l i n gm a p so nt h es y s t e m p e r f o r m a n c eb ye x i tc h a r ti n 叁g nc h a n n e l 、w ev a l i d a t et h ec o n c l u s i o nw h i c hi sg o t b ys i m u l a t i o n i no r d e rt oi m p r o v et h ep e r f o r m a n c eo fb i c m i db a s e do nc o d e s d r a m a t i c a l l yb yc o m p a r i n gt ob i c mw i t ht h es a m ec o n s t i t u e n tc o d e t h er e a s o no f t h i s p h e n o m e n o ni sa n a l y z e da n da ni m p r o v e dj o i n t d e m o d u l a t ed e c o d i n gm e t h o di s p r o p o s e db yc o m b i n i n gt h ec h a r a c t e r i s t i c so fl d p ca n db i c m - i d s i m u l a t i o nr e s u l t s s h o wt h a tt h ep e r f o r m a n c eo ft h i se n h a n c e dl d p c b i c m - i di si m p r o v e d k e y w o r d s ：b i t i n t e r l e a v ec o d e dm o d u l a t i o nw i t hi t e r a t i v ed e c o d i n g l o w d e n s i t y p a r i t y - c h e c k ，s i g n a ll a b e l i n g ，e x t r i n s i c i n f o r m a t i o nt r a n s f e r c h a r t ， m u t u a li n f o r m a t i o n i i i 重庆大学硕士学位论文 1 绪论 1 绪论 1 1 课题背景及研究意义 高功率效率、高频谱效率和高传输可靠性是现代无线通信系统一直追求的目 标，伴随着现代通信技术和计算机技术的迅猛发展和广泛应用，每天都有各种新 的通信业务和信息业务不断涌现，与此同时，人们对通信质量和数据传输速率的 要求也在不断提高。但是由于移动通信信道中的各种衰落、符号间干扰、多径干 扰、多用户干扰、热噪声和功率限制等因素，使得信号在经过信道传输到达通信 系统接收端的过程中，不可避免地要受到各种干扰而出现信号失真等问题。为了 解决这些问题，编码调制技术应运而生，作为一种极具应用前景的通信技术，一 直受到人们的广泛关注。 信道编码l l j 是对抗信道非理想因素( 如噪声和干扰) 的技术，实现方法是通过 在发送端信息比特中按某种规则添加一定的冗余码元来对抗信道干扰和噪声，从 而在一定程度上增强传输可靠性，进而提高通信系统的功率利用率；在接收端按 发送端相应的规则对接收到的信息序列进行译码，检错或者纠错并通过判决恢复 原始信息序列，添加的冗余信息会占用一定的频带资源，使得频谱利用效率降低， 所以可以说，信道编码是以牺牲频谱效率来换取传输可靠性的提高 2 1 。 根据香农信息论的基本理论【3 j ，m a s s e y 提出了将编码与调制联合优化的思想， 在文献【3 冲他论证了将二者作为一个整体考虑可以有效的解决通信系统信息传输 可靠性和有效性之间的矛盾，可以获得较大的联合编码增益，从而改善系统性能， 从此为信道编码调制技术的研究指明了新的方向，这种技术称为之联合编码调制 技术。通过将编码和调制联合设计，可以使通信系统在不占用额外频谱资源的情 况下获得较大的编码增益，因而能够同时提高频谱效率和功率效率。最为典型的 编码调制技术当属网格编码调制( t c m ) 技术1 4 j 和比特交织编码调制( b i c m ) 技术【5 j 。t c m 技术是通过使码字间的最小欧氏距离最大化【6 j ，从而获得系统在加 性高斯白噪声( a w g n ) 信道下表现的优异性能，但t c m 在衰落信道下性能并 不理想；而b i c m 技术是通过在t c m 的结构中引入比特交织器来实现汉明距离的 最大化1 7 j ，从而改善了码字间的最小欧氏距离，在理想交织时，编码器和调制器可 以分离设计，因而系统的设计具有高度的灵活性，b i c m 技术虽然牺牲了一些欧氏 距离特性，但可以使得码字的分集数最大，所以在衰落信道下性能也比较优异。 x i a o d o n gl i 和j a r i t c e y 将t u r b o 码的迭代译码思想应用于b i c m 系统中，提 出了比特交织编码调制迭代译码( b i c m i d ) 方案【8 j ，b i c m i d 技术是对b i c m 的 一次重要改进，在保证衰落信道下分集阶数的同时，通过将译码输出的信息反馈 重庆大学硕士学位论文 1 绪论 给解调器，作为解映射的先验信息，相当于增加了系统的欧氏距离，所以在a w g n 信道下可以获得与t c m 一样好的误码性能。由于b i c m i d 技术在a w g n 信道 和衰落信道下都能够提供接近香农限的优异性能，所以近年来它成为无线通信技 术的研究热点之一，受到了学术界和产业界的广泛关注p 。 现代通信系统中，好的纠错码的选择和设计也是保证数据可靠传输的一个重 要的组成部分。香农信道编码定n t l l 峙旨出，对给定的有干扰的信道，存在确定的 参数一信道容量c ，假定信道中消息传送速度为r ，如果r c ，则不可能实现无误码通信。根据香农信道 编码理论，人们一直在致力于构造纠错能力接近香农理论极限且编译码复杂度尽 可能低的好码。在众多的编码方案中，低密度奇偶校验( l o w d e n s i t yp a i l t y c h e c k ， l d p c ) 码是近年来蓬勃发展起来的一种性能优异的好码i l 引，其性能可以和t u r b o 码【l3 】进行媲美，并且l d p c 码采用的是并行译码方式，相比于t u r b o 码，其译码 延时和复杂度都有很大的降低。 联合l d p c 码优异的译码性能和b i c m i d 技术的高频带利用率，将传统的 b i c m i d 结构中的卷积码用l d p c 码来代替，研究联合l d p c 码的b i c m i d 系 统的性能是非常有意义的工作 1 4 - 1 5 。目前对l d p c b i c m i d 系统的研究主要集中 在映射方式的选择、交织器的设计及迭代译码算法的设计和改进等方面，但对于 不存在g r a y 映射的l d p c b i c m i d 系统，如何选择星座映射方式以及如何提高系 统中解调器和译码器之间的迭代译码增益对系统性能有重要影响，本文针对上述 两个问题开展研究，并得出相应结论。 1 2 国内外研究现状 本文所研究的是联合l d p c 码的比特交织编码调制迭代译码技术，其纠错码 为当前研究比较热门的l d p c 码。l d p c 码是一种线性分组码，其校验矩阵为稀疏 矩阵，首先由g a l l a g e r 在上世纪六十年代提出u6 | ，其主要创新是在接收端引入了 迭代译码算法，但是当时由于计算能力的限制，并没有引起足够重视，一直到t u r b o 码被发现和广泛的应用后，才由m a c k a y 重新提出【1 7 j 。 近年来，在l d p c 码领域所取得的大量的研究成果表明l d p c 码具有非常优 异的性能【1 8 - 1 9 ，尤其是一些码长较长的l d p c 码的性能甚至比t u r b o 码的性能还 要优越。研究表明在慢衰落信道中，l d p c 码性能优于t u r b o 码【20 1 ，l d p c 码具 有的良好的汉明距离特性也是其中一个重要原因。人们在基于图模型研究l d p c 码时，发现t u r b o 码也可以看作是一种图模型上的l d p c 码【2 ，它们的迭代译码 算法可以看成是，人工智能理论中贝叶斯( b a y e s i a n ) n 络上p e a r l 置信传播( b e l i e f 2 重庆大学硕士学位论文 1 绪论 p r o p a g a t i o n ，b p ) 算法在有环( c y c l e ) 图【2 2 】上的应用。与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 码已经被很多系统采用， 作为编码方案的备选方案之一。例如：下代卫星数字视频广播标准d v b s 2 已 经采纳了基于l d p c 码的编码方案【2 3 】，同时l d p c 编码方案还被中国自主研发的 c m m b ( c h i n a m o b i l em u l t i m e d i a b r o a d c a s t i n g ，中国移动多媒体广播) 体系架 构中的核心技术s t i m i 作为内码的编译码方案【2 4 1 ，在目前l o g b s 以太标准的制定 中，l d p c 码也受到了极大的关注1 2 5 j 。 在二十世纪八十年代之前，通信系统中的编译码器和调制解调器是分别独立 设计的。在频带受限的信道中，为避免信息有效传输速率降低，纠错编码所需的 冗余度可通过增加调制信号集来实现。调制则主要是指映射星座的设计，其作用 是将编码之后的符号序列映射到二维复平面上进行传输。但是在功率和频带都受 限的信道中，扩大调制信号集会导致信号间欧氏空间距离变小，引起系统误码率 性能急剧下降。而如果要弥补这一性能损失，则需要设计一个具有更高编码增益 的纠错码，这就导致了编译码复杂度的大幅度增加。如果权衡各种因素对编码器 和调制器进行设计，这样的系统实际性能也很难达到预期的效果，造成这种局面 的主要原因就是编码器和调制器是分开独立设计的。 八十年代初期，人们发现设计最佳的编码调制系统时，应该把编码序列的欧 氏距离而不是汉明距离作为设计度量。i m a i 和h i r a k a w a 的研究也证明了m a s s e y 提出的使用联合编码调制技术来实现信道编码和数字调制联合优化的思想的优越 性【26 | ，把信道编码和调制作为一个整体进行联合优化，使得信道编码技术有了突 破性进展。该思想在欧氏空间优化码字，不需要采用复杂度很高的信道编码就可 以获得较大的编码增益。基于上述指导思想，联合编码调制技术之后就有了突飞 猛进的发展。 19 8 2 年，gu n g e r b o e c k 提出了一种在不需要牺牲数据传输率或者说不需要额 外带宽的情况下就可以改善误码性能的技术网格编码调制技术( t c m ) ，这正 式标志着调制和信道编码相结合的技术的诞生。其核心思想是把信道编码和调制 结合在一起进行设计，在发送端，首先对信息序列实现( n + 1 ，n ) 的卷积编码，然后 进行卷积码到调制符号集的映射，调制符号集中有2 n + j 个信号；在接收端，收到 的信号解调后经解映射送入译码器进行维特比( v i t e r b i ) 译码。研究表明在a w g n 信道下，相对于独立设计的编码、调制系统，t c m 能够在既不增加信道带宽也不 重庆大学硕士学位论文1 绪论 降低信息传输速率的情况下，获得3 - 6 d b 的编码增益1 2 川。 1 9 9 2 年，z e h a v i 基于t c m 的思想提出了比特交织编码调制( b i c m ) 技术。 b i c m 技术与t c m 的区别是在编码器和调制器之间增加了比特交织器。b i c m 追 求的是汉明距离的最大化，虽然牺牲了一些欧氏距离特征，但码分集数的最大化 能使b i c m 技术在瑞利衰落信道下具有较高的鲁棒性幽j 。此外，b i c m 还可以看 作是级联码的一个特例，因而设计灵活性也比较高，可根据实际需求设计不同的 编码调制组合方案【2 9 】。后来，c a l r e 等人给出了关于b i c m 详细的理论分析和设计 准则，并指出g r a y 标识是最优映射方法【3 0 1 ，为今后研究比特交织编码调制系统提 供了很好的理论依据，目前，各种移动通信规范和标准以及长期规划中都采用了 该技术p 1 1 。 九十年代末期，x i a o d o n gl i 和j a r i t c e y 在看到了t u r b o 码有着能够接近 s h a n n o n 限的优良性能的基础上，研究了迭代反馈译码的译码方法，应用到b i c m 系统中，就是将b i c m 中译码器输出的似然比信息作为解调器的输入反馈到解调 器中，通过反馈迭代提高b i c m 系统的误码性能，称之为b i c m i d 技术。b i c m i d 是一种被设计应用于无线通信中的信道编译码方法，是一种编码、调制和迭代译 码相结合的技术。b i c m i d 既采纳了t c m 中编码和调制相结合的思想，又应用了 t u r b o 码的迭代译码原理，并且在结构设计上加入了比特交织器和软输入软输出 ( s i s o ，s o f ti n p u ts o f to u t ) 译码器【32 | ，采用了最大后验概率( m a p ) 算法与迭代译 码思想相结合的判决方式，最终实现次优译码【3 3 1 。 近几年，国内外对b i c m i d 技术不仅在理论上有了深入研究，而且已经在工 程应用与实现方面取得了很大的成就【3 4 1 ，尤其是在移动通信和多媒体通信中的应 用取得了很大的进展。由于g r a y 映射已经被证明是l d p c b i c m i d 系统的最佳映 射【35 | ，目前，对采用l d p c 码作为信道编码的b i c m i d 系统的优化主要考虑在格 雷映射的情况下，通过对l d p c 码编码进行优化从而改善系统的性能。对于不存 在g r a y 映射方式的系统，其星座映射方式的选择未开展研究。 同时，由于在l d p c b i c m i d 系统中格雷映射在迭代译码过程中所获得的迭 代反馈增益较少【3 引，如何提高迭代带来的系统增益是亟需解决的问题，所以星座 映射图、交织器和译码算法之间的联合优化设计，也是目前研究的一大热点【3 7 1 ， 联合l d p c 码的b i c m i d 技术是一种组合较好的编码调制技术，其作为一种新型 的编码调制技术，必将成为未来通信优化设计的一大热f - j 3 8 】。 1 3 本文的主要工作及章节安排 联合l d p c 编码的b i c m i d 系统能够有效提高编码增益，同时易于结合其他 先进技术，这些优点使得它在新一代通信系统中不断成长，并成为了十分具有竞 重庆大学硕士学位论文 1 绪论 争力的关键技术。本文针对l d p c b i c m i d 系统开展研究，探索不存在格雷映射 的系统星座映射方式的选择方法以及提高l d p c b i c m i d 系统解调器和译码器之 间的迭代译码增益的改进方法。论文组织结构安排如下： 第一章：介绍论文的研究背景和研究意义、综述l d p c b i c m i d 技术的国内 外研究现状和发展趋势，对论文的研究内容和组织结构进行简要说明。 第二章：总结l d p c 码的相关知识和b i c m i d 技术的基本理论，介绍l d p c 码的矩阵表示和二分图表示，分析l d p c 码的基本编译码算法流程，并将b i c m 和b i c m i d 系统性能与t c m 系统性能进行比较，为研究l d p c b i c m i d 系统奠 定技术基础。 第三章：针对l d p c b i c m i d 系统结构，用互信息理论研究星座映射方式对 l d p c b i c m i d 系统性能的影响，重点对不存在格雷( g r a y ) 映射的星形1 6 q a m 映射方式的设计进行设计，提出一种适合此系统的优化设计准则，并给出相应的 星座映射方式，仿真验证系统性能的优越性，从而为不存在g r a y 映射的 l d p c b i c m 。i d 系统提供了一种设计星座映射的准则。 第四章：根据第三章的理论分析，通过仿真研究l d p c 码码长、列重，交织， 迭代次数等参数对l d p c b i c m i d 系统性能的影响。 第五章：研究一种分析迭代译码收敛性能的有效方法一一外部信息传递 ( e x i t ) 图，从而可以准确、直观的描述迭代译码的过程，通过绘制各星座映射 方式随着信噪比的提高e x i t 图的变化曲线，验证了论文提出的星座映射准则的正 确性。另外，本文给出了一种改进结构以改善l d p c b i c m i d 系统外迭代译码增 益不大这一缺点，通过把外迭代、解交织及解调插入到l d p c 码自身的迭代译码 过程中来提高译码准确度和收敛速度。 第六章：全文研究工作总结，并对未来研究进行展望。 重庆大学硕士学位论文 2l d p c 码理论和b i c m i d 技术 2l d p c 码理论和b i c m i d 技术 2 1l d p c 码的基本原理 信道编码是通过在长度为七位的信息序列后面，以一定的规则增加长度为 即一尼位的校验码元，组成长度为，2 位的码字。如果校验码元的产生仅仅与本组的七 个信息位有关，与其他组的信息位均无关，译码时也仅仅利用本组的码元，其他 组码元均不参与，这种码称之为分组码，用( 船，尼) 表示分组码集合。我们主要关注 分组码中的线形分组码，线性分组码是分组码中最重要的一类码，l d p c 码就是一 类线性分组码，线性分组码定义如下【3 9 】：对于码长为玎，有g 个码字的分组码c ， 当且仅当其g 个码字构成的卯( g ) 上所有的t 1 维向量组成了向量空间刀的一个尼 维子空间时，称该分组码为l 疗，尼l 线性分组码，且cc 霹，后称为c 的维数。 2 1 1l d p c 码的矩阵表示 凹( 2 ) 域上的l d p c 码c 是一种( 胛，尼) 线性分组码，码长为，2 ，信息序列的长 度为k ，校验序列长为疗一七，可以用其校验矩阵日唯一定义。日是一个m , 的矩 阵，矩阵的每一行对应着一个校验方程，每一列对应着一位码字。校验矩阵h 的 行重是指每一行中非零元素的个数，列重为每一列中非零元素的个数。( 2 1 ) 式表 示一个5 1 0 的校验矩阵，同时给出了矩阵每一行所对应的校验方程，其中码字 c = c 1 ，c 2 ，c 3 ，c 4 ，c 5 ，c 6 ，c 7 ，c 8c 9 ，c l o ) c ，河茸爻己h c 1 = 0 。 h = c loc 2oc 3oc 4 = 0 c loc 5oc 6oc 7 = 0 c 2oc 5oc 8oc 9 = 0( 2 1 ) c 3oc 6oc 8oc 1 0 = 0 c 4oc 7oc 9oc l o = 0 根据行重与列重之间的关系，我们可以把l d p c 码分为两大类：规贝1 j ( r e g u l a r ) l d p c 码和非规贝, k j ( i r r e g u l a r ) l d p c 码【4 0 1 。如果校验矩阵的各行中非零元素的个数相 同，并且各列中非零元素的个数也是相同的，则称该l d p c 码为规则l d p c 码， 否则称之为非规则l d p c 码。本文的研究均是基于规则l d p c 码的，所以对非规 则l d p c 码不做过多说明。对于行重为p ，列重为1 ，码长为托的规则l d p c 码， 可简记为( 船，丫，p ) ，例如式( 2 1 ) 中的l d p c 码即可记为( 1 0 ，2 ，4 ) 。 之所以称之为l d p c 码，就是因为其校验矩阵h 是稀疏矩阵，即矩阵中1 的 个数远远小于0 的个数，或者说日矩阵的p 值和丫值与码长的比值都很小，这样才 能够构造出性能较高、复杂度较低的l d p c 码。 6 o o 0 1 l 0 0 1 o 1 o 0 1 1 0 o 1 o o 1 o 1 o l 0 o 1 1 0 0 1 o o o 1 1 o o 1 0 1 o 1 o 0 1 1 o 0 o 重庆大学硕士学位论文 2l d p c 码理论和b i c m i d 技术 2 1 2l d p c 码的二分图表示 l d p c 码除了可以用校验矩阵表示之外，还可以用双向的图模型来表示【4 ，二 分图( b i p a r t i t eg r a p h ) 4 2 】表示就是其中比较方便的一种，此方法能形象地表示l d p c 码的编译码特性，二分图也称t a n n e r 图。用g = ( y ，e ) 表示l d p c 码的t a n n e r 图， 其中v ：圪t jv 表示节点集合，对于维数为 ，2 的校验矩阵日，在图中，cm t a n n e r 变量节点集合用圪= ( 6 1 ，b 2 ，一b 。) 表示，对应日矩阵的各列，同时对应各个码字； 校验节点集合用圪= ( q ，c ，c 。) 表示，对应日矩阵的各行，同时对应各个校验方 程。e 圪杉表示校验节点和变量节点之间相连的边的集合。只有当校验矩阵h 的第f 行，第，列元素是非零的，相应的二分图中的第，个变量节点与第f 个校验节 点才会有一条边相连，即当h ，= 1 时，节点c ，和节点b ，之间有一条边相连，边 ( c ib ，) e 。与节点相连的边的个数称为节点的度，从某一节点出发经过几条边后 又回到此节点称为一个循环，其中所经过的边的个数称为循环长度，把最短的循 环长度称为图g 的周长。上- - d , 节中式( 2 1 ) 所示的校验矩阵用二分图表示，如图 2 1 所示，从图中可以看出，此l d p c 码具有1 0 个变量节点和5 个校验节点，每 个变量节点都有2 条边，每个校验节点都有4 条边。 校验节点 变量节点 b lb 2b 3b 4b 5b 6b 7b 8b 9b l o 图2 1 校验矩阵的二分图表示 f i g 2 1 t h et a n n e rg r a p ho fc h e c km a t r i x 图2 1 描述了校验矩阵为( 1 0 ，2 ，4 ) 的l d p c 码二分图，图中的方框和圆圈分 别用来表示校验节点和变量节点，可以看出，图中的每一个校验节点都有4 根连 线，对应的校验节点的度为4 ，而每一个变量节点都有2 根连线，所以这里对应的 变量节点的度为2 。二分图中的边代表了校验节点与变量节点之间的关系，只有当 某一个校验等式包含了此变量时，相应的变量节点才会通过边和校验节点之间进 行连接，进而可以清楚地得到，在l d p c 码的二分图中，边的条数与校验矩阵中l 重庆大学硕士学位论文 2l d p c 码理论和b i c m i d 技术 的个数是相等的。 通过分析二分图，我们可以得知l d p c 码的周长，即二分图中最小环的长度。 由于b p 译码算法的迭代过程就是通过二分图中的边，在校验节点和变量节点之 间交换信息，如果存在长度过短的环，就会导致从某个节点发出的信息很快又会 传回来，产生了自身信息的叠加，造成了信息的独立性被破坏，从而影响译码的 正确率【4 3 l 。 2 2l d p c 码的编码方法 2 2 1 基于高斯消去的编码 基于高斯消去的编码也就是直接编码方法，对于一个码长为n ，有k 位信息比 特o ，p ：，p 。) 的l d p c 码，其校验信息序列的长度为m = ，? 一k 。利用高斯消去法， 产生一个下三角矩阵，然后通过矩阵的初等行列变换，将校验矩阵h 化为式( 2 2 ) 的形式【4 4 】： h = 旧l i 肌。mj( 2 2 ) 其中，h 。为m k 的二元矩阵，脚。m 为m m 的单位矩阵。进一步可以得到生 成矩阵g 为： r 一1 g = k 妯叫j ( 2 3 ) 通过生成矩阵，根据公式c = u g 即可得到编码码字c 。 高斯消去法的l d p c 码编码方法所面临的一个主要问题就是其较高的编码复 杂度和编码延时，因为生成矩阵g 不是稀疏矩阵，从而破坏了原有奇偶校验矩阵h 的稀疏性，所以这样的编码方法计算复杂度比较高，编码复杂度与l d p c 码码长 的二次方成正比，尤其是在码长较长时，编码的复杂度更是大的惊人，对于编码 器的实现是非常不利的；此外，这种编码方法还存在另外一个问题就是：如果用 二分图来分析l d p c 码，是不需要考虑生成矩阵g 的，但要找到一个合适的算法 可以用校验矩阵日来产生生成矩阵g ，而这个校验矩阵很难找。 为了解决上述问题，于是t j r i c h a r d s o n 和r l u r b a n k e 在文献 4 5 1 中提出了一 种新的编码方法一基于近似下三角矩阵的编码方法，提出了利用校验矩阵的稀疏 性对校验矩阵进行一定的预处理之后，实现在线性时间内编码的有效算法，初步 解决了l d p c 码应用时面临的一个主要问题。此方法极大的降低了l d p c 码编码 的复杂度，使其仅具有线性复杂度，因此具有较高的实用价值，下面将对此方法 进行详细介绍。 2 2 2 基于近似下三角矩阵的编码 基于近似下三角矩阵的编码方法是通过对矩阵的行和列进行重排来保持矩阵 重庆大学硕士学位论文 2l d p c 码理论和b i c m i d 技术 的稀疏性，变换后的矩阵虽然不是一个完全的下三角形矩阵，但可以看成是一个 近似的下三角矩阵，如图2 2 所示，把稀疏矩阵日分成六块，l d p c 码编码输出的 前门一m 位即为发端发送的信息序列。将得到的近似下三角矩阵左乘一个矩阵做线 性变换得到一个新的矩阵用来递推校验比特，见式( 2 4 ) 。 卜n m 斗g 叫4 卜m g _ 0 a b 丁 cde 图2 2 近似下三角矩阵 f i g 2 2t h et r i a n g l em a t r i xo fa p p r o x i m a t i o n m g 士 g ( 一三一。项詈三三) = ( 一e 丁乞+ c e 丁乏+ 。吾) c 2 我们将编码码字记作x = ( j ，p 。，p ：) ，其中，s 代表发端信息比特序列，其长度 为n - m ，p ，和p ：合起来代表编码后所得到的校验序列，长度分别为g 和m g ， 利用h x r = 0 可得到下列方程，从而可以分别递推出两部分校验序列p l 和p ： - - e t 笠萨+ 卜( - e 型rb + d ) p ：0 ( 2 5 ) 1_ 1 彳+ c r 一 ： “) 观察上面两个方程，根据( 2 5 ) 式中的第二个方程可以首先求出p ，然后把p 。带 入( 2 5 ) 式中的第一个方程即可求出p ：，求出结果如下： p j = 一( - p e ；t ：- l b 丁+ 一。a ) _ s 1 t ( _ + e 印t j - 1 a ) + c 砖r ( 2 6 ) 【p ；= 一丁一印j ) 。 显然，采用这种编码算法可以大大降低编码复杂度。我们可以进一步分析出 计算p ，时的计算复杂度与9 2 成正比，同时由于矩阵a 、b 和t 都是稀疏矩阵，因 此计算p ：时的计算复杂度与力成正比。而且文献 4 6 】中已经证明了优化后的l d p c 码，g 的大小与万成正比。因此基于近似下三角矩阵的编码算法最终的计算复杂 9 下li m i上 重庆大学硕士学位论文 2l d p c 码理论和b i c m i d 技术 度是与码长n 成正比的，而采用高斯消去法的编码算法计算复杂度与n 2 成正比。 2 3l d p c 码的译码算法 推动l d p c 码实用化的原因不仅仅在于其优异的性能，还在于其低复杂度的 译码，而且可实现全并行译码，非常有利于硬件实现。l d p c 码的译码方法一般可 以分为基于硬判决的译码和基于软判决的译码两大类。基于硬判决的译码算法虽 然运算