（物理电子学专业论文）ldpc码编码及译码算法的研究.pdf

摘要 低密度奇偶校验码( l o w - d e n s i t y - p a r i t y - c h e e k e o d e s ，简称l d p c 码) 是当前 通信领域的热门研究课题之一，是第四代移动通信系统强有力的竞争者。l d p c 码具有优秀的译码性能，迭代的概率译码算法使得l d p c 码可以达到接近香农限 的性能，而且译码的复杂度较低；译码算法本质上是并行算法，有利于硬件的并 行实现，减少译码延时；它能够在迭代运行的过程中确定码字是否己译出，以决 定译码过程能否结束，减少迭代次数；同时其译码错误是可以检测的；译码后的 误码率可以随着信噪比的增加而任意减小，没有误码率下降减速的e r r o rf l o o r 现 象。l d p c 码编码的复杂度较高，同时在码长较长时，由于必须在接收到所有的 信息比特后才能够进行编码，这就会给编码带来一定的延时。 本文对l d p c 码进行了系统的研究。首先介绍了l d p c 码的结构和校验矩 阵的构造方法；接着介绍了基于m e s s a g ep a s s i n g 算法的l d p c 码的几种迭代译 码算法，l d p c 码的这些迭代译码算法包括，比特翻转( b f ) 算法、加权的比特 翻转( w b f ) 算法、置信传播( b p ) 算法、最小和( m i n s u m ) 算法、归一化的 最小和算法以及基于可靠性的迭代译码算法等多种算法，另外还介绍了用于计算 噪声门限的基于b p 算法的密度演变算法；然后探讨了l d p c 码如何克服其较高 的编码复杂度，利用l d p c 码校验矩阵的稀疏性进行编码的方法，并对两种编码 方法进行基于c p l d 的v e r i l o gh d l 设计，给出了编码的仿真波形；最后给出了 不同码长和不同码率的l d p c 码在高斯白噪声信道下的误码率性能的仿真结果， 并用基于b p 算法的密度演变算法举例计算了译码的噪声门限，并与仿真结果相 比较。另外还研究了一种简化的b p 译码算法，利用曲线拟合的方法减少迭代运 算量，以降低译码的复杂度。 关键词：l d p c 码，m e s s a g ep a s s i n g 算法，迭代译码，b p 算法，编码，v e f i l o gh d l ， a b s t r a c t l o w - d e n s i t y p a r i t y - c h e c k - c o d e si sc u r r e n t l yo n eo ft h ep o pr e s e a r c ht h e s e si n c o m m u n i c a t i o nf i e l d ，i ti st h ep o w e r f u lc o m p e t i t i o ni nt h e4 t hg e n e r a t i o no fm o b i l e c o m m u n i c a t i o ns y s t e m t h ed e c o d i n gp e r f o r m a n c eo fl d p ci se x c e l l e n ta n dc a nb en e a r t h es h a n n o nl i m i tb yi t e r a t i v ep r o b a b i l i t yd e c o d i n ga l g o r i t h m i th a sl o wc o m p l e x i t y ， t h ed e c o d i n ga l g o r i t h mi se s s e n t i a l l yp a r a l l e l 。s oi t i ss u i t a b l et or e a l i z eo n h a r d w a r ei np a r a l l e la n dr e d u c et h ed e c o d i n gd e l a yt i m e i tc a nm a k ec e r t a i nt h a t i ft h ec o d e sa r ed e c o d e di nt h ei t e r a t i v ed e c o d i n gp r o c e s sa n di ft h ep r o c e s sc a n b ef i n i 、s h e di no r d e rt or e d u c ei t e r a t i v et i m e s ，a tt h es a m et i m et h ed e c o d i n ge r r o r c a nb ed e t e c t e d b i te r r o rr a t e ( b e r ) a f t e rd e c o d i n gc a nb ed e c r e a s e da r b i t r a r i l y a l o n gw i t ht h ei n c r e a s eo fs i g n a l t o - n o i s er a t e ( s n r ) ，a n dt h ee r r o rf l o o rp h e n o m e n o n c a nn o to c c u r e t h ec o m p l e x i t yo fe n c o d i n gi sh i g h b e c a u s et h ee n c o d i n gp r o c e s s b e g i n sa f t e rr e c e i v i n ga l ln e e d e ds i g n a lb i t s ，i tb r i n g sc e r t a i nd e l a yt i m ew h i l e t h el e n g t ho ft h ec o d e si sv e r yl o n g t h i sp a p e rg 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 t t h es t r u c t u r e s a n ds o m ec h e c km a t r i xc o n s t r u c t i o nm e t h o d so fl d i ) cc o d e sa r ei n t r o d u c e d ：t h e ns e v e r a l i t e r a t i v em e s s a g ep a s s i n ga l g o r i t h m sf o rl d p cc o d e sa r ei n t r o d u c e d l d p cc o d e sc a n b ed e c o d e dw i t hv a r i o u sd e c o d i n ga l g o r i t h m s ，s u c ha sb i tf 1 i p p i n g ( b f ) a l g o r i t h m 、 w e i g h t e db f ( w b f ) a l g o r i t h m 、b e l i e fp r o p a g a t i o n ( b p ) a l g o r i t h m 、m i n - s u ma l g o r i t h m 、 n o r m a l i z e dm i n s u ma l g o r i t h ma n di t e r a t i v ed e c o d i n ga l g o r i t h mb a s e do nr e l i a b i l i t y e t c ，t h ed e n s i t ye v o l u t i o na l g o r i t h mo nab a s i so fb pa l g o r i t h mf o rc a l c u l a t i n gn o i s e t h r e s h o l di sa l s oi n t r o d u c e d ；a f t e rt h a t ，i ti sd i s c u s s e dt h a th o wt os o l v et h e p r o b l e mo fi t sh i g he n c o d i n gc o m p l e x i t y ，s o m ee n c o d i n gm e t h o d sm a k i n gu s eo f t h e s p a r s i t yo fp a r i t yc h e c km a t r i xa r eg i v e n ，w eh a v ea l s od e s i g n e dt w oe n c o d i n gm e t h o d s i nv e r i l o gt t d ll a n g u a g ea n dt h e i rs i m u l a t i n gw a v e f o r m sa r ep r e s e n t e d ：f i n a l l y ，s o m e s i m u l a t i n gr e s u l t so fb e rp e r f o r m a n c eo fd i f f e r e n tl e n g t ha n dr a t ef o ra d d i t i v ew h i t e g a u s s i a nn o i s e ( a w g n ) c h a n n e l sa r ep r e s e n t e d ，a n da ne x a m p l ei sg i v e nt oc a l c u l a t e t h en o i s et h r e s h o l db yu s eo fd e n s i t ye v o l u t i o na l g o r i t h mo nab a s i so fb pa l g o r i t h m ， a n di t i sc o m p a r e dw i t ht h es i m u l a t i n gr e s u l t i na d d i t i o n ，w eh a v es t u d i e dak i n d o fs i m p l i f i e db e l i e f p r o p a g a t i o nd e c o d i n ga l g o r i t h mt h a tu s e dm a t h e m a t i cm e t h o d b yc u r v ef i t t i n gt or e d u c ei t e r a t i v eo p e r a t i o n s ，s oa st or e d u c ed e c o d i n gc o m p l e x i t y k e y w o r d s ：l d p c c o d e s ，m e s s a g ep a s s i n ga l g o r i t h m ，i t e r a t i v ed e c o d i n g ，b e l i e f p r o p a g a t i o n ，e n c o d e v e r i l o g i d l i i 前言 在香农的信息论建立以后，人们利用了代数中的一些理论，通过代数的方法 构造了许多纠错码，并研究了与之相适应的译码算法。这些码字大部分都是线性 分组码，比如汉明码、循环码和b c h 码，但是这些码字都是短码，因为这些码字 的纠错译码算法的复杂度随着码长的增加成指数级增长，长码的实现十分困难。 1 9 6 2 年，g a l l a g e r 名e 对纠错编码的研究中，提出t g a l l a g e r ：q 。这种编码因为校验 矩阵的稀疏性，使得译码的复杂度与码长保持线性的关系，码长较长时依然可以 有效地译码。然而当时人们普遍认为级联码更容易实现，以及一些技术条件的限 制，导致人们忽视了这种编码的存在。 1 9 9 3 年性能可以逼近香农限的t u r b o 码的出现，带来了纠错码理论上的突破， 在此基础上，人们纷纷用新的思想对各种编码进行研究。1 9 9 5 年，m a c k a y 和 w i b e r g 等人对g a l l a g e ：码重新进行了研究，发现g a l l a g e r l - q 也具有逼近香农限的性 能，而且具有较低的译码复杂度。经过一段时间的研究，人们将g a l l a g e r 码发展 为l d p c ( l o w - d e s i t y p a r i t y c h e c k - c o d e s ) 码，其性能甚至超过了著名的t u r b o 码。从1 9 9 9 年开始，关于l d p c 码的研究文献大量出现，l d p c 码已成为当前通 信领域的热门研究课题之一，并成为第四代通信系统( 4 g ) 强有力的竞争者。 l d p c 码具有优秀的译码性能，迭代的概率译码算法使得l d p c 码可以达到 接近香农限的性能，目前最优的l d p c 码方案距离香农限仅有0 0 0 4 5 d b ，而且 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 ) 算法。在编码二分图中没有圈的情况下，b p 算 法将成为最大似然译码，但是在编码长度有限的情况下圈的存在是必然的，因此 b p 算法的性能较最大似然译码还有一定的差距。而最大似然译码的复杂度又太 高，难以实现。因此如何改进b p 算法，缩小这种差距，同时使得算法实现的复 杂度又不至于太高成为了l d p c 码的一个研究课题。 在编码的数学模型上，l d p c 码具有简单的数学模型：二分图。l d p c 码的 缺点主要是编码的复杂度较高，虽然有研究表明它可以在线性时间内编码，但是 其复杂度相对于卷积码的即时编码来说，编码复杂度仍然过大。同时在码长较长 时，由于必须在接收到所有的信息比特后才能够进行编码，这就会给编码带来一 定的延时。另外，l d p c 码性能的优越性通常要在码长较长时才能够体现出来， 当码长为中短长度时，由于编码中短长度圈的存在，会在某种程度上降低编码的 性能。因此如何能克服其较高的编码复杂度，减少编码的运算量也同样成为人们 所关注的一个问题。 i i i 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 码的的圈长大小和码间距离对l d p c 码的译码性能的影响， 还介绍了l d p c 码校验矩阵的几种主要的构造方式。第三章论述了l d p c 码几 种主要的译码算法，包括比特翻转算法、加权的比特翻转算法、置信传播算法、 最小和算法及基于可靠性的迭代译码算法等，另外还讨论了一种用于确定译码门 限的基于b p 算法的密度演变算法。第四章探讨了利用l d p c 码校验矩阵的稀疏 性进行有效编码的方法、构造半随机校验矩阵的编码方法等几种编码方法，并对 两种编码方法进行了基于c p l d 的v e a i l o gh d l 设计，给出了编码的仿真波形； 第五章给出了不同码长和不同码率的l d p c 码在高斯白噪声信道下的几种译码 算法的误码率性能仿真结果，并且使用基于b p 算法的密度演变算法举例计算了 译码的噪声门限，并与仿真结果相比较。另外还研究了种简化的b p 算法，利 用曲线拟合的方法减少迭代运算量，以降低译码的复杂度。 学位论文独剖性声明 本入帮熬声鹱； l 、壁耱淡“求燕、翅黪”戆凝学糖糖飙攀嫒究工铭。 2 、本论文是貔个人在导师辩蜉下谶行的研究工佟和淑獬的研究 液聚。 3 、搴谂囊孛豫薅l 文羚，赛露褰验、数器耧蠢关瓣辩逡憝粪实翦。 4 、零论文孛熔蟹l 文髑致谢鹣内攀辨，幂魁食其饿入或其它搬掬 基经靛表或撰写过酌研究裁果。 5 、萁穗灏叁瓣零袋巍蘑徽瓣舞教溜澄盛论交枣终了声骥雾袭添 了谢惫。 撵鼗签名$ 猫蠲；型l ：鱼皇 学位论文使用授权声明 零入竞垒了辫您寒辨簸大学露关爨鼹、捷罔学位沧义豹娥定，鬻 校霄较保留学位论炎并翔匿家燕管部门绒其擀定税 鸯送交论文酌魂 子鞭_ 鞴纸藏激；霄投将攀毽谂冀= 篷予嚣蒸裁瓣簿酶少耋鬟黼势灸谬 论支漾入攀梭嚣繁德菝粪耀；枣援将学位谚文蕊蠹餐绽久蠢关数摄 库逃释检紫；有掇将学位论文驹标蘧期摘要淤缡如j i 暾。保密晌警撼 论文寝鼹密嚣逶鬻零瓣怒。 馋赣签名：i ：! 堕 瑟麓； 翌k ：生： 第一章绪论 第一章绪论 i i 数字通信系统 通信系统的目的在于将信息从储源及时可靠地( 有时还须秘密地) 传送副信 寝。逶售售邀中的啜声会苓霹避免地对传竣信息产擞不圆程度鲍于摅，从磷可能 降低通信可靠性，所以通信系统设计的核心闯题就是在有随机噪声的信道中如何 竟黢手撬，减夺售慧黄竣豹差错，阏瓣又不降低售惠赞竣豹效率，郄如鹰解决系 统的有效性与可靠蚀之间的矛盾。般地，通信系统的可靠性用误比特率( b e r ) 来甏餐，嚣蠢效蛙瘸痿怠传徐速率r ( 魄特绩遂德弩) 亲键霪。s h a n n o n 奁1 9 4 8 年发表的信息和编码理论的奠基性论文“通信的数学理论”i l j 中首次阐明了在有 撬潦詹信遂上实瑷靠逶信豹方法，指密实现有效甏露靠逡信怠传输麴途经耱是 通过编码。根据s h a n n o n 的信息理论，数字通信系统的基零组成如图1 1 所示。 翻1 1 数字通信系统模型 隧l ，l 中，信源编码嚣是把信源发出的消息如语言、图像、文字等转换成二 进制( 也可转换为多进制) 形式的信息序列。为了抗击传输过程中的各种干扰， 往臻要人为建增匆一些多余度，傻笑具有蠡动捡镫戏鳆镫力，这耱功能激售道 编码器完成。数字调制器的作用是手巴纠错码送出的信息序列变换成适合于储道传 赣懿售号。数字售譬在售遵捷输过程中，憨会遇到舞秘于拔嚣傻德痿号失粪，失 真的信号经数字解调器变成二进制( 或多进制) 信息序列。由于信道干扰的影响， 该镶惠毒残中霹栽蠢有镑谈，经避镕遴译磁器对其中熬错误送行纲正，霉经过售 源译码器恢复成原来的消息送给用户。 第一章绪论 1 2 信道编码理论 1 9 4 8 年，信息论的创始人s h a n n o n 从理论上证明了信道编码定理又称为 s h a n n o n 第二定理。它指出每个信道都有一定的信道容量c ，对于任意传输速率 r 小于信道容量c ，存在有码率为胄、码长为n 的分组码和，删) 卷积码， 若用最大似然译码，则随码长的增加其译码错误概率见可以任意小m 。 、p 。a6 8 一”6 ( 脚 ( 1 1 ) p 。ac e 一( ”+ 1 ) ”。5c ( 。) = ao e 一”t 。口( 。) ( 1 2 ) 式中，以和“。为大于0 的系数，毛( r ) 和e o ( r ) 为正实函数，称为误差指数，它 与r 、c 的关系 2 1 如图1 2 所示。由图可以看出：e ( r ) 随信道容量c 的增大而 增加，随码率r 的增加而减小。 这个存在性定理告诉我们可以实现以接近信道容量的传输速率进行通信，但 并没有给出逼近信道容量的码的具体编译码方法。 s h a n n o n 在信道编码定理的证明中引用了三个基本条件： 1 、采用随机编译码方式； 2 、编译码的码长n 趋于无穷大； 3 、译码采用最佳的最大后验译码。 在高斯白噪声信道时，信道容量： p c = 形1 0 9 2 【1 + 萧1 ( 圳5 ) 1 _ 3 上式为著名的s h a n n o n 公式，式中是信道所能提供的带宽，b = e 。t 是 信号概率，段是信号能量，r 是分组码信号的持续时间即信号宽度，e s w 是单 位频带的信号功率， ，0 是单位频带的噪声功率，b ( w n o ) 是信噪比。 口 巴q j r 图1 , 2e ( r ) 与r 的关系 2 第一苹绪论 由上面几个公式及图1 2 可知，为了满足一定误码率的要求，可用以下两类 方法实现。 一是增加信道容量c ，从而使e ( r ) 增加，由式( 1 3 ) 可知，增加c 的方法可 以采用诸如加大系统带宽或增加信噪比的方法达到。当噪声功率0 趋于0 时， 信道容量趋于无穷，即无干扰信道容量为无穷大；增加信道带宽形并不能无限 制的使信道容量增加。增加发射机功率；应用高增益天线；采用分集接收及低噪 声器件等通信中常用的方法都是通过增加信道容量c ，从而使e ( r ) 增加，以减 小误码率。 另一种方法是在r 一定下，增加分组码长r t ( 也就是增加分组码信号持续的 时间t ) ，可使p 随行的增加呈指数下降。但由于码长l l 的增加，当r 保持一定时， 可能使发送的码字数2 指数增加，从而增加了译码设备的复杂性。这种方法就 是信道编码定理所指出减少误码率的另一个方向。 一般我们可将信道编译码器所使用的纠错码从性能上分为坏码和好码。所谓 坏码是指只有将码率降至零才能使误码率为任意小的编码方式：而好码又可以分 为当误码率任意小时，码率逼近信道容量限的非常好码和码率可达到的非零最大 值小于信道容量限的一般好码。虽然s h a n n o n 指出一个随机选择的码为好码的概 率很高，但随机码的最大似然译码的复杂度往往与码长呈指数关系，即在误码率 随码长趋于无穷而趋向于零的同时，译码复杂度以指数增长。 自信道编码定理提出以来，如何构造一个逼近信道容量限的实用好码成了大 家关注的课题，并逐渐形成了纠错编码理论。下面对其进行简要概述。 1 3 纠错编码的发展 在香农的信息论建立以后，人们利用了代数中的些理论，通过代数的方法 构造了许多纠错码，并研究了与之相适应的译码算法。这些码字大部分都是线性 分组码，比如说戈雷码、汉明码、循环码和b c h 码，它们的译码算法主要采用 大数逻辑译码和捕错译码。但是这些码字都是短码，因为这些码字的纠错译码算 法的复杂度随着码长的增加成指数级增长，长码的实现十分困难，投入实际使用 的主要是短码，而这些短码的性能距离香农限很远。要达到香农限，必须要码长 较长的编码，所以1 9 6 2 年，g a l l a g e r 在【3 j 中描述了一种编码，现在通常称之为 g a l l a g e r 码，这种编码因为校验矩阵的稀疏性，使得译码的复杂度与码长保持线 第一章绪论 性的关系，码长较长时依然可以有效地译码。然而当时人们普遍认为级联码更容 易实现，以及一些技术条件的限制，导致人们忽视了这种编码的存在。 卷积码也是在同一时期提出的另一类重要的纠错编码，它在编码过程中引入 了寄存器，增加了码元之间的相关性。在相同复杂度的条件下可以获得比线性分 组码更高的编码增益，但是这种相关性同时也增加了分析和设计卷积码的复杂 性。随着人们对卷积码研究的深入，在卷积码的译码算法方面也出现了序列译码 和v i t e r b i 译码算法。因为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 码【4 】，在信道编码的理论和 应用中取得了突破性的进展。这种编码能够在码长较长时逼近香农的理论极限， 同时其译码复杂度也是可以接受的。t u 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 码获得巨大成功的启发下，另一类具有相似特征和性能的编码复活 了，这就是l d p c ( l o wd e n s i t yp a r i t yc h e c k ) 码。l d p c 码是g a l l a g e r 码的推 广，d j c m a c k a y 、m n e a l 和n w i b e r g 等人对g a l l a g e r 码重新进行了研究，发 现g a l l a g e r 码虽然性能较t u r b o 码稍有差距，但是它同样具有逼近香农限的性能 i s 。在g a l l a g e r 码的基础上，他们进一步研究了多元域上的l d p c 码【6 l ，发现多元 域上的编码较二元域上g a u a g e r 码的性能有较大提高且域的阶数越高编码的性 能越好。m g ；l u b y 和m m i t z e n m a e h e r 等人对g a l l a g e r 码进行了推广，提出非正 则的l d p c 码【7 1 ，这种编码的性能能够赶上甚至超过t u r b o 码的性能。和t u r b o 码的译码算法类似，l d p c 码的译码算法也是一种并行的迭代译码算法。 4 第一章绪论 1 4l d p c 码特点和研究现状 l d p c 码在m a c k a y9 5 年的文献 5 1 发表以后，重新得到人们的重视。许多研究 人员都投入到l d p c 码的研究之中，从1 9 9 9 年开始这方面的研究文献大量出现， l d p c 码己成为当前通信领域的热门研究课题之一，并成为第四代通信系统( 4 g ) 强有力的竞争者。经过几年的研究发展，l d p c 码的相关技术也逐渐走向成熟， 以下是一些l d p c 码的特点和研究现状。 l 、l d p c 码的特点 l d p c 码是一种具有稀疏校验矩阵的线性分组码，具有能够逼近香农限的性 能特性，而且由于校验矩阵地稀疏性，译码的复杂度较低，可实现线性复杂度； 译码算法本质上是并行算法，有利于硬件的并行实现，减少译码延时；它能够在 自己的迭代运行的过程中确定码字是否己译出，以决定译码过程能否结束，减少 迭代次数；同时其译码错误是可以检测的，目前的实验研究表明不可检测的错误 几乎从未出现；译码后的误码率可以随着信噪比的增加任意减小，没有误码率下 降减速的e r r o r f l o o r 现象；另外，置信传播算法存在一种译码门限效应，只有当 信道噪声方差低于门限值时，译码后的误码率可以趋于0 ，否则将趋向于一个大 于零的正数；在编码的数学模型上，l d p c 码具有简单的数学模型：二分卧剐。 l d p c 码的缺点主要是编码的复杂度较高，虽然有研究表明它可以在线性时间内 编码，但是其复杂度相对于卷积码的即时编码来说，编码复杂度仍然过大。同时 在码长较长时，由于必须在接收到所有的信息比特后才能够进行编码，这就会给 编码带来一定的延时。另外，l d p c 码性能的优越性通常要在码长较长时才能够 体现出来，当码长为中短长度时，由于编码中短长度圈的存在，会在某种程度上 降低编码的性能。 2 、l d p c 码的分类 根据二分图中信息节点和校验节点次数分布的不同，l d p c 码可以分为正则 码和非正则码。正则码是所有信息节点有相同次数，所有的校验节点也有相同次 数的编码。而非正则码是正则码的推广，它的次数分布无论是信息节点还是校验 节点都不再有次数相同的限制。由于次数分布选择上的自由性只要适当选择非正 则码的次数分布，会在译码时导致一种波状效应，极大的提高译码的门限值，相 第一章绪论 应的在性能上相对正则码也有较大的提高。 3 、l d p c 码的译码 l d p c 码译码算法中性能最好的是连续性的b p ( b e l i e f p r o p a g a t i o n ) 算法【5 】， b p 算法本质上是并行算法，在编码二分图中没有圈的情况下，b p 算法将成为最 大似然译码，但是在编码长度有限的情况下圈的存在是必然的，因此b p 算法的 性能较最大似然译码仍有一定的差距。而最大似然译码的复杂度又太高，难以实 际实现。因此如何改进b p 算法，缩小这种差距，同时使得算法实现的复杂度又 不至于太高成为了l d p c 码的一个研究课题。一种可行的方案是基于迭代信息可 靠性的译码算法，它将b p 算法与o s d 算法结合，在每次b p 译码迭代后增加 o s d 算法的迭代运行，提高了译码性能【9 】；也可以采用一些数学方法对迭代过程 中的函数进行简化处理【1 0 1 ，以降低译码的复杂度；还有快速收敛的译码算法【1 1 】 及其他的改进算法等【】2 1 1 埘。上面的算法都是针对高斯信道，目前在非高斯的低 质量信道上，l d p c 码译码算法的研究也已经展开，如瑞利衰落信道【1 4 】【1 5 】、部分 响应信划16 】1 1 7 1 等。 4 、l d p c 码的编码 l d p c 码所面临的一个主要问题是其较高的编码复杂度和编码时延。对其采 用普通的编码方法，l d p c 码具有二次方的编码复杂度，在码长较长时这是难以 接受的。t j r i c h a r d s o n 和r l u r b a n k e 在【l8 】中利用校验矩阵的稀疏性对校验矩阵 进行一定的预处理后，在线性时间内编码的有效算法，初步解决了l d p c 码的应 用所面临的一个主要问题。但是编码前的数据接收过程引入的编码时延仍然是 l d p c 码需要解决的一个问题，目前的解决办法有l d p c 编码系统符号同步技术 等1 1 9 1 。l i n 等在口o 】提出的一种具有循环码特性的码字，同样具有稀疏的校验矩阵， 可以使用b p 算法，这种码字的编码完全可以通过线性移位反馈寄存器来实现， 具有线性复杂度和线性时延的编码。另外还有采用预判决信息的l d p c 码编码调 制方案2 1 1 及快速编码方面的研究1 等。 5 、影响l d p c 码的性能的因素 l d p c 码性能的好坏受到众多因素的影响，其中l d p c 码编码结构的选择决 定了译码的门限值，门限值是每一种编码结构在理论上能够达到的极限性能。而 6 第一章绪论 编码的长度决定了其性能能够在何种程度上逼近该门限值。 对l d p c 码的译码性能分析已经有了一些较为完善的理论，在理想的编码结 构条件下，t j 砒c h a r d s o n 和r l u r b a n k e 在】中对整个m e s s a g ep 觞s m g 算法给 出完整的数学分析，计算出了随译码迭代次数的增加，码字比特可靠性信息的概 率演化方程。但是有限长的l d p c 码中，其编码结构中必然有闭合环路的存在， 因此对这种情况下的译码算法性能分析是不可回避的问题，目前对编码结构中的 闭合环路是如何影响译码性能，还只有一个模糊的概念需要进一步的研究探讨。 此外对译码算法还有一些基于高斯近似的分析洲等。 在接收端译码算法的选择是影响编码性能的决定性因素，要得到好的性能就 要付出复杂度上的代价。在译码过程中对信道中的信噪比估计的准确性也是影响 译码性能的一个重要因素，如果信噪比估计失配会使译码性能降低，估计的偏差 越大性能的损失越大，甚至造成译码器不能够正常译码。 6 、l d p c 码的设计方法 l d p c 码性能的优越性通常要在码长较长时才能够体现出来，当码长为中短 长度时，由于编码结构中短长度的闭合环路的存在，会在某种程度上降低编码的 性能。考虑到影响l d p c 码性能的因素，要设计好的l d p c 码，首先要根据应 用中纠错性能和时延等方面的要求选择合适的码长，然后根据信道类型和性能需 求寻找具有较高译码门限值的编码结构，对这方面现有的搜索方法主要有 鼬c h a r d s o n 等人提供的局部优化和全局优化的搜索方澍2 5 1 。但是它们的搜索量都 相当大，需要借助计算机进行搜索，更完善有效的搜索算法有待进一步的研究。 目前高斯信道下门限值较香农极限仅仅差o 0 0 4 5 d b 的次数分布对已经找到了。 选好次数分布对之后，需要在已选定的码长和次数分布对之上选择具有合适二分 图结构的编码以获得尽可能好的编码性能。这主要是如何构造没有短长度圈或圈 的平均长度尽可能大的校验矩阵。对于长码长的编码，随机构造是一种可行的方 法，因为码长越大，矩阵越稀疏，短长度圈出现的概率就越小，且由于大数定理 的作用，圈的长度分布趋于一致，编码的性能也趋于一致：但是对中短长度的编 码，校验矩阵对编码性能就具有较为明显的影响，需要研究合适的构造方法，以 构造出好的校验矩阵，获得好的编码性能。这方面地构造方法主要有组合构造法 、有限几何构造法【2 0 】、群论构造法【2 7 】和图论构造法【2 8 】，还有基于循环矩阵 的构造方法【3 及循环差集构造方法f 3 l 】等。另外需要根据信道类型和性能要求选 第一章绪论 择合适的译码算法，尽可能以最小的代价获得较好的译码性能。 7 、l d p c 码的实现和应用 在工程实现上，主要有基于f p g a 的实现吲、基于d s p 的实现【3 3 以及v l s i ( j i i 大规模集成电路) 实现【3 4 】【3 5 】p 6 】。由于l d p c 码的优越性，有望在通信中得到广泛 的应用。目前在第四代移动通信中使用l d p c 码的提案已经提交：l d p c 码还可 以广泛应用于卫星数字电视【3 _ 7 】、深空通信、磁存储器【3 8 】【3 9 】和其他数据通信等方 面。目前已有很多系统采用l d p c 码，基于l d p c 码的编码方案已经被下一代卫 星数字视频广播标准d v b s 2 采纳；i e e e 8 0 2 3 a n 工作小组在面向双绞线的 1 0 g b s 以太网标准“1 0 g b a s e - - t ”草案中，也采用了l d p c 码。另外，由于l d p c 码数学模型上的成功性，引起了人们用l d p c 码的观点对许多编码进行了重新研 究，获得了许多新的认识和成果。 1 5 本章小结 本章首先介绍了信道编码理论、纠错编码的发展情况以及l d p c 码的提出过 程，接着详细阐述了l d p c 码的特点、设计方法和应用领域，同时对目前在编译 码过程中所存在的复杂度问题和影响l d p c 码的误码率性能的二分图中的圈的 长度问题以及译码的噪声门限问题进行了深入的分析，为本课题的研究工作奠定 了基础。 第二章l d p c 码的构造 第二章l d p c 码的构造 l d p c 码揭示了一种新的具有低密度校验矩阵的分组编码构造方式。它利用 校验矩阵的稀疏性解决长码的译码问题，可以在线性时间内译码，同时又近似于 香农提出的随机编码，获得了优秀的编码性能。g a u a g e r 提出的l d p c 码具有正则 的二分图结构，其二分图每个信息节点都有相同的次数，每个校验节点也都有相 同的次数，现在通常称为正则码。经过近几年的研究，人们在正则码的基础上进 行推广又提出了非正则码及多元域上的l d p c 码。对u ) p c 码来说，在不考虑码 长和次数分布对的情况下，编码校验矩阵的结构就成了影响其性能的重要因素， 反映在二分图上对编码性能有重要影响的就是图中圈的长度分布，需要采用一定 的方法对校验矩阵进行构造，获得好的编码。 本章首先从二分图的角度给出了正则码和非正则码的定义，介绍了二元域和 多元域的l d p c 码，然后给出了构造u ) p c 码校验矩阵的几种方法。 2 1l d p c 码的定义与结构 2 1 1l d p c 码的定义及其描述 一个码长为、信息位个数为k 的线性分组码可以由一个生成矩阵g 来定 义，信息序列s 通过g 映射成发送序列，也就是码字v = s g 。线性分组码也可 以由一个一致校验矩阵日来等效描述，所有码字均满足日v 7 = 0 。校验矩阵的 每一行表示一个校验约束c ；，其中所有非零元素对应的码元变量v ，构成一个校验 集，用一个校验方程表示；校验矩阵的每一列表示一个码元变量参与的校验约束， 当列元素不为零时，表示该码元变量参与了该行的校验约束。 l d p c 码是一种线性分组码，它的名字来源于其校验矩阵的稀疏性，即校验 矩阵中只有数量很少的“1 ”，大部分都是0 。g a u a g e r 最早给出了正则l d p c 码的定义，正则l d p c 码的校验矩阵日满足下面三个条件： ( 1 ) h 的每行有p 个“1 ”； ( 2 ) h 的每列有五个“1 ”，五3 ； ( 3 ) 与码长和日矩阵的行数m 相比，p 和力都很小。 9 第二章l d p c 码的构造 2 1 2l d p c 码的t a n n e r 图表示 任意一种线性分组码都可以表示成为t a n n e r 图( 编码二分图) 的结构。二 分图中将节点分为两个不同的集合，同一个集合内部的节点没有连线，只有属于 不同集合的两点之间可能有连线。对于l d p c 码，我们可以通过它的校验矩阵 日。的肘个校验方程和个变量，确定两个节点集合：变量节点集合和校验 节点集合。如果某个变量参与了某个校验方程，则这两个不同集合的节点之间有 一条边相连。 例如一个( 1 2 ，3 ，6 ) 的正则l d p c 码，它的校验矩阵如式( 2 1 ) 所示，对应的校验 方程组如式( 2 2 ) 所示。我们可以画出对应的编码二分图，如图2 1 所示，图中变 量节点集合 h ，1 ，：川。：) 和检验节点集合 c 。，c ：气) 内部不存在相连的边，但两个 集合之间有边相连，符合二分图的定义。图论中定义某个顶点x 相连接的边的数 目为该顶点的次数，即d e g ( x ) 。图2 1 中，每个变量节点v j 与三条边相连接，每 个校验节点c ，与六条边相连，所以有d e g ( v ，) = 3 ，d e g ( c ，) = 6 。在一个包含边和 节点的图形中，节点的次数分布很大程度上决定该图形的一些基本性质。 h = 1lo 0l 1o 1o o 0 0 0 l10 0l1 l1l o ol 010 0 01 ( 2 1 ) v l o v 2 0 v 3 0 v 6 0 v 7 0 v l l = 0 v 1 0 v 2 0v 3 0 v 4 0 v 5 0v 1 2 = 0 v 6 0 v 7 0 v 8 0 v 1 0 0 v 1 1 0 v 1 2 = 0r 、 v l o v 4 0v 8 0v 9 0 v 1 0 0v 1 2 = 0 v 2 0 v 4 0 v 5 0 v 7 0 v 8 0 v 9 = 0 v 3 0 v 5 0 v 6 0v 9 0 v 1 0 0 v 1 1 = 0 1 0 第二章l d p c 码的构造 图2 1 ( 1 2 ，3 ，6 ) 码的二分图 上面的二分图结构当中，四条粗体连线构成了一个有向的闭合环路，由v 1 起 始，最后返回h ，长度为4 。在一个l d p c 码的编码二分图中，会存在许多这样 的闭合环路，其中最短的闭合环路的长度，称之为最小圈长( g i r t h ) ，上例的二 分图中，g i r t h 即为4 。 通过上面的二分图结构，可以直观的看出对校验矩阵日做简单的行或列的 交换，不会改变对应的l d p c 码的二分图结构，以及g i r t h 的分布。有时我们按 照某种规则构造一个校验矩阵，在将该校验矩阵转化为生成矩阵的时候，会出现 存在冗余行或必须交换列的情况。在这种情况下，可以交换原有校验矩阵日中 部分行列的顺序，生成一个新的校