（通信与信息系统专业论文）ldpc码迭代译码算法的研究.pdf

摘要 摘要 低密度奇偶校验( 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 码 的定义及其图模型表达，并且分析了现有的l d p c 码的构造方法。接下来，本文 详细阐述了比特翻转( b f ) 类译码以及置信传播( b p ) 类译码这两大类不同的译 码算法前者可以实现非常低的译码复杂度，而后者可以达到最优化的误码性能。 具体介绍了包括比特翻转( b f ) ，加权比特翻转( w b f ) ，改善的加权比特翻转 ( m 忸f ) ，经典和积算法，对数域的和积算法等若干种当前比较被广泛接受的译 码算法并给出了我们的仿真实验结果。最后，本文介绍了m i w b f 、r r w b f 、m m s 、 f m s 和o m s 等较新的译码算法，然后在前人的基础上，提出了p i w b f 、f b f 和 l m m s 等改进的l d p c 迭代译码算法，并且通过仿真实验说明了这些算法在实际 译码应用中可以带来优点。 关键词：低密度奇偶校验码迭代译码比特翻转算法置信传播算法 a b s m s c t a b s t r a c t 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 si sac l a s so fl i n e a rb l o c kc o d ew h i c hc o u l d p r o v i d en e a rs h a n n o n l i m i tp e r f o r m a n c ea sw e l la sl o we r r o r - f l o o r f o rs o m el o n g l d p cc o d e s ，t h e i rp e r f o r m a n c e sa r ee v e nb e t t e rt h e nt h et u r b oc o d e i t e r a t i v ed e c o d i n g t e c h n i q u e sh a v eb e e nr e c e i v i n gm o r ea n dm o r ea t t e n t i o n sw i t ht h ei n v e n t i o no ft u r b o c o d e sa n dt h er e d i s c o v e r yo fl d p cc o d e s a l t h o u g ht h eo p t i m u md e c o d i n ga l g o r i t h m s c o u l dp r o v i d ev e r yg o o dp e r f o r m a n c ef o rl d p cc o d e s ，c o m p l i c a t e do p e r a t i o n sa r e i n v o l v e di nt h eo p t i m u md e c o d i n g ，a n dp r o h i b i tt h ew i d ea p p l i c a t i o n so fl d p cc o d e si n t h en e x tg e n e r a t i o nd i g i t a lc o m m u n i c a t i o na n ds t o r a g es y s t e m i nt h i sp a p e r , w er e v i e w e dt h ef u n d a m e n t a lk n o w l e d g ea n dr i s i n gh i s t o r yo ft h e c h a n n e lc o d i n g w ed e s c r i p tt h ec h a r a c t e r i z a t i o no fl d p cc o d e ，s h o w e dh o wt oe x p r e s s i ta sat a n n e rg r a p ha n dd i s c u s s e dh o wt om a k eag o o dl d p cc o d ef r o mm a n y a s p e c t s t h e n ，w ee x p o u n d e dt w of a m i l i e so fi t e r a t i v ed e c o d i n ga l g o r i t h mf o rl d p cc o d e s ，o n e i sb i t f l i p p i n ga l g o r i t h mw h i c he n a b l e sv e r yl o wc o m p l e x i t yi nd e c o d i n g ，t h eo t h e ri s b e l i e fp r o p a g a t i o na l g o r i t h mw h i c hc o u l dr e a c hv e r yg o o dp e r f o r m a n c e w ec o n c r e t e l y i n t r o d u c e db f , w b f , i w b f , s p a ，l o g - s p aa n da n a l y z e dt h e mb ys i m u l a t i n gt h e i r p e r f o r m a n c e a tl a s t ，w ei n t r o d u c e ds e v e r a ll a t e l ya n db e t t e rw a yo fl d p cd e c o d i n g a l g o r i t h m si n c l u d i n gm i w b f , r r w b f , m m s ，f m s ，o m s ，a n dp r o p o s e ds e v e r a ln e w a l g o r i t h m sl i k ep i w b f , f b fa n dl m m s ，w h i c hc o u l de n a b l el e s si t e r a t i o no rr e a c h h i g h e rp e r f o r m a n c ew h i l es t i l lk e e pl o wc o m p l e x i t y k e y w o r d ：l d p cl t e r a t i v ed e c o d i n gb i t f l i p p i n g b e l i e fp r o p a g a t i o n 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名： 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名：丝比 导师签名：重丝窒弛 日期趔j 日期全生艺：三= 2 第一章绪论 第一章绪论 低密度奇偶校验( l o w d e n s i t yp a r i t y - c h e c k , l d p c ) 码是一种可以进行迭代 译码的差错控制编码( e r r o rc o n t r o lc o d i n g ，也称纠错编码，本文对这两种名称 不做区分) ，性能优异。本文将介绍l d p c 码以及改进的降低复杂度的译码算法。 本章将简要地对数字通信系统以及l d p c 码进行介绍，并且将迅速回顾在编 码理论的历史上占据重要地位的发现。 1 1 数字通信系统 近年来，对高效可靠的数字传输和和存储系统的需求日益增长。这种需求随 着在商业、政府和军事领域面向数字信息的交换、处理和存储的的大规模高速数 据网的出现而变得更加迫切。这类系统的设计要求通信与计算机技术的融合，系 统设计者所关心的下一个主要问题就是如何控制差错使得数据能够可靠重现。目 前差错控制编码已经成为现代通信系统和数字存储系统设计中不可分割的部分。 图1 1 是一个典型的数字通信系统的示意刚1 1 。数字信息的传输与存储有很 多共同之处，两个过程都是要把数据从信源传送到信宿。在没有加以说明的情况 下，本文所描述的都是数字通信系统。 图1 1 数字通信系统模型 信源：信源可能是一个人或是一台计算机或者数据终端。 信源编码器：将信源的输出转换为二进制数字序列，这些序列成为信息序列 甜。对于连续信源，该过程还应该包括模拟7 数字( a d ) 转换。信源编码器被理 想化地设计成： ( 1 ) 为表示信源输出所要求的比特率最低。 ( 2 ) 信源的输出可以从信息序列“确切地重现( 信源编码不在本文的讨论) 信道编码器：将信息序列 变换成离散的编码序列，称之为码字。尽管在 某些应用中采用非二进制码，但在大多数情况下 ，是二进制序列。本文所关注的 2 l d p c 码迭代译码算法的研究 l d p c 码的编码器就是在这里实现的，属于信道编码的范畴，用以抵抗传输码字 的过程中所面临的噪声环境的影响。 调制器与解调器：离散符号并不适合在物理信道上传输。调制器将信道编码 器输出的每个符号转换为持续时间为t 秒传输的波形，以适合信道传输。这些波 形进入信道并受到噪声的干扰。典型的传输信道包括电话线、移动蜂窝电话、高 频无线电、遥测、微波和卫星链路、光缆等。比如在电话线路信道上，干扰可能 来自于开关脉冲噪声、热噪声或者来自其他线路的串音。解调器处理收到的每一 个持续时间为t 秒的波形，然后产生离散或者连续的输出。相对于编码序列l ， 解调器的输出序列称之为接收序列，。 信道译码器：将接收序列，变为二进制序列h ，称为估计信息序列。译码算 法是基于信道编码规则和信道的噪声特性而制定的。尽管噪声可能导致某些译码 错误，但是在理想情况下，将是信息序列口的重现。本文的主要目的就是设计， 实现和改进使译码误码率最小的信道译码器。 信源译码器：将估计信息序列变换为对信源输出的估计，并将该估计传送 到信宿。当信源是连续信源时，这一过程还包括了数字模拟( d a ) 转换。在一 个精心设计的系统中，除非信道干扰太严重，否则这个估计将会是对信源输出的 准确重现。 为了把注意力集中于信道编码器和信道译码器，在上述模型中，我们可以把 信源和信源编码器合并成一个输出为口的数字信源，把调制器，信道和解调器合 并成一个输入为l ，、输出为r 的编码信道，最后将信源译码器和信宿合并为数字 信宿。经过合并后简化的框图如图1 2 所示。 图1 2 用于编码系统的简化的数字通信系统模型 1 2 香农容量( s h a n n o nc a p a c i t y ) 众所周知，在信息传递的过程中，会伴随有噪声的存在。当周围有很大的噪 声( 干扰源) 存在的时候，交谈会变得很困难，但是如果我们有足够的耐心( 比 如重复说若干遍) 和洪亮的声音，还是依然有可能将自己想要表达的信息准确地 传达出去。然而，在数据通信的过程中，存在着可靠通信这种严格需要。事实上， 第一章绪论3 这需要接收方在即便是一定会产生某些误码的时候，仍然能够正确地将传递过来 的信息进行译码。1 9 4 8 年，克劳德香农一篇具有里程碑意义的论文1 2 】中曾经证 明，只要信息传输速率低于信道容量，通过对信息进行适当编码，可以在不牺牲 信息传输或存储速率的情况下，将有噪信道或者存储媒质引入的差错减到任意低 的程度，也就是说，在一个给定的带有噪声的通信信道中，存在一个可能获得的 可靠通信的最大速度( 对于每个信道中传输的信息量而言) 。可靠通信在这里是指 无误传输。换言之，即若传输速率低于信道容量，则可以达到无误传输；若传输 速率高于信道容量，则无法达到无误传输。 通信信道可以由输入，输出以及一组转移概率来定义。其中转移概率是指接 收端接收到某一符号，而发送端发送的是另特定符号的概率。二进制对称信道 ( b s c ) 是一个简单但不失代表性的模型：( 如图1 3 所示) 0 o 图1 3 二进制对称信道( b s c ) 对于非理想信道来说，接收到的符号序列通常和发送的有所不同，于是，在 需要无错传输的场合，编码理论研究者的工作就是对传输的信息进行编码，使接 收到的错误信息可以被纠正，或者至少可以被检测到。我们来定义码c ，它是一 个长度为n 的由有限集合所构成的向量。为了简化起见，我们假设它的信道输入 码表为二进制码表 0 ，l ，另外假设码字的数目为2 ，于是每个码字就可以唯一对 应一个长度为k 比特的串，则该码的码率r 可以定义为r = k n 比特每信道。 在一个有噪信道上传输一个给定的码c ，其中译码的任务就是从接收到的数 据中获得所有能获得的信息，由此来判断当初最有可能传输出来的码字。通常接 收到的码字会在随机的位置上出现误码，误码的个数取决于噪声的严重程度。直 观地讲，最期望接收到的码字就是出现误码的位置最少的那个。然而，对于大多 数码来说，最大似然译码器的复杂度过大，在实际中难以采用。其实常规的译码 可以归类为n p 完全问题p j 。 由此可以知道，最基本的译码方案自然而然的就是选取一个精心设计的码， 它的各个码字之间的不同码位足够多。如果考虑c 中所有可能的码字，那么最小 距离便可以定义为任意两个码字之间最少的不同的位置的个数。更广义地说，一 个码的距离谱描述了某一个码字和其各个邻码间的距离。综上所述，我们就是在 4l d p c 码迭代译码算法的研究 寻找这样一种拥有出色的距离特性和易于实现的近似最大似然译码器的码。 图1 4 以码率r 的函数的方式，表示出了采用b p s k 信号，连续输出的a w g n 信道上的香农刚舢。从此图，我们可以由码率r 来确定香农限。例如，采用b p s k 信号，连续输出的a w g n 信道上的码率r = 0 5 的系统，为了实现无误码的可靠 传输，所需的最小s n r ( 香农限) 是o 1 8 8 d b 。在本文中，为了方便进行统一比 较，我们进行的仿真实验所采用的l d p c 码的码率均为0 5 。 盒 已 z 、 岜 醛 栖 | ? 。 7 7 ， 0 0 1 0 20 30 40 50 60 70 80 ，91 码率r 图1 4 以码率r 为函数的香农限 1 3 纠错编码的发展 在2 0 世纪4 0 年代，h a m m i n g 提出了著名的( 7 ，4 ) h a m m i n g 码，能够纠正1 比特错误。在此基础上m g o l a y 构造了( 2 3 ，1 2 ) g o l a y 码，能够纠正3 个比特错误。 1 9 5 4 年r e e d 等人提出了r m 码和大数逻辑译码方法( m a j o r i t yl o g i cd e c o d i n g ， m l g ) ，在码字长度和纠错能力方面有较强的适应性，并且其译码复杂度低，较 h a m m i n g 码和g o l a y 码有了较大的提高。因此在2 0 世纪六七十年代的火星探测 方面r m 码得到了极为广泛的应用。 1 9 5 7 年，p r a n g e 提出了循环码，循环码是线性分组码的一个子类，它除了分 组码的特点外，还有循环特性，也就是说任何一个码字，循环移位以后，还是一 个码字，它可以用移位寄存器实现编码和伴随式计算译码。循环冗余校验码( c r c ) 就是循环码的一种，一般都是用于纠正一位错误，主要用于检错，而不是纠错。 1 9 5 9 年，b c h 码被提出。b c h 码是循环码的一个重要子类，其码长嚣= q “一1 ， m 是整数，二元( q - 2 ) b c h 码可以纠错的数目为( 2 ”一1 ) 2 。后来r e e d 和s o l o m a n 把b c h 码推广到非二元( q 2 ) 的情况，就是r s 码( r e e d s o l o m a n 码) ，这种编码的 第一章绪论 特点是能够同时纠正突发错误和随机错误。1 9 6 0 年r e e d 和s o l o m n 将b c h 码扩 展到高阶上得到r s 码。在1 9 6 7 年，r s 码的译码算法获得突破，也因此在之后 获得了广泛的应用，比如应用在c d 播放器、d v d 播放器等。 上面提到的这些码都是分组码，都是将k 个信息比特( 符号) ，经过m 个校验 关系并产生m 个校验比特( 符号) ，产生了n - - m + k 个编码后比特( 符号) 。分组码的 本身有一些不足，限制了它的运用。首先是，它必须被按帧传输、按帧译码，这 样在帧长较长时会带来一定的时延。第二是要求准确的帧同步。多数分组码接收 到的是解调器的硬判决输出，这样又会带来一些判决带来的误差，影响误码性能。 1 9 5 5 年，e l i a s 首先提出了卷积码。卷积码不是将数据分割成不同的分组，而 是通过移位寄存器将校验比特加入输入数据流中。卷积码的编码实现简单，用移 位寄存器可以实现，并且可以连续译码，无须准确的帧同步。由于卷积码在编码 过程中引入了寄存器，增加了码元之间的相关性，因此，在相同复杂度的条件下 可以获得比分组码更高的编码增益，代价是增加了分析和设计的复杂性。卷积码 的软判决译码大体上可以分为两类：一类是使符号错误概率即误码率最小的软判 决译码算法，比如1 9 7 4 年提出的b c j r 前向后向最大后验概率译码算法，另一类 是使码字错误概率即误帧率最小的译码算法，比如1 9 6 7 年提出的v i t e r b i 译码算 法等。随着各种卷积码的译码方法，尤其是v i t e r b i 译码算法的出现，卷积码逐渐 得以广泛应用，而后出现的t c m ( 格栅编码调制) 技术，更加促进了卷积码的发展 和应用。卷积码在实际的通信系统中得到了广泛应用，所有第二代移动通信标准 采用了卷积码为编码标准。g s m 采用r _ 1 2 ，k = 5 的卷积码，i s 9 4 和i s l 3 6 采用 r = i 2 ，k = 6 的卷积码，i s 9 5 上行采用r = i 2 ，k = 9 的卷积码，下行采用i p l 3 ， k - - - 9 的卷积码。卷积码的主要问题是它对突发性错误的纠错能力差。用交织和卷 积码结合的方式，可以在码比特送入信道前，进行分组交织，再进行卷积码编码， 在接收端，先解交织，再译码。经过这一交织与解交织的过程，突发性错误就变 成了随机错误，卷积码性能得到改善。 在1 9 6 6 年，有人提出将两个短码串联成长码，将编码的过程分级完成，目的 是构造具有较大等效分组长度的纠错码，并且将最大似然译码分段进行，其有纠 错能力强，并且译码简单的特点。 在t u r b o 码被提出以前，人们一直认为信道截止速率r 是信道码性能的实际 极限，而s h a n n o n 限是不可达到的理论限。法国的b e r r o u 等入在卷积码和级联码 的基础上，于1 9 9 3 年提出了一种全新的编码方案一t u r b o 码，它很好的利用了 s h a n n o n 信道编码定理中的随机性编译码条件，在信道编码的理论和应用中取得 了突破性的进展，是信道编码历史上的一个里程碑。t u r b o 译码时利用软输入软 输出的迭代译码算法( m a p 算法，s o v a 算法) 达到了接近s h a n n o n 极限的优异性 能( a w g n 下，1 8 次迭代，0 8 d b 达到l o 西误码率) ，同时译码复杂度也可以接受。 6 l d p c 码迭代译码算法的研究 t u r b o 码采用并行级联递归的编码器结构，是一种系统的卷积码，其译码算法主 要有m a p 算法、l o 争m a p 算法、s o v a 算法等。由于t u r b o 码优秀的性能，使其 成为编码界研究的热点，在通信中有广阔的应用前景。但是t u r b o 码也有其缺点， 它的译码复杂度仍然较大( 复杂度随码长成指数增长) ，且在码长较长时，由于交 织器的存在具有较大的时延，还有e r r o v f l o o r 效应。 1 4l d p c 码的发展 l d p c 码于1 9 6 2 年由g a l l a g e r 提出【5 】，在1 9 6 3 年作为他的博士学位论文1 6 】 发表，之后很长一段时间没有收到人们的重视。只有1 9 8 1 年t a n n e r 从图论的角 度研究过l d p c 码【7 1 。直到1 9 9 3 年b e r r o u 等提出了t u r b o 码【8 1 ，人们发现t u r b o 码从某种角度上说也是一种l d p c 码，近几年人们重新认识到l d p c 码所具有的 优越性能和巨大的实用价值。1 9 9 6 年m a c k a y 和n e m 的研究1 9 】表明采用l d p c 长码可以达到t u r b o 码的性能，而最近的研究表明，被优化的非规则l d p c 码采 用置信传播( b e l i e fp r o p a g a t i o n ) 译码算法时，能得到比t u r b o 码更好的性能，甚至 当码长较长的时候可以非常逼近香农限【l o 】。目前，l d p c 码被认为是迄今为止性 能最好的码，是当今信道编码领域的最令人瞩目的研究热点，近几年国际上对 l d p c 码的理论研究以及工程应用和v l s i 实现方面的研究都已取得重要进展。 基于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 码校验矩阵。 第三章主要介绍了几种经典的比特翻转译码算法的思路和实现方法，并且进 行了性能仿真实验。 第四章主要介绍了基于经典置信传播方法的和积译码算法，包括其概率域和 对数域的算法。 第五章中本文除了介绍了几种比较新颖的译码方法，主要提出了4 种新的译 码方法，并且给出了设计这些方法的思路及其误码性能仿真的交叉对比。 第二章l d p c 码概述 7 2 1 1l d p c 码的定义 第二章l d p c 码概述 2 1l d p c 码的描述 l d p c 码是一种线性分组码，可以用非常稀疏的校验矩阵或二分图来描述， 也就是说l d p c 码的校验矩阵的矩阵元素除一小部分不为0 外，其它绝大多数都 为0 。通常我们说一个( n ，j ，k ) l d p c 码是指其码长为n ，其奇偶校验矩阵每列包 含i 个1 ，其它元素为0 ；每行包含k 个1 ，其它元素为0 。j 和k 都远远小于1 1 ， 以满足校验矩阵的低密度特性。校验矩阵中列和行的个数即i 和k 为固定值l d p c 码称为规则码，否则称为非规则码。一般来说非规则的性能优于规则码。 l d p c 码可以由长度为n 的线性分组码c 由生成矩阵g 或奇偶校验矩阵h 唯 一确定。如果是由奇偶校验矩阵日确定的，码c 就是日的零空间。g f ( 2 ) 上的n 维向量 ，= ( v o ，m ，一。) 当前当且仅当讲r = 0 时是一个码字。显然，这意味着c 的码字的各个比特之间必须满足一组由日的各行确定的奇偶校验方程。于是， l d p c 码是通过奇偶校验矩阵定义的。 设码长为，信息位长为k ，校验位为 仁弘k ，码率为r = k n ，则码校验矩 阵是一个m x n 的矩阵。 定吠2 - 一1 】l d p c 码定义为具有如下结构特性的奇偶校验矩阵日的零空间： ( 1 ) 每一行含有p 个1 ； ( 2 ) 每一列含有y 个1 ； ( 3 ) 任何两列之间位置相同的l 的个数( 用五表示) 不大于1 ，即允= o 或者允= 1 ； ( 4 ) 与码长和日的行数相比，p 和y 都比较小。也就是说矩阵中很少一部分 元素非零，其他大部分元素都是零，l d p c 码的校验矩阵是稀疏矩阵。 由特型可以看出，奇偶校验矩阵的行重p 和列重y 是固定的，并且在日中没 有任何两行具有超过一个相同位置的1 。由于p 和y 都小于码长和日中的行数， 因此日中的1 的密度很小。正是因为这个原因，日被称为低密度奇偶校验矩阵 ( l o w d e n s i t yp a r i t y - c h e c km a t r i x ) ，由h 确定的码被称为l d p c 码，一般表述为 ( ，y ，p ) 。另外，我们定义奇偶校验矩阵日的密度r 为日中1 的总数与日中的元 素总数的比值。由此可以看到，厂= p n = 7 ，其中是矩阵日的行数。 由定义2 1 给出的l d p c 码被称为是( ，y ，p ) 规则( r e g u l a r ) l d p c 码。如果 奇偶校验矩阵h 的各行或者各列具有不同的重量，则该l d p c 被称为非规则 8l d p c 码迭代译码算法的研究 ( i r r e g u l a r ) 的。值得注意到是，日的各行并不要求在g f ( 2 ) 上线性独立。 考虑一个长度为n 的l d p c 码c ，由j x 以的奇偶校验矩阵日确定。令 ，h 2 ，h ，表示日的行向量，其中 哆= ( 乃 o ，乃 l ，h j 扩- ) 对于1 j j 。令 ，= ( v o ，m ，屹一。) 为c 中的一个码字，那么内积 n - ! s j - - v 一= m 乃，= o ( 1 - 1 ) i = o 给出了奇偶校验和( 或者叫奇偶校验方程) 。由日的，行可以确定，个这样的奇 偶校验和。若= 1 ，则称码元比特m 被内积 ，哆( 或以行) 所校验。对于o ，以， 令4 = 耐n ，燧n ，l ) 表示h 中可校验码字比特m 的行的集合。对于1 歹厂， 令 h ( j 1 ) - ( 磺，楞，喂一。) ( 1 2 ) 那么，础= 噬? = = h ，( i ，；= 1 。根据l d p c 码奇偶校验矩阵的第三条结构特性，可 知除m 外地任何一个码字比特至多被4 集合中的一行所校验。因此4 f 中的厂个行 向量关于码字比特为巧正交。令s 表示由4 的各行得到的奇偶校验和组成的集 合。那么，墨中的每个校验和都包括码字比特m ，同时其他n 1 个码字比特最多 被一个s 中等校验和包括。s 中的校验和被称为关于m 的正交。对于规则的l d p c 码c 的每个码字比特，都有7 个关于其正交的校验和。因此，c 可由一步大数逻 辑译码方法进行译码。任何少于iy 21 个无码的误码图样都可以被纠正。此时， 码的最小距离“至少为7 + 1 ，也就是7 + 1 。如果厂很小。一步大数逻辑译 码方法的误码率是非常高的。g a l l a g e r 提出了两种l d p c 码的译码方法，一种是 硬判决，另一种是软判决的，它们的误码性能要比一步大数译码好很多。 2 1 2 线性分组码的t a n n e r 图表达 图g 由一组顶点和一组边构成，顶点集记为v = “，b ，) ，边集记为 s = 乜，乞， ，每条边吃由一个无序顶点对( ，y ，) 确定。给图被记为g = ( y ，s ) ， 与边巳相关联的顶点v 和v ，叫做色的端点( e n dv e r t i c e s ) 。通常会以一个用点表示顶 点、用连接两头端点的直线表示边的平面图形来表示一个图。在这种图形表示中， 一条边的两个端点被称为以此边相连接，该边被称为与其端点相关联( i n c i d e n t ) 。 与顶点v 相关联的边的个数成为顶点m 的度( d e g r e e ) ，记为d ( k ) 。图2 1 为一个 由6 个顶点，1 0 条边组成的图。边b 连接顶点v 1 和。边b 、c 、d 与顶点u 相关 第二章l d p c 码概述9 联，因此顶点屹的度为3 。如果两条边与同一个顶点相关联，则称它们相邻 ( a d j a c c n t ) 或连接( c o n n e c t e d ) 。如果两个顶点被一条边连接，则称他们相邻。 例如，在图2 1 中，边a 和边h 相邻且由顶点心连接，顶点均和屹相邻。具有有 限数量的顶点和边的图被称为有限图( f i n i t eg r a p h ) 。 图2 1 有6 个顶点和1 0 条边图示例 图中的路径( p a t h ) 被定义为由一组顶点和边交替组成的有限序列，该序列 从顶点开始，至终点结束。序列中的每条边与其前一个顶点和后一个顶点相关联， 每个顶点之多在序列中出现一次。路径中边的数量被称为路径的长度( 1 e n g t h ) 。 例如，在图2 1 中，m ，b ，v 2 ，c ，v 4 ，h ，v 5 ，g ，v 3 组成了一条常委4 的路径。路径有可能 把同一个顶点既作为起始点也作为终结点，这种闭合路径被称为环( c y c l e ) 。在 环上，除了起点和终点意外，任意一个顶点最多出现一次。例如，在图2 1 中， 由h ，b ，屹，c ，v 4 ，a ，m 组成的闭合路径是一条长度为3 的环。闭合路径 m ，厂，屹，g ，v 3 ，f ，m 是长度为4 的环。一条起始和终止与同一顶点的边构成了长 度为一点环，这就是自环( s e l f - l o o p ) 。没有环的图被称为树( t r e e ) ，它是非循环 的。图2 2 给出了一个非循环图。一个图中的环的最短长度被称为图的周长( 西n h ) 。 图2 1 中给出的图的周长为3 。 图2 2 非循环图示例 1 0兰里! 竺里垄垡堡塑箜鲨堕堕窒 一_ 一 在图g 中，如果任意两个顶点之间至少存在一条路径，则图g 是连通 ( c o n n e c t e d ) 的。图2 1 和图2 2 都是连通图。对于图g = ( 乃占) ，如果其顶点集y 可被划分为两个不相交的子集乃和兄，使得边集g 中的任意一条边连接n 中断一 个顶点和凡中的一个顶点，以或托内部不存在被边连接的两个顶点，则称图 g ：( 儿占) 为二分图( b i p a r t i t e ) 。显然，二分图中没有自环。图2 3 给出了一个二分 图，其中九：“，v 2 ，屹) 和圪= v 4 ，屹，v 6 ，均，) 。 屹 屹 图2 3 二分图不例 定i 理2 j 如果二分图g = ( 厂，g ) 中包含有环，则环的长度必定为偶数。 证明：假设图g 中的一条环以乃中的顶点m 为起点，追踪这个环。环的第一 条边必然将v f 连接到y ：中的顶点0 ，环的第二条边必然将吩连接到 中的顶点 u 。环的第三条边将k 连接到托中的点m ，然后，环的第四条边疆m 连接到九中 亲一个顶点。这样的追找过程可以一直继续，知道环的最后一条边在起始顶点m 中 止。每次从一中东一个顶点出发，在回到 中的一个顶点，需要两条边，因此， 环的长度必然是2 的倍数，偶数。证毕。 图中的顶点通常也被称为节点( n o d e ) ，和顶点的意义相同，可以通用。 线性码可以采用不同的方式以图来表示。最著名的码的图形化表示方法是网 格表示，码的网格表示也是的采用基于网格的译码算法称为可能，从而在显著降 低译码复杂度的同时获得接近m l d ( 最大似然译码) 的性能。线性分组码的另一 个游泳的图形化表示方式为线性分组码的特纳图( t a n n e rg r a p h ) 表示。特纳图显 示了全体码元与校验码元的奇偶校验和之间的关联关系a 对于一个长度为n 的线性分组码，其奇偶校验矩阵日由j 行组成，依次为 氟，舷， ，。我们构造一个图q ，包括两个顶点集 和兄。第一个顶点集n 包括 n + n a ，。代表码的n 个码元比特，这些顶点记为v 0 ，嵋，屹- l ，被称为码元顶点 ( c o d e - b i tv 矾c e s ) 或是变量节点( v a r i a b l en o d e s ) 。第二个顶点集托包括- ，个】页 点，代表个奇偶校验和( 或方程) ，i g ns 。，s ：，曲由公式( 1 - 1 ) 给出，码元比特 必须满足这些约束。这些顶点被称为校验和顶点( c h e c k s u mv e r t i c e s ) 或校验节 以 如 协 垤 第二章l d p c 码概述 点( c h e c kn o d e s ) 。当且仅当校验和s ，中包含( 或校验) 码元比特m 的度等于包含 m 的校验和的个数，而校验和顶点s ，的度等于s ，所校验的码元比特数目。 对于规则l d p c 码而言，它的特纳图中，所有的码元顶点的度都相同且等于 y ( 奇偶校验矩阵的列重量) ，所有校验和的顶点的度都相同且等于p ( 奇偶校验 矩阵的行重量) 。这样的特纳图被称为是规则的( r e g u l a r ) 的。进一步来说，由定 义2 1 可知，不会存在两个码元比特同时被两个不同的校验和所校验，这说明一 个l d p c 码的特纳图g r 中不包含长度为4 的环。当采用基于置信度传播的迭代译 码算法( i t e r a t i v ed e c o d i n gb a s e do nb e l i e fp r o p a g a t i o n ，i d b p ) 【1 2 】【1 3 1 来对l d p c 码 ( 或其他线性分组码) 进行译码时，码的特纳图中不包含商都很短( 例如4 或6 ， 尤其是4 ) 的环这一点非常重要。短环限制了译码算法的性能，并阻止译码收敛 于最大似然译码。 考虑下面的线性码( 1 0 ，5 ) ，行重为4 ，列重为2 ，此校验矩阵的特纳图如图 2 4 所示。 c h e c k n o d e s n v a r i a b l e n o d e s 口n h = f o 、kk 、 c bc 、c 2c 3c c sc 6c 1 c sc e 图2 4 不例线性码的特纳图 观察此图，可以发现，变量节点c o ，q ，c 2 ，g 和校验节点厶相连接，这个关系是由h 中第0 行中b o o = h o 。= h o ：= h 0 3 = 1 ( 其他均为0 ) 得出的，其他几个节点的连接情 况可以以此类推。本例中的特纳图是规则的：每个变量节点邻接两条边，而每个 校验节点邻接4 条边，即变量节点的度为2 ，校验节点的度为4 。于是可得行重 w ，= 4 ，列重心_ 2 ，n = 1 0 ，m = 5 ，所= 刀”= 校验矩阵中非零元素个数。 图中使用粗线标出了长度为6 的环。更多有关图论的内容请参考文献【3 】，【7 。 0 o 0 l 1 o o 1 0 1 o o 1 l 0 o l 0 0 l o 1 0 1 0 o 1 1 0 0 1 o 0 0 1 1 o 0 l 0 l 0 l o o 1 1 0 0 o 1 2 l d p c 码迭代译码算法的研究 2 2 l d p c 码的构造方法 很明显，最直观的的构造l d p c 码的方法就是按照定义2 1 中的l d p c 码的 属性进行构造。文献中可以找到大量的码构造及码设计的方法，本节将简要介绍 其中最著名的几种。为了达到不同的目标，比如高效率编译码，高误码性能等， 不同的构造方法遵从的是不同的标准。 2 2 1 随机构造方法 随机构造方法主要包括以下四种：g a u a g e r 最初提出的方法( 使用该方法生 成的l d p c 码，称之为g a l l a g e r 码 ，m a y k a y 的随机方法，p e g 算法，b i t - f i l l i n g 算法和e x t e n d e db i t f i l l i n g 算法。前两种方法，都是根据行和列的列重，随机产 生h 矩阵，主要是针对规则l d p c 码。而后两者可以产生不规则l d p c 码。 g a l l a g e r 码 在文献【6 】中，g a l l a g e r 采用了简单的稀疏校验矩阵的随机置换和级联来模拟 随机码。g a l l a g e r 的方法可以简单的描述为：由确定的方式构造退贝呼校验矩阵( 比 如单位阵) ，将该矩阵的所有列做随机的排列组合，生成一系列规则子阵，再将这 些规则子阵组合成所需矩阵。 g a l l a g e r 在论文中定义了一种规则。将矩阵日表现为如下形式： h = q h 2 i h w c w ，w ，分别是校验矩阵日的列重与行重。子矩阵玩具有这样的结构：对于 任何大于1 的整数和w ，每一个子矩阵巩的大小都是t w ，行重为w r ，列 重为1 。日。的结构是：第i 行出现1 的位置在第“一1 ) w r + 1 n n i w 。其他子矩阵r 都是通过对e 进行列变换得到的。显然日是规则的，且其维数为p w cx g w 。由 于列的变换是随机的，所以不能保证日中没有长度为4 的环。g a l l a g e r 在论文中 指出，当w 3 ，w ， 时，这种码具有良好的距离特性，而且编码器复杂度较低。ew c 这种码也叫做g a l l a g e r 码。 图2 5 是一个使用m a t l b e 程序随机生成的g a l l a g e r 码校验矩阵( m a t l a b 程序清单见附录a ) 。= 3 ， = 3 ，w ，= 4 。矩阵尺寸为比w ，= 9 x 1 2 。 使 w = 9 0 1 o o o o 1 1 o o 1 0 0 1 0 0 1 0 0 0 1 o 第二章l d p c 码概述 1 3 1 o o o 1 o 01o lol 0oo o 1 o o o 1 o o 1 o 1 o o o 1 o o 1 o 1 o 0 l o o o 1 o 1 o 1 o 0 l o o 0 0 l o o l 1 0 0 o o 1 1 0 0 o 1 o o o 1 l o o 0 1 0 图2 5 g a l l a g e r 方法生成的小型l d p c 校验矩阵 o o 1 o l o o o 1 用此方法可以稳定地生成大型l d p c 校验矩阵，图2 6 是一个= 4 ，w 。= 7 0 ， 的g a l l a g e r 码校验矩阵的稀疏矩阵示意图。 t a n n e r 在1 9 8 1 年总结了这种l d p c 校验矩阵的构造方法，另外s o r o k i n e 等 人在进行码分多址通信信道的研究【1 4 】中，涉及过这种方法，m a c k a y 和其他人 之后也对这种构造方法进行了改进。 0 1 0 0 1 5 0 05 01 0 01 5 02 0 02 5 03 0 03 5 0 非零元素个数= 2 5 2 0 0 m a c k a y 码删1 7 m 8 1 图2 6g a l l a g e r 方法生成的稀疏矩阵示意图 1 4 l d p c 码迭代译码算法的研究 m a c k a y 独立地发现了使用稀疏矩阵进行二进制编码的优点，并且第一个展 示了l d p c 码接近香农极限的优异误码性能。m a c k a y 在他的主页上发布了他自 己设计并构造的大量用于数据通信与存储的l d p c 码。下面是m a c k a y 使用的一 些构造方法： 构造方法l ：固定行重，随机生成列重为彬的列，要求此列重尽可能接近。 构造方法2 ：这种方法是最基本的一种构造方法，它要求保证列重固定为y ， 而行的重量尽可能均匀地保持为p 。同时要求任意两列之间的交叠重量不超过l 。 构造方法3 ：在方法2 的基础上，去除短环。 构造方法4 ：在方法3 的基础上，使h = 【h i h ， 中的e 为可逆阵( 或至少保 证h 是满秩的) 。 m a c k a y 码的一个显著的缺点是它的结构无法充分保证编码的低复杂度。编 码是通过对h 进行高斯消去，得到校验矩阵的系统形式h = 垆 i 】，由此可以得 到生成矩阵g = iip ，】。问题在于通过g 进行编码的时候，子矩阵p r 通常不够稀 疏，使得当码长n = - 1 0 0 0 的时候，编码的复杂度较高。2 0 0 1 年r i c h a r d s o n 提出了 一种有效的仅使用h 矩阵进行编码的方法【