（通信与信息系统专业论文）低密度奇偶校验码的研究及其应用.pdf

摘要 自1 9 4 8 年s h a n n o n 提出并证明了著名的有扰信道编码定理以来，人们一直在 努力寻找一个更能逼近s h a n n o n 理论极限的好码。从早期的分组码、代数码、r s 码、卷积码，直到今天的t u r b o 码和低密度奇偶校验码( 1 0 wd e n s i i l yp a r i t yc h e c k c o d e s ，简称l d p c 码) ，系统性能与s h a n n o n 极限间的差距越来越小。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 码无论是在编译码方面还是在其应用方面，都 引来无数学者的注意。本文对l d p c 码进行了系统研究。首先从校验矩阵和二分图 两方面介绍了l d p c 码的定义，然后讨论了l d p c 码的结构及其编码思想，给出了 l d p c 码的一些原始构造方法，并根据l d p c 码的特点及目前l d p c 码编码时存在的 缺点，设计了基于单位矩阵的l d p c 码。该构造方式利用了分组交织器，使得构造 出来的l d p c 码含有很少的环。利用m a t l a b 对该码进行了仿真，仿真结果表明： 该码在系统性能上要比其它的l d p c 码有一定的改善；最后本文讨论了l d p c 码在 i e e e 8 0 2 1 6 a 中的应用以及l d p c 码在图像传输中的应用。 l d p c 码由于其性能的优越性及其在数学分析上的相对简单性，已经引起了编 码学术界的广泛兴趣。而且，对l d p c 码的研究也给其他编码带来了新的血液，使 得人们对t u r b o 码等其他编码技术有了新的认识。相信这样一种具有卓越性能的 编码方式必将在理论上有更进一步的发展并在实际中得到广泛的应用。 关键词：信道编码；低密度奇偶校验码；t u r b o 码；二分图；正交频分复用技术 a b s t r a c t s i n c es h a n n o np r o p o s e da n dp r o v e df a m o u sc o d i n gt h e o r e mi n1 9 4 8 ，p e o p l eh a v e b e e nm a k i n gg r e a te f f o r t st ol o o kf o rak i n do fg o o dc o d e ，w h o s ep e r f o r m a n c ec o u l d a p p r o a c ht ot h es h a n n o n st h e o r e t i c a ll i m i t f r o me a r l yb l o c kc o d e s ，a l g e b r ac o d e s ，r s c o d e sa n dc o n v o l u t i o n a lc o d e st ot u r b oc o d e sa n dl o wd e n s i t yp a r i t yc h e c kc o d e s ( l d p cc o d e s ) ；t h ec o d e ds y s t e mp e r f o r m a n c ei sc l o s i n gt ot h et h e o r e t i c a ll i m i t t h e a p p e a r a n c eo ft h et w oc o d e si sag r e a tb r e a k t h o u g ho nc h a n n e lc o d i n gt h e o r e mi nt h e f i e l do f c o m m u n i c a t i o n b u tb e c a u s et h ep e r f o r m a n c eo f l d p cc o d e si ss u p e r i o rt ot h a t o ft u r b oc o d e s ，p e o p l e sa t t e n t i o ni sm o r em a i n l yf o c u s e do nl d p cc o d er a t h e rt h a n t u r b oc o d e sa tt h em o m e n t a san e w c o d i n gt e c h n o l o g y ，l d p cc o d e sa r o u s em a n ys c h o l a r s c o n c e r nn o ti n t h eh a n do fc o d i n ga n dd e c o d i n g ，b u ti nt h eh a n do fa p p l i c a t i o n t h i sp a p e rg i v e sa s 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 t ，t h ed e f i n i t i o n so fl d p cc o d e sa r e i n t r o d u c e df r o mt h ea s p e c to fp a r i t ym a t r i xa n db i p a r t i t eg r a p h t h e nt h es t r u c t u r e so f l d p cc o d e sa n dt h et h o u g h to ft h e i re n c o d i n ga n dd e c o d i n ga r ed i s c u s s e d s o m e o r i g i n a l m e t h o d so fc o n s t r u c t i n gl d p cc o d e sa r ep r e s e n t e d o nt h eb a s eo ft h e c h a r a c t e r i s t i co fl d p cc o d ea n dt h ed i s a d v a n t a g eo fc o d i n g f lk i n do fl d p cc o d e s b a s e do i li d e n t i t ym a t r i xi sd e s i g n e d w h i c hc a l lm a k eu s eo fb l o c ki n t e r l e a v e r st or e d u c e t h ec y c l e s i ts h o w sb yt h em a t l a bs i m u l a t i o nt h a tt h ee r r o rp e r f o r m a n c ei si m p r o v e d w i t ht h en e wk i n do fl d p cc o d e s f i n a l l y ，t h ea p p l i c a t i o n so fl d p cc o d e st o i e e e s 0 2 1 6 aa n dp i c t u r et r a n s m i ta r ed i s c u s s e d ， l d p cc o d e sh a v er a i s e dal a r g ei n t e r e s ti nt h ec o d i n gc o m m u n i t yw i t hi t se x c e l l e n t p e r f o r m a n c ea n dr e l a t i v es i m p l ea n a l y s i si nm a t h e m a t i c s t h es t u d yo nl d p cc o d e s g i v e sn e wb l o o dt oo t h e rc o d i n gs c h e m e s ，b r i n gn e wr e c o g n i z et oo t h e rc o d e ss u c ha s t u r b oc o d e s s u c hc o d e sw i t l le x c e l l e n tp e r f o r m a n c em u s tb ed e v e l o p e df u r t h e ri n t h e o r ya n db ew i d e l yu s e di np r a c t i c e k e yw o r d s ：c h a n n e lc o d i n g ；l o w - d e n s i t yp a r i t y - c h e c kc o d e s ；t u r b oc o d e s ； b i p a r t i t eg r a p h ；o r t h o g o n a lf r e q u e n c yd i v i s i o nm u l t i p l e x i n g ( o r d m ) 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成博士硕士学位论文 ! 低蜜廑查堡撞坠照殴监窥丛基廛旦：。除论文中 已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开 发表或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：王蒡z 0 0 6 年j 月z o 日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或 扫描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于：保密口 不保密氏以请在以上方框内打“，) 论文作者签名；王努导师签名：蒯 日期：2 一口彳年；月2 dr 第1 章绪论 1 1 编码方式的演变过程 1 9 4 8 年，s h a n n o n 提出并证明了著名的有扰信道编码定理：对于一个信道容 量为c 的有扰信道，设信息源产生信息的速率为r ，若r s c ，则总可以找到一种 信道编码和译码方式使译码后的错误概率随着码长的增加，按指数下降到任意小 的值：而若r c ，则不存在能够实现无差错传输的编译码方式。若干年来，随着 通信技术的发展和实际应用的不断增加，人们一直在努力寻找一个更能逼近 s h a n n o n 理论极限的好码。从早期的分组码、代数码、r s 码、卷积码，直到今天 的l d p c 码，系统性能与s h a n n o n 极限问的差距越来越小。 我们知道，在当今的通信领域中有两种让人瞩目的码，一种是t u r b o 码，另 一种是l d p c 码，这两种码的出现，是信道编码理论在通信领域中一次大的飞跃。 t u r b o 码是由法国的c b e r r o u 等人在卷积码和级联码的基础上，于1 9 9 3 年提出来 的一种新的码型，它的提出标志着信道编码理论进入一个新的阶段【l 】。t u r b o 码又 称为并行级联卷积码，它巧妙地将卷积码和随机交织器结合在一起，有效地实现 了随机型编译码的思想，并通过交织器实现了由短码构造长码的方法，在性能方 面也达到了接近s h a n n o n 理论极限的性能。其最优译码算法是m a p 译码算法。m a p 译码算法主要基于早在1 9 7 4 年就已经提出来的b c j r 译码算法而形成的( 2 1 。m a p 译 码算法采用了迭代译码的思想，该思想是通过使分量译码器之间的软信息交换来 提高译码性能的。这也是t u r b o 码获得优异性能的根本原因之一。然而，这种算 法在实现过程中复杂度非常高，因为它涉及了指数加法和实数递归乘法的运算。 为了简化译码复杂度和运算时延，人们提出了对数形式的m a p 算法，即l o r - m a p 算法并从中衍生出了复杂度更低、但其性能却大幅下降的m a x l o r m a p 算法 p l 。此外，人们还提出了采用逐序列的软输出v i t e r b i 算法，即所谓s o v a 算法。 l d p c 码是一类线性纠错码，是著名学者r g g a l l a g e r 于1 9 6 2 年就提出来的 一种低密度奇偶校验码【4 l 。如果说t u r b o 码的出现将纠错编码理论推向了一个新的 境界，那么l d p c 码的再现为编码理论的研究带来了又一个新的高潮。虽然l d p c 码很早就被提出，但是由于当时计算机水平不够，硬件实现困难，所以g a l l a g e r 当年在其博士论文中，只给出了l d p c 码的构造方法，迭代译码算法及其性能在理 论上的证明。之后，m a c k e y 于1 9 9 9 年证明了性能优异的l d p c 码是存在的，并给 出了一些构造l d p c 码的思路【5 1 。我们知道，g a l l a g e r 最初提出来的l d p c 码是具 有正则的l d p c 码，也就是说校验矩阵中每行所含非零元素个数是相同的，对于正 则l d p c 码的定义，我们将在下一节中给出。随着人们对l d p c 码的日益重视。各 种构造方法不断的涌现，在1 9 9 8 年以前，人们对l d p c 码的研究主要集中在如何 构造正则的或者是近似正则的二分图。而在1 9 9 8 年，l u b y 等人对g a l l a g e r 码进 行了推广，提出了可以改善l d p c 码性能的非正则l d p c 码【6 l 。1 9 9 9 年，r i c h a r d s o n 、 s h o k r o l l a h i 和u r b a n k e 发现，如果在码长足够长的时候( 比方说1 0 6b i t ) ，不规 则l d p c 码在高斯白噪声信道下，其性能可达到距离s h a n n o n 性能限仅0 1 3 d b 7 1 。 2 0 0 0 年，c h u n g 把码长设置为1 0 7b i t ，码率为1 2 ，而且在a w g n 信道下对二元l d p c 码做了性能仿真，结果发现其性能距s h a n n o n 限仅差0 o l d b 观。2 0 0 1 年以后，l d p c 码与通信领域的其它先进技术相结合成为了一个热门话题。b e nl u 等人提出了基 于l d p c 码的空时编码o f d m 系统【9 1 ，该系统结合了空间分集技术、选择性衰落分集 技术，以较低的计算复杂度达到了较高的系统性能。 1 2l d p c 码的概述 l d p c ( l o wd e n s i t yp a r i t yc h e c k ) 码，又穗为g a l l a g e r 码，是一大类可以 用稀疏校验矩阵定义的线性纠错码，由于校验矩阵是稀疏的，所以称之为低密度 的，也就是说，校验矩阵的元素除了一小部分不为0 以外，其他绝大多数都为0 。 l d p c 码是由g a l l a g e r 于1 9 6 2 年提出的一种性能接近香农( s h a n n o n ) 限的好码【4 1 ， 并采用了迭代译码思想来进行译码，所以我们又称之为哥拉格( g a l l a g e r ) 码。 在很长的一段时间里，限于当时的条件和人们认识的水平，l d p c 码并未受到人们 的重视。直到1 9 9 3 年，b e r r o u 等提出了t u r b o 码后，人们发现t u r b o 码其实就是 一种l d p c 码，l d p c 码才又重新引起了人们的研究兴趣。1 9 9 6 年，d j c m a c k a y 和r i n e a l 对这种正则型l d p c 码重新进行了研究，发现它们也如t u r b o 码那 样具有逼近香农限的性能i s 城，从而使l d p c 码的研究跨入了一个崭新的阶段。 从此，人们纷纷加入到l d p c 码的研究行列，由i e e e 、 i e e 等主办的一些重大国 际学术会议和著名学术期刊均发表了大量l d p c 码的研究成果，而且，人们最近发 现长的l d p c 码的性能要好于同等条件下的t u r b o 码【2 0 】。l d p c 码现已成为当今信 道编码领域最瞩目的研究热点。 1 2 1l d p c 的定义 简单的说，l d p c 码是一种具有稀疏校验矩阵的线性纠错码，其定义通常有两 种方式：一种是用校验矩阵来定义，另一种是用t a n n e r 图( 也叫二分图) 来定 义。首先我们来介绍一下第一种定义方法。 一、矩阵定义 对于一个码长为，原始信息长度为足的二进制l d p c 码c 来说，我们可以用 一个大小为m n 阶的校验矩阵来定义。校验矩阵h 中的大部分元素等于0 ， 只有- d , 部分的元素为1 ，而且校验矩阵的每行代表一个校验位，每列代表一个码 元。对于第埘个校验位( 1 肌m ) 来说，其包含的信息比特我们记为集合n ) ， 第h 个码元( 1 竹) 参与的校验比特集合我们记为m ( n ) 。图1 1 给出了校验矩阵 的一般结构。 蟊= l0 00 ： ： 0l 00 n列 呻 00 100 l0 010 0 l o0l l0 0l0 十 m 行 山 图1 1 校验矩阵的一般结构 f i g 1 1t h eg e n e r a ls t r u c t u r eo f p a r i t y - c h e c km a t r i x 与一般的校验矩阵相比，l d p c 码的校验矩阵有所不同，其校验矩阵中含有少 数量的非零元素，所以我们称之为低密度，也就是这个低密度特性能使我们为l d p c 码设计出了低复杂度的译码算法。 如果一个l d p c 码的校验矩阵日是满秩的，那么该码的校验位长度肘：n k 码率，= n - _ 型u = 1 一m 。但有时，校验矩阵日的m 个行向量不是独立的，也就是 说，校验矩阵日的秩小于m ，在这种情况下，m 一世且r l - - - m 。对于这种 情况我们可以通过高斯消去法以及必要的列置换，把校验矩阵改成如下形式； 日斗 叫学 其中，( 。圳洲圳为单位矩阵。我们假设某一l d p c 码( ，k ) 的校验矩阵被 变换为式( 1 1 ) 的形式以后，下面有d 行元素为零，那么在种情况下，矩阵日的秩 为m d ，并且定义的码是( ，k4 - d ) 。对于满秩的校验矩阵胃来说，就不会在式 ( 1 1 ) 的下面有全零行向量。 二、二分图定义 就像卷积码可以用格状图表示一样，l d p c 码可以用二分图来表示。在用二分 图来表示l d p c 码的时候，我们分别用变量节点和校验节点来表示校验矩阵h 的列 和行，也就是说，在二分图的一边有个节点，每个节点表示码字的一个比特位， 我们称之左节点，而在另一边有m 个节点，每个节点表示码字的一个校验集，我 们称之为右节点：至于校验矩阵中的“l ”元素，我们用对应变量节点和校验节点 之间的连线来表示，这样所得到的图就是与该校验矩阵相对应的二分图，如图i 2 所示。我们称一条边两端的节点为相邻节点，每个节点相连的边数为该节点的度 x lx 3x 3再 r li z w 图1 2 二分图 f i g 1 2b i p a r t i t eg r a p h 数。在二分图中，每个变量节点聍都与集合m 0 ) 的所有校验节点相连，其度数 d ，0 ) = i m 0 l ，同理，每个校验节点m 都与集合) 的所有变量节点相连，其度 数为d 。向) = 幻) 。 从二分图中，我们看到含有大小为四的环x 。寸而斗南寸z 2 叶一) ，这种小 环在设计l d p c 码的时候是要尽量避免的，因为人们在研究过程中逐渐发现，当l d p c 码对应的二分图中含有长度较小的环时，会影响迭代译码算法的性能】，从而该 码的纠错性熊就会有所下降。而且环的数量和环的大小同码的分布重量一样对 l d p c 码的纠错性能有着重要影响。目前，人们一直在研究消除小环的方法，包括有 援索法，代数法等。 1 2 2l d p c 码的分类 前面我们已经了解到，l d p c 码可以用校验矩阵和二分图来表示，我们根据校 验矩阵日中各列“1 ”的个数是否相同，把l d p c 码分为正则码和非正则码。在介 绍规则码和非规则码之前，我们首先来了解一下行重和列重的定义。所谓的行重 就是指校验节点的度数，也就是校验矩阵中每行非零元素的个数，用二分图来描 述下的话，就是指与某个校验节点相连的边数；同理，列重是指变量节点的度 数，即校验矩阵中每列“l ”的个数，在二分图中，就是指于某个变量节点相连的 边数。如果一个码的校验矩阵每一行中非零元素的个数是相同的，我们就称这种 码为正则l d p c 码，且用如，j ，七) 来表示该码字。其中， 为码长，为每列非零元 素的个数，| 】 为每行非零元素的个数。有了规则l d p c 码，那么对应的就有非规则 l d p c 码，对于非规则l d p c 码来说，其校验矩阵日中的行重或列重量就不再相同， 在其对应的二分图中，变量节点之间以及校验节点之间的度数有可能是不相同的， 分别用序列a 阮，如，以) 和p 如，p 2 ，岛) 来描述它的次数分布，其中丑和n 分别表示的是非规则图上度为i 的变量节点和校验节点的边数在总边数中所占的 比例，m 和d 分别表示的是变量节点和校验节点的最大度数，序列 和p 分别满 d 足等式 = l 和成= 1 。此外，非正则l d p c 码还可以用节点分布多项式五g ) 和 l z im p b ) 来定义，这两个多项式分别定义了变量节点和校验节点的分布情况。更具体 化一点，我们令 且g ) = p g ) = 妻如，- 2 2 妻 - j = 2 环在设计l d p c 码的时候是要尽量避免的，因为人们在研究过程中逐渐发现，当l d p c 码对应的二分图中含有长度较小的环时，会影响迭代译码算法的性能，从而该 码的纠错性能就会有所下降。而且环鲍数量和环的大小同码盼分布重量一样对 l d p c 码的纠错性能有着重要影响。目前，人们一直在研究消除小环的方法，包括有 搜索法，代数法等。 1 22l d p c 码的分类 前面我们已经了解到，l d p c 码可以用校验矩阵和二分图来表示，我们根据校 验矩阵中各列“l ”的个数是否相同，把l d p c 码分为正则码和非正则码。在介 绍规则码和非规则码之前，我们首先来了解下行重和列重的定义。所谓的行重 就是指校验节点的度数，也就是校验矩阵中每行非零元素的个数，用二分图来描 述一下的话，就是指与某个校验节点相连的边数；同理，列重是指变量节点的度 数，即校验矩阵中每列“l ”的个数，在二分图中，就是指于某个变量节点相连的 边数。如果一个码的校验矩阵每一行中非零元素的个数是相同的，我们就称这种 码为正则l d p c 码，且用如， ) 来表示该码字，其中，”为码长，j 为每列非零元 素的个数，l 为每行非零元素的个数。有了规则l d p c 码，那么对应的就有非规则 l d p c 码，对于非规则l d p c 码来说，其校验矩阵h 中的行重或列重量就不再相同， 在其对应的二分图中，变量节点之间以及校验节点之间的度数有可能是不相同的， 分别用序列丑( ，也，以) 和p b ，岛，办) 来描述它的次数分布，其中 和n 分别表示的是非规则图上度为f 的变量节点和校验节点的边数在总边数中所占的 比例，m 和d 分别表示的是变量节点和校验节点的最夫度数，序列 和p 分别满 md 足等式 = 1 和一= 1 。此外，非正则l d p c 码还可以用节点分布多项式 0 ) 和 ，t l扣1 p b ) 来定义，这两个多项式分别定义了变量节点和校验节点的分布情况。更具体 化一点，我们令 化一点，我们令 o ) = o ，x 。 p o ) = 羔p 矿 这里，d ，和d 。分别是变量节点和校验节点的最大度数，丑，和p ，分别表示与度 数为，的变量节点和校验节点相连的边数在总边数中所占的比例。 1 2 3l d p c 码的优缺点 众所周知，l d p c 码现已成为当今信道编码领域最瞩目的研究热点。那么，是 什么样的力量让这么多人来研究它呢? 我们知道，l d p c 码的校验矩阵是稀疏的， 也正是因为这个特点，其译码复杂度不太高，而且可以在线性复杂度内实现译码 过程，且可实现完全的并行操作，硬件复杂度也低，适合用硬件实现，这一特点 是t u r b o 码不能与之相比的。这种码在译码过程中可以确定码字是否译出，来决 定译码过程是否结束，从而减少迭代次数，所以我们说该码的吞吐量大，极具高 速译码潜力。同时，其译码性能要优于t u r b o 码，如图( 1 3 ) 所示。l d p c 码还具 有较大的灵活性和较低的差错平底特性( e r r o rf l o o r ) ；其描述简单，对严格的 理论分析具有可验证性；由于校验矩阵是稀疏的，所以编码器对校验矩阵的存储， 只需要很小的存储容量；此外，l d p c 码含有内在的交织器，所以它不像t u r b o 码 需要交织器来实现随机交织。当然，l d p c 码也有它的缺点，其主要缺点在于其 图1 3 码长为2 4 0 0 比特、码率为i 2 的l d p c 码与t u r b o 码的性能比较 f i g 1 3t h ep e r f o r m a n c ec o m p a r i s i o nb e t w e e nr a t e - 1 2l d p cc o d e sa n dt u r b oc o d ew i t h i n f o r m a t i o nl e n 群h j 2 4 0 0 编码复杂度高，其编码复杂度为0 0 2 ) 。虽然最新的研究表明它可以在线性时间内 6 编码，但是其复杂度相对于卷积码等来说仍然过大；而且，由于当码的长度不够 长的时候，会有中短长度的环存在，所以l d p c 码性能的优越性通常需要在码长较 长的时候才能体现出来；但是当码长较大的时候，由于l d p c 码在编码的时候，必 须接收到所有的信息比特以后才能进行编码，这样就会给编码带来一定的时延。 1 2 4l d p c 的发展动态 我们知道，l d p c 码自1 9 9 5 年被重新得到人们的重视以后，众多的科研人员纷 纷加入了l d p c 码的研究行列中，由i e e e 、 i e e 等主办的一些重大国际学术会议 和著名学术期刊也均发表了大量l d p c 码的研究成果。随着人们对l d p c 码的不断 研究，l d p c 码的相关技术也逐渐走向成熟。在这一节里，我们着重介绍下l d p c 码在近几年来的发展动态以及研究方向。 一、码结构的设计 在早期，l d p c 码虽然具有很好的性能，但是校验矩阵一直是由计算机随机构 造的，而没有一种好的系统分析方法来得到。此外，由于用计算机随机构造的l d p c 码的校验矩阵，并不是系统形式，使得编码复杂度比较高，所以说，码的构造成 了人们研究的热点。 二、编码方法的研究 在上面已经提到：l d p c 码的编码复杂度比较高，它与码长的关系为o k ：) ，所 以人们在对l d p c 码的编码方法进行研究的时候，主要目的就在于减少编码的时间， 并提高码的系统性能。但是前面也已经说过，编码复杂度高的主要原因在于校验 矩阵，所以在研究编码方面，我们要着眼于怎样才能构造出“好的”校验矩阵。 三、译码算法的改进 编码与译码是编码方案的两个方面。l d p c 码之所以能具有这么好的性能，与 它所采用的译码方式是密不可分的。g a l l a g e r 曾经提出了两种译码算法：种是 硬判决译码，另一种是概率译码。后来，人们又提出了置信传播算法，或称为消 息传递方法( b p 算法) 、和乘积算法( s p 算法) ，这种算法的译码复杂度是比较 低的，而且是可实现的。但是人们并不满足于现状，提出了基于b p 算法、复杂度 更低的译码方法a 由于在整个b p 译码算法中用到了两个概率值的差，也正是这个 做差运算使这个算法对于量化特别敏感。而在实际应用中，我们必然要用到量化， 所以又有人提出了一种基于校验似然比( p a r i t y1 i k e l i h o o dr a t i o ，简称为p l r ) 的译码算法来克服上面的缺点。 四、l d p c 码的应用 由于l d p c 码具有很好的编码性能，使得人们在研究l d p c 码的同时，其应用 也成为人们日益关注的问题。多媒体图像的高可靠性传输是下一代移动通信的目 标，而移动衰落信道环境恶劣，长突发错误的产生很容易降低图像传输的质量， 因此，在传输图像的系统中，采用信道编码方案对图像数据进行冗余保护成为一 种必要手段，而l d p c 码的编码方式是目前最为优秀的，所以将l d p c 码应用于图 像传输中将成为一种必然。 i e e e 8 0 2 1 6 a 把i e e e 8 0 2 1 6 定义的第二代无线城域网的空中接口标准扩展到 2 11 g h z 的低频段，支持非视距( n l o s ) 连接和点到多点的宽带无线接入系统。 在该协议中，建议的f e c 编码方式有r s 码和卷积码的级联码r s c c 、卷积t u r b o 码以及分组t u r b o 码三种。但是我们知道，l d p c 码是一种性能很好的码型，而且 其译码复杂度与码长呈线性关系，所以，人们鉴于l d p c 码的种种优点，提出了把 l d p c 码应用于i e e e 8 0 2 1 6 a 协议中的想法。 随着对l d p c 码的深入研究，l d p c 码的应用也将逐渐广泛，在论文的第五章将 会更深入地介绍。总之，l d p c 码的出现是对纠错码研究的一个新篇章。 1 3 论文章节安排 本论文共分六章对l d p c 码进行研究。第二章着重研究l d p c 码的构造方法； 第三章主要阐述l d p c 码的编码方法和改进；第四章详细说明了l d p c 码在译码 过程中所采用的b p 译码算法，以及译码算法的改进。第五章是l d p c 码的应用， 主要介绍l d p c 码在图像传输和i e e e 9 0 2 1 6 a 协议中的应用；在最后一章，也就是 论文的第六章，对论文进行了总结，并作了展望。 8 第2 章l d p c 码的构造 众所周知，一个码的好坏完全由它的校验矩阵来确定，也就是说校验矩阵的 结构对于码的性能有着决定性作用，所以我们有必要先对码的结构作一了解。l d p c 码是用一个稀疏校验矩阵来定义的，所谓的稀疏校验矩阵，就是指校验矩阵中每 行、每列包含的“1 ”的个数相对于码长来说都是很小的数。我们根据校验矩阵中 每行的行重和每列的列重是否相同，把l d p c 码分为正则l d p c 码和非正则l d p c 码： 如果一个码有相同的行重和列重，我们称之为正则码【4 】：如果一个校验矩阵的各个 行重或列重不一样，我们称这种码为非正则码【。在文献 1 3 中指出：非正则码 在译码性能上要优于正则码的性能，但是正则码由于其结构规则所以更适合于 v l s i 的实现。 从第一章l d p c 码的定义我们可以看出，要设计一个l d p c 码，最直接最有效 的方法就是按照指定标准构造个低密度奇偶校验矩阵h 。随着l d p c 码越来越多 地得到人们的重视，其构造方法也层出不穷。当然，构造方法的不断推出，无非 是为了实现以下几个目的：优化码结构；增大二分图中的周期：减少编码复杂度。 下面我们从正则码和非正则码两个方面来分别介绍下l d p c 码的结构。 2 1 正则l d p c 码 正则l d p c 码是l d p c 码中最简单的形式，早在1 9 6 2 年，g a l l a g e r 就提出了其 构造方法，但是限于当时的条件和人们认识的水平，这种码一直未受到人们的认 可。多年以后，当l d p c 码再次走进人们的视眼的时候，这种码的构造方法开始层 出不穷，下面我们将着重介绍几种构造方法。 2 1 1g a f | a g e r 的构造方法 1 9 6 2 年，g a l l a g e r 在文献 4 中提出了一种构造0 ，七) 正则l d p c 码的方法， 我们把这种方法构造出来的l d p c 码称为正则码或g a l l a g e r 码。该方法的具体思 想是：首先构造一个每列只有一个“l ”，每行有| i 个“l ”的子矩阵风，然后对珥。 进行( ，一1 ) 次随机的列置换，分别得到( ，一1 ) 个子矩阵，利用这_ ，个子矩阵得到校 验矩阵h ，这样得到的校验矩阵码长为n ，行重为七，列重为，其结构如下所示： 9 h = 疗( h 。) 其中，为矩阵h 。的列置换。下面我们给出一个( 2 0 ，3 ，4 ) l d p c 码的矩阵形式， 如图2 1 所示，从矩阵的结构我们可以更清楚地理解g a l l a g e r 的构造方法。 llll0 0 000 o11 0 0 0 0 00 0 0 0 0 00 00 o o o0 l0 0 0l0 0lo 0 01 0 0l0 oo o o o1o o 000 0 0 0 0 0 0 0 00 l 10 0 0 0 0 o 00o0 0 0l1ll0 o000 0 0 0 0 0 0 0l111 00 0 0 0 0 0 0 0 000 11 0 010 0 0l0 0 000 0 0 010 000 0010 l00 0 0 0001 o ol 000 0100001 0 0 00 0 0 000l0 l0 0 0 0l0 0 0 0 0l0l0 00 0 0 010 0 0 0 01 0 0 00 o o o o 1l _- 00 oo 0 0 lo o1 _ 0 0 图2 1 码长为2 0 ，列重为3 ，行重为4 的正则码的校验矩阵 f i g 2 1t h ep a r r y - c h e c km a r xo f r e g u l a rl d p cc o d e 对于0 ，_ ，k ) m ml d p c 码，给定校验矩阵后，如果校验矩阵的行是线性无关 的，那么编码的码率为l 一丢；相反，若校验矩阵的行是线性相关的，那么编码的 码率要大于1 一丢，也就是说，任何一个正则码的码率都不会小于1 一丢。 2 1 2 广义l d p c 码的构造方法 广义l d p c 码( 简称为g l d 码) 最早是由l e n t m a i e r 1 4 】和b o u t r o s 1 5 】单独提出 来的，作为g a l l a g e r 提出来的l d p c 码的推广形式，广义l d p c 码是利用线性分组 1 0 、， 厅 o o o ， o ，o o o o o 0 0 0 0 0 0 0 0 o o ， o o 1 o o o o 0 0 0 0 l 0 0 0 o o o o o o o ，o o o o o o o o o o o 0 ， o o o 0 o o o o o o o o o 码的校验矩阵来取代l d p c 码中每一个奇偶校验等式而形成的，其构造思想与 g a l l a g e r 码的构造思想大致相同。广义l d p c 码可以运用基于构造码所用的软输入 软输出译码思想的迭代译码方法进行译码，这种方法将在第四章进行阐述。此外， 广义l d p c 码的译码器结构规则，而且可以并行实现，这一点对于实际中智能电路 的实现是非常有益的。 众所周知，l d p c 码是通过一个稀疏校验矩阵来定义的，校验矩阵中的每一行 是一个纠正单个错误的校验等式，由于广义l d p c 码是l d p c 码的通用型，所以该 码也可以由一个稀疏校验矩阵日来定义，而且这个矩阵可以通过用一个码c o ( ”，七) 的校验矩阵矗替换l d p c 码的每一行来形成。对于长度为v 、行重为t 、列重为， 的广义l b p c 码来说，我们可以通过，个列重为“1 ”、行重为“k ”的构造矩阵h 。 构成。首先，我们选择个合适的校验矩阵风作为基矩阵。该矩阵具有如下特点： ， ( 1 ) 该矩阵对应的码长为n ，且要求竺为个整数； 门 ( 2 ) 该矩阵对应的列重为“1 ”、行重为“七”； ( 3 ) 为了使所生成的g l d 码对应的校验矩阵中没有任何两个子码有多余一列的 非零元素是重叠的，我们要求叱押。 有了构造矩阵编以后，我们把凰作为子矩阵的块对角矩阵来形成第一个子矩阵 h 1 ，该矩阵的行重和列重与矩阵峨的相同；接着对日1 进行o 1 ) 次列置换得到 u 1 ) 个子矩阵日2 ，h ，最后把这，个子矩阵从上到下依次排列得出矩阵 h 。图2 2 为广义l b p c 码校验矩阵的结构图，其中万，( 2 f ，) 代表一个随机的列 置换( 即对胃1 进行随机列置换) 。 日1 = 图2 2 广义l d p c 码校验矩阵的结构图 f i g 2 2t h ec o n s t r u c t i o n a lg r a p ho f g e n e r a ll d p cc o d e k 7 1 日 h 。i。；o爵 。o 1_i： 一一 一一- 0西一一0o 曼o|io可 2 1 3m a c k a y 的构造方法 m a c k a y 在构造校验矩阵时，引入了一些重量为2 的列来降低整个校验矩阵的 重量，以减少二分图中圈的数量，由此减少译码算法受到圈的影响，但是引入重 量为2 的列会导致低重量码字的出现，需要采取措施减少其出现的概率。为此， m a c k a y 给出了如下的构造方法【5 】： 构造法1 a ：对于m n 的矩阵，我们可以随机地构造，使其列重为j ( 如，= 3 ) ， 行熏尽可能相同，且任意两列重叠的1 的个数不大于l 。图2 3 给出了码率为一1 ， 2 列重= 3 的构造。 m n 图2 3 码率为昙，列重，= 3 的构造 f i g 2 3t h ec o n s t r u c t i o no f c o d e s ，r o t ei s1 2a n dc o l u m nw e i g h ti s3 图2 4 构造法2 a 产生的矩阵 f i g 2 4t h em a t r i xb yc o n s t r u c t i o nm e t h o d2 a 构造法2 a ：利用该构造方法构造的校验矩阵，前等列的列重量都为2 ，且 这些列重为2 的列有两个等- 等的单位矩阵构成，如图2 4 所示，任何一列中都 没有重叠的“l ”。剩余的f 一等 列是随机构造的，其列重为3 ，每行1 的个数 尽可能一致，且整个矩阵中任意两列重叠的l 的个数不大于i 。图2 4 为码率为= 1 j 的码的构造结构。 构造法1 b 和2 b ：分别从利用构造法1 a 和2 a 构造出来的矩阵中删除一小部分 列，使得对应新矩阵的二分图中没有小于某个长度，( 如l = 6 ) 的圈，这两种方法 我们分别称之为1 b 和2 b 。 2 1 4 组合学构造法 组合学构造法是一种基于组合数学中b i b d 理论的构造方法，该方法构造出来 的l d p c 码为正则l d p c 码，且没有长度为4 的循环 1 8 l 。b i b d 是b a l a n c e di n c o m p l e t e b l o c kd e s i g n 的缩写，即均衡不完全的区组设计1 1 9 1 ，下面我们给出该设计的定义。 设j = 扛，x ：，x ，j 为试验对象集合，v 为试验对象的数目。所谓均衡不完全 的区组，指的是由x 中的子集构成区组的集合。占为区组的数目，即设为 旧，岛，玩 。每组有的七个元素，并满足以下的条件： ( 1 ) x 中的每一个元素在b 组中正好出现r 次 ( 2 ) 任意一对属于爿的元素在b 组中正好同时出现五次 ( 3 ) k v 满足以上条件的b i b d 记为( b ，v ，r ，k ，凡) 一设计。 一个b i b d 可以用只包含0 和1 的邻接矩阵q 来表示，其列对应集合x 中的元 素，行对应需要设计的区组。如果集合中的第，个元素在第i 个块置中，那么将矩 阵元钆置为1 ，否则置为0 。显然，该矩阵为b v 维矩阵，且具有如下的性质： ( 1 ) 每行有k 个1 ： ( 2 ) 每列有r 个1 ： ( 3 ) 任两列之间有z 个l 在相同的位置。 我们知道，当旯= 1 ，k 和r 相对于v 都很小时，邻接矩阵q 是一个低密度的稀 疏矩阵，可用于生成l d p c 码。其中，旯= i 这一条件保证了该码对应的二分图中没 有长度为4 的循环，从而提高了系统的性能。 经过多年的研究，许多五= 1 和具有小的k 和r 的b i b d 被构造出来了，他们的 邻接矩阵就可以用来生成l d p c 码。例如，对于满足4 ，+ 1 为某一质数的幂的整数f 存在如下的b i