（信号与信息处理专业论文）ldpc编译码算法研究与应用.pdf

l 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 【1 】在上个世纪六十年代初 发现，但是限于当时的计算水平和人们对这种形式非常简单的码的认识不足，数 年来它一直遭受冷遇，这期间只有r m i c h a c lt a i l n e r 7 】等对它进行了零星的研 究，且几乎没有实质性的进展。而自从u ) p c 码被m a c k a y 和n e a l 等人重新发 现之后，其优越的性能很快引起研究人员的重视，u ) p c 码迅速成为人们研究的 焦点。经过几年的研究和发展，人们在各方面都取得了突破性的进展，u ) p c 码 的相关技术也日趋成熟，甚至已经开始有了商业化的应用成果。 u ) p c 码的近期研究大体包括以下几个方面： 1 1l d p c 码的码结构分析及其优化 2 ) l d p c 码编码方法研究 3 ) l d p c 码译码算法性能分析 4 ) u ) p c 码的硬件实现 5 1u ) p c 码的应用 本文主要就目前较为流行的各种u ) p c 译码算法进行了分析比较，并且创新 地提出了在空时系统中适用的新的u ) p c 译码算法，穿梭天线译码( c r o s s a n t e l l n am e s s a g ep a s s i n 曲算法，简称c a m p 算法。该算法已于2 0 0 6 年1 月在 美国拉斯韦加斯举行的c c n c 2 0 0 6 会议d e i n o i l s 删i o ns e s s i o n 上发表，收录在 d e m o n s t r a t i o np r o c e e d i n g 中。关于c a m p 算法的分析主要集中在第五章。下面 对该算法提出背景和基本内容作出简要的介绍。 不同于空时分组码，在各发射天线上发送不相关的数据，仅仅用空时结构来 提高信道容量。在没有空间分集的情况下，用u ) p c 码的超强纠错性能来抵制衰 落的影响。 当发射天线数大于1 时，不同天线发送符号之间会产生干扰。译码器外信息 输入是引入多天线干扰( 乘以m 以o 信道逆矩阵) 的a w g n 信道下的似然概率。 标准的置信度传播译码算法并非针对空时系统设计，外信息参数默认是a w g n 信道下的似然概率，而且在每次迭代过程中保持不变。如果在空时系统中沿用标 准的置信度传播译码算法不太合理。针对该问题，本文不仅提出了l d p c 编码的 空时系统框架结构，而且提供一种类似于置信度传播算法的穿梭天线消息算法。 穿梭天线消息传递算法通过将由其他发射天线的累积似然概率推导出的伪后验 概率传递给当前的译码天线更新外信息，并以此来抵消其他发射天线符号引入的 干扰。 为了滤除干扰，外信息计算节点协同译码单元进行若干次迭代计算。在 1 锄n e r 图上，除了变量节点和冗余校验节点之外，还增加了外信息计算节点。 关键字： 低密度循环冗余校验( u ) p c ) 码，分层空时结构，置信度传播( b p ) 译码算法，穿 梭天线译码( c a m p ) 算法，外信息 l d p ce n c o d i n ga n dd e c o d i n ga l g o r i t h m r e s e a r c ha n di t sa p p l i c a t i o n a b s t r a c t l d p c ( l o wd e n s l 时p a r 时c h e c k ) c o d ew a s6 r s ti n v e n t e db yg a l l a g e r 【l 】i n1 9 6 2 b e c a u s e o ft h el i m i to fc o r n p u t e lt h er e s e a r c h c so nt h i sk i n do fc o d ep m c e s ss l o w l yp e 叩i ed i dn o tp a y a r l ya n e m i o no nt h i sk i l l do fc o d e ss e v e r a jd e c a d e s ，u n t i lm a c k a va n dn e a lf 7 1r e d i s c o v e r e di ti n 1 9 9 8t h em e n to f t h i sc o d ew a ss 0 0 np r o v e da t l dl d p cc o d eb e c o m e sp e o p l e sr e s e a r c hh o t s p o t a r e rs e v e r a ly e a f s d e v e l o p n 【】e n t ，r e s e a r c h e r sm a k eg r e a tp r o g r e s so ne v e r yb r a n c h e s 锄dl d p c t e c l l n i q u e sb e c o m e sm 咖r ea n de v e nh a sc o m m e r c i a la p p l i c a t i o n s c u r r e n t 坤s e a r c hb r 柚c h e so nu d p cc o d ea r eg e n e m l l yd i v i d e da sf o l l o w s ： 1 ) l d p cc o d es t n l c h l r e 柚a l y s i s 柚do p t i r n i z 血o n 2 ) ) p ce n c o m g m c i l l o d sr e s e a r c h 3 ) u ) p cd e c o d i n ga l g o r i t mp e r f b 胁a i i c ea n a l y s i s 4 )h 甜d w 黜l m p l e 眦n 诅t i o no f l d p cc o d e 5 ) 1 1 l ea p p l i c a h o no f 【d p cc o d e m ym 粥t e rd i s s e n a h o nm a i n l yc 伽1 p a r e ds e v e m li n l p o r t a n tl d p cd e c o d i n ga l g o f i l ma n d i 蛐o v a t i v e l yp m p o s e d an e wd e c o d i n ga 1 9 0 r i m mc a l l e dc a m p ( c f o s sa n t e 蛐am e s s a g ep a s s l n g ) w h i c hi ss p e c i a lf o rm eu ) p cc o d e ds p a c e - t i m es y s t e m n i i sa 1 9 0 一m mh a sb e e np u b l l s h e do n c c n c 2 0 0 6d e 啪璐心撕o np r o c e e d i n g s t h ed l s c u s s i o no nc a m pa 1 鲫t 1 1 mi sm a i n l yi nc h 印吼 5 f o l l o w i n g i s i h e b r i e f i n 仃o d u c 缸o no f t h e b a c k g r o l l l l d a n d b a s i cc 伽地n t so f c a m p a l g 嘶t h m u n l i k es p a c e t i m eb l o c kc o d e ，w e 仃a n s i i l i ti r r e l e v a n ti n f 0 咖a t i o ni ne a c h 锄s m n 柚t e i 】1 l a a n do n l ym a l el i s eo fm es p a c e 石m es t m c t i l r et oi n c r e a s et l l ec h 枷e lc a p a c n y - w i m o u ts p a c e d i v e r s i t y ，l d p ci su s e dt oc o n q u e rm e 砌u e n c eo f 跚i i l g w h e nt h en a l l s i l l i ta n t e 衄a s n u m b e ri sm o r et h a n1 d i f r e l 它n ta n t e n n a sw i l li n t e r f e r ee a c h o m e r s t h ei n p u to fe x 打i t l s l ci n f 0 衄a t i o ni st h el i k e l i h o o dp m b a b i l 时u n d e ra w g nc h 咖e lw 曲 m l l l t i p l e - a n t e n n ai n t e r f b r e n c e h o w e v e ls t a n d a r db e l i e f p r o p a g a t i o nw a sn o td e s i g n e ds p e c i a lf 打 s p a c et i m es 廿u c t u r ea n dd e f a u l te x t r i l l s i ci n f o a t i o ni sm el i k e l l h o o dp r o b a b i l i t yu n d e ra w g n c h 枷e lw h l c hi ss e tf i x e dd u r i n gw h o l er e c u r s i v ep m c e s s o b v i o u s l y i ti sn o tr e a s o n d b l ew eu s e s t a n d a r db e l i e fp r o p a g a t i o na l g o r i m mi ns p a c e 石m es y s t e m h 1o r d e rt os o i v em ep r o b l e m ，t h i s d i s s e r t a t i o nn o to n l yp r o p o s e dal d p cc o d e ds p a c en n l es t m c t i l r e ，b u ta l s op r o p o s e dab e l l e f p r o p a g a t i o nl j k e da l g o r l t h r n ，c a m pa l g o r l t h f n t h l sa l g o r i t h mu p d a t e se x t r i n s i ci n f o i m 撕o nb y c a l c u l a t i n go t h e ra 1 1 t e 加a s ap o s t 甜撕p r o b a b i l 毋a n dp a s s i n gi tt ot h ec u n md e c o d i n g 柚t e 妯a t oc a n c e lt 1 1 ei n t e r f b r e n c ei n 柚o d u c e db ys y m b o l sf m mo t h e ra 1 1 把n n a s i no r d e rt of i h e rm u l t i p l ea n t e n n ai n t e r f e r e n c e ，e x 埘n s i cm f 0 “n a t i o nc a l c u l a t i o nn o d e s o p e r a t es e v e r a lc o m p u t a n o nt o g e t h e rw i md e c o d e r s i nt a n n e rg r a p h ，b e s i d e sv a “d b l er l o d e sa n d p a r i t yc h e c kn o d e s ，t h e r ea r ee x 打i n s i cm f o r m a t l o nc a l c u l a t i o nn o d e st o o k e yw o r d ： l d p c ( l o wd e i l s l t yp a r i t yc h e c kn o d e s ) ，l a y e r e ds p a c et l m es t m c i u r e ，b e l i e fp r o p a g a t i o n ( b p ) ， c m s sa 1 1 t e 加ad e c o d i i l g ( c a m p ) e x 廿i n s j ci n f o n a 缸o n 声明 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：暨雀 日期： 3 丛五：墨：4 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：翻量 日期 导师签名：望塑日期 ：比京邮电人学硕士论文 1 1 信道编码理论概述 第一章绪论 一般地说，通信系统是指从一个地方向另一个地方传送信息的系统，例如， 电话网、无线通信、电视、移动通信、计算机网等。而存储系统在某种意义上也 可以看成从现在向将来发送信息的通信系统，例如，磁盘或光盘驱动器、磁带记 录器、视频播放器等。这些系统都可以抽象为下面的通信系统模型来描述 1 。 图1 1 通信系统模型 编码器( e n c o d e r ) 的功能是将消息变成适合于信道传输的信号，在通信系统 中称为发信机，而在存储系统中称为记录器或写入器。编码器包括：信源编码器 ( s o u r c ee n c o d e r ) ，信道编码器( c h 锄e le n c o d e r ) 、调制器( m o d u l a t o r ) 如图1 2 所示。应该指出，在模拟通信系统中的编码器仅包含调制器，编码器中主要部分 功能如下： 图1 2 编码器的组成 译码器( d e c o d e r ) 实现与编码器相反的功能，即从信号中恢复消息，在通信 系统中称为接收机，而在存储系统中称为回放系统或读出器。译码器包括：解调 器、信道译码器、信源译码器，如图1 3 所示。在模拟通信系统中译码器仅包含 解调器。 北京邮【乜火学硕l 。论文 一竺! 兰h 甚h 墨卜 消息符号符号信号 图1 3 译码器的组成 图1 2 和图1 3 中的信道编译码部分是以特定的控制手段，引入适量冗余比特， 以克服信息在传输过程中受到的噪声和干扰影响。根据s h 籼o n 提出的信道编 码定理，对任意一个平稳离散无日| 乙有噪声信源，都有一个固定的值，称之为信 道容量，记做c 。只要信息的传输率低于信道容量，就必然存在一种编码方法， 使得信息出现差错的概率随码长的增加趋于任意小；反之，当信息传输速率超过 信道容量时，则不存在这样的编码方法。这就是著名的信道编码定理，他给出了 特定信道上信息传输速率的上确界。 定理1 1 ( 信道编码定理) ：任意离散输入无记忆平稳信道存在信道容量c ， 对预期的任一数据速率r o ，有可能设计一对编译码器， 以保证该信道中速率为r 的数据传输具有小于p 的译码错误概率。 信道编码定理指出，在有扰信道中，只要信息传输速率小于信道容量，就有 可能实现任意可靠的信息传输。这个存在性定理提醒我们可以实现以接近信道容 量的传输速率进行通信。但遗憾的是该定理采用的是非构造性的证明方法，其中 并没有给出逼近信道容量的码的具体编译码方法。 s h 蛐o n 在信道编码定理的证明中引用了三个基本条件，即： 1 ) 采用随机编码方式； 2 ) 码字长度趋近于无穷大； 3 、译码采用最佳的最大似然译码。 一般可将信道编译码器所使用的纠错码从性能上分为坏码和好码。所谓坏码 是指只有将码率降至零彳能使误码率为任意小的编码方式；而好码又可以分为当 误码率任意小时，码率逼近信道容量限的非常好码和码率可达到的非零最大值小 于信道容量限的般好码。虽然s h a 皿o n 指出一个随机选择的码以很高的概率 为好码，但随机码的最大似然译码复杂度往往与码长呈指数关系，即在误码率随 码长趋于无穷而趋向于零的同时，译码复杂度以指数增长，而在实际应用中，只 能使用以码长多项式的时间和空问复杂度内完成编译码的纠错码，因而尽管一般 的随机码是好码，但不能看作是实用码。 自信道编码定理提出以来，如何构造一个逼近信道容量限的实用好码成了众 多研究学者竟相研究的课题，并逐渐形成信扈、沦的个重要分支一信道编码理 论。五十多年来，人们构造实用好码的探索基本上是按照s h a n n o n 所引用的基 北京帅l u 大学顺卜论文 本条件的后两条为主线展丌的。虽然从理论上讲，除了目前已知的码外，几乎所 有的码都是好码，但到目前为止，构造出真正意义上的实用好码还有很长的距离。 虽然如此，通过众多学者，特别是有关数学和信息论学术界的研究人员五十多年 的共同努力，目前已经取得了很多成果。 纠错码 2 3 】 4 从构造方法上可分为分组码( b l o c kc o d e s ) 和卷积码 ( c o n v o l u t i o n a lc o d e ) 两大部分。在分组码方面，第一个分组码是1 9 5 0 年发现的 能纠正单个错误的h 啪m i n g 码；在整个5 0 年代，基于代数理论又发现了多个短 码长的分组码，如1 9 5 4 年g o l a y 发现的g o l a y 码以及r e e d 和m u i i e r 发现的 r m 码，p 啪g c 在1 9 5 7 年发现的循环码等。最有意义的是b o s e 和r a y c h a u d h u r i 在1 9 6 0 年及h o c u e n 曲e m 在1 9 5 9 分别独立发现的能纠正多个错误的b c h 码，以及 r e e d 和s o i o m o n 在1 9 6 0 发现的非二进制r s 码。实际上，b c h 码可以看作是某个r s 码的子域子码，而r s 码又可以看作是b c h 码的特例。其后发现的分组码主要有 1 9 7 0 年的g o p p a 码和1 9 8 2 年发现的代数几何码。在所有这些分组码中，除了( 沁p p a 码和代数几何码中存在的个别达到s h a n n o n 限的渐进好码外，其它均不是好码。 分组码的译码主要采用基于代数的硬判决译码。 卷积码最早是由e l i a s 提出，早期被称为树码( n e ec o d e s ) ，现在称为格形码 ( t r e l l i gc o d e s ) 或卷积码。卷积码具有动态格图结构，可用有限状态机来描述 其状态。由于缺乏有效的理论研究工具，对卷积码的有效研究成果不是很多，目 前性能好的卷积码的构造方法主要借助于计算机搜索来获得。卷积码的译码一般 采用概率译码，由于译码算法的简单、实用和易于实现，卷积码被广泛应用于实 际中。 1 9 6 6 年，f o m e y 将分组码和卷积码结合起来，提出了级联码( c 0 n c a t e n a t e d c o d e s ) 的概念。级联码一般采用r s 码作为外码，卷积码作为内码。f o m e v 的 研究表明，级联码在性能得到较大改善的情况下，其译码复杂度并不显著增加。 根据对接收信号处理方式的不同，纠错码的译码可以分为硬判决译码和软判 决译码。硬判决译码是基于传统纠错码观点的译码方法，解调器首先对信道输出 值进行最佳硬判决，再将判决结果送入译码器，译码器根据解调器的判决结果， 利用码字的代数结构来纠正其中的错误。而软判决译码则充分利用了信道输出的 波形信息，解调器将匹配滤波器输出的一个实数值送入译码器，由于实数值包括 了比硬判决更多的信道信息，译码器能够通过概率译码充分利用这些信息，从而 获得比硬判决译码更大的编码增益。 总之，尽管随机码是理论上的好码，但出于其编码实现的困难性和无法承受 的译码复杂度而只被用做理论分析的工具，在信道编码定理和后来的许多编码理 论成果中，代数码理论始终占据了主导地位，使得传统的信道编码技术受到临界 北京邮电大学硕一l 论文 速率( c r i t i c a ir a t e ) ，也称作截止速率( c u t o 行r a t e ) r 的限制 5 。 1 9 9 3 年t u r b o 码 6 【7 的提出被看作是信道编码理论研究的重要里程碑。 b e h 伽等人将卷积码和随机交织器相结合，同时采用软输出迭代译码来毕近最 大似然译码，取得了超乎寻常的优异性能，并一举超越了截止速率，直接逼近 s h 锄o n 提出的信道容量限。n 曲。码是一种信道编码理论界梦寐以求的可实用 非常好码，它的出现标志着信道编码理论研究进入了一个崭新的阶段。t u r b o 码 成功的根本原因在于其实现方案中长码构造的为随机性是核心，它通过随机交织 器对信息序列的伪随机置换实现了随机编码的思想，从而为s h a l l i l o n 随机编码 理论的应用研究奠定了基础。 随着t u r b o 码的深入研究，人们重新发现g a l l a g e r 早在1 9 6 2 年提出的低 密度校验码 8 【9 ( 1 0 wd e n s i t yp 撕t y c h e c kc o d e s ， 简称l d p c 码) 也是一种具 有渐进特性的非常好码，它的译码性能同样可以逼近s h a n n o n 信道容量限 1 0 1 1 1 2 ，两者都是基于图构造的低密度码，译码算法具有等价性，从而使两者在基 于图模型的编译码研究中得到了统一。 1 2l d p c 码简介 g a l l a g c r 于1 9 6 2 年提出的l d p c 码，是一种具有稀疏的校验矩阵的分组码。 所谓的“低密度”正是来源于矩阵的稀疏性。 0 o 0 0 o o 111 olo o01 10o 0o 0 o ol 11o 图1 4 规则u ) p c 码 由线性分组码的性质，在域f 上，码长为”，位信息比特的编码c 可 用( ”a ) n 的校验矩阵h 描述：c ( h ) = x f _ 胁7 = o ) 。 1 o o o 1 o o 1 0 1 0 o 1 0 o 1 o o l o o 1 o o o 1 o o l o o o l 1 o o o 0 1 0 o l 1 o 0 1 o o o 1 o 0 o 1 o o 1 o 0 o 0 1 o l o o 1 o l o o 1 1 h ：比京j f l f j _ 1 人学砸l 论文 121l d p c 码的图结构 在l d p c 码的研究过程中，t a 皿e r 提出“二分图( b i p a n i t eg r 印h ) ”模型对 u ) p c 码进行分析f 1 3 ，二分图由变量节点( v a 曲1 en o d e s ) 、校验节点( c h e c k n o d e s ) 以及连接它们的边( e d g e ) 组成。图2 1 中的校验矩阵对应图2 2 ( a ) 中的二分图。左侧的节点为变量节点，代表了编码后的比特位，对应校验矩阵中 相应的列；右侧的节点为校验节点，代表了编码比特组成的校验方程，对应校验 矩阵中相应的行；图中的边则表示左侧的某个比特出现在右侧的某个校验方程 中，对应了校验矩阵中的非o 元素。 1 2 2 规则码和非规则码 上述例子是个二元域上的l d p c 码，其编码的校验矩阵中，每一列有d 、，( - 3 ) 个非零元素，每一行有以( = 4 ) 个非零元素。即，编码码字x 中的每个比特参加吐， 个校验约束，而每个校验约束包括d ，个比特。在二分图中，d ，吐分别表示与 变量节点和校验节点相连的边数，称为该节点的次数( d e g r e e ) 。当为常数时( 如 上面的例子) ，即所有比特点的次数都一样，所有校验节点的次数也都一样，这 样的l d p c 码称为规则( r e g u l a r ) l d p c 码，简称规则码。 v a l 1 a b l o n o d e s ( a )r e g l i l a rl d p c c o d e v a r i a b l e n 0 d e s 图1 5l d p c 码的二分图 ( b )i r r e g l l l a r l d p cc o ( 1 e 北京邮电大学坝l 论文 而当二分图中的比特节点的次数各不相同( 校验节点的次数也有相应的变 动) 时，这样的u ) p c 码称为非规则( i 玎e g u l a r ) l d p c 码，简称非规则码。非 规则码通常用次数分布对( d e g r e ed i s 砸b u t i o np a i r ) ( a ，p ) 来描述： d 紫 一“ 五 ) = 五z 、p o ) = 一x 4 分别为变量节点和校验节点的次数分布多 扛2净2 项式；丑( 肛) 表示与次数为f 的比特( 校验) 节点相连的边数在总边数中所占的 比例；d ( d ，) 表示比特( 校验) 节点中的最大次数。图1 5 ( b ) 为一例 = o 4 ， 丑= o 6 ，岛= o 6 ，岛= o 4 的非规则码。 由于非规则码中节点次数分布的不均匀，次数高的变量节点因为受到较多的 校验约束的监督，将较快地被正确译码。反过来，它们又将给其它次数较低的节 点提供更可靠的译码信息。这就是所谓的“波浪效应( w a v ee 腩c t ) ”。 从变量节点的角度看，其次数越高越好，因为它进行监督的校验节点越多， 提供的译码信息越准确，使得它能更快更准确地被译码：但是从校验节点角度看， 则是次数越低越好，这样它提供给与之相邻的比特节点的校验信息就更准确。针 对这一矛盾，非规则码显然比规则码能够更好地实现两者的平衡。这正是我们研 究、优化非规则码的目的所在。 对( 旯，p ) 非规则码，若给定码长月，码率r ，则校验节点的个数m z ( 1 月) n 。 设二分图中的总边数为e ，则： 小孚= p ( 功出= 掰je f 。 0 士： ( 1 一1 ) t 一2 t _ i ， p ( 曲出p ( x ) 出 o0 d 丑表示与次数为f 的比特节点相连的边数；e 互则表示次数为f 的比特节 i 点的个数；同理，e 旦表示次数为f 的校验节点的个数。 z 由线性分组码的定义，在校验矩阵日的行向量线性无关的条件下，码率： 月：! 竺：1 一兰 珂n 对( d 。，d ，) 规则码而言， 码的码率又可以写成： ，司专 ( a ，d ) 非规则码的码率 ( 1 2 ) 由于二分图中的总边数e = n 一。= m d 。，所以规则 ( 1 3 ) 北京邮l u 人学硕卜论文 p ( x ) 出 r 。m5 1 一卜 j ( ) 出 0 1 3l d p c 码的发展状况 ( 1 4 ) u ) p c ( h wd e n s i t yp a r i t yc h e c k ) 码最初由g a l l a g e r 【1 在上个世纪六十年代初 发现，但是限于当时的计算水平和人们对这种形式非常简单的码的认识不足，数 年来它一直遭受冷遇，这期间只有r m i c h a e lt 越n e r 7 】等对它进行了零星的研 究，且几乎没有实质性的进展。而自从u ) p c 码被m a c k a y 和n e a l 等人重新发 现之后，其优越的性能很快引起研究人员的重视，u ) p c 码迅速成为人们研究的 焦点。经过几年的研究和发展，人们在各方面都取得了突破性的进展，l d p c 码 的相关技术也日趋成熟，甚至已经开始有了商业化的应用成果。 u ) p c 码的研究与进展大体包括以下几个方面： 1 3 1l d p c 码结构及其优化 因为u ) p c 码是一种线性分组码，它的码结构可由校验矩阵确定，所以所谓 码结构设计也是校验矩阵的构造。u ) p c 码的校验矩阵构造方法目前主要有几何 方法、图论方法、实验设计方法、置换方法等。 按照校验矩阵的行和列是否都具有固定个数的非零元素可将l d p c 码分为 规则码和非规则码。另一种分类方法是将它分为二元域和多元域上的u ) p c 码。 m g l u b y 1 4 等指出，非规则l i ) p c 码的性能优于相应的正则u ) p c 码。而 m c _ d a v e “1 5 等的研究表明多元域上的l d p c 码的性能较二元域上g a l l a g 盯码 的性能有较大提高，且域的阶数越高，编码的性能越好。 在寻找好的码结构( 所谓好的码结构就是既有好的性能又有较低的编码复杂 度的码结构) 方面，l u b y 等【1 4 采用基于线性规划的方法来设计线性时间可编码 的非规则码。d j c ，m a c k a y 等 1 6 提出对非正则码采用先选择轮廓再选择结构的 两步选择方法，并指出能快速编码的l d p c 矩阵通常具有下三角形结构。 t jm c h a r d s o n 等 1 7 通过优化二分图的次数分布，设计出性能逼近香浓限的非规 则l d p c 码。t jr i c h a r d s o n 和rl u r b a n k e 1 8 探讨了奇偶校验矩阵稀疏度如何 确定的问题，并找到了一种使编码时间与码块长度实际上符合线性关系( 而非通 常认为的平方关系) 的构造方法。m g l u b y 1 9 等也提出了一类基于级联二分图的 u ) p c 码，用于可抹信道，它不仅是线性时间编码，而且也可实现线性时间译码。 d a s p i e i m a 】1 2 0 丌发了一种试探法来寻找非规则l d p c 码参数的好的分布，并 北京邮屯大学硕p 论文 构建出在很低s n r 下b e r 低于t u r b o 码的码率1 2 的u ) p c 码。j c 锄p e l l o 等 2 1 提出采用扩展的比特填充算法来设计具有高码率、高g i n h 和b e r 性能的良好的 l d p c 码。y m a o 和a h b a n i h a s h e m i 2 2 】提出根据g i n h 的分布来设计好的l d p c 码的方法。s j j o h n s o n 和s r w e l l e r 2 3 提出一种基于k i r k m a l lt r i p l e 系统的组合 设计方法，适合于构建短码长、高码率和在其二分图中不出现长度为4 的环、g i r h 至少为6 的规则u ) p c 码。y | k o u ，s l i n 和m f o s s o r i e r 2 4 】【2 5 探讨了基于有限几 何学的u ) p c 码结构，基于欧式几何和投影几何中的线和点，构造出了4 类u ) p c 码。该构造方法与上述各种构造方法的不同之处，也正是该方法的优越之处在于： 通过该方法构造出来的码结构具有循环或准循环的形式，因此可以再线性时间内 编码，并可通过简单的反馈移位寄存器实现，且这四类码有好的最小距离，它们 的二分图的g i r n l 为6 ，而随机生成的l d p c 码的最小距离往往难以确定。 1 3 2l d p c 码的译码和性能分析 在译码的研究方面，g a l l a g e r 曾给出了两种l i ) p c 码的迭代译码算法：硬判 决算法和软判决算法。硬判决算法简单易行，但是性能较差；后者虽然有好的性 能，但实现复杂度太高。于是作为二者的折衷， 2 6 中提出了消息传递算法 ( m e s s a g ep a s s i n ga l g o 删l i n ) 。f r k s c l l i s c h a n g 等【2 7 对消息传递算法作了推广，将 它扩展为一种更加通用的算法：和积算法( s u m - p r o d u c ta l g o r i t h m ) ，并指出和积算 法实际上包含了大量的实际译码算法( 如前向后向算法、b p 算法、维特比算法 等) ，它可应用于任何f 如t o r 图，众多的实际译码算法均可有和积算法框架导出。 m p f o s s o r i e r 2 8 2 9 】研究了降低复杂度的u ) p c 码的迭代译码，提出了 a p p _ b a s e d 和b p - b a s e d 算法的密度演进算法及其离散形式。 在性能分析及译码相关的一些方面，d j c m a c 砭a y 和c p h e s k e l h 3 0 研究了 u ) p c 码采用b p 算法译码时译码性能随实际噪声变化的敏感程度，得出了噪声 估计失配与译码性能的函数关系。m g l u b y 等在 1 4 】中给出了一种新的基于 m a n i n 旦a l e s 的c o n c e n t r a t i o nb o l l l l d s 方法来分析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 将 1 4 】中的方法从b s c 和m a s s a g e p a s s i n g 译 码算法的约束条件推广到各类信道模型，开发了一种称为“密度寻优”( d e n s i t y e v 0 1 u t i o n ) 算法的数值程序来近似估计噪声门限( 在该门限以下可望成功的采用置 信传播算法) ，提出了一种通用的方法来确定具有离散或连续输出字符集的任何 二元输入无记忆信道中采用m e s s a g e p a s s i n g 译码的l d p c 码的性能。特别对于 b p 算法，该方法可提供任何精度的性能估计。s y c h u n de ta 1 3 1 利用消息分布 的高斯近似对密度寻优算法进行简化，证明采用高斯近似可在不降低精度前提下 快速找到门限和快速、容易地优化次数分布。sc h u n g ，g d f o m e y ，t j r i c h a r d s o n 北京帅f b 入学颂i j 论文 和r u r b a n k e 等【3 2 提出了b p 算法的密度寻优的离散形式，在简化了密度寻优 的计算复杂度的同时还考虑了有限量化的影响。x w e i 和a n a k a i l s u 3 3 1 给出了 m a x l o g m a p 译码的密度寻优算法。工s p o l l o c k 3 4 和s 瓜e d a 等 3 5 】认为l d p c 码的译码算法可以从信息集合的观点和置信度传播的方法来分析和设计。“p i n g 和、v k l e u n g 3 6 提出了一种奇偶似然比技术，克服了传统的和积算法在实现时 对量化误差较敏感的问题。 y o n g y im a o 和ah ba 1 1 s h e m i 3 7 3 8 从迭代策略角度对译码算法进行了研 究，提出了一种基于t a r h l e r 图的g i n h 分布的概率方案译码方法。在不增加复杂 度的情况下，概率方案的性能较传统的瀑布方案有明显改善。 13 3 l d p c 码的硬件实现 t b h a t t 3 9 等提出采用定点d s p 实现u ) p c 码的方案。h a l o e l i g e r 等 4 0 建议用模拟v l s i 实现u ) p c 码的和积算法译码模块，以避免数字实现中十分复 杂的实数运算。t z h a l l g 和k k p a r h i 4 1 提出了一种码与译码器联合设计的面向 v l s i 实现的方法，适合执行部分并行译码。b l e v i n ee ta 1 【4 2 则给出了种可以 用于目前商用f p g a 实现的u ) p c 码验证性设计方案。 13 4 l p p c 码的应用 l d p c 码在多种信道环境下的优异性能吸引人们不断探讨它在各个领域的 应用：在款带接入网中不对称数字用户( a d s l ) 中的应用方面，e e l e f i l l c d o u 等4 3 1 提出了基于二元u ) p c 码的多电平编码，并研究了采用此种编码的传输性能。在 磁记录系统方面，h s o n g 4 4 研究了l 【) p c 码的应用情况，e y e 0 等 4 5 对l d p c 码用于有记忆块衰落( b l o c kf a d i n g ) 信道的性能进行了评估。j h o u 等 4 6 研究了用 于瑞利衰落信道l d p c 码的优化和性能分析。b m y h r e 4 7 提出一种用于慢变化 平坦衰落信道的速率自适应l d p c 编码调制的方案，其应用还可推广到 f e c a r 0 系统。 1 4 本人所做工作及本文结构 本文首先介绍了几种经典的l d p c 构造算法，然后就目前较为流行的各种 u ) p c 译码算法进行了分析比较，最后创新地提出了在空时系统中适用的新的 l d p c 译码算法，穿梭天线译码( c m s sa m e n n am e s s a g ep a s s i n g ) 算法，简称 c a m p 算法。该算法已于2 0 0 6 年1 月在美国拉斯韦加斯举行的c c n c 2 0 0 6 会议 d e r n o n s t r a t i o ns e s s i o n 上发表，收录在d 鲫1 0 n s t l 撕o np r o c e e d l n g 中。关于c a m p - ， 北京邮u 火学坝。l 论文 算法的分析主要集中在第五章。 本文结构安排如下，第二章主要介绍了u ) p c 码的一些经典的构造方式和其 中一种简化编码方法。第三章开始分析各种较为流行的译码方法。第四章对第三 章中的部分译码算法进行了数值仿真并且进行评价。第五章是本文的重点和创新 点，主要讨论了u ) p c 编码的空时结构和c 址佃算法，包括理论分析和数值仿 真。 1 5 本章小结 本章简要回顾了信道编码理论发展情况，介绍u ) p c 信道编码的基本术语， 重点分析了当前该领域的研究热点，最后给出了本文的结构，为下面章节的展丌 奠定了基础。 北京邮r 也人学硕：l 论文 第二章l d p c 码的构造与简化编码 2 1 l d p c 码的构造 u ) p c 码是一种具有稀疏校验矩阵的线性分组码。由线性分组码的性质，域 f ( 本章讨论的是二元域) 上长n ，t 维的编码c 可用一t ) m 维的校验矩阵h 描 述： c ( h ) ：= x p ：h x l = 0 )f 2 1 1 l d p c 码也可以用校验矩阵描述。只要校验矩阵定了，就可相应地容易地产 生编译码器，整个l d p c 码也就确定了。 记= n 一七为h 的行数，h = i ，f = 1 ，n ，= 1 ，。h 的行对应二分图 中的校验节点，h 的列对应二分图中的变量节点，如果 二：1 ，则表示变量节点 v f 和校验节点c ，之间有边相连，反之则表示两节点之间没有边直接相连。据此， 我们可以根据h 构造出对应的二分图。二分图也可成为两种颜色可着色的图，所 谓两种颜色可着色的图指的是可用两种颜色对图中所有的边着色，使得图中任何 一个环( 即闭回路，且回路所包含的任何两条边均不同) 上的相邻边的颜色相异。 由着色定理可知该图中只包含偶数长度的环。 对本文中用到的符号表示说明如下： d 。，也：分别表示变量节点v j 和c ，的次数( 即某节点伸出的边的个数) ：对 于规则码来说，各变量节点和各校验节点的次数分别是同一个值，记为d 和d 。 ( q ) ：与变量节点q 有边相连的校验节点的下标； ( c ，) ：与校验节点c ，有边相连的变量节点的下标； ( v ) ，：( v ) 与，的差集； ( 。，) z ：( 0 ) 与f 的差集。 因为校验节点的图结构对码的最小距离和译码性能有直接的重要影响，所以 问题的关键在于如何构造没有短环或环的平均长度尽可能大的校验矩阵。 2 1 1 图结构对码性能的影响 4 8 】中指出二分图中环的存在是我们对迭代译码过程进行准确概率分析的一 个障碍，并且