（通信与信息系统专业论文）ldpc码的研究及其在ieee+80216a+mimoofdm系统中的应用.pdf

南京邮l 也学院坝l 刚亢生学位论文 摘要 摘要 l d p c 码是g a l l a g e r 最早于1 9 6 2 年提出的一种具有稀疏校验矩阵的线性分 组码，可是限于当时的条件和人们的认识水平它并没有获得很大的发展而且逐渐 被人们所遗忘了。之后，在t u r b o 码的巨大成功的带动下，m a c k a y 等人重新研 究了它，并发现l d 阢码具有逼近香农限的特性。现在，l d p c 码已经成为纠锚编 码领域罩的研究热点，它在许多领域具有极其广泛的应用前景。 本文对l d p c 码进行了以下的研究： 介绍了l d p c 码的基础知识、构造方法，介绍了萨则码、非正则码的概念并 比较了他们的性能，介绍了构造高圈长的l d p c 码的方法和圈长对性能的影响： 探讨了l d p c 码基于近似下三角矩阵的线性编码算法：研究了l d p c 码的译码 算法，分别对硬判决译码和软判决译码进行了介绍并对i 种t 要的译码算法的 性能进行了仿真比较。 基于l d p c 码的优越性能，本文研究其在空时编码m i m 0 一o f d m 系统中的 应用。首先剥l d p c 码在i e e e 8 0 21 6 a 的o f d m 环境中的应用进行了研究选 取了三种码长的非一则码在s u l 3 、s u l 5 多径信道模型下进行了仿真和性能分析； 最后探讨了l d p c 码与空时编码m i m o o f d m 系统结合在多径信道中的应用， 并进行了仿真分析。 关键词：l d p c 码，正则码，非正则码，二分图，圈，g i n h ，线性编码，m p 算 法，b p 算法，o f d m ，t u r b o 码，空时编码，m i m o 南京【| ! | j u 学院m 正l j 形f 宄生学位论上 a b s t r a c t l d p cc o d e sw e r eo r i g i n a l l yi n v e n t e da n d i n v e s t i g a t e db yg a l l a g e r l d p c c o d e s a r el i n e a rb l o c kc o d e sw i t hl o wd e n s i t yp a r i t ym a t r i x i n t e r e s ti nl d p cc o d e s w a sr e k i n d l e di nt h ew a k eo ft h ed i s c o v e r yo ft u r b oc o d e s m a c k a ye ta 1 r e d i s c o v e r e d l d p cc o d e sa n dp r o v e dt h e i rc a p a c i t yo fa p p r o a c ho fs h a n n o nl i m i tl d p cc o d e s h a v eb e c o m eah o ts p o to fr e s e a r c hi nt h ea r e ao fe r r o rc o r r e c t i n gc o d e sa n dh a v e m u c hp r o s p e c ti na p p l i c a t i o n t h i st h e s i sg i v e sas y s t e m a t i ci n v e s t i g a t i o no fl d p cc o d e s ： f i r s tw ei n t r o d u c eb a s i ck n o w l e d g eo fl d p cc o d e s a n a l y z et h ep e r f o r m a n c eo f r e g u i a ra n di r 诧g u i a rc o d e s色i nc r o d u c ea ne m c i e n tm e t h o dt oc o n s t r u c tl d p c c o d e sw i t hh i g hg i n ha n dc o m p a r ep e r f o r m a n c eo fl d p cc o d e sw i t hd i f k r e n t a v e r a g eg i r t h t h e nw ed i s c u s st h ep r o b l e mo fi i n e a re n c o d i n go fl d p cc o d e sa n d i n t r o d u c et h ee n c o d i n ga l g o r i t h mb a s e do na p p r o x i m a t e1 0 w e rc r i a n g u l a t i o n s f i n a l l y ， 、er e s e a r c hd e c o d i n ga l g o r i t h m so fl d p cc o d e sa n dg i v es i m u l a t i o nr e s u l t so ft h r e e d e c o d i n ga l g o r i t h m s t h ea p p i i c a t i o no fl d p cc o d e st om i m o o f d ms v s t e mi ss “l d i e d ，f i r s tw e s t u d yt h ea p p i i c a t i o no fl d p cc o d e st oo f d ms v s t e mo fi e e e8 0 2 ，l6 aa n d s i m u l a t e dp e r f b r m a n c ei ns u l 3a n ds u l 5f a d i n gc h a n n e l s t h e nw ec o n s i d e rt h e p e r f o r m a n c eo fm i m o o f d ms y s t e mc o d e dw i t hl d p ca n dg ；v es i m u l a t i o nr e s u l t s i nf a d i n 2c h a n n e l k e y w o r d s ： l d p cc o d e s r e g u l a rc o d e s ，i r r e g u l a rc o d e s ，b i p a r t i t eg r a p h c y c i e ，g i r t h ， l i n e a rt i m ee n c o d i n g ，m pa l g o r i t h m ，b pa l g o r i t h m ，o f d m ，t u r b o ，s t c ， m i m o 南京邮电学院学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电学院或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名： 签塑盎日期：盘查：芏 南京邮电学院学位论文使用授权声明 南京邮电学院、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 嘏权 南京邮电学院研究生部办理。 研究生签名： 塑数查 导师签名 南京f | _ l ；i u 学院彤2 m 究生学位论爻 谪一帝绪论 第一章绪论 1 1 信道编码的历史与l d p c 码的发展状况 在现代通信系统中，信道中存在各种噪声和衰落的影响，为了保证信息的可 靠、有效地传输，纠错编码技术是必需的。随着无线数字通信的发展以及各种高 速率、突发性强的新业务的出现，对纠错编码技术的研究也显得更加必要。 纠错编码理论的起源可以追溯到1 9 4 8 年香农信息论的问世。香衣第二定理 也称信道编码定理。指出实现可靠通信所允许的传输速率的上限为信道容量。在 信道带宽受限和功率受限的条件下，带限a w o n 信道的信道容量c 表示为： c 1 卸r l o 小惫j m ， 其中为带宽，巴为信道输入带限信号的平均功率。若传输速率为信道容量， 即只、= c 毛，则 芳一i o 小芳，鲁j m z ， 熹= 等 m ， _ o ( ? 、 _ 焉m 0 等- t n z 叫s a b m 。， 表明在带限a w g n 信道中，传输速率达到信道容量时，可靠通信所需的最小比 特能噪比为- 1 6 d b ，称之为香农限。香农限成为设计信追编码时试图逼近的信噪 比下限。信道编码定理的提出奠定了纠错码的基石，此后人们根据香农的思想， 提出了一系列设计好码和有效译码的方法，使纠错码技术飞速发展。 纠错码主要有分组码和卷积妈两犬类。线性分组码是发展最早的类纠错 码。线性分组码以代数中的群论、域论等理论为数学基础，利用各种代数方法设 计好的纠错码，并研究相应的译码算法，包括戈雷码、汉明码、循环码和b c h 码等短码。其中类重要的编码b c h 码进一步演化出了扩展b c h 码、缩短b c h 南京f | | | f i u 学院坝h 叶究生学位呛殳弛一节绪论 码、r s 码等编码，在通信系统中应用极其广泛。分组码的译码通常采用大数逻 辑译码和捕错译码。 五十年代引进的卷积码是另一类重要的纠错码。卷积码在编码过程中引入了 寄存器，从而增加了码元之间的相关性，在相同复杂度的条件下可以获得比分组 码更高的编码增益，但也增加了分析和设计的复杂性。随着各种卷积码的译码方 法，尤其是维特比( v i t e r b i ) 译码算法的出现，卷积码逐渐得以广泛应用，而后 出现的t c m ( 格栅编码调制) 技术，更加促进了卷积码的发展和应用，并使其 逐渐成为通信领域中的主导地位。 八十年代和九十年代初，经过几十年的研究和实践，纠错编码理论和技术取 得了很大的发展。法国的c b e r r o u 等人在卷积码和数联码的基础上，于1 9 9 3 年 提出了种全新的编码方案t u r b o 码，在信道编码的理沦和应用中取得了突 破性的进展。这种编码能够随着码长的增朋而逼近香农的理论极限，同时译码复 杂度也可以接受。t l i r b o 码采用并行级联递归的编码器结构，是一种系统的卷积 码，其译码算法主要有m a p 算法、l o g m a p 算法、s o v a 算法等。 t u r b o 码具有独特的编码结构和译码思想：在子编码器中采用反馈型的系统 卷积码，且在子编码器问引入交织嚣，减少子编码器之问信息的相关性，模仿了 随机编码的形式；同时在译码中采用了软输入、软输出的译码信息和信息反馈的 译码器形式，引入了迭代译码思想。由于t u r b o 码优秀的性能，使其成为编码界 研究的热点，在通信中有广阔的应用前景。但是t u r b o 码也有其缺点，它的译码 复杂度仍然较大，且在码长较长时，由于交织器的存在具有较大的时延。 在t u r b o 码的启发下，另一类具有相似特性和性能的编码重新进入了人们的 视野。这就是l d p c ( l o wd e n s i t yp a r i 【yc h e c k 一低密度奇偶校验) 码。l d p c 码 是g a l l a g e r 1 】于1 9 6 2 年提出的g a l l a g e r 码的推广。经过数十年的沉寂，随着计 算机硬件和相关理论的发展，d jc m a c k a y 和m n e a l 等对其进行重新研究，发 现它也具有逼近香农限的性能 2 1 【3 】。文献 1 5 】中的研究结果显示，对于 b l - a w g m 信道，码率为l 2 的非f 则l d p c 码具有距容量不到00 6 d b 的门限： 计算机仿真结果表明，精心设计的非f 则l d p c 码( 码长为1 0 6 ) 可获得在 b e r = 1 0 。6 时仅偏离容量o 1 3 d b 的性能；理论上极限性能仅仅比香农限高 o 0 0 4 5 d b 的非萨则玛次数分布对已经找到( 1 6 j 。l d p c 码的优异性能及其在信息 南京f | 1 l ；l 乜学院坝h 究生学位论文 笫一章绪论 可靠传输中的良好应用前景( 如深空通信、第4 代移动通信系统、高速与甚高速 数字用户线等) 已经引起了编码界的关注，成为通信领域中新的研究热点。 l d p c 码在m a c k a y 于9 6 年发表的文献 2 】后重新得到了人们的重视，许多 研究人员都投入到l d p c 码的研究中。从1 9 9 9 年丌始这方面的研究文献大量 出现。经过几年的研究和发展，人们在各方面都取得了很大的进展，l d p c 码的 相关技术也门趋成熟，甚至已经丌始有了觚少化的应用成果。 m g l u b y 等【8 】采用基丁线性规划的方法来设计线性时间可编码的非正则 码；t j r i c h a r d s o n 等1 5 】通过优化二分图的次数分却，设计出性能逼近香农限的 非正则码：j c a m p e l l o 等 9 提 h 采用扩展的比特填充算法来没计高码率、高g i n h 的优秀l d p c 码；y k o u ，s l i n 和m f o s s o r i e r 【1 3 1 4 探泔了基于有限几何学的 l d p c 码结构，构造出了半循环的l d p c 码。 在如何减小编码的复杂度方面，mg l u b y 等 1 8 1 9 】提出了一类基于级联二 分图的l d p c 码，可用于存疑信道；m a c k a y 、w i l s o n 和d a v e y 等 2 0 】建议强制 性的使奇偶校验矩阵具有下三角阵的形式：tj r i c h a r d s o n 和r l u r b a n k e 2 i 】提 出重排稀疏矩阵的行或列，得到具何近似下三角结构的校验矩阵。 译码研究方面，m a c k a y 等f 6 1 提出了基ril r 译码信息的和积算法： r i c h a r d s o n 等 2 2 总结归纳出了m p ( m e s s a g ep a s s i n g ) 算法类：xw e i 等【3 8 】4 哿 t u r b o 码中简化l o g m a p 算法得到的m a x l o g m a p 算法的思想引入l d p c 码的 译码算法中，得到适用于l d p c 码的m a x - l o g m a p 算法。 l d p c 码的实现通常要考虑性能、复杂度和灵活性等各种因素。研究人员已 经提出了一些基于d s p 、f p g a 和v l s i 的l d p c 码的实现方案。f l a r i o n 公司已 经丌发出称为v e c t o p l d p c 的l d p c 编译码器产品。l d p c 码具有广阔的应用 阿景，在光纤通信、卫星通信、磁光全息存储、移动和固定无线通信和数字用 户线中将得到广泛的应用。如v o c a l 公司提出了用于w l a n 的l d p c t u r b o 码不对称解决方案，使得移动终端的电池使用时问可延长4 倍。 1 2 i e e e 8 0 2 1 6 a 协议与o f d m 简介 目前主流的宽带无线接入技术主要有无线个人域网( w p a n ) 技术，如蓝牙 南京_ | | | 5 t u 学院h 川冗生学位论艾 第一一帚绪论 技术( b l u e t o o t h ) 和i e e e8 0 21 5 ；无线局域网( w l a n ) 技术，如【e e e8 0 2 1 l b l l a 和e t s i 的h i p e r l a n 2 ：固定宽带无线接入( f b w a ) 技术，如i e e e8 0 2 1 6 无线城域网( w m a n ) 技术。 l e e e8 0 2 1 6 协议为第二代无线城域网定义了w i r e i e s s m a n l m 空中接口，支 持l o 一6 6 g h z ( 即传统的l m d s 系统) 的超高频段。该标准描述了一个点到多 点( p m p ：p o i n t t o m u l t i p o i n t ) 的固定宽带无线接入系统的空中接口，包括媒体 访问控制( m a c ：m e d l l l m a c c e s sc o n t r o i ) 层和物理层( p h y ：p h y s i c a ll a y e r ) 两大部分。 i e e e8 0 2 1 6 a 协议对i e e e 标准8 0 21 6 进行了修正，增强了m a c 层的功能 ( 不仅支持p m p 网络结构，还可选用m e s h 拓扑) 。并丌发了新的物理层规范， 直接支持游离和同益增长的移动用，。，把空中接口扩展到2 一l l g h z ( 即传统的 m m d s 系统) 的低频段。在这个频段，系统成本更低，用户覆盖范围更大，受 雨衰影响较小。采用新的物理传输技术，系统可以在非视距传输环境下运行，因 此能直接支持慢速移动终端，但速率也相对低蝗。 8 0 2 1 6 a 为物理层定义了三种传输标准：一是基于坼载波调制技术的单载波 系统w i r e l e s s m a n s c ；二是基于采用2 5 6 个子载波的o f d m 调制技术的多载波 系统w i r e l e s s m a n o f d m ；三是采用2 0 4 8 个子载波的多址技术 w i r e l e s s m a n o f d m a 。本文讨论的是8 0 2 1 6 a 中最重要的一种物理层标准：即 基于o f d m 调制技术的多载波系统。 o f d m 的提出已经有近4 0 年的历史，但这种多载波传输技术在无线数掘方 面的应用却是近1 0 年来的新趋势。近年来，由于o f d m 其频谱利用率高、成本 低、具有较强的抗多径衰落能力等原因越来越受到人们的关注。随着d s p 芯片 技术的发展，傅立叶变换反变换，6 4 1 2 6 2 5 6 q a m 的高速调制技术，格栅编码 技术、软判决技术、信道自适应技术等的引入，人们丌始集中精力丌发0 f d m 技术在移动通信领域的应用，o f d m 被视为第四代移动通信的关键技术之一。 1 3m i m 0 与空时编码 m i m o ( m u l t i p l e i n p u tm u l t i p l e o uc p u ) 技术最早是由m a r c o n i 于1 9 0 8 南京_ j 】| j u 学院坝l 州e 生学位论己 第一节绪论 年提出的，是第三代和未来移动通信系统实现高数据速率、高系统容量，提高传 输质量的重要途径。在当前移动通信系统中，由于诸多业务对上下行链路容量要 求的不对称性，尤其对下行容量有很高的要求，如视频多媒体、下载等业务，下 行链路的容量构成了整个系统的瓶颈。但是如果在发送端和接收端都使用多天线 ( 即m i m o 系统) ，此时的信道容量将随着天线数量的增大而线性增大。也就是 蜕可以利用m i m o 信道成倍地提高无线信道容量，在不增加带宽和天线发送功率 的情况下，频谱利用率可以成倍地提高。 利用m i m o 技术既可以提高信道的容量，同时也可以提高信道的可靠性， 降低误码率。前者是利用m i m 0 信道提供的空间复用增益，后者是利用m i m o 信道提供的空间分集增益。实现空问复用增益的算法主要有贝尔实验室的 b l a s t 算法、z f 算法、m m s e 算法、m l 算法。目前m l m o 技术领域另一个 研究热点就是基于发射分集的空时编码，主要有分层空时编码( b l a s t ) 、空时格 形码( s t t c ) 和空时分组码( s t b c ) 。 空时编码( s t c ) 的概念是基于w in t e r s 在2 0 世纪8 0 年代中期所做的关于 天线分集对于无线通信容量的重要性的丌创性工作。9 0 年代s t a n f o r d 的 r a l e i g h 和c i o f f i 、瑞士a s c o m 的w i t t n e b e n 进一步奠定了空时码的基础。1 9 9 6 年g j f o s c h i n i 提出了在无线通信中采用多元天线构造的分层空时结构，1 9 9 8 年v t a r o k h 等人在此启发下，首先提出空时码的概念，信号在时间和空矧域上 都引入了编码，这就称为空时码。 空时编码的有效工作需要在发射利接收端使用多个天线，因为字时编码同时 利用时阳j 和空间两维柬构造码字，这样4 能有效抵消衰落，提高功率效率：并且 能够在传输信道中实现并行的多路传送，提高频谱效率。需要说明的是，空时编 码技术因为属于分集的范畴，所以要求在多敞射体的多径情况下应用，天线间距 应适当拉丌以保证发射、接收信号的相互独立性，以充分利用多散射体所造成的 多径。 空时编码方案结合了信道编码和多发送天线，通过空时编码后的数据被串并 转换成n 个数据流，每路数据流经脉冲形成、调制，然后通过n 个天线同时发 送到无线空间。在接收端，可以用单一天线，也可以用多个天线进行接收，每一 个接收天线接收到的是n 个发送信号与干扰噪声线性的叠加( 衰落系数为权重) ， 南京邮 u 学院坝j i 究生学位论文鹕一章绪论 然后通过最大似然检测的方法，f 确地识别出发送信号。空时译码算法和信道估 计技术结合以获得分集增益和编码增益。空时码集发射分集和编码于一体，具有 较好的频率有效性和功率有效性。 1 9 9 8 年，a 1 a m o u t i 首次提出了使用两个天线发射的空时分组码，该方案可 以获得最大分集增益和最大传输速率，是一种简单而有效的编码方案。根据诈交 设计理论的s t b c 无时日j 冗余，不能获得编码增益，却具有较低的译码复杂度， 利用最大似然译码算法即可，而且还可能得到最大的发射分集增益。空时分组码 可以实现与最大比合并( m r c ) 接收机相同的性能。 空时分组码应用在多径情况下可以有效抵抗衰落，本文将研究把l d p c 码应 用于空时分组码的m i m o o f d m 系统，并在多径信道下仿真其性能。 1 4 本文的内容与框架 本文对l d p c 码的构造、编码和译码算法进行了一系列的研究，并将l d p c 码应用于i e e e8 0 2 1 6 a 协议的o f d m 系统和m i m o o f d m 系统，对其性能进行 了仿真。本文从第二章丌始的内容如下： 第二章介绍了l d p c 码的基础知识与构造。 第三章主要讨论了l d p c 码的编码与译码。 第四章介绍了o f d m 的基本原理和空时编码技术。 第五章将l d p c 码应用于l e e e8 0 2 1 6 a 协议和空时编码的m i m o o f d m 系 统，对其性能进行仿真与分析。 南京| _ | | j u 学院删f 刈j 宄生学位论卫萌一幸l d p c 码摧础 第二章l d p c 码基础 l d p c 码是一种具有稀疏校验矩阵的线性分组码，所谓的“稀疏”就是 校验矩阵中l 的比例非常少，除了少数1 其他元素全为0 。l d p c 其他线性分组码一样，可以出校验矩阵h 描述。在域f 上，码长为n 。k l d p c 码，可由0 一女) 的校验矩阵爿描述：c ：= k ，”：胁7 = o ，码率，： 图2 1 是一个l d p c 码的校验矩阵，这个矩阵的每列都含有3 个l ，每行 有6 个1 ，这就是( 3 ，6 ) 萨则码。 h ： 1 1 o 1 o o 2 1l d p c 码的描述 1 1 o o 1 0 o 0 11 o0 11 1 o o l 剀2 j( 3 ，6 ) 止删l d p c 码 指其 码和 维的 都含 t a n n e r 提出用“二分图( b i p a r t i t e o r a p h ) ”来描述l d p c 码。二分图由变量 节点( v a r i a b l e n o d e s ) 、校验节点( c h e c k n o d e s ) 和连接两种节点的边( e d g e s ) 组成。变量节点对应码字中的编码比特或者是校验矩阵的列，而校验节点对应校 验比特或者是校验矩阵的行，：分图中的边则对应校验砸阵巾的1 ：零元素，当且 汉当编码比特j 参与了校验约束，时相应的变量节点平u 校验节点，之削有边相 连，并且对应校验矩阵的相应入口，= 1 。这样二分图便与l d p c 码一一对应。 用二分图表示l d p c 码的优点是便于理解译码和性能分析。图2 2 为图2 - 1 的( 3 ， 6 ) l d p c 码的二分图表示，图中左边的黑色节点表示变量节点，右边的白色节 点表示校验节点。从变量( 校验) 节点发出的边的数量称为变量( 校验) 节点的 次数( d e g r e e ) ，图2 2 的l d p c 码的所有变量节点的次数均为3 ，校验节点的次 数均为6 。所有从变量节点发出的边的总数等于所有从校验节点发出的边的总 南京l | | f l u 学院坝卜 d f 究生学位论史 鹕一幸l d p c 妈早础 数。根据变量节点和校验节点次数分句的不同，l d p c 码可以分为f 则( r e g u l a r ) 码和非f 则( i r r e g u l a r ) 码。g a l l a g e r 最初提出的l d p c 码就是正则码。 2 1 1 正则码 幽2 - 2( 3 ，6 ) 止则l d p c 码的二分幽 二分图中所有变量节点的次数都相同，所有校验节点的次数也都相同的 l d p c 码为f 则码，也就是二分图同则的节点都有年日同的边数与之相连。正则码 的校验矩阵所有行的重量相等，所有列的重量也都相等。定义为( 巩，以) 的正 则码表示该正则码的变量节点的次数为吐，校验节点的次数为d ，若校验矩阵月 是( m ，n ) 维，则码率 r ：尘旦：l 一生 门d c f 2 1 1 2 1 2 非正则码 在g a l l a g e r 最初提出的诉则码的所有变量节j _ ( 校验节点) 的次数都是一样 的t 实际上这种规定是不必要的，而且m a c k a ”n e a i 2 】和m l u b y 3 】等人发现 允许变量节点和校验节点的次数变化并仔细的选择他们的次数可以得到性能更 好的l d p c 码，这就是非萨则码。非讵则码通常用次数分斫】对( d e z r e ed i s t r i b u t i o n p a i r ) 来描述。 在l d p c 码的理论中通常会去关注的是一个码集而不是一些个别的码。这些 码集则可以由二分图集来定义【4 】【5 】。二分图集是根据一对次数分布束定义的。 南京| | | | 5 l u 学院坝l j 研究生学位论义 第一章l d p c 鹋早础 一个次数分命y ( x ) ：= ，x ”1 可以简单地用一个非负系数的多项式表示，并且该 多项式满足，( 1 ) = 1 。，表示了在二分图中与次数为f 的节点( 变量或者校验) 相 连的边的比例。利用缩写p 表示求和善等2l y b 域。p 的值是节点平均次数 的倒数。给出次数分布对( ，p ) 就可以决定该二分图集对应码集的码率r ( 五，户) m 小l _ 普 ( 2 - 2 ) 例如，图2 - 2 对应的次数分布对是b 2 ，x5 ) ，其对应的l d p c 码的码率为三。 由次数分布对( 五，p ) 和自然数 ( 作为码长) ，可以定义二分图集c ”( 五，p ) 。 所有在图集c “( a ，p ) 罩的二分图的左节点与丑0 ) ：= ，x ”1 相关，而右节点则与 p ( x ) ：= n x 1 相关，这些次数分御是边的左分布和右分布，通过转换这些边的 次数分布可以得到节点的次数分布 ( 2 - 3 ) f 2 4 ) 每一个c ”n ，p ) 中的二分图的次数为f 的变量节点的个数为 互，次数为f 的校验节点个数为( 1 一r ( 丑，p ” 声，。如此，由变量节点出发可得二分图中边的总 数为 e = m 互= 鲁 j li l 由校验节点出发同样可以得到二分图中边的总数 ( 2 5 ) 2 驴砒砌声一= ( 1 以p ) ) 亡 ( 2 - 6 ) ，2 li 口 由( 2 5 ) 和( 2 6 ) 可以推出码率的公式( 2 2 ) 。 现在由给定的次数分布对( ，p ) 和自然数n 来得到一个二分图的集合 9 土巾旦巾 j l 等 丑 万 南京| t 【| ：t l 学院坝i 州究生学世论立 猜，幸l d p c 蚂枯础 c “，p ) 。假设所选择的( p ) 和n 使得所有节点和边的个数都为整数，可以任 意的给定这些节点一个固定的顺序。集合c ”( 丑，p ) 中的任一个j 分图都有”z 个 变量节点的次数为，( 1 一r ( ，尸) ) n 芦，个校验节点的次数为f 。剩下的问题是随机 的构造二分图中的边生成集合( ( 五，p ) 。设想一个次数为f 的节点有i 个插孔 它的f 条边从这些插孔延伸出来，可以给这些插孔编号，这样图的左右各有总边 数个编号的插孔。令仃为【e 】：= l ，e ) 上的一个排列。通过将左边第f 个插孔 与右边第盯( f ) 个插孔相连接，就将一个二分图与一种排列对应起来。令a 取遍( 的e ! 个排列集合就得到一个二分图集合。再贼予这些排列相等的概率就得到一 个等概分却的二分图集合c ”( 五，p ) 。 把二分图集合c ”( 丑，p ) 中任一二分图与l d p c 码对应起来，等价于将二分图 与l d p c 码的奇偶校验矩阵对应起柬。最自然的方法如下：当第f 个右节点与第 个丘节点相连时将二元域上校验矩阵的第f 行第，列的元素置为1 。但是，由于 集合c ”似，尸) 中二分图的节点之问有可能出现多条相连的边，需要更加细致的定 义二分图和校验矩阵之间的对应方法。如果编码在域g f ( 2 ) 上进行，一种对应方 法是当第f 个右节点与第个左节点有奇数条边相连时，将矩阵第f 行第，列 的元素置为l ，否则为o ，这就消除了重边的问题。但是某些情况需要更细致的 对应方法，方便的是用如下方法建立的二分图对应矩阵：如果第f 个右节点和 第个左节点有d 条边相连，那么矩阵疗的第，行第列有( ，个为l 的矩阵元。 这种矩阵称为扩展奇偶校验矩阵或二分图的扩展邻接矩阵。昆然矩阵片等价于 h 的模2 和。在后续的文章中如果泌到一分图| 勺邻接矩阵和扩展邻接矩阵是分 别指矩阵和。这样山于每一个二分图都有个与之对应的编码，我们将不 加区别的使用二分图和编码这两个概念。 通过优化节点的次数分布，非正则码的性能比正则码有较大的提高。在非j 下 则码译码过程中，次数高的变量节点因为受到较多的校验约束，将较快地被f 确 译码，这样它们就可以给相连的校验节点更加有效的概率信息，而这些校验节点 o 籀一幸l ，d p c 蚂早础 又可以给与它们相连的次数较小的变量节点提供更可靠的译码信息，这就是所谓 的“波浪效应”。 从变量节点的角度来看，其次数越高越好，剥它进行监督的校验节点越多， 它就能从更多的校验节点得到更多的译码信息，使得它能更快更准确地被译码； 但从校验节点的角度看，却恰恰相反，次数越低就能给相邻的变量节点提供更有 效的校验信息。显然对于这一矛盾，非一则码比正则码更好的实现了两者的平衡。 2 1 ，3 非正则码的次数分布对的优化 采用迭代消息传递译码的l d p c 码存在噪声门限现象( n o i s et h r e s h o l d ) ：如 果信道噪声水平低于i 、1 限值，码集中几乎任何一种码都会随着迭代次数或码长的 增加，误码率将趋于零：反之，如果信道噪声水平高于门限值，误码率将大于某 一f 常数而不管码长多长迭代多少次。门限值可看成是码容量( c a p a c i t y ) ，它表 征了l d p c 码能够容忍的信道环境的恶劣程度。 g a i l a g e r 在文献 1 】中分析了币则码在b s c 信道中的性能。l u b y 等发现噪声 门限现象同样存在于非币则码【3 】，并且设计出在b e c 信道中很接近香农限的非 币则码。r i c h a r d s o n 等把这个概念推广到m p 算法集( 包括b p 算法) ，提出密度 演进( d e ：d e n s i t ve v o l u t i o n ) 的数值计算方法，通过考察译码消息的概率密度函 数( p d f ) 在译码迭代中的演进情况，分析译码是否收敛从而计算得到噪声门限。 密度演进是基于泽码算法的，它与系统中所使用的译码器相关，由于译码幸月始信 息与信道相关所以同时信道类型也对密度演迸有影响。l d p c 码的内在结构( 正 则非币则性、次数分布等) 是决定门限值或码容量的决定因素。 既然l d p c 码有对应的噪声门限值，因此优化设计l d p c 码就是在次数分 柿对的解空1 日j 中搜索具有高门限值的l d p c 码。非t t ：则码的优化是一个非线性价 值方程最小化问题，在这方面主要有微分演进( d i f f e r e n t i a le v o i u t i o n ) 和粒子群 体优化算法( p s o ) ，其中微分演进已经成功地应用到删除信道、a w g n 信道【1 5 和非相干平坦瑞利衰落信道 1 7 】的非正则码优化。 南京【i | | j l u 学院坝u i 宄生学位论文 第一章l d p c 码牡础 2 1 4 正则码和非正则码的性能比较 j j 罪型器码 k = q 照 一 k、 、 、 一， 气 j j 釜 l 、 f 嶂 00 5 e b ，n o ( db ) 52 削2 3 码k ：1 0 0 2 码率1 2 的止| l ! | j 码与1 fj 【：! j ! | j 码的性能比较 斗正则码 。 e _ 非正则码 、 t 、 l 、 。 、 、 心 e b ，n o ( d b l 幽2 4 码艮1 0 0 2 码率i 2 的：则鸭与1 f 正! j 1 1 j 码的平均迭代次数 本节对码长为l 0 0 2 、码率为l 2 、的( 3 ，6 ) 诈则l d p c 码和同码长、同码 市京l u 学院埘：l 。驯究生学位论文 鹚一章l d p c 妈早础 率的非f 则l d p c 码进行了性能仿真。非于则码的次数分柿对为 ：2 0 3 3 0 2 ，五，2 0 2 5 0 l ，五42 0 1 ( ) 9 8 ，五52 0 3 0 9 9 ，p 5 2 0 0 3 4 3 ，p 2 0 ，7 9 6 3 尸7 = o 1 6 9 3 。仿真的环境是a w g 信道，b p s k 调制。 图2 3 给出了正则码和非f 则码的误比特率与信噪比的性能曲线，可以看到 非正则码的性能明显好于正则码的。图2 4 给出的是两种l d p c 码的平均译码迭 代次数的比较，显示出非f 则码在同信噪比时所需的译码迭代次数也要少于f 则 码。因此在相同情况下，非正则码可以在更快的译码时间内达到更好的译码性能。 2 1 5 多元域的l d p c l d p c 码的定义可以推广到多元域g f ( 目1 。多元域上的l d p c 码具有较二进 制l d p c 码更好的性能，而且研究表明在越大的域上构造编码，它的性能可以得 到越大的提高l o 。 因为对于l d p c 码来说，如果它的校验矩阵h 列重量足够大，那么它可以 更接近香农限。但是如果增加列重量，这会使得二分图中圈的数目急剧增加，从 而使迭代译码算法的性能下降。而在g f ( q ) 域上构造的l d p c 码则可以解决这个 矛盾，它的校验矩阵可以增加与之对应的二进制校验矩阵奶中列的平均重量， 但它的二分图并没有改变，不会造成节点之问圈的数目的增加，从而使得译码性 能得到显著的提高，但随着性能的提高译码复杂度也会增加。 2 2l d p c 码的构造 l d p c 码的构造就是校验矩阵的构造，研究构造校验矩阵的目的是构造具有 优秀性能、计算复杂度低的校验矩阵。刈于l d p c 码末随，于其稀疏校验矩阵 的结构对码距和译码性能有较大的影响，构造l d p c 码的主要问题在于如何构造 没有短长度圈或圈的平均长度尽可能大的校验矩阵。下面以g i 九h ( 最小圈长) 的概念丌始介绍几种l d p c 码校验矩阵的构造方法，并将详细研究有效构造高 百r t h 的扩展比特填充算法。 南京邮 u 学院坝l 1 究生学位论文 筑幸l d p c 鹋桀础 2 2 1g i r d l 的概念 月三 剀2 5 含有g i r t h = 4 的罔的校验矩阵幽2 6 含有g i n h = 6 的罔的拨验矩阵 信息比特 校验约柬艇、麟 c lqc 3c 4 曲c 1 旬c 3c 4 如c 6 图2 7 含有g i 柏= 4 的罔的_ 二分幽 幽2 8 含有g l r t h = 6 的圈的一分幽 所谓的g i n h 就是二分图上最小圈的长度，圈的概念在图2 - 5 至2 8 形象地给 出。如果校验矩阵的两列( 行) 上同时有两个非零元处于相同的行( 列) ，那么 就会构成一个四边的闭合路径，如图2 5 所示，这个闭合路径通常称为圈( c y c l e ) 。 同时把圈的边数也就是圈中包含的非零元的个数称为圈长。图2 一j 中的圈的圈长 为4 。依此类推，只要用垂直和水平的箭头线能够把校验矩阵中的若干个非零元 连接起来形成闭合路径，并且保证垂直线不同列；水平线不同行，就表示有圈的 存在。如图2 6 ，校验矩阵h 的3 列、3 行：形成了一个长为6 的圈。图2 7 和2 - 8 分别为长度为4 和6 的圈在二分图中的表现形式。 通常在码长较短的情钞己f 校验矩阵( 二分网) 都会含有国，而当中最短的圈 的圈长就定义为陔校验矩阵( 二分图) 的g i n h 。g i r t h 的概念可以推广到节点， 假如经过节点“有长度为8 、1 0 、1 2 以及更长的圈，则我们说该节点“的g i n h 为8 。由此可以定义二分图中变量节点的g i n h 分布( g i n hd i s t r i b l i t i o n ) g ( ，) ， ，= 4 ，6 ，。一，。、是这个二分图中所有变量节点的g i r t h 的最大值，g ( f ) 为所有 g i r t h = ，的变量节点在所有变量节点中所占的比例。平均值1 艺( 2 t ) ，2 七则定义 南京邮i u 学院坝i = 1 j i 究生学位、色卫 鹚一年l d p c 峭毕础 为平均g i n h 。 对于l d p c 码来说，二分图中圈的存在是对迭代译码过程进行概率分析的一 个障碍，并且在后续的章节中介绍的l d p c 码的信息传递( m e s s a g ep a s s i n g ) 迭 代译码算法是假定变量节点相互独立的，对于没有圈的校验矩阵，信息传递算法 可提供最优解码，可以得到准确的后验概率。在信息传递算法中一个重要的原则 是外部信息的传递，也就是在迭代的过程中各边传递的信息均来自外部其他边信 息。而对于一个长度为，的圈，其中的节点发出的信息币反馈到自己所需要的迭 代次数为f ，2 。因此，构造具有高百n h 的校验矩阵具有很大意义。 2 - 2 2 各种构造方法 2 2 2 1g a l l a g e r 的构造方法 g a l l a g e r 1 】最初给出的( 巩，4 ) 萨则码的构造方法：对于码长为n 的( 巩， 4 ) f 则码，将校验矩阵按行水平的分割为巩个相同大小的子矩阵，每个子矩阵 的任列都只包含个非零元。第一个子矩阵以预定的方式构造，如可以用递减 的形式包含所有的非零元，矩阵的第，行所有的非零元都分布在第( ，1 ) 反十1 到磷 列。其它下面的吐1 个子矩阵都是第一个子矩阵的随机排列。这种构造方法可 如下表示： h = 1 1 1 1 1 1 l l 圩为第一个子矩阵，校验矩阵圩如下构造 h = 万( o ) ( 2 7 1 f 2 - 8 ) 这罩丌为矩阵日。的列置换。上面h 矩阵的第一个子矩阵为h 。，也可以用。 的任一置换代替，得到如下更加对称的构造方法： 南京i | | i f i u 学院f 喇i 。 l j | 宄生学位论义 第一辛i d p c 码璀础 月1 h o f ! ( h o ) ( 2 9 ) 2 2 2 2m a c k a y 的构造方法 m a c k a y 在校验矩阵中引入一些重量为2 的列，降低整个校验矩阵的重量以 减少二分图中圈的数量，由此降低圈对译码算法的影响。但是引入重量为2 的列 会导致低重量码字的出现，需要采取措施减少其的出现概率。m a c k a y 给出了如 下指导性的构造方法6 1 。 构造法1 a ：这是最基本的构造方法，该方法构造的矩阵每列的重量都为一固定 值，( 例如产3 ) ，随机的构造矩阵使得每行的重量尽可能的相等，而 每两列之问重叠的非