（通信与信息系统专业论文）ldpc编译码优化设计与在dscdma系统中的应用.pdf

重庆邮电大学硕士论文摘要 摘要 低密度奇偶校验码l d p c 码( l o w - d e n s i t yp a r i t y c h e c kc o d e s ) 性能接近香农 限，具有编码增益高、译码简单快捷、码字灵活等优点，是当前编码界的研究热 点。与此同时，第三代( 3 g ) 移动通信系统也逐渐进入了商用阶段。为了实现3 g 移动通信系统多业务支持、高数据率传输的目的，高效信道编译码的研究成为了 被关注的焦点。常用的信道编译码如乘积码、t u r b o 码等已经不能满足3 g 移动通 信系统及其未来演进系统的诸多要求，而l d p c 码凭借着其优良的性能与巨大的 应用潜力被越来越多学者们认可。 本文研究了t d s c d m a 系统及其演进系统中，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 码在不同调制 方式下的性能进行了比较。然后，对t d s c d m a 系统的演进作了介绍，对目前标 准规定的上行使用s c f d m a 与下行使用o f d m a 的3 gl t e 系统物理层技术作了 深入的研究，并给出了规则l d p c 码在该系统中的性能仿真。对于规则l d p c 码 在该系统中仿真性能不及t u r b o 码的情况，通过分析其原因，选择了准循环低密 度奇偶校验码( q c l d p c ) 进行研究。 q c l d p c 码利用代数学或组合理论构造具有准循环结构的校验矩阵，与其它 l d p c 码相比，q c l d p c 码具有极低的线性编码复杂度。文中简要介绍q c l d p c 码的定义和编码方法，对其编译码算法进行改进，设计实现了q c l d p c 码的快速 编码算法，并对并行加权比特翻转译码算法进行改进，对其性能进行了仿真。最 后，将改进后的l d p c 编译码方案应用于t d s c d m a 系统及3 gl t e 系统中，与 t u r b o 码进行性能对比，仿真结果表明基于本文提出的l d p c 码具有比t u r b o 码更 优的性能。可以预见，在下一代移动通信系统中，l d p c 码必有广泛的应用前景。 关键词：信道编译码，3 g p p 长期演进，低密度奇偶校验码，准循环低密度奇 偶校验码 重庆邮电大学硕士论文 a b s t r a c t a b s t r a c t 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 sh a v et h ea d v a n t a g e so fh i g l le n c o d i n g g a i n ，l o wd e c o d i n gc o m p l e x i t ya n df l e x i b l ec o d e s ，a n dt h ep e r f o r m a n c ei sn e a r i n g s h a n n o nl i m i t m e a n w h i l e ，t h e3 r dg e n e r a t i o n ( 3 g ) m o b i l ec o m m u n i c a t i o ns y s t e mh a s g r a d u a l l ye n t e r e dm a t e r i a l i z a t i o ns t a g e i no r d e rt os a t i s f yt h en e e di nav a r i e t yo f s e r v i c e sa n dt h eh i g hd a t ar a t e ，t h eh i i 曲e f f i c i e n tc o d e sh a v eu n d o u b t e d l yh i g h l i g h t e di n t h es t u d yo f3 ga n dt h e3 gl e t s y s t e m u n f o r t u n a t e l y , t h em o s tc o m m o n l y c o d e ss u c h a st u r b op r o d u c tc o d e s ( t p c ) a n dt u r b oc o d e sa r ev i r t u a l l yf a l l i n gs h o r to fm e e t i n g t h e s er e q u i r e m e n t s ；w h i l et h el d p cc o d e sh a v eb e e ni n c r e a s i n g l yr e c o g n i z e db y r e s e a r c h e r sf o rt h e i rg o o dp e r f o r m a n c e ，f l e x i b i l i t ya n dt h eu n i v e r s a la d a p t a b i l i t y t h i sp a p e rc h i e f l yf o c u so no p t i m i z e dd e s i g n i n go fc o d i n ga n dd e c o d i n go ft h e l d p cc o d e s ，a n dt h ep e r f o r m a n c eo fl d p cc o d e si n3 g - s y s t e ma n dt h el o n gt e r m e v o l u t i o ns y s t e m t h es i m u l a t i o nr e s u l t ss u g g e s t e dt h a tl d p cc o d e sh a v ea p p a r e n t a d v a n t a g e so v e rt u r b oc o d e si nt h es a i ds y s t e m w ec a nc o n s t r u c tr a n d o mc o d el e n g t h a n dc o d er a t ei na na c c e p t a b l er a n g e t h i sa t t r i b u t eo fl d p cc o d e ss i m p l i f i e dt h e a p p l i c a t i o ni nt h ec o m m u n i c a t i o ns y s t e m f i r s to fa l lw es u m m a r i z e dt h eb a s i ct h e o r e t i c a lk n o w l e d g eo fc o m m u n i c a t i o n s s y s t e ma n dc h a n n e lc o d i n g ，a n da n a l y s i st h er e s e a r c hs t a t u so ft h el d p cc o d e s t h e n w ed e t a i l e do nt h eb a s i ck n o w l e d g eo fl d p ca n dt h ee n c o d i n ga n dd e c o d i n gt h e o r y , a n di nt h i sp a p e rw ea n a l y z e dt h ep e r f o r m a n c ec o m p a r i s o no fl d p cc o d e si nd i f f e r e n t m o d u l a t i o n s u b s e q u e n t l y , w ei n t r o d u c e dt h et d s c d m as y s t e ma n di t sl o n g - t e r m e v o l u t i o ns y s t e mr e s e a r c h e di nt h i sp a p e r a tp r e s e n t ，3 g p ps t a n d a r d sr e q u i r et h a ti n l t es y s t e mu p l i n ku s es c - f d m at e c h n o l o g y , d o w n l i n ku s eo f d m a t e c h n o l o g y i n t h i sp a p e r ，w ed e e p l ys t u d i e di n t h i st e c h n o l o g y , a n dg a v et h ep e r f o r m a n c es i m u l a t i o n r e s u l to fr e g u l a rl d p cc o d e si ns a i ds y s t e m t h ep e r f o r m a n c eo fr e g u l a rl d p cc o d e s i nt h es i m u l a t i o ni sw o r s et h a nt h et u r b oc o d e i nr e s p o n s et ot h i ss i t u a t i o n ，w e a n a l y z e dt h er e a s o n sf o ri t ，a n dt h e nc h o s et h eq u a s i c y c l i cl o w - d e n s i t yp a r i t y c h e c k c o d e s ( q c - l d p c ) t os t u d y t h ec h e c k i n gm a t r i xo fq c l d p cw h i c hh a sc i r c l es t r u c t u r ec a i lb ec o n s t r u c t e d u s i n ga l g e b r am e t h o do rc o m b i n a t o r i a lt h e o r y , c o m p a r ew i t ho t h e rl d p c ，q c l d p c c o d e s c o m p l e x i t yo fl i n e a r i t ye n c o d i n gi sv e r yl o w i nt h i sp a p e rw eb r i e f l yi n t r o d u c e d 重痿堂皇奎兰堡主丝奎垒塑 _ _ _ - _ _ _ _ - - - _ _ _ _ _ _ - _ _ _ _ _ _ _ - _ _ - l _ _ _ _ _ _ - _ - _ - _ l _ - - _ - _ - _ _ - - _ _ - i - _ - _ - _ _ _ _ _ _ - i _ - _ _ _ - - 。一 t h ed e f i n i t i o na n de n c o d em e t h o do fq c l d p cc o d e s i ti s a l s ob r i n gf o r w a r dt h e d e s i g no fo p t i m i z ea n di m p r o v eo nt h ec o d i n ga n dd e c o d i n gm e t h o d aq u i c kc o d i n g a l g o r i t h m a n da ni m p r o v e dp a r a l l e lw e i g h t e db i tf l i p p e dd e c o d i n ga l g o r i t h mo f q c l d p cc o d e sw e r ep r o p o s e d i nt h i sp a p e r s i m u l a t i o np e r f o r m a n c ew a sg i v e ni nt h i s p a p e ra n dw ea n a l y z e dt h er e s u l t a tl a s tw ea p p l i e d t h i si m p r o v e dc o d i n ga n dd e c o d i n g m e t h o do fl d p ci n t ot d s c d m aa n d3 gl t es y s t e m s ，a n dc o m p a r e dt h e p e r f o r m a n c ew i t ht u r b oc o d e e x p e r i m e n tr e s u l t sm a k ec l e a rt h a tl d p ch a sb e t t e r p e r f o r m a n c et h a nt u r b oc o d e s i tc a nf o r e c a s tt h a t i nt h en e x tg e n e r a t i o nm o b i l e c o m m u n i c a t i o n ，l d p cw i l lp l a ya ni m p o r t a n tr o l e k e y w o r d s ：c h a n n e lc o d i n g ，3 g p pl o n gt e r me v o l u t i o n ，l o w - d e n s i t yp a r i t y c h e c k c o d e s ，q u a s i c y c l i cl o w - d e n s i t yp a r i t y - c h e c kc o d e s i i i 重庆邮电大学硕士论文第一章绪论 第一章绪论 本章首先介绍了t d s c d m a 系统及其长期演进系统，然后回顾了通信系统与 信道编译码相关知识，接着介绍了l d p c 码的发展以及研究现状，最后介绍了本 文的课题来源、论文结构及内容安排。 1 1t d s c d m a 及长期演进系统概述 随着数字通信技术的发展，8 0 年代末出现了以g s m 和i s 9 5 为代表的第二代 移动通信系统，这些系统主要是为9 6 k b p s 的低速数据业务及话音业务设计，与第 一代系统相比具有更高的频谱效率和更可靠的通信质量。被称为2 5 代的g p r s ( g e n e r a lp a c k e tr a d i os e r v i c e ) 系统和e d g e ( e n h a n c e dd a t ar a t e sf o rg s m e v o l u t i o n ) 系统增强了数据分组业务的传输能力，可以为移动用户提供除语音外 更多的无线数据业务，可支持的最大数据传输速率分别为1 6 0 k b p s 和3 8 4 k b p s 川。 对更高比特率数据业务和更高频谱利用率的迫切要求，成为推动第三代移动 通信系统发展的主要动力。该系统以于c d m a 技术为基础，主要包括采用直接序 列扩频方式的w c d m a 和t d s c d m a 系统，以及采用多载波方式的c d m a 2 0 0 0 系统。我国在第三代移动通信系统研究开发方面取得了巨大的进展，掌握了一大 批核心技术，其中t d s c d m a 系统就是我国提出的具有自主知识产权的第三代移 动通信体制标准。这些系统可同时支持话音和多媒体数据通信，并提供更多的宽 带信息业务，如高速数据、视频、文件传输等。支持的数据速率也大大提高，如 t d s c d m a 的传输速率在用户静止时最大为2 m b p s 、在用户高速移动时最大支持 1 4 4 k b p s 2 1 。目前，第三代移动通信系统的开发已基本完成，其商业化进程正逐步 启动。 由于移动通信、数字通信及i n t e m e t 的飞速发展和日益融合，移动用户对于多 种业务的需求不断增长，并期望得到更快、更好的服务，这就迫切要求尽快研究 出能提供更大带宽、更大容量和更灵活服务。然而，第三代移动通信系统距离人 类“不论何时，不论何地都能与任何人交流任何信息 的个人通信愿望仍有较大 距离。 国际标准化组织3 g p p 在经过认真的讨论后提出了新的挑战，那就是实现峰值 速率1 0 0 m 的数据传输。这是一个巨大的挑战，也就是说必须设计出7 - 5 0 倍于当 前系统传输速率的新技术，并且具有很好的向下兼容性，以保护现有的投资。这 一新的系统被称作l t e ( l o n gt e r me v o l u t i o n ) p j 。 3 gl t e 的总体目标包括：降低时延，提高用户数据传输速率，增大系统容量 重庆邮电大学硕士论文 第一章绪论 和覆盖范围，降低运营成本等。为了实现上述目标，需要改进和增强现有3 g 系统 的空中接口、网络结构以及物理层技术。 1 2 信道编码与通信系统概述 1 9 4 8 年，美国贝尔实验室的香农( c l a u d ee s h a n n o n ) ，在他的开创性的论文通 信的数学理论【4 】中，首次阐明了在有扰信道中实现可靠通信的方法，提出了著名 的有扰信道编码理论，奠定了纠错码的基石，标志着信息与编码理论这一学科的 创立。香农在该文中指出，任一通信信道都存在信道容量c ，当通信系统所要求的 传输速率r 小于c 时，则存在一种编码方法，只要码长足够长并且使用最大似然 译码，系统的错误传输概率可以达到任意小。虽然香农给出的仅仅是一个编码存 在性定理，但却推动了信道编码理论以及数字通信系统的飞跃发展。 目前，利用纠错码降低各类数字通信系统以及计算机存储和运算系统中的误 码率，提高通信质量，延长计算机无故障运行时间等，在全世界各个国家中已作 为- 1 7 标准技术而广泛采用。如今，纠错码技术已开始渗透到很多领域。利用纠 错码中的许多编译码原理和方法，与通信系统中的其它有关技术相结合，得到了 令人惊喜的结果。 在有扰信道中，信道编译码的好坏直接影响着一个通信系统的性能。根据香 农的阐述，所有的通信系统都可以归结为图1 1 所示的模型。 图1 1 通信系统模型 该模型中，信源产生待传送的信息，在数字通信系统中，我们可以抽象的认 为信源输出的是表征信息的二进制比特流。不失一般性，我们可以认为信源发送0 的概率和发送1 的概率相等；发射机将信息转换为适合的信号形式以适合信道传 输；信道是对传送信号的物理介质的抽象；接收机从信道接收信号并对信息进行 重建：信宿将接收到的信息恢复；从信道引入的噪声对接收机重建信息带来了很 大麻烦：因为噪声的存在，重建的信息并不是信源信息的复制版本，而是引入了 传输差错，这显然是我们所不希望的。 数字通信系统中，为了减小或消除传输差错而采取的差错控制方式大致可以 分为以下几个类型p j ： 2 重庆邮电大学硕士论文第一章绪论 重传反馈方式( a r q ) 。a r q 方式的系统如图1 2 所示。在发射端发送具有检 错能力的码，接收端的译码器检测接收到的码序列是否有错，并将判断结果通过 反向信道反馈给发射端。发射端根据这个判断结果，把接收端认为有错误的消息 再次发送，直到接收端认为接收正确为止。 图1 2a r q 方式下的通信系统模型 a r q 方式的编码器和译码器设计比较简单，同时，整个系统的纠错能力很强， 能够使系统获得很低的误码率；由于检错码的检错能力一般与信道的变化情况没 有关系，所以这种系统适应性很强。但是，系统需要发射端和接收端密切协调配 合，因此控制比较复杂：在信道恶劣的环境中，由于系统可能经常处于重发的阶 段，因此传送的连贯性和实时性很差，所以一般只适合于非实时的数据传输业务。 前向纠错方式( f e c ) 。前向纠错方式的系统如图1 3 所示。发送端发送具有 纠错能力的码，接收端收到码序列后，利用纠错译码器，不仅能发现错误，还能 够自动的纠正错误。其中，编码器通过增加冗余信息，将长度为k 的信源序列k 映射为长度为n 的码字c ，送入编码信道。编码信道将噪声图案e 迭加到发送码 字上，使得接收端接收到序列r 。接收端通过对r 译码得到重建后的码字c 。和重 建后的消息序列k i 。我们称这种纠错码是( n ，k ) 纠错码，并定义其码率为r = k n 。 在一次通信中，总的差错比特数和总的传送比特数之比称为误码率( b e r ) 。显然， 误码率是衡量纠错码的一个重要指标。误码率这个参数往往需要通过蒙特卡罗仿 真来得到，为了使结果更加靠近真实情况，需要很大的仿真点数。有时候，在通 信中我们需要将数据打包，只要数据包中有一个比特出现错误，我们就认为这个 包出现了传输错误。因此我们将总的错误数据包个数和总的传送数据包个数之比 称为误包率( f e r ) 。本文中，误包率定义为总的错误码字个数和总的传送码字个数 之比。 图1 3f e c 方式下的通信系统模型 3 重庆邮电大学硕士论文第一章绪论 前向纠错方式的优点在于实时性好，控制电路较重传反馈方式简单，因此能 够适用于多种通信业务。其缺点在于编译码器比较复杂，而且受信道环境影响很 大。随着编码理论的发展和硬件水平的提高，性能强大且可行性较好的纠错码编 译码器已经在当前的数字通信系统中得到了广泛应用。 混合纠错方式( h e c ) 。混合纠错方式是指发送的码同时具有检错和纠错的能 力。因此获得接收序列后，首先检查错误情况，如果在纠错码的纠错能力内，进 行纠错。如果不在纠错码的纠错能力内，则采用重传反馈方式。因此，这种纠错 方式是重传反馈方式和前向纠错方式的结合与折中，在实际通信系统中，也有着 很广泛的应用。 总而言之，差错控制是为了解决通信的可靠性问题的。如果对于一个通信系 统，在某种通信环境中的差错概率为零或者无限的趋近于零，我们就说在这种环 境中该通信系统是可靠的。接下来，本文将把讨论范围局限于前向纠错方式。前 向纠错方式中，纠错码的选择及其编码、译码器的设计是决定纠错能力的最重要 的因素，这也是信道编码研究的主要内容。 1 3l d p c 码的提出、发展及研究现状 1 9 6 2 年g a l l a g e r 在他的博士论文中提出了二元规则l d p c 码，也被称作 g a l l a g e r 码【6 1 。g a l l a g e r 证明了这类码具有很好的汉明距离特性，时满足g v 限的 渐进好码，在计算机上进行i o cl o g ( 1 0 9 ) ( n 为码长) 次后验概率迭代译码可以 获得依码长指数降低的比特错误概率，但限于当时的计算能力，l d p c 码被认为不 是实用码，在很长一段时间内没有受到人们的重视。 1 9 8 1 年，t a n n e r 在他的一篇奠基性的文章【7 】中正式提出了用图模型来描述码 字的概念，从而将l d p c 码的校验矩阵对应到被称为t a n n e r 图的双向二分图上， 采用t a n n e r 图构造的l d p c 码，通过并行译码可以显著地降低译码复杂度。t a n n e r 还仔细分析了最小和算法( m i n s u ma l g o r i t h m ) 与和积算法( s u m p r o d u c t a l g o r i t h m ) 两种信息传递算法，证明了有限无环t a n n e r 图的最小和译码算法与和 积译码算法的最优性。但t a n n e r 图在实际中是采用随机图构造的，其中不可避免 的存在小环路现象。这些小环会造成译码信息的重复传递，使译码过程中的消息 之间不满足独立性假设，影响了迭代译码算法的收敛性。 t u r b o 码的发现【8 j 重新引发了学者们对l d p c 码的研究兴趣。m a c k a y 和n e a l 利用随机构造的t a n n e r 图研究了l d p c 码的性能【9 】，发现采用和积译码算法的规 则l d p c 码具有和t u r b o 码相似的译码性能，在长码时甚至超过了t u r b o 码，这 4 重庆邮电大学硕士论文第一章绪论 一结果引起了信道编码界的极大关注。此后，d a v e y 和m a c k a y 从减少t a n n e r 图上 小环的概念出发提出了基于g f ( q ) ，q 2 的l d p c 码i l ，进一步提高了l d p c 码的 译码性能。 自m a c k a y 等重新发现l d p c 码之后，人们进一步的研究表明：基于非规则双 向图的l d p c 码的性能可以优于t u r b o 码，而且这样的码的性能可以非常接近 s h a n n o n 限。其中一个原因也在于l d p c 码具有良好的距离特性。由于l d p c 码不 仅具有良好的距离特性、小的译码错误概率和较低的译码复杂度，而且当适当码 长( 比如大于2 0 0 ) 时，不存在错误平台，其码率容易调整。实验结果中的错误几 乎均为可检测错误。所以l d p c 码无论在理论上还是在实用中都具有及其重要的 作用。l d p c 码的重新发现是继t u r b o 码后纠错编码领域中的又一大重大进展。 近年来，很多研究表明l d p c 码是一类性能优异的好码。l d p c 码比t u r b o 码在技术上更具有优势，更能使用未来系统高速数据传输和高性能的要求。继 t u r b o 码被i s 2 0 0 0 标准采用作为第三代移动通信系统手机中的纠错抗干扰方案 后，最近l d p c 码已经被世界各大通信公司采用或提出作为新一代移动通信系统 中的纠错抗干扰方案。 有关l d p c 码的研究，在理论方面，主要研究l d p c 码的性能，包括利用各 种方法寻找好的节点度的分布，计算其性能界和码率界，分析码结构中的环长与 性能的关系，构造具有较大环长的码等；另一方面则侧重于l d p c 码的实际应用， 包括l d p c 码在各种实际通信系统，特别是在未来高速宽带移动通信系统中的应 用、在磁记录系统中的应用、l d p c 码的硬件实现问题等。 1 4 本文研究工作及论文结构 本课题来源于国家“8 6 3 ”项目：“t d s c d m a 手机关键技术的研究与应用， 对第三代移动通信系统长期演进( 3 gl t e ) 中关键技术的研究。 本文主要讨论了目前信道编码领域的热点课题l d p c 码的理论。分析了主 要的编译码算法以及性能分析方法，并且将l d p c 码应用到3 gl t e ( t d d ) 系统中。 本文的结构如下： 第二章，介绍了l d p c 码基本理论和其描述方法。讨论了l d p c 码的随机构 造和结构化构造方法，并介绍了l d p c 常见的几种译码方法。 第三章，对3 gl t e 项目进行介绍，介绍了基于s c f d m a o f d m a 的3 g l t e ( t d d ) 系统设计及物理层技术构架，并将传统l d p c 码引入该系统，详细介绍 了其编译码方案，并给出了其仿真性能。 5 重庆邮电大学硕士论文 第一章绪论 第四章，讨论了q c l d p c 码，并介绍其构造及译码方案，并给出在3 g l t e ( t d d ) 系统中的仿真。 第五章，在第四章的基础上，对于基于3 0l t e ( t d d ) 系统的q c l d p c 的编 译码算法进行优化设计，提出了一种新的快速编码构造方法和新的译码算法，对 其性能仿真比较本文提出的算法具有的优势。 第六章，总结全文，讨论下一步的工作和需要解决的问题。 6 重庆邮电大学硕士论文 第二章l d p c 码 第二章l d p c 码 弟一早 田与 早在1 9 6 3 年g a l l a g e r 就提出了低密度校验码( l o wd e n s i t yp a r i t yc h e c kc o d e s ， 简称l d p c 码) 1 6 j ，m a c k e y 、s p i e l m a n 和w i b e r g 几乎同时“再发现了l d p c 码 【9 】【1 1 】【1 2 】。进一步的研究表明：基于非规则双向图的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 码的性能仿真。 2 1l d p c 码 2 1 1l d p c 码的基本知识 l d p c 码属于线性分组码的一种，因其校验矩阵是稀疏矩阵而得名。假设某 l d p c 码的校验矩阵凰为m x 玎阶矩阵，该l d p c 码可以记做( 门，k ，) ，其中以为码 长，为校验矩阵每列的重量，即列中l 的个数，称为列重( c o l u m nw e i g h t ) ，k 为 校验矩阵每行的重量，即行中i 的个数，称为行重( r o ww e i g h t ) ，且一般有 2 ，k 。 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 ) 两大类， 当h 的行重p 和列重，保持不变或尽可能的保持均匀时，我们称这样的l d p c 码 为规则l d p c 码，反之如果列、行重变化差异较大时，称为非规则的l d p c 码。 l u b y ，m i t z e n m a c h e r 等在文献【1 3 】中证明了正确设计的非规则l d p c 码的性能要优 于规则l d p c 。 下面所示的校验矩阵风，是一个( 1 2 ，3 ，6 ) 规则l d p c 码的例子，该l d p c 码行重为6 ，列重为3 。 7 重庆邮电大学硕士论文 第二章l d p c 码 2 1 2l d p c 的二分图 l d p c 码的校验矩阵可以用t a n n e r 图来表示 7 1 。t a n n e r 图的作用类似于卷积 码中的格图，是表示l d p c 码的重要工具，对于译码算法以及码的优化都具有重 要的作用。 用于表示l d p c 码的t a n n e r 图又称为二分 羽( b i p a r t i t eg r a p h ) 。二分图中的节点 分为校验节点( c h e c kn o d e s ) 和比特节点( b i tn o d e s ) 或称变量节点( v a r i a b l en o d e s ) ，分 别对应于编码变量节点和校验方程。每个比特节点表示码字中的某一位，对应 于校验矩阵的一列；每一个校验节点表示某个校验方程，对应于校验矩阵的一行。 如果某一位出现在某一个校验方程中，则对应的二分图中的比特节点和校验节点 有一条“边”( e d g e ) 相连，图2 1 就是对应前面的凰矩阵的二分图。 燹毓节点 图2 1 ( 1 2 ，3 ，6 ) 规则l d p c 码二分图 二分图中如果从某一节点出发，沿着边经过不同的节点之后又回到原节点， 则称所经过的节点组成一个“环 ( c y c l e ) 。依次连接该环上不同节点的边的数 目称为“环长( c y c l el e n g t h ) 。一个特定l d p c 的最小环长，称为该l d p c 码 的围长( g i r t h ) 。如图2 1 中左侧的边a b c d a 组成了环，环长为4 ，而图中对 应的l d p c 码最小环长即为4 。需要指出，最小环长在一定程度上体现了该l d p c 码的码间距离，是决定码性能的重要因素，也是很多学者在试图构造性能优良的 l d p c 码时必须考虑的问题。 低密度奇偶校验码本质上是一种线性分组码，它通过一个生成矩阵g 将信息 序列映射成发送序列，也就是码字序列。对于生成矩阵g ，完全等效的存在一个 奇偶校验矩阵h ，所有的码字序列v 构成了h 的零空间，即h v r = 0 。 l d p c 码的奇偶校验矩阵h 是一个稀疏矩阵，相对于行与列的长度n 、m ，校 8 重庆邮电大学硕士论文 第二章l d p c 码 验矩阵中每行、列中非零元素的数目( 即行重、列重) 非常小，这也是l d p c 码 之所以称为低密度码的原因。由于校验矩阵h 的稀疏性以及构造时所使用的不同 规则，使得不同l d p c 码的编码t a n n e r 图具有不同的闭合环路分布。而二分图中 闭合环路是影响l d p c 码性能的重要因素，它使得l d p c 码在类似置信传播( b e l i e f p r o p a g a t i o n ) 算法的一类迭代译码算法下，表现出完全不同的译码性能。 l d p c 码的二分图中的变量节点和校验节点，分别对应于校验矩阵h 中的n 列和m 行。同一个集合内部的节点没有连线，只有属于不同集合的两点之间可能 有连线，每一条连线对应于校验矩阵中的“1 。为了方便，我们借用g a l l a g e r 对 l d p c 码的表示方法：将码长为n ，行重、列重分别为p 和y 的l d p c 码称为 ( n ，厂，p ) l d p c 码。 式2 1 是某个( 8 ，2 ，4 ) l d p c 码的校验矩阵和相应的校验方程，根据校验 矩阵我们可以画出它的二分图( 图2 2 ) 。图中变量节点集合( m ，v 2 ，) 和校验节 点集合( q ，c 2 ，c 4 ) 内部不存在相连的边，但两类节点之间存在着连线。变量节点 和校验节点之间存在连线意味着该变量比特参加了此校验式，也就是校验矩阵某 一行中“1 的位置。我们将每个节点上的连线数目称为该节点的度( d e g r e e ) ， 图2 2 中，变量节点的度( 盔，) 为2 ，校验节点的度( 吐) 为4 。 h = 11 10 01 0 0 l0 0o 0l ll 0o 1l lo o l lo ol l0 0l 图2 2 ( 8 ，2 ，4 ) l d p c 码的二分图 式( 2 1 ) 的二分图结构中，四条粗线构成了一个有向的闭合环路，由v l 起始， 经过c l - - - v 3 - - - c 2 ，最后返回v l 。在一个l d p c 码的二分图中，每个节点都会存在 许多这样的闭合环路，我们将其中长度最小的一个称为该节点的最小环长( s h o r t e s t c y c l e ) 。二分图中所有节点的最小环长中，长度最小的称为二分图的围长( g i r t h ) ， 上例的二分图中，g i r t h 与变量节点l 的最小环长相等，都是4 。 l d p c 码二分图结构中g i r t h 的大小对l d p c 码的译码性能有很大影响。 t a n n e r 【2 4 】认为g i r t h 的长度将直接关系到l d p c 码码字的最小码距，并给出了最小 码距的下界与g i r t i l 的关系式： 9 、jiz，l 协垤协n 0 o 0 0 吃k 屹 0 o o o 吃如以住 0 0 0 e u h 吃屹 重庆邮电大学硕士论文 第二章l d p c 码 。d旦垒三i砉紫+争(d一)(y一-)h譬2)，4g，2为奇数，、 d d 区譬二1 2 1 兰二! ! 葚：二!g 2 为偶数 【d o ( r 一1 j 一1 其中，d 为l d p c 码的最小码距，g 为l d p c 码的g i r t h ，y 为变量节点的度， d 为二分图中子码( s u b c o d e ) 的最小码距。从公式中可以看出，g i r t h 长度越大， l d p c 码的最小码距越大，译码性能也就更好。仿真结果表明，如果二分图中存在 长度为4 的g i r t h ，l d p c 码的误码率性能将会很差，所以我们在构造l d p c 码的 校验矩阵时，要尽量避免二分图中出现g i r t h 为4 的情况。 l d p c 码的译码算法主要是迭代译码算法，因为某些节点存在闭合环路，当迭 代次数较多时，到达这些节点的信息不再满足统计独立的特性，从而使得译码性 能与最大似然算法有一定的差距。因此，我们在设计l d p c 码时，在保证g i r t h 大 于4 的情况下，各个节点的最小环长越大越好。令人惊奇的是，即使二分图中存 在不少这样的闭合环路，但只要g i r t h 大于4 ，l d p c 码应用迭代译码算法依然可 以取得较好的误码率性能。g a l l a g e r 认为造成这种现象的原因是：随着迭代次数的 增加，独立性产生的影响越来越小，而且趋向于相互抵消，当迭代次数到达一定 时，闭合环路影响译码结果的可能性很小例。 图2 3 是不同码长l d p c 码的最小环长分布，从图中可以看出，随着码长的增 加，拥有较短长度闭合环路的节点越来越少。例如，码长为l1 5 2 的l d p c 码，最 小环长只有两种：6 和8 ，而长度为6 的节点占了3 9 。当码长增加到9 2 1 6 ，二 分图中已经没有长度为6 的闭合环路，最小环长为l o 的节点有5 0 。最小环长的 分布状况可以作为衡量l d p c 码结构好坏的一个准则，二分图结构中短长度的环 占的比重越少，l d p c 码的译码就越接近理想中无环( c y c l ef r e e ) 的假设。当l d p c 码的码长趋向于无穷，其编码二分图结构可以看作近似无环，l d p c 码在b p 算法 下的译码性能也就完全等效于最大似然译码。 1 0 重庆邮电大学硕士论文 第二章l d p c 码 图2 3 不同码长的l d p c 最小环长分布 2 1 3 规则与非规则l d p c 码 在l d p c 码的校验矩阵中，如果行列重量固定为( p ，y ) ，即每个校验节点 有p 个变量节点参与校验，每个变量节点参与y 个校验节点，我们称之为规则 l d p c 码。g a l l a g e r 最初提出的g a l l a g e r 码就具有这种性质。从编码二分图的角度 来看，这种l d p c 码的变量节点度全部为y ，而校验节点的度都为p 。我们还可以 适当放宽上述规则l d p c 码的条件，行列重量的均值可以不是一个整数，但行列 重量尽量服从均匀分布。另外为了保证l d p c 码的二分图上不存在长度为4 的环， 我们通常要求行与行以及列与列之间的交叠部分重量不超过l ，所谓交叠部分即任 意两列或两行的相同部分。我们可以将规则l d p c 码校验矩阵h 的特征概括如下： h 的每行行重固定为p ，每列列重固定为y 。 任意两行，两列之间交叠部分重量最多为1 。 行重p 和列重7 相对于h 的行数m 、列数n 很小，h 是个稀疏矩阵。 规则l d p c 码的最小码率r 可以通过下式计算： 厂= ( n m ) i n = 1 一m = 1 - r p ( 2 3 ) 在规则l d p c 码的校验矩阵中，行重和列重的均值保持不变，所以校验矩阵 中l 的个数随着码长的增加而线性增长，整个校验矩阵的元素个数则成平方增长。 当码长达到一定长度时，校验矩阵h 是非常稀疏的低密度矩阵。对于规则的l d p c 码，m a c k a y 在【4 】中给出了以下两个结论： 对于任意给定列重大于3 的l d p c 码，存在某个小于信道传输容量且大于 零的速率r ，当码长足够长时，可以实现以小于r 且不为零的速率无差错的传输。 也就是说任意给定一个不为零的传输速率r ，存在一个小于相应香农限的噪声门 限，当信道噪声低于该门限且码长足够长的时候，可以实现以r 速率无差错的传输。 当l d p c 码的校验矩阵h 的列重y 不固定，而是根据信道特性和传输速率 重庆邮电大学硕士论文第二章l d p c 码 来确定时，则一定可以找到一个最佳码，实现在任意小于信道传输容量的速率下 无差错的传输。 对于l d p c 码的每个变量节点来说，当它参与的校验式越多，即度y 越大，则 它可以从更多的校验节点获取信息，也就可以更加准确的判断出它的正确值。对 于h 的每个校验节点来说，当它涉及的变量节点越少即度p 越小，则它可以更准 确的估计相关变量节点的状态。这种情况对于规则l d p c 码来说是一对不可克服 的矛盾，于是l u b y ，m i t z e n m a c h e r 等人就引入了非规则l d p c 码的概念。 在非规则l d p c 码的编码二分图中，两个集合内部的节点度数不再保持相同， 即每个变量节点参与的校验式数目或每个校