（通信与信息系统专业论文）ldpc编码技术研究.pdf

摘要 捅妥 l d p c ( l o w d e n s i t yp a r i t y c h e c kc o d e s ) 码是一种基于矩阵构造编码和迭代译码的新 型信道编码方案，它具有很低的译码复杂度，并且拥有逼近香农极限的优异性能，目前 最好的l d p c 码字性能距香农极限仅o 0 0 4 5 d b 。随着研究的深入，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 码字的性能，同时还 能够确定信道域值，并帮助优化设计低密度校验矩阵的度分布。 关键词：l d p c 码，矩阵构造，先验信息，加权译码 中国科学技术大学硕士学俺沦文 c a nd e t e 咖i n et h ec h a n n e lv a l u el i m i tf o rs u c c e s s 如l t r a n s m i s s i o n ，a n dc o u l do p t i m i z et h e d e g r e ed i s t r i b u t i o nf o r i o w d e n s i t yp a r i t ym a t r i x k e yw o r d s ：l d p cc o d e s ，m a t r i xc o n s t r u c t i o n ，p r i o r i - k n o w l e d g e ，w e i g h t e dd e c o d i n g 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除己特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：垄登 渺g 年r 其j ! 日 第l 章绪论 第1 章绪论 1 1数字通信系统描述 通信系统是为了将信源信息高效、可靠地传送到接收端。有扰通信信道的噪声会对 传输信息产生干扰，从而可能降低通信可靠性。所以，通信系统设计的中心问题是在随 机噪声干扰下如何有效而可靠地传输信息。一般地，通信系统的可靠性用错误比特率 ( b e r ) 来衡量，有效性用传输速率r 比特信道符号来衡量。早期人们普遍认为通信系统 的可靠性与有效性是一对不可调和的矛盾【lj ，在有扰通信信道上要实现任意小的信息传 输错误概率的唯一途径就是把传输速率降低至零。s h a n n o n 信息和编码理论的奠基性论 文通信的数学理论f 2 】于1 9 4 8 年发表之后改变了这一观念，他首次阐明了在有扰信道 中实现可靠通信的方法，指出实现有效而可靠地传输信息的途径是编码。目前典型的数 字通信系统，如有线通信、无线通信、雷达和声纳等系统的基本组成如图1 1 所示。 编码信道 图1 1 数字通信系统模犁 在数字通信系统中，信源编码器将消息源产生的二进制信息序列进行信源编码，目 的是在允许的失真范围内，通过尽可能地去除信源中的冗余，从而使用最少的比特以尽 可能有效地表示信源。在这里，对于信号失真的度量依赖于信源的性质和实际的应用环 境，其中，最为常用的失真度量为信号的均方误差。s h 锄o n 在信源编码定理【4 】中指出， 对于给定信源和失真度量d ，一定存在最小速率为r = 尺( d ) ( 比特信源符号) 的信源编码 方式用以描述信源而平均失真不超过d 。显然，信源的率失真函数尺( d ) 给出了在确定失 真度量条件下信源的最小速率。 信号在信道中传输时，存在着信道噪声、衰落、各种干扰以及信道本身的非理想频 率响应等诸多不利因素。为了保证数据传输的可靠性，通常将信源编码器输出的信息比 特流在发送之前进行信道编码，即通过有效地添加冗余，使得接收器能够以非常高的概 率正确的从已经失真的接收信号中还原出原始信息比特流。s h 踟o n 在他著名的信道编 码定理中给出了在噪声信道中数据传输速率的上界，即信道容量。信道编码定理是：若 中国科学技术大学硕士学位论文 有一离散、平稳、无记忆信道，其信道容量为c ，只要待传送的实际信启率尺 c ，则一定不存在这样的方案。 根据以上讨论不难看出，编码在现代通信系统中起着全关重要的作用，已经成为了 现代通信系统中不可或缺的一个重要组成部分。编码可以从总体上划分为两类：信源编 码和信道编码。这两类编码在通信系统中有着不同的作用，其中，信源编码研究如何更 加有效地表示信源，而信道编码则是研究如何克服信道中的各种失真从而保证数据的可 靠传输。s h 锄o n 在信源信道分离定理【4 1 ( s o u r c e c h 锄e ls e p a r a t j o nc h e o 叫) 中指出，假定 在接收端所允许的信号的最大失真为d ，如果信源的码率小于信道容量尺( d ) c ，则接 收端可以在允许失真d 范围内恢复信源输出；相反，小存在这样的方案。分离定理的一 个重要意义在于，它证明了信道编码的设计可以不依赖于具体的信源类型。本文研究的 内容是信道编码，所以假定信源产生的信息经过了有效的信源编码，产生的信息比特流 为满足独立同分布的二进制比特流，然后研究信道编码技术对于出错比特的纠错能力。 1 2信道编码理论发展历程 香农提出了信道编码定理，并在其证明中引用了三个基本条件【2 】：1 、采用随机编码 方式；2 、码字长度趋于无穷大；3 、采用最大似然译码算法。指出一个随机选择的码以 很高的概率为好码，对于随机码的最大似然译码，其译码复杂度g 与所传输的信息比特 数呈指数关系，即为g = e x p ) ，随机码的误码率上限为以g 一晶( 足) 憎，误码率风随着 码长趋于无穷大而趋向于0 的同时，译码复杂度以指数增长，可见随机码在实际系统 里其实并不实用。由于信道编码定理证明的非构造性，并没有给出如何构造逼近香农容 量限的编码方法，构造一个逼近香农容量限的纠错码成了众多学者争相研究的课题，并 逐渐形成了信息论的一个重要分支玮道编码理论。五十多年来，人们对构造实用好 码的探索基本上是按照香农所提出的后两条基本条件为主线展开的。虽然从理论上讲， 除了目前已知的码外，几乎所有的码都是好码，但到目前为止，离构造出真正意义上的 实用好码还有较长的距离。尽管如此，国内外众多数字和信息论学术界的研究人员仍然 取得了很多优异的研究成果。 从构造方法上看，纠错码可分为分组码和卷积码两大类。在上个世纪五十年代到六 十年代，人们主要研究了线性分组码。这类编码以代数中的群论、域论等理论为数学基 础，利用各种代数方法设计好的纠错码，并研究与之相适应的译码算法。 2 第1 章绪论 第一个分组码是1 9 5 0 年发现的能纠正单个错误的汉明( h a r m t l i n g ) 码。1 9 5 0 年汉明 ( h a 舢血n gr 聊发表的论文检错码与纠错码【5 】是开拓编码理论研究的第一篇论文。 这篇论文主要考虑在大型计算机中如何纠正单个错误。但是h 锄m i n g 码存在许多卅i 足 的地方，首先是效率不高，码率只有4 7 ，其次是纠错能力不行，只能纠正单一的错误。 m g o l a y 针对汉明码的缺点提出了性能更好的格雷码( g o l a y 码) 【6 1 。g o l a y 发现了两种编 码，一种是二元g o l a y 码，采用1 2 个数据比特，1 1 个校验比特为一组，能纠正3 个错 误。第二种是三元g o l a y 码，以三进制数为运算域，6 个数据符号，5 个校验符号为一 组，可以纠正2 个错误。这两种码基本原理相同，都是将g 元符号按每七个分为一组， 然后通过编码得到咒后个g 元符号作为冗余校验符号，最后由校验符号和信息符号组成 有刀个g 元符号的码子符号，编码码率为r = 舶。 m u l l e r 在1 9 5 4 年以布尔逻辑代数方式提出了r e e d m u l l e r 码( r m 码) 1 7 j ，它比 h a m m i n g 码和g o l a y 码好的地方是它可以改变码字大小和纠错能力，是i k e d 在m u l l e r 基础上得到的一种新的分组码，也是继格雷码之后提出的最主要的一类分组码。r m 码 在汉明码和格雷码的基础上前进了一大步，在码字长度和纠错能力方面具有更强的适应 性。 继r m 码之后，p r 觚g e 于1 9 5 7 年又提出了循环码的概念f 引。循环码实际上也是一类 分组码，但是它的码字具有循环移位特性，即码字比特经过循环移位以后仍然是码字集 合中的码字。这种循环结构使码字的设计范围大大增加，同时大大的简化了编译码结构。 循环码的一个非常重要的子集就是分别由h o c q u e n 曲e m 在1 9 5 9 年以及b o s e 和r a y c h u a d h u r i 研究组在19 6 0 年几乎同时提出的b c h ( b o s ec h u a d h u r ih o c q u e n 曲e m ) 码， b c h 码的码字长度为甩= 珂m 一1 ，其中朋为一个整数。二元b c h 码( 旷2 ) 的纠错能力限 为， 2 ) 的情况，得到 了r s ( r e e d s o l o m o n ) 码。r s 码的最大优点是其非二元特性可以纠正突发错误并日它也 能纠正随机错误。但直到1 9 6 7 年b e r l e k a m p 给出了一个非常有效的译码算法之后，r s 码才在实际系统中崭露头角，比如在c d 播放器、d v d 播放器以及c d p d ( c e l l u l a rd i g i t a l p a c k e td a t a ) 标准中都得到了很好的应用。 上面所讨论的这些都是分组码，分组码本身的一些不足，限制了它的运用。第一， 它必须是按帧传输、按帧译码，这样在帧长较长时会带来一定的时延。第二是要求准确 的帧同步，这样才能准确译码。多数分组码要求解调器的硬判决输出，这样又会带来一 些判决误差，影响性能。另外，分组码的译码方法通常都采用大数逻辑译码和捕错译码， 其译码复杂度与码长成指数关系，码长越长，译码复杂度越大，而且上升趋势很快，所 以基本上不实用。能够实用的只是短码长的情形，而短码的性能有限，难以达到逼近 s h a r u l o n 极限的目标，s h a n n o n 限的逼近需要长码，这就需要去寻找能够有效译码的长 分组码。 中国科学技术大学颂士学位论文 1 9 5 5 年，e i i a l s 等人首先提出了卷积码【9 】。卷积码不是将数据分割成不同的分组，而 是通过移位寄存器将校验比特加入输入数据流中。每甩比特输出是当前七比特输入和寄 存器中的聊比特的线性组合，每次输出总的比特数与约束长度七有关，其码率为存一次编 码间隔中数据比特七与输出比特数行之比。卷积码与分组码不同在于它在编码的过程中 引入了寄存器，增加了码元之间的相关性，在相同的复杂度下可以获得比分组码更高的 编码增益，但是这种相关性同时也增加了分析和设计卷积码的复杂性。随着人们对卷积 码研究的深入，在卷积码的译码算法方面出现了序列译码算法、门限译码算法和维特比 ( v i t e r b i ) 译码算法【加】。维特比i t e r b i ) 译码算法的出现，使卷积码逐渐成为研究和应用的 重点，以后出现的t c m ( 栅格编码调制) 技术进一步确立了卷积码在纠错码应用中的主导 地位，特别是在通信系统中得到了极为广泛的应用。其中，约束长度肛7 ，码率为1 2 和1 3 的o d e n w a l d e r 卷积码已经成为商业卫星通信系统中的标准编码方法。在移动通信 领域，g s m 采用约束长度肛5 ，码率为1 2 的卷积码；在i s 9 5c d m a 系统中，上行链 路中采用的是约束长度庐9 ，码率为1 2 的卷积码。 卷积码的主要问题是对突发性错误的纠错能力差。但是采用交织和卷积码结合的方 式，可以在码比特送入信道前，进行分组交织，再进行卷积码编码，存接收端，先解交 织，再译码。经过这一交织与解交织的过程，突发性错误就变成了随机错误。卷积码性 能得到改善。 经过上个世纪几十年的研究和实践，纠错码理论和技术取得了很大的发展，但是距 离s h a n n o n 理论极限仍然还有一定的距离，难以找到逼近s h a 肌o n 极限的编码方案，这 使得人们一度认为s h a m o n 极限仅仅是理论上的极限，是不可能达到的。此时，法国的 c b e 啪u 等人在1 9 9 3 年提出了一种全新的信道编码方案：t u r b o 码j ，在信道编码的理 论和应用中取得了突破性的进展，具有里程碑的意义。它打破了串行级联编码的结构， 采用并行级联编码。t u r b o 码的基本思想在于利用短码构造长码，在译码时，将长码化 为短码，再利用软输入软输出的迭代译码算法( m a p 算法，s o v a 算法) 达到了接近 s h a n n o n 极限的性能。 t u r b o 码的优异性能使其一度成为编码界研究的热点，其理论和技术也逐渐成熟起 来。t u r b o 码在通信中有广词的应用前景，在诸如星际探测、移动通信、数字电视、数 字广播、卫星通信中都得到广泛应用。但是t u r b o 码也有自身的缺点，它的译码复杂度 仍然较高，且码长较长时，交织器的存在使得时延较大。 就在人们热点研究t u r b o 码的时候，有人注意到了一种早在1 9 6 2 年就由g a l l a g e r 提出来的信道编码方案l d p c 码( l o wd e n s 埘p a r 时c h e c kc o d e s ) 屹j 【1 3 j ，它利用校验 矩阵的稀疏性，使得译码复杂度只与码长成线性关系，在长码长的情况下仍然可以有效 的进行译码，因而具有更简单的译码算法。后来d j m a c k a y 、m n e a l 和n w i b e 唱等人 对l d p c 码重新进行了研究f j 4 】 1 5 】，发现l d p c 码与t u r b o 一样具有逼近s h a 衄o n 极限的 4 第l 幸绪论 为其前向纠错编码方案；美国h u 曲e s 公司和一些研究机构也已经研究出使用l d p c 码 的编译码芯片。w i m a x 以及b 3 g 等标准里面也采用了低密度的编译码方案。相信随着 l d p c 码的进一步技术成熟，更多的未来通信系统会采用这种具有优异性能和应用前景 的编码方法。 1 4论文研究内容及安排 第一章介绍了信息论和信道编码的发展历程，重点介绍了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 码的研究现状的看法，同时 指出了l d p c 码的未来发展趋势。 第2 章l d p c 码基本原珲 第2 章l d p c 码基本原理 2 1l d p c 码概述 l d p c ( l o w d e n s 时p a r 时c h e c kc o d e s ) 码是一种由稀疏校验矩阵定义的线性分组 码，最初由g a l l a g e r 于1 9 6 2 年提出【1 2 】。但由于当时技术条件的限制，人们的兴趣大都 集中在有实现可能的编码方式上，比如卷积码、级联码等，以至于l d p c 码在很长一段 时间内几乎被人们遗忘。直到1 9 9 6 年，m a c k a y 和n e a l 随机构造的l d p c 码1 1 4j 存码长 很长时性能超过了b e r r o u 等人提出的t u r b o 码，而且在实现上更有优势，才激起人们重 新研究l d p c 码的热情。 l d p c 码具有诸多优异特性。其校验矩阵是一个天然交织器，译码复杂度随着码长 的增加呈线性增长，且具有逼近s h 锄o n 极限的性能；它的描述和实现简单，有严格的 理论分析工具可对其进行验证；它的译码算法可并行处理，有利于在硬件上的并行实现， 减少了译码时延；可进行动态判决译码，即在迭代译码过程中进行译码判决，以决定是 否结束译码进程，如此可以减少译码迭代次数；由于具有较大的码距，使得不能被译码 检测的错误很少，因此具有良好的检错性能；很少出现误码甲台( e r r o rf l o o r ) 现象，误码 率随信噪比的增大快速下降；有成熟的t 锄e r 图和因子图等简单实用的图模型描述，使 得理论分析更加简单有效。 目前仍然存在很多因素在限制l d p c 码的实际应用。由于校验矩阵中短循环的存在， 当码长很短时性能较差，因此只有长码才能体现l d p c 码存性能上的优势，但随之带来 了许多问题。长码的编码复杂度高，而且对于硬件存储器的需求也大，虽然目前已经有 了线性时间编码复杂度的实现方法，但与卷积码等编码方式相比仍然太大。另外，l d p c 码需要对一组信息序列一起编码，码长较长时，为了接收完所有信息比特进行编码，需 要等待较多的时间，而这将带来编码的时延。所以研究更加快速实用的编码方法成为一 个重点问题。 2 2l d p c 码的定义 l d p c 码可用一个稀疏的非系统的校验矩阵且。圳。定义，其中月为码长，七为信息 位个数，所有码字c 均满足c h r = 0 。校验矩阵“稀疏”是因为矩阵中除了少数元素 为“l 外，其余大部分元素全部是“0 ”，其每行中“1 ”的个数( 以下简称行重) 远远小 于校验矩阵的列数。根据l d p c 码校验矩阵元素为“1 ”分布情况的不同，可以将之分 为r e g u l a r 和i r r e g u l a r 两种。r e g u l a rl d p c 码( 正则l d p c 码) 中，每一行为“l ”的元素 个数相同并且每一列为“1 ”的元素个数也一样，即矩阵的各行行重和各列列重分别一 致；反之，如果校验矩阵的行重或者列重不一致就称为i 玎e g u l a rl d p c 码( 非正则l d p c 码) 。根据g a l i a g e r 最早给出的正则l d p c 码的定义，描述如下【1 2 】： 9 中国科学技术大学颁上学位论文 正则l d p c 码：对于一个码长为甩，校验位长为耽的l d p c 码，若其校验矩阵每行 “1 ”的个数全为k ，每列“1 ”的个数全为i ，则称其为正则l d p c 码，记参数为( j 幼， 并且通常满足条件? 歹 毛 朋，k 以。g a l l a g e r 证明了当歹3 时，这类l d p c 码具有很 好的汉明距离特性。 非正则l d p c 码：类似于正则l d p c 码的定义，不同的是校验矩阵每列“l 的个 数或每行“1 的个数不全部相同。研究表明，通过优化非正则l d p c 码的校验矩阵中 元素“l ”的分布，可以得到比正则l d p c 码更好的性能，不过在硬件实现方面具有更 大的复杂度，需要更多系统资源。 对于校验矩阵风。，假设其秩为，= r a n k ( 邱，那么其合法码字个数是2 一，。若校验 矩阵不满秩，即， 聊，则合法码字个数大于2 一m 。l d p c 码的码率r 应该为r = 伽一枷， 而大家常常用r = ( 聆一所) 门计算码率，由于r r ，所以应让校验矩阵尽量满秩，才可 以让月接近真实的r 值。 l d p c 码的校验矩阵一般都是用非系统形式给出的。例如，个( 1 0 ，2 ，4 ) 的校验矩 阵可以用图2 1 所示： 0 = 1 1 1 100o0o0 10ool 1 10oo o1oo1oo1 10 0o1oo1o1o1 o0o1o0101 1 图2 1 ( 1 0 ，2 ，4 ) l d p c 码的校验矩阵 除了用校验矩阵表示l d p c 码以外，还可以用双向的图模型表示l d p c 码，其中 t a l m e r 图表示是比较方便的一种，可以形象地刻画l d p c 码的编译码特性。t a r u l e r 图是 一种双向图，可以用g = ( y ，e ) 表示，其中y 是节点的集合，y = u 圪。对维数为聊 的校验矩阵日。，圪= ( 6 l ，6 2 ，玩) 称为比特节点，对应校验矩阵的列，同时对应码字 中的比特位；圪= 似，c 2 ，c 。) 是校验节点，对应校验矩阵的行，也就是校验方程。e 是 比特节点和校验节点之间相连的边的集合k ，同类节点之间没有边相连，只有 在两类节点之间有边存在。如果校验矩阵的第f 行第列元素为非零，则t a n n e r 图的第 ，个比特节点与第f 个校验节点有一条边相连。即当矗，= l 时，节点c 与6 ，之间有一条边 相连，边( c ，6 ，) e 。与节点相连的边数目称为该节点的度( d e g r e e ) ，从某个节点出发又 回到此节点为一循环( c y c l e ) ，所经过的边的条数称为循环的周长，其中最短循环的周长 称为图g 的g i r t h 。校验矩阵的行重和列重与节点的度一致，t a n n e r 图与校验矩阵一 对应。上图中的校验矩阵刘应的t a n n e r 图如图2 2 所示，具有1 0 个比特节点和5 个校 验节点，每个比特节点都有2 条边，每个校验节点都有4 条边。 l o 中国科学技术大学硕士学位沦文 日= 睇：) 陋2 ，日= i( 2 2 ) lcdej 。 该矩阵形状如下： 卜一n - m h i g 一m - 占 i _ 一心 图2 3近似下三角校验矩阵形状 将校验矩阵左乘如下矩阵 匕一- ， 得到 b 曼+ c e 幺j 口) p 4 ， lf 2 4 、 一e t 一| a + c e t 。lb + do1 j。 那么m r = 驴可以分解为如下两个表达式： 4 s r + 却；+ 印；= 口 ( 2 - 5 ) ( 一e t 一1a + c ) s t + 一e t b + d ) p l = o q q 定义够= 一e r 一，曰+ d ，并日假设妒非奇异，则求解上面两式可得： p f = 一缈一7 f ，一e 丁一7 彳+ a j r ( 2 - 7 ) p 罗= 一r 一似j r + 却；j ( 2 - 8 ) 通过如上两个公式可以计算校验信息p ，和p ：，从而得到码字。下面对这种矩阵变 换编码方法的复杂度进行分析，由前面推导可知，因为系统信息比特可以直接得到，所 以复杂度就集中在计算p ，和p ：的两个公式。 根据r i c h a r d s o n 和u r b a n l ( e 在 3 2 】中有关复杂度计算的描述，对于p ，和p ：的计算 复杂度估计分别如表2 1 和表2 2 所示： 统计两个关于计算校验信息p ，和p ：的复杂度的分析表格，可以得到矩阵变换方法 的编码复杂度为d ( 以+ 9 2 ) 。为了降低编码复杂度，应该让g 尽量小。r i c h a r d s o n 等存文 章中提出了三种g r e e d y 算法对矩阵的下三角化进行讨论，它们是g r e e d y 算法a 、g r e e d y 算法b 和g r e e d y 算法c ，其中g r e e d y 算法a h 、g r e e d y 算法b h 和g r e e d y 算法c h 分 别表示直接作用算法a 、b 和c 于校验矩阵，而g r e e d y 算法a h t 、g r e e d y 算法b h t 1 2 第2 章l d p c 码摹木原理 和g r e e d y 算法c h t 表示作用三种算法于校验矩阵的转置。三种g r e e d y 算法可以让g 尽量小，从而降低l d p c 编码的复杂度， 表2 - 1 校验信息pj 的计算复杂度分析 操作解释 复杂度 4 s r 稀疏矩阵与向量的乘法d ( 胛) z - j ( 彳j r )令一= 4 j7 ，复杂度同上 0 ( 门) 一e ( r 一爿s7 ) 令y ；= 丁一彳j7 ，复杂度同上d ( 门) c s l 稀疏矩阵与向量的乘法 0 ( 甩) ( 一e r 一7 彳j r ) + ( o r ) 两个向量的加法运算 d ( 甩) 一9 7f e r 一。4 s r + c 奢r ) g g 的密集矩阵与向量的乘法 0 ( 9 2 ) 表2 2 校验信息p2 的计算复杂度分析 操作解释复杂度 爿j r 稀疏矩阵与向量的乘法 p ( 刀) b 设 稀疏矩阵与向量的乘法 d ( 胛) 纠s r ) + ( 却7 j 两个向量的加法 0 ( 甩) 一丁一阳j r + 却f 夕令一= ( 爿j r + 却7 ) ，则j r 一7 一，d ( 刀) 仍然是稀疏矩阵与向量的乘法 矩阵燹决算法编冯过程总结如卜： 第一步：预处理过程，输入非奇异校验矩阵，输出形如( 三三：) 的等价矩阵，并 且要保证一e r 一曰+ j d 为非奇异矩阵。预处理过程包括近似下三角化校验矩阵和矩阵的 秩校验。近似下三角化是通过行列置换将校验矩阵变成形如( ：三：) 的近似下三角 矩阵，并且通过应用几个g r e e d y 算法让g 尽量小。矩阵的秩校验则是利用高斯消元法 完成如下矩阵运算： ( 一：丁一，1 ) ( ：三：) = ( 一e r 乞+ c 一；，占+ j 口) c 2 9 ， 关键是要检验矩阵一r 一，占+ d 是否奇异，如果奇异，那么需要进一步进行列置 换使它最终非奇异。 第二步：实际编码过程，当校验矩阵已经按照预处理过程的要求化成了形如 中国科学技术大学硕士学位论文 ( 三三：) 的非奇异矩阵，那么对于给定的输入信息序列s ，只需要通过公式( 2 7 ) 和 ( 2 - 8 ) 计算校验信息p ，和儿就可以得到编码输出码字c = p ，p ，肌) 。 校验矩阵变换编码算法虽然可以实现近似线性的编码复杂度，但是它对编码矩阵的 原始结构要求较高，很多矩阵仅通过简单的行列置换并不能满足该方法的诸多限制条 件，因此应用也遇到一些困难。降低编码复杂度的另外一个有效措施是设计具有特殊结 构的校验矩阵，如循环码和准循环码，仅通过信息位或者校验位数量的移位寄存器即可 实现该类编码，复杂度低，与分组长度成线性关系，没有大的编码延迟，而且易于硬件 实现。类循环码已经成为当前的一个研究热点。 2 4l d p c 码的译码思想 l d p c 码的译码算法有硬判决译码算法、软判决译码算法和混合判决译码算法三种。 它们有着不同的纠错性能和译码运算复杂度，硬判决译码复杂度低，但性能相刘。最差； 软判决译码纠错性能最好，刁 过复杂度也最高；混合判决译码则在性能和复杂度之间有 一个折中。 g a l l a g e r 在其博士论文【1 2 中提出了两种l d p c 码的译码方法，一种称为比特翻转 ( b i tf l i p p i n g ，b f ) 译码，另一种是信息传递译码。 b f 译码是一种基于迭代的硬判决译码算法，它首先对输入译码器的数据进行硬判 决，然后将得到的“o ”、“1 ”序列代入所有校验方程计算各个校验子的结果，如果发生 错误，校验方程不满足，则根据校验结果找出使得校验式不成立数目最多的比特节点， 并将该比特节点对应的比特值进行翻转( 0 变为1 或l 变为0 ) ，至此完成一次迭代。迭 代中止条件是达到最大迭代次数或者所有校验方程都校验成立。b f 译码操作简单，硬 件实现容易，但性能要比软判决译码差很多。 g a l l a g e r 的软判决概率译码可以看作是t a n n e r 图上的置信传播( b e l i e fp r o p a g a i i o n ， b p ) 译码算法，也称为和 | 算法( ( s u mp r o d u c ta l g o “t h m ，s p a ) 或信息传递( m e s s a g e p a s s i n g ，m p ) 译码算法，由于其性能最优，因此应用也最广。译码思想大致是：对某一个 接收码字进行译码时，先根据接收数据和信道信息初始化每个比特节点的概率软信息； 再将比特节点的概率信息传递给校验节点，校验节点的概率信息是参与该校验方程的所 有比特节点对该校验方程的概率贡献：然后校验节点将概率信息传递给比特节点，对于 某个比特节点而言，该软信息就是它所参与的所有校验方程对它的概率贡献；最后，比 特节点利用从它参与的所有校验方程那里得到的概率信息以及信道初始化信息进行译 码判决。如此则完成了一次信息传递和迭代过程，当某次判决译码成功或者达到迭代次 数上限时就停止译码，否则进入下一次迭代过程。 经过几十年地不断发展，l d p c 码的译码算法得到不断完善，出现了很多新的译码 算法。包括1 9 8 1 年t a n n e r 提出的基于t a n n e f 图的并行译码算法，1 9 9 8 年r i c h a r d s o n ， 1 4 第翼矍鋈嘉甜为烈靳簦萋北蠹羹 l 蓁霎翼| 霎| 薹| 冀霰豢萎j 预羹搓冀嚣霎喜雾疆塑曼章薹垂；羹垂耋谚岑羹臻i 羹一霎l 飘 i 毫t 薹i 塾霪焉墨甥型| 霎蘸堋博嗜錾塞囊至牟拆蓁咎氅囊一萋；鬟i ；鬟$ ； 靼震理鬟孽噬舂强蔼瑶嵩蠼窿鋈羹都亲妤嘉捌霎壅薹雾西醋；粕妻西浏浑塞邑舐霎 磺她啪臻唾膏羹臻，曼霎型虱勤马幽蚕茧薹摹虿蠹装蓁鹰惯佃鹭也i 复舞霎有的虑萎纛 露j 薹吲鹤；薹| 强 第3 章l d p c 码校验矩阵构造方法 第3 章l d p c 码校验矩阵构造方法 l d p c 码的编码关键就是构造低密度奇偶校验矩阵，不仅如此，校验矩阵在译码过 程中也起着至关重要的作用。根据构造方式的不同，目前l d p c 码校验矩阵主要有随机 化、半随机华和结构化等几种构造方法。随机化构造方法在l d p c 码的早期研究中出现 较多，以g a l l a g e r 、m a c k a y 以及r i c h a r d s o n 等人为代表。此方法构造的校验矩阵由于具 有随机特性，因而纠错性能良好，但由于矩阵结构不固定，无法实现简单编码，译码时 校验矩阵的存储复杂度也高，所以在实际系统中的不易应用，特别是磁记录和光纤通信 等高速传输场合。近年来结构化的构造方法已经成为l d p c 码校验矩阵构造领域的主要 研究热点，如循环码和类循环码、几何设计法、组合设计法以及性能优越的p e g 方法等。 这是因为结构化构造方法不仅可以克服校验矩阵中短循环的产生，而且生成的l d p c 码 字可以是循环码或类循环码，具有线性时间编码复杂度，同时矩阵具有确定的结构，便 于硬件实现。性能上由于结构化方法可以设计g i n h 较大的码字，因此并不会比随机校验 矩阵构造的码字差多少。 3 1随机构造法 3 1 1 g a l l a g e r 构造法 g a l l a g e r 最早在 1 3 】中提出了一种简单的l d p c 码校验矩阵随机化构造法，此方法构 造的校验矩阵度分布为( 矾，以) ，其中矾3 ，构造过程如下：根据校验矩阵码长以及行 列重等参数，首先设计一个基矩阵风，基矩阵中每列都只有一个元素值为1 ，并且第f 行中为l 的元素全都分布在从( f 一1 ) 以+ 1 到试的以个连续列中，如图3 1 所示。然后对 基矩阵做随机列变换，得到其余玑一1 个子矩阵，并将这矾一1 个子矩阵以等概率随机排 列的方式叠放在基矩阵的下面，从而构成一个l d p c 码的集合，如图3 2 所示。 风= l l1 1 、- - 、r j t 个l 1 1 l 1 、- - - v j 以个l 图3 。l基矩阵结构 h = h q 乃( 凰) 死一- ( 风) 11 1 1 、- 、，- j t 个l 图3 2由基矩阵构造l d p c 码的校验矩阵 其中刀，( 凰) 表示通过凰的随机列变换生成的子矩阵。可以看出用这样的方法得到 第3 章l d p c 码校验矩阵构造方法 3 2半随机构造法 校验矩阵的随机构造方法可以不受码长、码率等参数限制，参数选择灵活而且性能 好，不过其不固定的结构使得编码复杂度高。下面介绍一类半随机的l d p c 码，它们具 有编码简单以及参数选择灵活的特点。 3 2 1 半随机l d p c 码 文献【3 4 】介绍了一类半随机l d p c 码，它将码长为九，信息位为七的l d p c 码校验 矩阵分解为两个子矩阵，形如胃= 【h 一日d 】。其中“是一个( 胛一七) 克的矩阵，称为信 息位矩阵，它采用随机方法构造；日，是一个( ，l 一。七) ( ”一七) 的矩阵，称为校验位矩阵， 它是双对角线形式的下三角方阵，具有如下形式： h p= 10o uu 11o uu o1 1 【) u 0o0 1o 000 1 1 相应的将校验矩阵所对应的码字向量c 分解为对应的校验位向量c ，和信息位向量 c d ，即有c = 【c p 一】，校验矩阵与码字向量c 之间有如下关系： 广， 胁r = 日，日d 】| 二| h ，f ，+ h o j = 口 ( 3 - 1 ) l j 在二进制情况下，公式( 3 1 ) 可变换成如下形式： 日即p = 日屯d ( 3 2 ) 由上式可知，给定任意一个信息位向量c d ，能够利用构造出的校验位矩阵日p 和信 息位矩阵日d 直接计算出c p ，从而得到码字向量c 。有两种方法可以计算c ，一是 c p = 日p r i 【日c ，c d 】，二是直接对公式( 3 2 ) 进行高斯消元求得c p ，后者较前者更简单，具 有线性计算复杂度。 总结半随机构造法，先是利用随机方法构造一个信息位矩阵h j ，然后根据参数设 定一个校验位矩阵日，给定信息位向量c d 后，再分两步完成编码： l 、计算中间映射向量l ，= 日d c d 2 、用高斯消元法解方程h ，c ，= l ，求得校验位向量c ，从而获得编码码字 c = 陋，c d 】 3 2 2 兀旋转l d p c 码 文献 3 5 】描述了一种基于兀旋转的l d p c 码构造方法，它实际上是在半随机l d p c 码 的基础上来构造的。由半随机l d p c 码的校验矩阵结构可知日= 【p 4 】，在冗旋转 1 9 中国科学技术大学硕上学位沦文 次数。假设区组矩阵抒是以x 中的元素为行，区组为列的矩阵，那么矩阵中元素拓，= l 表示元素屯被区组6 ，所包含，否则 ，= o 。根据如上对应关系，还可以得到w = 掀。 介绍了b i b d 理论后，下面详细讨论如何利用三维循环网格图来构造b i b d 和l d p c 码的校验矩阵。 3 3 1 2 基于三维循环网格图的b i b d 构造 根据b i b d 理论，如果构造了一个b i b d ，那么就可以对应得到一个l d p c 码的奇 偶校验矩阵，从而得到一组l d p c 码字。这里介绍一种用三维循环网格图构造b i b d 的 方法。 首先构造一个尺度为c r q 的三维循环网格图，描述如下： 上口，f f c p ( c ，r ，q ) = ( x ，j ，z ) ：0 x c 一1 ，0 y r 一1 ，o z q 一1 ) 其中r 为质数，q 、c 为正整数( c 一般取为3 ) ，c 、又、q 可分别看作三维循环网格 图对应x 、y 、z 坐标上的量，如图3 3 所示： 图3 3 ( 3 ，5 ，2 8 3 ) 三维循珂、网格图 构造网格图之后，需要对网格内各个元素点进行编号，一般按照z 轴优先，x 轴其 次，y 轴最后的顺序将各个元素节点编号填入网格内。想要在网格图内部构造组平面， 然后在各个平面内生成一组直线，直线对应着均衡不完全区组设计的各个区组，而直线 上各个点就对应着区组中的元素。为了构造一组平面，先在图中顶部r c 平面内构造一 组直线，然后沿着该直线向z 轴切开网格图，得到一组切面作为甲面组，再在该组甲面 内部作直线得到区组。下面详细介绍这个过程以及相关参数的选择。 3 2 1 拈 嬲 嬲 3 2 x 萋錾曼篓蚕篓瞬卸卿矧崮矛杰霪 霪囊陉薹| 雾巡，蠢霸童列霾墓i i 。l 登j 照苌垂竖萋蓁蠢；竺羹囊豁爷；可墨葫童墅 雾舅耱鐾；墼冀琵罂篷嘎萋巨缘分；羹和不- 平行子翥鬟薹瑟馨烊篓霎鋈可汁堕塞 i 夔i 羹l 捌霎：部霪萋叫崾雾隧霎莲；萋型一堇垡爵鲜i 薹| 囊鋈诗篓一倒 丰 獯摒；丽菊丽 菰稀萋僮卷雾耋萋二羹= 型f 蓁耄二照冀嚣型理蓁；耄羹羹；嚣耋靖蟹鋈i ；霎仕薹球蓁希 端型而萎芦萋墼薹羹；蓁薰藿錾霎：薰鬟；* 望i 璀暄季暨蟛量；冀| 警喜= 翼些附鸯 冀篷填鍪螫；弱塑需攫薹爷蠡可她i 雕戊姜量茎绸鏊i 耄刿型。副 引誊薹| 趔薹i 掣萋霎妻 氨薹蒺圭；季錾霎秘i 蓼凳；襄冀鼋囊妻；萋塑誉昼萋鲔 x 中l 斐蚕薹霉喜藩同巍刍她嗣童墓；i 霎 蓊墼嚣黧饕；溪豢垫薹塞塑耋霉臻建鬻到墅要，k 墼笔握篓露菘囊堤蔷哩墼 霁攀藉掣羹j 掣利如蠢超翼繁乳囊按凰器斜；一手帑器竹薹辩蓁 * 羹! 萋一霎。剥 壁笋塞翥情瘗幕= 囊雾翥鬟羹掣塞纛霉些茎喜藿l 萎霎萎霎霪主璧莲l 耋囊器i i 耋霎二 掌；貉臻萝主鐾瞧铂攀厦缘萋季一些羹纛；蓄羹毪一蠢珊奏薹筵循圉l 墨；彳_ 蓝丙薹 雾篓薹嚣旭凰稍蓁鏊f ：型沛囊羹刽型冀卧更需雾番碡蓁三蓁丽蠹羹院蓍羹妻 黼鬟；蹦裂薹甭百；露澜羹霪；基霎；妻l 蓄萋| | | 幕幽薹面；奏耄i 引引勰拳当箫希麓 曩霎皿雾蹙；雾爱誓誊；希萎爨蔫篓囊一萨一零 显篓萋篓墓主耋雾鏖留鲢喾r 雕雾 囊；型爱萼提叠曜螺葡篓蚕墅雾髅堡雾萋起遵圣i 蠕姜嚣矿以| ；蓐墅薹涠嗟 狻囊j 攀堕雾；磊瑚淄哺誊毛耋；奠，秦翼掣利邑劐双蓁l 薹霎萋一霎蓁萎奏奏：毒萎萎耋专辜詈睾篓篓 霎i 鬈髦：i i 皇蠢1 垂蓄i 等羹薹雾鍪霆蓁薹羹雾蒌囊 蓁鏊羹圃雾羔篓熏瓷垂耋纛囊霎霸裂载墓型霎叫誉i 是鏊曜旱耋群哙导囊善膏叁囊苴； 猁降靖甥莉攀鍪雾莹量蓁塞篙裂导潦廿慧遣悟静j 墓存囊鋈望羹零藿塌露唆皤蠖季妊薹 雾陲鬻甚竖爵錾爱薯悬篪坫： 鬟薹羹孰趔薹囊囊薹亚篓。；r 基霸蒂忑幕罐：荫篓蔫 鞲鍪阿塑篷鐾蠢萎薹黍鬲端；赢裂蠢笪雾树融掣验理阻堕芎篡i 薹! 蓁；塞蔷剖娄割剽剡翔塞蓊旨矍薹 叶羹霆参列塑希量垫謦雾蓁冀鬣鬣撵鍪篓墓；薹翥娶摹髦薹搿埔囊蚓馥蚕二莓嶷环 囊埔蘸攀；钙邂筌蠢羟巍璎翔一蜊薹喜；翦；雾l 囊j 鬟攀蓄j 喜南篓耋稀鬓冀褐；鏊豆冀雾瓤錾 篓蕈煞醑耪裤猎诺落耀垮瑗霎霎；季摹旨露孽季萋| | 耋黎青薹菱妻喜羹囊j 蓁i 羹攀和蘩瑚送 竖c 熹鋈蒸孺雾靴蒜誊i 剐彭雾霁荫；萎驰匪羹斜囊萋鬈篓笺导美需鬟器! 荔馨循型驯 薷萎墼豢羹冀雾藿馥雾囊蓬璧絷鬟羲笞毋；一羹薹引赚醋至鱼谨蓁薹型冀誊囊经瞥藿 缉士塑亘线薹名；塞静曩型妻蓁零狻耀瑙望嚣塑塑鑫靶毖袭霎弛冀蓄辇萋蓠羹雾簿粤至 霁塑羹薹捌酉雾羞亟袋；毳杉：灞隋囊碍毳簦茎曲士辫型显零薹蓁型缸霉墅蓁篓；霾薅l 萋一 主i 羹蓁薹篓霎萎紊妻窭墼霸凳鎏莠蓁垄i 主! 薹羹! x 第3 非l d p c 码接艟摊孵毋碹刀 ；篓 逸一携避霆! 薹羹鋈霪蓁雾茎蓁皑鉴矍羹耋葡! 碧豳萋崇磊落些簿擀群鬻掣 醋霄蛩融翅i 降陶羹儒涮礞缚储薹能妊翼i 季 。罾坚颡囊震羹鬯琵* 薹! 霉一lj 茎 士褥蛾剥耋蓁雨，枣奶碰僦蓟和蓟划耋藿参羹薹薹匡羹羹蓁萋妻薹萎i 霎垂鐾l i 耋薹i i 当“爹茎囊窭需拶譬墼转群一鏊薹芳；蠢蓁烈；篓稻蠢霁鬟朝乳霎銎i ；燮霰鎏垦 鬻丢雾奘薷甥罐噻鹱霉= 蒜囊蓥第薹| l 羹羹藕堀强薹坦臻霎璧粪罐