（信息与通信工程专业论文）ldpc码的编码调制研究.pdf

浙江大学硕上学位论文 摘要 摘要 低密度校验l d p c 码( l o w - d e n s i t yp a r i t yc h e c kc o d e s ) 是除了t u r b o 码 之外，又一类近香农限的编码方法。由于l d p c 码的出色译码性能，有关它的研 究成为当前的热点之一。在实际应用中，通信在很多情况下必须在频带受限的信 道下进行，所以对多进制调制和译码的研究就变得非常重要。 本文首先研究了多进制调制下l d p c 码的译码算法：广义迭代译码算法和多 进制调制下的二进制迭代译码算法。然后重点研究了多级编码调制的三种译码算 法：多级译码、并行译码和混合译码，并且在高斯信道下对其进行了仿真，仿真 结果显示混合译码的性能明显优于其它两种译码方法。在此基础上，对可分解的 l d p c 码进行了改进，将映射方式由传统的o n g e r b o e c k 分集方式改为块分集方式， 译码方法由多级译码改为混合译码，并且分别在高斯信道和r a y l e i g h 信道下进 行了仿真。仿真结果显示改进后的可分解的l d p c 码不仅在性能上有了很大提高， 并且能提供不等性能保护u e p 。 关键字：l d p c 码，多进制调制，多级编码，混合译码，集分割，高斯信道，r a y l e i g h 衰落信道 浙江大学硕士学位论文a b s t r a c t a b s t r a c t b e s i d e st u r b oc o d e s ，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 sf o r ma n o t h e rc l a s s o fs h a n n o nl i m i t ( o rc h a n n e lc a p a c i t y ) - a p p r o a c h i n gc o d e sw h i c hh a sa t t r a c t e d b o o m i n gi n t e r e s ti n t h el a s tf e wy e a r sb e c a u s eo ft h e i re x c e l l e n t d e c o d i n g p e r f o r m a n c e i np r a c t i c e ，c o m m u n i c a t i o ni su s u a l l yw o r k i n gu n d e rb a n dl i m i t e d c h a n n e l s ，s oi ti sv e r yi m p o r t a u tt oi n v e s t i g a t et h ep e r f o r m a n c eo fm a r ym o d u l a t i o n a n di t sd e c o d i n g t h i sp a p e rf i r s ts u m m a r i z e st h ea l g o r i t h m so fl d p cd e c o d i n gu n d e rm r a y m o d u l a t i o nw h i c hc o n t a i n sg e n e r i ci t e r a t i v ed e c o d i n ga l g o r i t h m sa n db i n a r yi t e r a t i v e d e c o d i n ga l g o r i t h m s t h e nw ef o c u so nt h ed e c o d i n ga l g o r i t h m so fm u l t i l e v e lc o d e d m o d u l a t i o n ，i n c l u d i n gm u l t i - s t a g ed e c o d i n g ，p a r a l l e ld e c o d i n ga n dh y b r i dd e c o d i n g ， a n dt h e i rs i m u l a t i o nr e s u l t su n d e ra w g nc h a n n e la r ec o m p a r e d i ti m p l i e st h a tt h e p e r f o r m a n c eo fh y b r i dd e c o d i n gi sb e t t e rt h a no t h e rd e c o d i n ga l g o r i t h m s n e x t ，t h e d e c o m p o s a b l el d p c i si m p r o v e d ，w h i c hc h a n g e st h eu n g e r b o e c ks e t t i n gp a r t i t i o nt o b l o c kp a r t i t i o na n dc h a n g e sm u l t i - s t a g ed e c o d i n gt oh y b r i dd e c o d i n g t h es i m u l a t i o n u n d e rb o t ha w g na n dr a y l e i g hf a d i n gc h a n n e ls h o w st h a tn o to n l yt h eb i te r r o rr a t e p e r f o r m a n c ei si m p r o v e ds i g n i f i c a n t l yb u ta l s ot h eu n e q u a le r r o rp r o t e c t i o nf e a t u r e c a nb eu t i l i z e d k a yw o r d s ：l d p c ，m a r ym o d u l a t i o n ，m u l t i l e v e le n c o d i n g ，h y b r i dd e c o d i n g ，s e t p a r t i t i o n i n g ，g a u s sc h a n n e l ，r a y l e i g hf a d i n gc h a n n e l 1 1 1 浙江大学硕士学位论文 图目录 图目录 图卜1数字通信模型框图1 图2 1规则l d p c 码的t a n n e r 图1 1 图2 2校验节点信息更新图1 3 图2 3比特节点信息更新图13 图3 1传统的b i c m 系统框图1 9 图3 2码字为l d p c 码的b i c m 系统框图2 0 图3 3多级编码器的系统框图2 1 图3 4 传统的u n g e r b o e c k 分集方式的分集方法图2 2 图3 5u n g e r b o e c k 分集( u p ) 8p s k 2 2 图3 6u n g e r b o e c k 分集( u p ) 1 6 q a m 2 3 图3 7 块分集( b p ) 8p s k 23 图3 8 块分集( b p ) 16 q a m 2 3 图3 9非标准分集( u b p ) 1 6q a m ( 1 ) 2 4 图3 1 0 非标准分集( u b p ) 1 6q a m ( 2 ) 2 4 图3 1 1 四级的多级译码( m s d ) 框图2 6 图3 1 2 四级的多极并行译码( p d l ) 框图2 7 图3 13 四级的混合译码( 1 ) 框图2 7 图3 1 4 四级的混合译码( 2 ) 框图2 8 图3 1 5 子码是基于欧氏几何的( 1 0 2 4 ，7 8 1 ) l d p c 码的多级译码性能曲线 图2 9 图3 1 6 子码是基于欧氏几何的( 1 0 2 4 ，7 8 1 ) l d p c 码的多级译码下的各 级平均迭代次数曲线图3 0 图3 1 7 子码是基于欧氏几何的( 1 0 2 4 ，7 8 1 ) l d p c 码的混合译码性能曲 线图3 1 图3 1 8 子码是基于欧氏几何的( 1 0 2 4 ，7 8 1 ) l d p c 码的混合译码下的各 级平均迭代次数曲线图3 2 图3 1 9 子码是基于欧氏几何的( 1 0 2 4 ，7 8 1 ) l d p c 码另外一种混合译码 性能曲线图3 3 v i 浙江大学硕士学位论文图目录 图3 2 0 子码是基于欧氏几何的( 1 0 2 4 ，7 8 1 ) l d p c 码，映射方式分别采 用u p 、b p 、u b p 的译码性能对比曲线图3 5 图4 1高斯信道模型3 9 图4 2r a y l e i g h 衰落信道模型4 0 图4 3可分解的l d p c 码的编码框图4 1 图4 4可分解的l d p c 码的编码调制以及多级译码框图4 2 图4 5可分解的( 4 0 9 6 ，2 8 0 0 ) l d p c 码译码为多级译码，与基于二进制 译码的性能对比曲线4 4 图4 6 可分解的( 4 0 9 6 ，2 8 0 0 ) l d p c 码，译码为多级译码，与广义迭代 译码算法的性能对比曲线4 5 图4 7可分解的l d p c 码的编码调制以及混合译码框图4 6 图4 8改进后的可分解的l d p c 码总的译码性能和各级子码的译码性能曲 线，a w g n ，1 6 q a m 4 8 图4 9改进后的可分解的l d p c 码和采用u n g e r b o e d k 集分割方式和多级 译码的可分解l d p c 码的译码性能曲线，a w g n ，1 6 q a m 4 9 图4 1 0 改进后的可分解的l d p c 码和采用广义迭代译码算法的可分解l d p c 码的译码性能曲线，a w g n ，1 6 q a m 5 0 图4 1 1 采用u n g e r b o e d k 集分割方式和多级译码的可分解l d p c 码的平均 迭代次数曲线，a w g n ，16 q a m 5 1 图4 1 2 改进后的可分解的l d p c 码采用块分集的集分割方式和混合译码的 平均迭代次数曲线，a w g n ，16 q a m 5 1 图4 1 3 改进后的可分解的( 4 0 9 6 ，2 8 0 0 ) l d p c 码的译码性能曲线5 5 图4 1 4 改进后的可分解的( 4 0 9 6 ，2 8 0 0 ) l d p c 码的平均迭代次数曲线5 5 图4 1 5 可分解的( 4 0 9 6 ，2 8 0 0 ) l d p c 码的译码性能曲线5 6 图4 1 6 可分解的( 4 0 9 6 ，2 8 0 0 ) l d p c 码的平均迭代次数曲线5 6 图4 1 7 改进的可分解l d p c 码和改进的广义迭代译码算法的性能对比曲线 5 7 v l i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得逝姿盘鲎或其他教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 学位论文作者签名：尕5 唧 签字日期：p 7 啤；月7 汐日 学位论文版权使用授权书 本学位论文作者完全了解逝姿盘堂有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权坐 鎏盘堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：张台锢c 7 3 签字日期：如p 年弓月p 日 导师虢黼? = 5 ，磅 i 签字日期：扫f 口年弓月f 口日 学位论文作者毕业后去向：浙江杭州依赛通信有限公司 工作单位：杭州依赛通信有限公司 电话：0 5 7 1 - - 8 8 8 6 5 1 3 3 通讯地址：杭州市文三路3 9 8 号东方通信大厦7 楼 邮编：3 1 0 0 1 3 浙江大学硕士学位论文 致谢 致谢 首先要感谢我的导师陈惠芳副教授和谢磊副教授，在我读研的两年半时间 内，他们给了我无微不至的关心和帮助。他们悉心指导我的学习研究。没有他们 给予我的帮助，我是不可能顺利完成学业的。他们的学识和人格魅力深深影响着 我，在以后的人生道路上我会永远以他们为榜样，并将永远感谢他们的教导。 我还要感谢我的父母，他们时时刻刻关心着我。虽然他们不在我的身边，但 是他们时刻关心我的学 - - j 和生活，在我遇到困难的时候鼓励我，支持我。我将永 远记住他们对我的养育之思。 我还要感谢已经毕业的刘亚师兄，正是有了他的前期理论成果才使我比较顺 利并完整的完成硕士论文，与他的讨论使我受益匪浅。 我还要感谢给予我帮助的高明师兄，汪莹博士，王政博士，金煦硕士，李珊 硕士，艾鑫硕士，李振华硕士，王徐敏硕士，华磊硕士，杨磊硕士，朱诗宇硕士， 与他们的讨论和交流对我的科研工作带来了很大的帮助。跟他们在一起学 - - j ，我 感到很快乐，和他们的友情我会永远珍惜。 我还要感谢我的男朋友张超硕士，在我读研期间他一直陪伴着我，当我在学 - j 和生活中遇到困难的时候，他会鼓励和支持我，让我学会乐观的生活态度。 最后，我想怀着一颗感恩的心，祝福我的亲人、导师、朋友一生平安。 浙江大学硕士学位论文绪论 第1 章绪论 本章介绍了本文的组织结构和研究方向。首先介绍了数字通信的基本模型和 编码调制的概念，接着介绍了l d p c 码在国内外的研究历史与现状，最后给出了 本文的组织结构和主要贡献。 1 1数字通信模型 近年来，有关数字信息如何能够被更有效、可靠的传输已经成为数字通信领 域的研究热点。本文的研究内容是基于l d p c 码的编码调制，是数字通信系统的 一部分，所以本节重点介绍数字通信系统的模型以及系统中各部分的功能和作 用。数字通信系统的模型框图如图1 - 1 所示： 图卜1 数字通信模型框图 图1 - 1 的上半部分是整个系统的发送部分，包括信源编码、信道编码以及数 字调制。而下半部分是整个系统的接收部分，是发送部分的逆变换，包括数字解 调、信道译码和信源译码。 信源产生数字通信系统要传送的信息，可以是模拟信号也可以是离散信号， 通常是由符号序列或时间函数组成。 信源编码将信源发送出的信号转换成数字序列，即二进制比特序列。信源编 码从本质上讲，是将信源输出的信号进行压缩，消除信源信息中的冗余度，提高 传输效率。但是这样做都是基于一个原则，就是在接收端能够将信源信息无损的 恢复重建出来。 信道编码的作用是把信源编码器输出的数字系列转换成适合于信道传输的 浙江大学硕士学位论文 绪论 符号序列。信道编码的目的是通过对消息序列引入一定的冗余度，对其输出序列 提供保护，来抵抗信道噪声产生的干扰n 1 ，提高信号的抗干扰能力。信道编码还 可以在系统带宽，信号功率以及硬件复杂度受限的情况下，增加通信的可靠性。 数字调制：离散信号不适合在物理信道或者数字存储媒介上传输和记录，所 以这就需要数字调制器来将码字序列转换成能够适合信道传输的连续波形信号。 调制方式的不同，可以在物理信道上传递不同数量的信息比特，可以根据实际需 要选择不同的调制方式。 数字信号传输时经过信道会叠加上信道中的噪声和干扰。常用的信道有电话 线、微波、卫星传输、光缆等。 在接收端，数字解调器的作用是对加噪后的信号波形进行处理，将其还原为 二进制比特序列，来表示对所发送数据码元的最优估计。 信道译码：将信道接收下来的比特序列转换成信息估计序列。译码器采用的 译码方法是根据信道编码方法和信道噪声特性来选择的。信道译码的作用是使信 道噪声所造成的信号判决错误最少。在理想条件下，尽管由于噪声的影响会导致 信道译码器接收到的序列并不是码字，但是通过合适的译码方法，信道译码器输 出的信息估计序列应该同经过信源编码后的信息序列完全一样。评价编码器和调 制器性能的好坏，主要是看译码后的码字的误码率。 最后一步是信源译码，是信源编码的逆过程。它的作用是从信道译码器中接 收信息估计序列，重新构造信源原始信号。由于信道译码可能出现的错误，以及 信源编码器中可能引入失真，所以信源译码器输出的信号可能只是信源信号的近 似。信源信号与重构信号间的差别代表了数字通信系统引入的失真程度。 1 2 编码调制 传统上，数字通信系统中的编码与调制是作为两部分分开考虑的，调制器与 解调器将模拟波形信号转换为数字离散信号，而编码器和解码器则用于纠正信号 在数字信道中发生的错误。编码效率越低，即码字中的校验比特所占的比重越大， 码的纠错性能越好，但增加了带宽和译码的复杂性。对于功率受限的信道，为了 达到所需的性能，可以用频带的展宽换取功率的节省。但是考虑到频带受限的问 题，过去不能将编码方案用于频带受限的信道中。实际上，在这样的信道中，为 了达到高效传输的目的，经常使用一些高效调制技术，例如正交幅度调制( q a m ) ， 浙江大学硕上学位论文绪论 相位调制( m p s k ) 等。 编码调制乜1 ( c o d i n gm o d u l a ti o n ，c m ) 的中心思想是将编码与调制结合起 来实现系统的最优化设计，以提高数据传输系统的性能。高效编码调制与传统的 将纠错编码与调制分离的技术相比，其最大的优越性就在于能够在既不展宽频带 又不降低有效数据传输率的前提下，提高系统的性能。 1 3 l d p c 码的研究历史与现状 l d p c 码是除了t u r b o 码之外的另一类接近香农限的编码方法。它最早由 g a l l a g e r 在2 0 世纪6 0 年代初发现d 1 。但是人们并没有重视这个重大发现，后来 t a n n e r 在1 9 8 1n 1 年首次用图论的方法描述l d p c 码，打破了这一局面。但是一直 到1 9 9 0 s b 印 1 ，迭代译码在l d p c 码上的应用，人们才真正开始重视l d p c 码，并 出现了典型的译码算法，即s u m - p r o d u c t 算法和m i n - s u m 算法。研究已经证实， 足够长的l d p c 码经过迭代译码算法的性能，非常接近香农限畴1 。这个发现使得 l d p c 码在纠错码领域可以跟t u r b o 码相媲美，并且之后在许多通信领域和数字 存储系统得到广泛应用。 与t u r b o 码相比，l d p c 码具有以下优点：第一，l d p c 码不像t u r b o 码那样 需要长的交织器来达到好的纠错性能；第二，l d p c 码具有很好的分组纠错性能； 第三，误码平层出现在很低的b e r 上；最后，译码不用基于网格图。 正因为l d p c 码具有如上所述的优点，很多学者都致力于这方面的研究。到 目前为止，l d p c 码的研究主要集中在以下几个方面： 一、校验矩阵的构造 g all a g e r 在提出l d p c 码的时候就给出了一种编码方法，我们称之为 g a l l a g e r 构造法1 。这是一种随机构造校验矩阵的方法，它构造出来的校验矩阵 具有行重和列重固定的特点，并且列重大于等于3 ，校验矩阵中的元素均匀分布。 这一类随机构造法还有m a c k a y 构造法拍1 、d a v e y 构造法、p e g 构造法n 4 1 等。其 中m a c k a y 构造法构造的校验矩阵，其对应的t a n n e r 图中循环的数目最少，而且 同时又引入列重为2 的列；d a v e y 构造法是在m a c k a y 矩阵的基础上，把单位矩 阵划分成维数更小的多层单位矩阵，得到的矩阵被称为超轻矩阵；p e g 构造法是 按照e d g e b y e d g e 的方式在校验节点和变量节点之间建立连接，关键的一点是 浙江大学硕士学位论文绪论 在增加新边时尽量使图的g i r t h 最大。这些方法都是利用计算机按照一定的规律 进行搜索，没有一定的数学结构，所以编码复杂度很大。 跟随机构造法对应的是结构构造法。这种方法构造的校验矩阵具有确定的结 构，编码实现简单，使得硬件实现比较简单，推动了l d p c 码的实用化。这种方 法主要分为两个研究方向，即有限几何构造法n 7 ，川和组合设计法n 卜2 6 1 。有限几何 构造法是利用空间中的点和线的结构来构造校验矩阵，这种方法构造出来的校验 矩阵是规则的，因为行重是线上包含的点数，而列重是空间中相交于一点的线的 条数。很重要的一点是，这种方法构造出来的校验矩阵对应的t a n n e r 图中是没 有四环。另外，由于构造校验矩阵是根据空间几何的原理，所以编码的复杂度比 较低，利用仿真和实现。组合设计法又称为平衡不完全区组设计( b i b d ) ，可以 用来构造无四环的校验矩阵。 在时变信道下，由于信道特性不是一成不变的，所以要想达到好的纠错性能， 就需要根据信道情况改变l d p c 码的码率，这就衍生出一个研究方向，即速率兼 容l d p c 码的构造瞳7 刮。这种构造方法分为两种，一种是随机删除，一种是最佳 删除。前者是不考虑其他因素，只是将母码中的一些比特随机删除，从而得到一 个不同码率的码字，因为它的随机性，所以性能不一定会好。后者就是解决某些 性能不好的方法。通过某些方法，既得到想要的码率，又能得到比较好的译码性 能。 二、译码算法研究 l d p c 码的译码算法分为两类，即基于硬判决的译码和基于软判决的译码。 基于硬判决的译码的运算量低，复杂度小，比较实用，但是译码性能不如基于软 判决的译码。基于软判决的译码的译码性能比较好，但是复杂度高。所以近年来 各种软硬结合的算法的提出，推动了l d p c 码的实用化。 在t a n n e r 用图论的方法描述校验矩阵之后，l d p c 码才真正被重视起来，一 个重要的原因就是，基于t a n n e r 图的译码算法的复杂度和计算量都大大降低。 l d p c 码的典型译码算法就是基于t a n n e r 图，即我们常说的置信传播的算法，也 叫做消息传递算法。这一类算法又分为两种主要的算法，即s u m - p r o d u c t 算法和 m i n s u m 算法。其中m i n - s u m 算法是s u m p r o d u c t 算法的简化算法，所以在性能 上要比s u m - p r o d u c t 算法差一些。这两种算法已经被广泛应用于二进制译码中， 4 浙江大学硕士学位论文 绪论 而且译码性能良好。而且在二进制下，可以将译码算法应用到对数域，算法中的 乘法可以用加法代替，从而降低了计算复杂度。但是对于广义迭代译码算法，由 于其巨大的计算量，使得在多进制调制下的译码复杂度太高，应用起来就会受到 限制。所以很多学者致力于这方面的研究，以期寻找降低复杂度的算法，达到复 杂度和性能的折中。 还有一类算法是比特翻转算法( w b f ) ，这是g a l l a g e r 在提出l d p c 码时提出 的一种译码算法1 。在传输过程如果有可检测的错误发生，就会有相应的校验方 程不满足，错误图样中的某些位就会等于1 。比特翻转算法正是利用了接收序列 的某些比特翻转与相应的校验方程失败的数目的变化进行译码的。这种算法具有 与硬判决相同的计算量，但是又可以获得比硬判决更好的性能。后面的学者研究 和改进的主要是如何能更准确地定位发生错误的比特位置，以及如何降低计算 量。 当应用到中等长度的码时，消息传递算法的性能要比最大似然译码( m l d ) 算法差一些，这主要是由迭代译码方法本身的缺陷和码结构中短环的存在造成 的。针对这一情况，又有一种算法，它是一种连续阶段上进行重处理的策略，被 成为分阶统计译码( o s d ) 6 8 1 考虑到复杂度的问题，0 s d 算法只能进行很小的 重处理阶段。0 s d 算法的核心主要包含两部分，即构建最可靠的信息集合和系统 处理最可靠集合中的候选码字。 目前二进制下的译码算法算法已经比较成熟了，但是多进制下的译码算法由 于过高的译码复杂度，导致应用受限。所以，如何在不降低译码性能的情况下， 降低多进制译码复杂度是目前的一个重要研究方向。 三、码字结构优化 译码性能的好坏跟码字结构有很大的关系。由于在利用b p 算法进行译码的 时候，信道参数存在一个门限值，在低于门限值的时候，随着迭代次数的增加， 可以减小错误概率到任意小，但是一旦高于这个门限值，算法不再随着迭代次数 的增加而收敛。所以研究l d p c 码的渐进性就显得很重要，我们研究的主要工具 就是密度进化理论( d e ) n 。4 1 1 和外部信息转移图( e x i t ) 4 2 , 4 3 。这两种工具都是 为了分析迭代译码的收敛性。 密度进化理论中还有一种重要的方法，就是高斯近似，它是一种估计码的极 浙江大学硕士学位论文绪论 限和设计好码的度数分布的简化方法，它可以将多维校验消息和变量消息的密度 进化简化为一维均值的进化，从而可以大大降低计算量，这种方法也是因此而得 名。对于规则码，在a w g n 信道条件下，初始消息服从均值为2 o 2 ，方差为4 o z 的高斯分布。研究表明高斯近似与密度进化计算出来的信道参数的极限值仅仅相 差0 3 1 2 。不管对于规则码还是非规则码，度数分布不同，码容量不同。 所以在给定码率，要达到的错误概率，一定的迭代次数以及不同的码参数的情况 下，密度进化分析得到的信道参数极限是不一样的。 e x i t 是一种分析迭代译码收敛性的有力工具，它是从互信息的角度分析译 码的收敛性。目前已有将变量节点与校验节点度数进行联合优化的方法，得到了 距离香农限更近的度数分布乜1 。 四、编码调制 随着通信技术的发展，带宽的有效利用变得越来越重要，通常是采用多进制 调制方式来提高带宽利用的有效性。所以研究多进制调制下码字的译码性能就势 在必行。l d p c 码的编码调制系统主要有两个方向，一个是多级编码调制( m l c ) 4 4 - 4 5 1 ，另一个是比特交织码调制系统( b i c m ) 4 9 - 5 1 1 。这个两个系统都是基于多进 制调制的，两个系统的区别在于b i c m 只需要一个编码器和一个译码器，而m l c 可以采用多个编码器和译码器。 对于比特交织码调制系统( b i c m ) 的研究目前主要是译码算法的简化研究， 即在尽量不降低译码复杂度的情况下，降低译码算法的复杂度。 m l c 可以根据信道情况选择合适的码率，并用相应的译码器进行译码。而且， 编码器可以相同也可以不同，所以在码率的选择上m l c 具有更大的灵活性。二者 相比，m l c 有一个很重要的优点就是，由于每一级的译码器是单独的，所以可以 实现并行译码，从而大大降低译码复杂度。m l c 的译码方法主要是多级译码( m l c ) ， 并行译码( p d l ) ，另外还有一些译码方法是以上两种的结合，即基于多级译码和 并行译码的混合译码算法。多级译码的特点是除了第一级之外，其他各级译码的 初始信息不仅是信道接收来的，还要利用前面几级的译码结果，所以这种方法可 能会受到“错误传递”的影响，而使译码效果比较差。并行译码的特点是每一级 的译码是独立的，所以不会存在“错误传递”的问题。不同的译码方法对应于不 同的映射方式b 2 5 才能达到比较好的译码性能。基于l d p c 码的m l c 系统在衰落 6 浙江大学硕士学位论文 绪论 信道下也能够取得很好的性能。与b c h 码相比，l d p c 码在性能上有很大的提高。 比特交织码调制系统的译码算法主要是广义迭代译码算法，以及基于广义迭代译 码算法的改进算法。根据调制方式的特点，对广义迭代译码算法进行简化，以期 达到降低译码复杂度的目的。 五、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 不对称解决方案， 即下行链路采用l d p c 码，而上行链路采用t u r b o 码。这种方法已被用于i e e e 8 0 2 1 1a b gw l a n ，使得移动终端的电池使用寿命延长了4 倍。另外，l d p c 码 的一个很重要的应用是用于d v b - $ 2 4 1 ( 欧洲新一代数字卫星广播标准) 上，与 第一代相比，它的最大变化是编码方式上将l d p c 码作为内码，b c h 码为外码， 这种级联码的性能非常好，在距离香农限仅0 7 到1d b 的情况下可以得到准无 误码的接收，比d v b s 标准提高了3 d b 。同样地，在我国的数字电视地面传输 标准中钉，l d p c 码也成为了信道编码的重要解决方案。 另外，在链路自适应技术u 们，物理层、应用层的联合优化系统中b ，l d p c 码也有很重要的应用。在图像数字水印系统中，也用到了l d p c 码。可见，l d p c 码的应用是非常广泛的。 1 4 本文的组织结构和贡献 本文的组织结构如下： 第二章首先介绍了l d p c 码的基本概念以及校验矩阵的t a n n e r 图表示法，然 后介绍了基于t a n n e r 图的迭代译码算法的原理。在此基础上介绍了典型的消息 传递译码方法m i n s u m 算法和s u m - p r o d u c t 算法。最后介绍了多进制调制下的二 进制迭代译码方法。 第三章首先介绍了编码调制的概念，然后介绍了多进制调制系统。l d p c 码 的多进制调制系统主要分为两类，即比特交织码调制系统( b i c m ) 和多级编码调 制系统( m l c ) 。本章重点讨论了多级编码调制系统，在介绍了基本概念和集分割 的定义以及方式之后，又介绍了多级编码的三种译码方法。最后对三种译码方法 在加性白高斯信道下进行了仿真，并给出了译码性能曲线。 第四章是本文的重点。首先简要介绍了可分解l d p c 码的定义和由来，然后 浙江大学硕士学位论文 绪论 针对之前的调制方式和译码性能存在的问题，在a w g n 信道条件下进行了改进。 通过改变调制方式以及译码方式，实现了性能上的提高。并且对改进后的系统在 r a y l e i g h 信道下进行了仿真，并给出了性能曲线。 第五章是本文的总结与展望。 浙江大学硕：上学位论文l d p c 码及多进制调制下的译码算法 第2 章l d p c 码及多进制调制下的译码算法 l d p c 码是除了t u r b o 码之外的另一类接近香农限的编码方法。它最早由 g a l l a g e r 在2 0 世纪6 0 年代初发现b 1 。但是这个重大的发现当时并没能引起人们 的注意，这主要是因为当时的计算能力有限。2 0 年后，t a n n e r 用图论的观点重 新阐释了l d p c 码n 1 ，但是由于没有合适的译码算法，这个发现再次被忽略了。 一直到1 9 9 0 s ，迭代译码的提出，才真正引起人们对l d p c 码的重视，并提出了 典型的译码算法，即s u m - p r o d u c t 算法和m i n - s u m 算法。研究已经证实，足够长 的l d p c 码经过迭代译码算法译码后的性能，非常接近香农限。这个发现使得l d p c 码在纠错码领域成为t u r b o 码的最大竞争者，并且之后在许多通信领域和数字存 储系统得到广泛应用。与t u r b o 码相比，l d p c 码具有以下优点：第一，l d p c 码 不需要长的交织器就能达到好的纠错性能；第二，l d p c 码具有好的分组纠错性 能；第三，误码平曾出现在很低的b e r 上；最后，译码不基于网格图。 本章我们将首先介绍l d p c 码的基本概念和t a n n e r 图表示方法，接着，介绍 l d p c 码的迭代译码算法，重点介绍广义迭代译码算法和多进制调制下的二进制 迭代译码算法。 2 1l d p c 码的基本概念及t a n n e r 图表示 一个长度为咒的线性分组码可以由一个生成矩阵或者一个校验矩阵唯一确 定，如果它由校验矩阵h 确定，则这个码字是校验矩阵的零空间。一个g f ( 2 ) 域 上的r 维向量v = ( v 。，v v 川) 要想成为一个码字，它必须满足v 木h r = 0 。简单 地说，码字c 的每一个比特必须满足校验矩阵每一行代表的校验方程。l d p c 码就 是由校验方程确定的。 g a l l a g e r 给出了l d p c 码的定义口，5 引，即一个由校验矩阵的零空间确定的l d p c 码，它的校验矩阵h 必须满足以下四个属性： ( i ) 每一行包含p 个1 ； ( 2 ) 每一列包含y 个1 ； ( 3 ) 任何两列中相同位置上取i 的个数定义为允，那么a = 0 ，或者a = i ； ( 4 ) p 和厂的值都远远小于码长和校验矩阵的行数。 o 浙江大学硕士学位论文l d p c 码及多进制调制下的译码算法 上面的属性( 1 ) 和( 2 ) 是说校验矩阵h 的行重和列重分别为常数p 和，。 属性( 3 ) 是说任何两列中相同位置上取1 的个数不超过1 。因为p 和y 的值都远 远小于码长和校验矩阵的行数，所以校验矩阵h 中1 的密度很低。也正因为这个 原因，矩阵被称为低密度校验矩阵( 1 0 wd e n si t yp a r it yc h e c km a t r i x ) ，而由 这个矩阵h 确定的码字叫做低密度校验码( l d p c ) 。 实际上，上面由g a ll a g e r 所定义的l d p c 码的校验矩阵h 具有相同的行重和 列重，所以被称为规则l d p c 码。l d p c 码还有一类，叫做非规则l d p c 码，即每 一行或者每一列不必一定具有相同的行重或者列重，只要保证校验矩阵的稀疏性 就可以了。已经证实非规则l d p c 码比规则l d p c 码具有更好的性能。 还有一点要注意，跟其它线性分组码的校验矩阵不同，l d p c 码的校验矩阵 的行不一定是线性独立的，所以要确定码字的码率，必须要先确定校验矩阵h 的 行秩。 上面介绍了l d p c 码的矩阵表示法，虽然矩阵表示法已经可以确定l d p c 码了， 但是这样的方式仍然不够直观。1 9 8 1 年，t a n n e r 首次将二分图引入编码来表示 l d p c 码，因而又把这种二分图叫做t a n n e r 图1 。用t a n n e r 图描述的l d p c 码， 不但形象直观，而且也可以更方便地描述译码算法。 t a n n e r 图由边和节点组成，而节点分为两类，并且边只连接不同类型的节 点。这两类节点在t a n n e r 图中被称为变量节点和校验节点。变量节点集合v = ( v o ，u ，屹一。) 中的每个节点v j 分别和码字比特对应；校验比特集合s = s o ，s m 一。) 中的每个节点置分别和每个校验方程对应。 一个码字的t a n n e r 图根据如下规则构造：当且仅当校验矩阵h 中的红，= 1 时，在t a n n e r 图中将变量节点，和校验节点s ，相连。以一个( 10 ，5 ) 线性分组 码为例，行重为4 ，列重为2 ，校验矩阵h 可以表示为： h = i o 0 o o l 1 0 0 1 0 1 0 o 1 1 0 0 l 0 0 l o 1 o l o o l l 0 0 1 o 0 0 l l o o 1 o l 0 l o 0 l 1 o o o 浙江丈学硕士学位论文l d p c 码及多进制调制下的译码算法 则校验矩阵h 对应的t a n n e r 图如图2 - 1 所示： 氏 、r凡 、 校验节点 7 比特节点0 7 c oc lc 2c 3c 4c 5c 6c 7c sc 9 图2 1 规则l d p c 码的t a n n e r 图 在t a n n e r 图中，节点的度( d e g r e e ) 是指与此节点相连的边的数目。所以， 变量节点v ，的度等于码字比特c ，参与的校验方程的数目，而校验节点s ，的度为第 f 个校验方程所能校验码字比特的个数。对于规则l d p c 码来说，t a n n e r 图中所 有变量节点的度都相同，等于校验矩阵h 的列重，而且，所有校验节点的度也相 同，并且等于校验矩阵h 的行重。满足上述条件的二分图称为规则二分图，否则 就是非规则二分图。在t a n n e r 图中，还有一个很重要的概念，叫做环( g i r t h ) 。 环是指从某个节点出发，经过1 ，条边，最终又回到这个节点，并且环的周期为1 ，。 在t a n n e r 图中最小的环的周期称为t a n n e r 图的周期。易得环的周期都是偶数的， 而且环的最小可能的周期为4 。在编码的时候，为了提高迭代译码的性能，我们 应尽可能的减少短环的产生，特别要避免的是四环的存在。 前面提到的( 1 0 ，5 ) 线性分组码对应的t a n n e r 图是规则的：每个变量节点 都有两条边与之相连，而每个校验节点都有四条边与之相连。该t a n n e r 图的周 期为6 ，在图2 - 1 中用虚线表示。 2 2l d p c 码的广义迭代译码算法 g a l l a g e r 除了在1 9 6 0 年提出l d p c 码之外，他还提出了接近最佳的译码算法。 自从迭代译码在l d p c 码中成功应用，很多学者纷纷研究l d p c 码的译码算法，试 图寻找复杂度低而译码性能好的译码方法。1 9 9 6 年，w i b e r g 在他的博士论文中 首次系统的提出基于t a n n e r 图的广义迭代译码算法b ，算法的结构同t a n n e r 图有直接的关系，变量节点不再代表每个比特，而代表的是每个符号，因此在广 浙江大学硕士学位论文l d p c 码及多进制调制下的译码算法 义迭代译码算法中，又将其称为符号节点。此后又基于此发现其他相关算法。这 些算法本质上都是根据图模型产生的迭代计算。这些算法的名字分别是： s u m - p r o d u c t 算法( s p a ) ，置信传播算法( b p a ) ，以及消息传递算法( m p a ) 。消 息传递通常指代所有的迭代算法，包括s p a ( b p a ) 和其他近似算法。 与格码的最大后验概率译码类似，我们也要计算后验概率( a p p ) ，当给定比 特的值为1 和接收码字y = y o y , 虼一。】，而发送码字码字为c = c o c , 乞一。】。为了 不失一般性，我们在译码比特e 时，先计算它的后验概率 e a q = 1 y ) ( 2 - 1 ) 或者后验概率似然比( l r ) ) 全等箦 阻2 ， 下面我们将计算l o g 域的后验概率似然比( 1 0 9 - a p p ) ，也叫做l l r ： 地) _ _ al o g ( 等舞) ( 2 _ 3 ) 消息传递算法钉( m p a ) 对p ( q = 1 y ) ，( q ) ，三( q ) 的计算都是基于码字的 t a n n e r 图的迭代算法。我们可以假定，变量节点代表一种类型，校验节点代表 另一种类型。在一个半次迭代中，每个变量节点处理它的输入概率信息，并且把 结果传递给它的邻居校验节点。( 其中两个节点被称为邻居，是指它们被同一条 边相连。) 下图表示的是消息坼。：从变量节点传递到校验节点f o 。值得注意的 是，以后传递给校验节点f o 的信息是所有传递给变量节点c o 的校验节点的信息和 信道信息，但是校验节点f o 除外，即在迭代计算中只有外部信息被传递。 浙江大学硕士学位论文l d p c 码及多进制调制下的译码算法 j 、 、l 图2 2 校验节点信息更新图 在另一个半次迭代中，每个校验节点处理它的输入概率信息，并且把结果传 递给它的邻居变量节点。下图表示的是消息m 甜从校验节点五传递到变量节点 c 4 。跟前面提到的类似，也只有外部信息被传递。 五 c oqc 2c 3 图2 3 比特节点信息更新图 按照上面的迭代方法，经过一定的迭代次数之后，译码器计算所译码字比特 e 的a p p ，l r 或者l l r ，如果已经达到之前规定的停止迭代准则，则译码结束， 输出码字。如果经过最大迭代次数之后，译码器计算所译码字比特c t 的a p p ，l r 或者l l r ，如果仍然不能达到规定的停止迭代准则，则停止迭代，输出译码结果 作为最终的码字。常用的一个停止译码准则是；h ，：0 ，其中，三是中间判决码字。 消息传递译码算法是假设通过译码过程传递的消息是独立的。当只是独立 的，只有t a n n e r 图中无环的时候，前面的独立假设才能成立。正是