（交通信息工程及控制专业论文）低密度奇偶校验码构造、并行级联与译码器设计的研究.pdf

中文摘要 中文摘要 摘要：低密度奇偶校验( l o w d e n s i t yp a r i t y c h e c k ，l d p c ) 码是一种具有逼近 s h a n n o n 限性能的优秀纠错编码，在无线通信、卫星通信、数字广播和磁盘存储等 诸多领域得到了广泛地应用。本论文探讨了l d p c 码在后3 代( b 3 g ) 移动通信 系统和基于通信的列车控制( c b t c ) 系统中的应用，针对b 3 g 和c b t c 系统在 差错平底、编译码复杂度及硬件复杂度等方面提出的要求，对l d p c 码的构造、 并行级联与译码器设计进行了研究。 第三章提出了两种低差错平底l d p c 码构造法，即基于环多项式的渐进边增 长( p e g p ) 构造法和基于加权环多项式的渐进边增长( p e g w p ) 构造法。p e g p 构造法不仅实现了较大的围长，而且减少了短环的数量；p e g w p 构造法还尽可能 地避免短环通过节点度较低的比特节点。仿真结果表明，p e g p 和p e g w p 构造法 明显地改善了码字的性能，降低了差错平底。 第四章提出了快速编码l d p c 码的构造方法，直接构造具有近似下三角校验 矩阵的l d p c 码。该码不仅具有线性编码复杂度，且编码前无需进行行列重排， 而译码性能则几乎没有恶化。 第五章提出了一种新的级联码一一并行交织级联l d p c ( p i c l d p c ) 码。 p i c l d p c 码将长码字的译码分解为若干个短码字的译码，利用交织器实现了各短 码字之间的信息交换，以较低的译码复杂度和存储器占用，实现了较好的性能。 第六章对l d p c 和p i c l d p c 译码器的设计进行了研究。针对串行结构译码器 译码速度较低的不足，提出了两种改进的译码时序设计方案，即基于更新群的时 序设计方案和基于分散式校验的时序设计方案。两种改进设计方案不仅大幅度地 提高了译码速度，而且改善了译码性能，使得采用低成本f p g a 芯片实现中、高 速译码成为现实。 关键词：低密度奇偶校验码、环、线性编码复杂度、缴联玛、现场可编程门阵列 分类号：t n 9 2 9 5 a b s t r a c t 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 k ( l d p c ) c o d e sa r ee x c e l l e n te r r o r - c o r r e c t i n gc o d e s 、v i t h p e r f o r m a n c ec l o s et ot h es h a n n o ni i m i t , w i d e l ya p p l i e di nm a n yf i e l d s s u c ha sw i r e l e s s c o m m u n i c a t i o n ，s a t e l l i t ec o m m u n i c a t i o n ，d i g i t a lb r o a d c a s t i n ga n dm a g n e t i cr e c o r d e r s ， t h i sd i s s e r t a t i o ne x p l o r e st h ea p p l i c a t i o n so fl d p cc o d e si nb e y o n d3 g ( b 3 g ) s y s t e m s a n dc o m m u n i c a t i o n sb a s e dt r a i nc o n t r o l ( c b t c ) s y s t e m t oa d d r e s sc h a l l e n g e so fe r r o r f l o o r s ，e n c o d i n ga n dd e c o d i n gc o m p l e x i t ya n dh a r d w a r ec o m p l e x i t nt h ec o n s t r u c t i o n ， p a r a l l e lc o n c a t e n a t i o na n dd e c o d e rd e s i g no fl d p cc o d e sa r ei n v e s t i g a t e d c h a p t e r3p r e s e n t st w oc o n s t r u c t i o nm e t h o d so fl d p cc o d e sw i t hi o we r r o rf l o o r s ， c a l l e dp r o g r e s s i v ee d g e g r o w t hc o n s t r u c t i o nb a s e do np o l y n o m i a lo fc y c l e ( p e g p ) a n d p r o g r e s s i v ee d g e g r o w t hc o n s t r u c t i o nb a s e do nw e i g h e dp o l y n o m i a lo f c y c l e ( p e g w p ) w i t ht h ea i do fp o l y n o m i a lo fc y c l e ，p e g pc o n s t r u c t i o nm a x i m i z e st h eg i r t ha n d m l n i m i z e st h en u m b e ro fs h o r tc y c l e s b e s i d e s p e g w pc o n s t r u c t i o na v o i d ss h o r t c y c l e sp a s s i n gt h r o u g hv a r i a b l en o d e sw i t hl o wd e g r e e s i m u l a t i o nr e s u l t ss h o wt h a t p e g pa n dp e g w pc o n s t r u c t i o n si m p r o v et h ep e r f o r m a n c ea n dl o w e re r r o rf l o o r so f l d p cc o d e ss i g n i f i c a n t l y i nc h a p t e r4 ，ah o v e lc o n s t r u c t i o nm e t h o df o rl d p cc o d e sw i t hf a s te n c o d i n gi s p r o p o s e d a na p p r o x i m a t el o w e rt r i a n g u l a rc h e c km a t r i x i sc o n s t r u c t e db ym o d i f i e d p e g pm e t h o d s i m u l a t i o nr e s u l t ss h o wt h a tt h ec o n s t r u c t e dc o d e sh a v el i n e a re n c o d i n g c o m p l e x i t ya n dd o n tn e e dp e r f o r m i n gr o wa n dc o l u m np e r m u t a t i o n sb e f o r ee n c o d i n g w i t hl i t t l ep e r f o r m a n c ed e g r a d a t i o n i nc h a p t e r5 ，an e wc l a s so fp a r a l l e lc o n c a t e n a t e dc o d e sb u i i tf r o ml d p cc o d e s ， c a l l e dp a r a l l e li n t e r l e a v e dc o n c a t e n a t e dl d p c ( p i c l d p c ) c o d e si si n t r o d u c e d p i c l d p cc o d e sb r e a kt h ef a i r l yd e c o d i n gc o m p l e x i t yo fl o n gc o d ei n t ot h o s eo f s e v e r a ls h o r t e rc o d e s ，w h i l em a i n t a i n i n gt h ei n f o r m a t i o ne x c h a n g eb e t w e e nt h e m i n t h i ss c h e m e p i c ，l d p cc o d e sc a na c h i e v eg o o dp e r f o r m a n c e 谢t hl o w e rd e c o d i n g c o m p l e x i t ya n dr e d u c e dm e m o r yr e q u i r e m e n t s c h a p t e r6d i s c u s s e st h ed e s i g na n di m p l e m e n t a t i o no fl d p ca n dp i c l d p c d e c o d e r s t w om o d i f i e ds c h e d u l e s ，t h es c h e d u l eb a s e do nu p d a t i n gg r o u p sa n dt h e s c h e d u l eb a s e do nd i s t r i b u t e dc h e c k s ，a r ep r o p o s e d s i m u l a t i o nr e s u l t ss h o wt h a tt h e t w os c h e d u l e sc a ne n h a n c et h et h r o u g h p u to fd e c o d e ra n di m p r o v et h ep e r f o r m a n c e t h ep r o p o s e dd e c o d e rc a na c h i e v em e d i u mt oh i g ht h r o u g h p u tu s i n gl o w - c o s tf p g a n 北京交通大学博七学何论文 d e v i c e k e y w o r d s ：l o w - d e n s i t yp a r i t y c h e e k ( l d p c ) c o d e s ，c y c l e s ，l i n e a re n c o d i n g c o m p l e x i t y , c o n c a t e n a t e dc o d e s ，f i e l d - p r o g r a m m a b l eg a t ea r r a y ( f p g a ) c l a s s n o ：t n 9 2 9 5 1 1 1 致谢 光阴荏苒，岁月如梭，在博士论文即将完成之际，我要在此对所有给予我指导、 支持、鼓励和帮助的人表示感谢。 首先要衷心感谢导师谈振辉教授和师母金晓军高工，感谢他们为我提供了良好 的研究条件，感谢他们给予我的悉心指导和言传身教，引领我走上科学研究的道 路。导师谈振辉教授渊博的知识、严谨的治学态度、敏锐的学术洞察力、对研究 工作高度热情，都必将使我受益终身；他强烈的民族使命感，严以律己，宽以待 人的做人原则，平易近人的待人风格，更是我永远学习的楷模。 感谢姚冬节教授在研究上给予我的指导，帮助我克服了一个又一个困难。姚老 师扎实的理论功底、丰富的实践经验、对事业高度的负责的精神都给我留下了深 刻的印象。 感谢朱刚、陶成、闻映红、孙听、李旭等各位老师给予的指导、关心和帮助， 使我能够顺利地完成博士论文。 陈霞博士对论文提出了许多宝贵的意见，她对理论精妙的分析，透彻的见解都 使我受益匪浅。 特别感谢田野、王欣、李常茗三位博士，与他们讨论和交流，扩展了我的思路， 给了我很多启发和灵感，本文的许多成果是我们共同努力的结晶。感谢我的室友 李磊博士，他面对困境时乐观豁达的心态，创新性的思维方法，都使我受益良多。 感谢闰岩硕士在无线衰落信道研究给予的帮助，感谢吴祖辉硕士和秦文丽硕士 对论文进行的细心校对。在论文工作期间，还得到了陈月云博士、唐睿博士、张 金宝博士、张令文博士、陈洄硕士、郑姗姗硕士、李文亮硕士、逯春蕊硕士等的 大力支持，在此表示衷心感湔。 最后我要对我的父母表示最深的谢意。感谢他们二十多年来的扰育和培养，他 们的体谅与包容，理解和支持是我动力的源泉。 最后再次向所有关心、帮助和支持我的老师、同学、亲人和朋友表示诚挚的谢 意。 第一章绪论 1 1 研究背景 第一章绪论 自上世纪8 0 年代以来，移动通信技术得到了突飞猛进的发展，在不到三十年 的时间旱，已经经历了三个主要的发展阶段，即第一代模拟蜂窝移动通信系统， 第二代数字蜂窝移动通信( 2 g ) 系统及2 5 代的g p r s 系统，和正在进入大规模 商用化应用的第三代移动通信( 3 g ) 系统。3 g 系统较2 g 系统在数掘速率和系统 容量上都有了明显的提高，可以支持数据、语音、视频和图像等多媒体业务】。然 而3 g 系统的频谱利用率仍然较低，2 m b p s 的最高数据速率无法满足用户对高速、 宽带数据传输业务不断增长的需求。而且3 g 系统没有全球统一的标准，w c d m a 、 c d m a 2 0 0 0 和t d s c d m a 三大标准之间无法兼容。因此，世界各国在推动3 g 系 统商用化的同时，已经开始了后3 g ( b e y o n d3 g ，b 3 g ) 也称4 g 通信系统的研究 工作。 b 3 g 系统具有如下主要特点：更高的频谱效率、更高的数据速率( 1 0 0 m b p s 1 g b p s ) 、更高的传输可靠性、支持高速移动接收( 2 5 0 k i n h ) 、更好的兼容性和灵 活性、全i p 的核心网、支持多种业务等【2 4 1 。 然而，移动通信的环境非常复杂多变，不仅存在多径传播引起的接收信号幅 度的剧烈变化，即多径衰落，而且当移动台处于高速运动时，多普勒频移和扩展 的增大会造成信道的频域弥散，导致时间选择性衰落。为了实现高速移动环境下 高速数据的高可靠性传输，b 3 g 系统在物理层和链路层采用了一系列先进技术， 包括多载波技术、m i m o 技术、逼近s h a n n o n 限的信道编码技术和链路自适应技 术等。 此外，随着我国铁路进入前所未有的快速发展时期，高速铁路的建设正如火 如茶的展开，传统的铁路信号系统必将逐步让位于基于通信的列车控制 ( c o m m u n i c a t i o n sb a s e dt r a i nc o n t r o l ，c b t c ) 系统1 6 - 7 1 。车地双向无线通信是c b t c 系统的基础，其链路可靠性是保障列车运行安全的关键。 因此研究满足b 3 g 和c b t c 系统可靠性要求的信道编码技术，抢占技术发展的 制高点，形成具有自主知识产权的理论体系，对发展我国的b 3 g 和c b t c 系统，增 北京交通人学博十学侍论文 强国际竞争力都具有十分重大的理论价值和现实意义。 b 3 g 和c b t c 系统对信道编码技术的主要要求有： 1 具有较强的纠错能力和较低的差错平底( e r r o rf l o o r ) 。 2 为保证数据的可靠传输，通常采用前向纠错( f e c ) 与检错重发( a r q ) 相结 合的差错控制策略，即混合纠错( h e c ) 方式。因此要求信道编码不仅要具有 较强的纠错能力，还必须具有很强的检错能力。 3 能够适应各种不同的信道，始终保持较好的性能。 4 具有较低的编译码时延，实时性较好。 5 编译码器易于实现，硬件成本和功耗较低。 1 2 信道编码技术的发展与现状 通信的目的是将信息由信源可靠、有效、安全地传递到信宿。然而由于信道 不可避免地存在各种噪声和干扰，接收的信息可能发生错误，降低了传输的可靠 性。1 9 4 8 年，信息论的奠基人c e ，s h a n n o n 在具有单程碑意义的论文通信的数 学理论( 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 ) 1 8 1 中指出，采用信道编码可以 实现信息有效且可靠地传输，并提出了著名的信道编码定理：对于一个有扰信道， 如果信息传输速率r 不大于信道容量c ，就必然存在某种信道编码方法，使得译 码差错概率随码长增加趋近于任意小。 信道编码定理只给出了好码的存在性证明，并没有给出如何构造好码的具体 方法。因此，寻找逼近s h a n n o n 容量限的好码一直是信道编码研究的目标。 1 2 1 早期的信道编码研究 1 9 5 0 年，h a m m i n g 提出了一种以奇偶校验为基础的线性分组码，即汉明码【9 1 。 汉明码及其类码( 如扩展汉明码和缩短汉明码) 编译码电路简单，易于实现，与 当时的技术条件相适合，应用十分广泛。随着技术的进步，较低的纠错能力成为 了制约汉明码发展的关键因素。m i c h e l s o n 和f m e m a n 提出了采用v i t e r b i 算法【1 0 1 ， a s h i k h m i n 和l i t s y n 提出采用最大后验概率( m a x i m u ma p o s t e r i o r i ，m a p ) 算法l l l j 进行汉明码的译码，以取代传统的硬判决译码，提高了纠错性能。在此之后，研 2 第一章绪论 究人员又相继提出了一系列信道编码，如m j e g o l a y 于1 9 5 4 年发现了格雷 ( g o l a y ) 码1 1 2 j ，同年i s r e e d 和d e m u l l e r 发现了r e e d m u l l e r 码( 简称r m 码) 。 1 9 5 4 年e l i a s 提出的乘积码 t 3 - 1 4 蛆常被认为是最早的级联码。乘积码由一个多 维码矩阵组成，矩阵中的每 亍和每列均为一个线性分组码字。译码时，先按行( 或 列) 进行译码，再利用译码得到的外信息进行列( 或行) 的译码，如此进行迭代。 乘积码具有怠好的抗突发错误的能力，而且可以进行并行译码，译码时延较小， 差错平底较低。1 9 6 6 年f o m e y 提出了级联码【l5 1 ，通过将长码字的译码分解为若干 个短码字的译码，从而以较低的译码复杂度获得了较好的纠错性能。 循环码作为线性分组码的一个重要子类，具有严密的代数学理论，研究也最 为成熟 1 6 - 1 7 ，除具有线性码的一般性质( 即封闭性) 外，还具有循环性，即循环 码的任何一个许用码字进行循环移位后，得到的仍是该循环码的一个许用码字。 循环码可以按照臻求的纠错能力进行构造，而且译码算法简单，编译码器硬件实 现难度低。h h o c q u e n g h e m 于1 9 5 9 年， r c b o s e 和d ，k r a y c h a u d h u r i 于1 9 6 0 年分别提出了一种可以纠正多个错误的循环码，即b c h ( b o s e - c h a u d h u r i h o c q u e n g h e m ) 码 1 8 - 1 9 】。b c h 码是循环码的一个大类，具有结 构简单、纠错能力强、编译码复杂度低、理论分析容易等特点，无论是在理论研 究还是实际应用中部有着十分重要的地位。i s ，r e e d 和g s o l o m o n 构造了一类具有 较强纠镨能力的多进制b c h 码，即罗德一所罗门码( r e e d s o l o m o nc o d e s ) ，简称 为r s 码【2 0 】。r s 码不仅可以纠i f 随机错误，而且可以纠正突发错误。 卷积码最早由e l i a s 提出【2 ”。卷积编码器的输出序列不仅取决于当前的输入比 特，而且与之前若干个输入比特有关。卷积码的译码算法主要有序列译码算法1 2 2 】、 f a n o 译码算法【2 3 】和v i t e r b i 译码算法。其中v i t e r b i 译码算法是序列整体似然度 最大意义上的最佳译码算法，得到了最为广泛的采用。卷积码具有与线性分组码 相当的性能，但理论工具较为缺乏，好码在很大程度上依赖计算机搜索。 1 2 2t u r b o 码与l d p c 码 自1 9 4 8 年s h a n n o n 信道编码定理提出以来，经过几十年的努力，研究人员取 得了一系列的成果，但距s h a n n o n 限始终有相当的距离。有的研究人员甚至认为， 以可承受的译码复杂度无法实现逼近s h a n n o n 限的性能。壹到1 9 9 3 年，b e r r o u 等 北京交通人学博十：学传论文 人将卷积码与并行级联码相结合，提出了并行级联卷积码( p a r a l l e lc o n c a t e n a t e d c o n v o l u t i o n a lc o d e s ，p c c c ) 2 5 - 2 6 1 ，即t u r b o 码。 t u r b o 码采用随机交织器将两个卷积码编码器并行级联，译码器采用软输入软 输出( s o f t - i ns o f t - o u t ，s l s o ) 的迭代译码算法( 如b c j r 算法【2 7 】，s o v a 算法 2 8 - 2 9 1 ) ， 利用两个s i s o 成员译码器之间的信息传递，不断提高译码的可靠度，以可接受的 译码复杂度实现了逼近s h a n n o n 限的译码性能。仿真结果显示，i 2 码率，交织器 长度为6 5 5 3 6 比特的t u r b o 码，在进行1 8 次译码迭代后，距s h a n n o n 限仅o 7 d b 。 t u r b o 码的发现是信道编码领域最重大的研究进展之一，立即轰动了整个编码界， 并在3 g 等系统中得到了应用。 t u r b o 码的成功，极大地鼓舞了研究人员的信心。在对t u r b o 原理的研究过程 中，又相继取得了一系列成果，如t u r b o 乘积码1 3 口j ( t u r b op r o d u c tc o d e ，t p c ) 、t u r b o 空时码口1 - 3 2 1 ，此外，t u r b o 原理还广泛地应用于编码调制( 如t u r b o t c m ) d 3 - 3 4 】、 均衡【3 5 】、多用户检钡, 1 , 3 6 - 3 7 1 等诸多领域。而最为重大的成果当属m a c k a y d s 、n e a l 和s p i e l m a n 等人【3 9 l 发现g a u a g e r 于1 9 6 2 提出的低密度奇偶校验( 1 0 w d e n s i t y p a r i t y ，c h e c k ，l d p c ) 码同样具有逼近s h a n n o n 限的性能。1 9 6 2 年o a l l a g e r 虽然 已经证明l d p c 码是一种具有渐进特性的好码，但受当时技术水平的制约，理论 研究和实际应用难以进行，在之后的三十多年间未能得到足够的重视。随着l d p c 码的重新提出和研究的深入，研究人员发现l d p c 码在二进制对称信道( b i n a r y s y m m e t r i cc h a n n e l ，b s c ) 、加性高斯白噪声( a d d i t i v e w h i t e g a u s s i a n n o i s e ，a w g n ) 信道、删除信道( e r a s u r ec h a n n e l ) 、衰落信道等各种信道下均具有优异的性能。 s a c y o u n gc h u n g 等人对1 2 码率，码长1 07 比特的l d p c 码进行了仿真，实现了 距s h a n n o n 限0 0 0 4 5 d b 的优异性能【4 “。l d p c 码是继t u r b o 码之后信道编码领域 取得的又一重大成果，在很多方面甚至要超过了t u r b o 码，其主要优点有： 1 l d p c 码译码复杂度低于t u r b o 译码算法，而且可以进行并行处理，实现高速译 码，译码实时性较好1 4 2 1 。 2 l d p c 码具有更低的差错平底1 4 3 - 4 4 1 ，适用于对误码率要求苛刻的应用。 3 l d p c 码不仅具有较强的纠错能力，同时还具有极强的检错能力，而t u r b o 码则 无检错能力。对于中等以上长度的l d p c 码，可认为发尘不可检测错误的概率 为零 4 5 1 。因此，在混合纠错( h e c ) 系统中，无需要附加检错编码( 如c r c ) 。 4 第一章绪论 4 l d p c 码具有良好的内交织特性，抗衰落能力较好【4 6 】。 5 l d p c 码的码长、码率和节点度分布等参数可以根据实际情况灵活设置。 6 描述简单，对严格的理论分析具有可验证性。 然而l d p c 码也存在不足： 】编码复杂度较大，虽然可以通过对校验矩阵进行一定的处理后可以实现近似的 线性译码复杂度，但仍明显大于t u r b o 码。 2 编译码器存储校验矩阵( 或其相关矩阵) 将占用较大的存储空间。 3 当采用并行译码结构时，虽然可以获得极高的译码速度，但译码器的硬件复杂 度也相当大。 1 3 论文的章节内容与主要贡献 经过对各种信道编码方案的分析和比较，我们认为以l d p c 码作为b 3 g 和 c b t c 系统的信道编码最为合适，但l d p c 码也并非尽善尽美，仍有许多问题值得 研究。本论文结合b 3 g 和c b t c 系统的特点，重点研究了l d p c 码的构造、并行 级联、译码器的设计与实现。具体内容安排如下： 第二章介绍了l d p c 码的基本原理，包括l d p c 码的定义、图理论与几种经 典的译码算法，并对影响l d p c 码译码性能的因素进行了分析，特别是分析了环 对性能的影响。 第三章提出了两种低差错平底l d p c 码的构造方法，即基于环多项式的渐进 边增长( p r o g r e s s i v ee d g e g r o w t hb a s e d o np o l y n o m i a lo f c y c l e ，p e g p ) 构造法和基 于加权环多项式的渐进边增长( p r o g r e s s i v ee d g e - g r o w t hb a s e d0 1 1w e i g h e d p o l y n o m i a lo f c y c l e p e g w p ) 构造法。p e g p 和p e g w p 构造法优化了码字设计， 不仅实现了较大的围长，而且尽可能地减少了最短环的数量并且避免短环通过节 点度较低的比特节点，明显地改善了码字的性能，降低了差错平底。 第四章将码字的构造与编码相结合，提出了一种快速编码l d p c 码的构造方 法。该码在p e g p 构造法的基础上，直接构造具有近似下三角校验矩阵的l d p c 码。该码具有线性编码复杂度，编码前无需进行行列重排，译码性能则几乎没有 恶化。 ， 第五章提出一种新的级联码并行交织级联l d p c ( p a r a l l e li n t e r l e a v e d 北京交通人学| 尊+ 学位论文 c o n c a t e n a t e dl d p c ，p i c l d p c ) 码，并介绍了p i c l d p c 的构造、编码与基于迭 代的译码算法。p i c l d p c 以较低的译码复杂度和译码器存储量占用，实现了接近 l d p c 码的性能，降低了长码的应用难度。 第六章对l d p c 和p i c l d p c 译码器的设计与实现进行了研究。针对串行结 构译码器译码速度较低的不足，提出了两种改进的译码时序设计方案，即基于更 新群的时序设计方案和基于分散式校验的时序设计方案。两种改进方案缩短迭代 时间和加快译码收敛速度，大幅度地提高了译码速度，而且改善了译码性能，使 得采用低成本f p g a 芯片实现中、高速译码成为现实。 第七章对全文进行总结，并对下一步研究工作予以展望。 第一二章l d p c 码基础理论 第二章l d p c 码基础理论 自1 9 9 6 年m a c k a y 和s p l e m a n 重掰发现l d p c 码以来，l d p c 码以其优异的 性能和较为简单的译码器结构，引起了广泛的关注和研究，成为信道编码领域的 热点。研究人员在l d p c 码的图理论、构造方法、编译码算法等领域展开了深入 的研究，取得了丰硕的研究成果。本章将简要介绍l d p c 码的定义、图理论与几 种经典的译码算法，并对影响l d p c 码译码性能的因素进行了分析，特别是分析 了环对性能的影响。 2 1l d p c 码的图理论 l d p c 码的校验矩阵具有稀疏的特性，即低密度。如图2 1 所示的校验矩阵中， 每行表示一个校验式，每列表示一个码元比特。 日= 1 0 0 01 00010 01 lo0 001 0 lo 01o ol01 0 000lol0 0l0 001l 000 0l o o1l0 0 0 10 0 01 0 01o 1 01 0 0 0l0 o 0l00l00 1l0 0 01o olo 010l0 0 10 010 0l0 0l0 0 陶2 1 具有稀疏特性的校验矩阵 f i g u r e2 ias p a r s ep a r i t y - c h e c km a t r i x 假设工= ( 而，恐，_ ：) 为该l d p c 码的一个许用码字，则其必然满足式( 2 1 ) 所示的校验方程组， 7 北京交通人学搏十学位论文 x 1 0 墨( 9 x 9 0 x 1 2 = 0 x l0 算6 0 o x i l = 0 屯0 o 两。一l = 0 墨0 0 x 7 0 一2 = 0 x 3 0 矗0 恐。五2 = 0 ( 2 ，1 ) x 3 ( g x 5 0 而。五l = 0 x 3 ( 9 x 6 0 x 9 0 五o = 0 x 2 0 墨( g x s ( g x l o = 0 一( 9 x 4 ( 9 x 7 0 而i = 0 l d p c 码也可以表示为图的形式，因为最早由t a n n e r 提出，因此也称这种图 为t a n n e r 图【4 7 】。此后，w i b e r g 将隐含节点( h i d d e n s t a t ev a r i a b l e ) 引入t a n n e r 图， 扩展了图的应用范围【4 甜。 酗2 2 l d p c 码的t a n n e r 图 f i g u r e2 2t a n n e rg r a p hf o ral d p cc o d e 作为描述l d p c 码最为重要的数学模型，t a n n e r 图由校验节点、比特节点和 连接校验节点和比特节点的边组成。图2 2 为图2 1 所示的l d p c 码所对应的t a n n e r 图。t a n n e r 图中上方的是校验节点，i = 1 - - 聊，分别对应l d p c 码中的每个校验式， 下方的为比特节点( 也称可变节点) j ，歹= 1 ，与码字中的每个比特相对应。 连接校验节点和比特节点之自j 的边表示该比特参与了该校验式，与校验矩阵中的 非零元素相对应。由此可知，t a n n e r 图与校验矩阵之间具有确定的关系。与比特 节点相连的边数( 即校验矩阵的列重) 被称为比特节点度西，同理，与校验节点 相连接的边数( 即校验矩阵的行重) 称为该校验节点的节点度反。图2 2 中，各比 第二章l d p c 码基础理论 特节点的节点度均为3 ，各校验节点的节点度均为4 ，这样的l d p c 码被称为正则 ( r e g u l a r ) l d p c 码，可表示为( ，巩，以) ；对于比特节点度和校验节点度不完 全相同的码字，则称为非正则( i r r e g u l a r ) l d p c 码。非币则l d p c 码通常采用比 特节点度分布函数五( 工) 和校验节点度的分布函数p ( x ) 予以描述，分别为 丑( 石) = 乃x 一 ( 2 2 ) p ( x ) = 乃x 川 ( 2 3 ) 其中，乃表示与节点度为的比特节点相连的边在总边数中所占比率，而p ；表 示与节点度为的校验节点相连的边在总边数中所占比率。因此，节点度为，的比 特节点的个数为 州护嵩 节点度为j 的校验节点的个数为 f ( 肛丽m p 7 面j 而码字的平均列重( m e a nc o l u m nw e i g h ，m c w ) 为 m c w 2 专丢以( 聆) m c w 是l d p c 码的一个重要参数，对码字的性能，特别是差错平底有相当大 的影响。显然，正则l d p c 码可以认为是非正则l d p c 码的一个特例，即 五( j ) = x 咖一，p ( x ) = x 出一。 m g l u b y 等人指出【5 0 - 5 1 ，由于波浪效应的存在，非正则码的性能要优于码率 和码长相同的正则码，而且还可以方便地实现不等错误保护 5 2 - 5 3 1 。t j r i c h a r d s o n 等人提出了搜索非正则码最佳的节点度分布的局部优化和全局优化方法 5 4 - 5 5 1 ，从 而可以构造具有逼近s l a n n o n 限能力的码字。然而非正则码编译码器的实现难度要 略大于正则码。 在t a n n e r 图中，由某个比特节点( 或校验节点) 出发，经过若干不重复的边 和节点，最终回到该节点，就构成了一个环( c y c l e ) 。图2 2 用粗实线标示了一个 9 北京交通人学 枣十学俺论文 环，该环包含6 条边，即该环的长度为6 。t a n n e r 图为二分图，即只有校验节点与 比特节点之间有边，所以环的长度必为偶数。 2 2l d p c 码的译码 l d p c 的译码算法可以分为硬判决译码算法和软判决译码算法两类。g a l l a g e r 提出的比特翻转( b i t f l i p p i n g ，b f ) 算法扎6 8 1 属于硬判决译码算法，其计算 复杂度很低，但译码性能较差。软判决译码算法的性能虽然明显好于硬判决译码 算法，但译码复杂度较大。如何在性能和复杂度之问取得良好的折中，是译码算 法研究的重要目标。 r ，j m c e l i e c e _ 平l a d j c m a c k a y 等人发现广泛应用于人工智能( a r t i f i c i a l i n t e l l i g e n c e ，a i ) 领域的j p e a r l 信度传播( b e l i e f p r o p a g a t i o n ，b p ) 理论，可以用 来解释t u r b o 码具有逼近s h a n n o n 限的优异性能的原因【6 2 - 6 3 1 ，n w i b e r g 针对基于图的 码字也提出了类似的译码算法1 。d b u r s h t e i n 和g m i l l e r 和j 用图理论证明了当 l d p c 码字足够长时，只要消息传递算法能够纠正足够多的错误，就一定可以纠正 所有错误【6 5 】。 在软判决译码算法中，对数域b p 算法( 即和积算法) ，以对数似然比( 1 0 9 l i k e l i h o o dr a t i o ，l l r ) 代替概率信息，不仅具有优异的性能，而且简化了运算， 从而得到了广泛的研究和应用。下面简要介绍对数域b p 算法。 假定c = ( q ，龟，知) 为l d p c 码的一个许用码字，经过b p s k 调制和a w g n 信道传输，信道噪声方差盯2 = 0 2 ( 0 为双边噪声功率谱密度) ，在接收端的接 收序列为y = ( y l 儿，y 。) 。( 珊) 表示与校验节点m 相连的比特节点的集合， m ( n ) 则表示与比特节点厅相连的校验节点的集合。( m ) ，z 表示从n ( m ) 中删除n ， 同理m ( 月) 卅表示从m ( n ) 中删除m 。假定校验节点聊传递给比特节点n 的l l r 为r ( m ，功，而比特节点刀传递给校验节点胁的l l r 为q ( m ，功。 b p 算法的步骤如下： 步骤1 初始化 对每一个脚和聍， 第一二章l d p c 码基础理论 q ( 撇，n ) = t ( n ) 。争只 ( 2 4 ) 其中，t ( 胛) 为比特n 的信道l l r 。 步骤2 迭代 步骤2 1 校验节点更新 对每个校验节点坍和甩n ( m ) ，耍新r ( 肌，i , 1 ) r ( m ，”) = 一丌s g n ( g ( 所，疗) ) 驴i 西( 9 ( m ，舟) ) i ( 2 5 ) 月e 【j ) 、月、n t ( 月，) 、h， 鼽灿4 鼬c 扯n i 募l 步骤2 2 比特节点更新 对每个比特节点n 和m m ( n ) ，更新q ( m ，”) g ( 垅， ) = l c ( 一) + r ( m ，珂) ( 2 6 ) 对每个比特节点n ，更新其后验l l r ， 上丁( 船) = t ( 盯) + 月( 肼，甩) ( 2 7 ) 步骤3 尝试译码 根据各比特节点的后验l l r 进行硬判决，生成码字矢量= 【o 。】 ：i 0 矿工丁( m ) 0 铲1 1 矿l t ( 。疗j o 步骤4 校验 如果肼7 = 0 7 ，则译码成功，结束迭代；否则，进一步判断是否已达到允许的最 大迭代次数，如尚未到达则回到步骤2 ，开始下一轮迭代，否则宣布译码失败，结 束译码。下面以图2 3 为图2 1 所定义的l d p c 码中的比特节点x i 在迭代译码中的 信息传递示意图。由图可见，比特节点玉虽然形式上只从与之相连的校验节点c 1 ， 岛和c 9 获得信息，但实际上随着迭代的进行，借助校验节点c ，c 2 和c 9 ，它可以间 接地从与之不相连的节点( 如c ) 处获得信息。对于全连通的t a n n e r 图，只要迭 代次数足够多，葺理论上可以从任意的校验节点获得信息，从而大大提高了译码 北京交通人学博士学位论文 的性能。从另一个角度而言，随着迭代的进行，各节点的信息将在整个t a n n e r 图 中进行传播，这也是b p 算法得名的原因。 l 璺| 2 3 信息传递示意剀 f i g u r e2 3i l l u s t r a t i o no f m e s s a g ep a s s i n g b p 算法具有优异的纠错性能，但其校验节点更新，如式( 2 5 ) 所示，包含大 量的指数和对数运算，计算较为复杂，也不利于硬件实现。m f o s s o f i e r 等x i 7 0 7 2 】 提出f f 9 u m p ( u n i f o r m l ym o s tp o w e r f u l ) b p b a s e d 算法和j c h e n 芹t m f o s s o r i e r 黜 的归化b p ( n o r m a l i z e db p b a s e d ) 算法与偏移b p ( o f f s e tb p b a s e d ) 算法硎，简 化了校验节点更新运算，在性能与复杂度之间取得了一个良好的折中。 2 3l d p c 码性能分析 l d p c 码是一种线性分组码，最小距离是其性能的决定因素，然而由于l d p c 码通常较长，计算最小距离的准确值十分困难。g a l l a g e r 将所有的( ，西，面) l d p c 码视为一个整体，即码字集合( e n s e m b l e ) ，进行研究。码字集中各码字的 1 2 第二章l d p c 码基础理论 最小距离是一个随机变量，具有如图2 4 所示的概率分靠函数。对于d 。3 d c d 。 的l d p c 码，当码长趋于无穷大时，最小距离的概率分布函数将逼近阶跃函数， 阶跃点为颤( 甄为最小距离与码长之比) 。因此对于码长较长的l d p c 码， 可以认为其最小距离至少为 ，氏，而对于中短l d p c 码，采用该方法计算最小距 离就不太准确了。 图2 4 最小距离分布函数 f i g u r e2 4t h ec u m u l a t i v ed i s t r i b u t i o nf u n c t i o no f m i n i m u md i s t a n c e b p 译码算法成立必须满足以下假设：各节点从其相邻节点所获得的信息与该 节点自身的信息无