（通信与信息系统专业论文）ldpc码编译码器的硬件实现.pdf

重庆邮电大学硕士论文摘要 摘要 低密度校验( l d p c ) 码是一种基于图和迭代译码的信道编码方案，性能 非常接近s h a n n o n 极限且实现复杂度低，具有很强的纠错抗干扰能力，更 能适应未来系统高速数据传输和高性能的要求。尽管由于l d p c 码重新研 究的时间较晚和第3 代移动通信标准失之交臂，但基于l d p c 编码的方案 极有可能成为4 g 移动通信系统的应用方案。目前，低复杂度的l d p c 码 编译码器的硬件实现一直是l d p c 码研究的热点问题之一。 本文主要针对l d p c 码编码器与译码器的硬件实现进行了研究。首先 对l d p c 码定义和t a n n e r 图表示以及l d p c 码构造方法进行了系统地介 绍，重点分析准循环l p d c 码。其次对l d p c 码编码算法进行研究，并分 析几种编码算法的复杂度，b p 译码算法和最小和译码算法进行了详细研 究，最小和译码算法可以简化校验节点的计算复杂度，以便于硬件实现。 最后针对选定的编译码方案进行了硬件设计。本文采用了模块化设计，在 对各个模块进行设计的基础上提出了一些改进的方案，在编码器的设计 中，改进了常用的移位寄存器设计法，从而简化矩阵乘法模块。在译码器 的设计中，对半并行l d p c 码译码算法的硬件实现进行了研究。在设计中 综合运用了“自顶向下”和“自下而上”的设计方法，通过功能模块分割，合 理设置系统参数，并通过模块之间的参数传递，使l d p c 码编译码器具有 较好的灵活性，并用v c r i i o g 语言在x i l l i n xv e r t e x 2 2v 6 0 0 0 获得硬件实现。 关键词：准循环l d p c 码，最小和译码算法，编码器，译码器 重庆邮电大学硕士论文 摘要 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 sa r eac l a s so fc h a n n e lc o d e s b a s e do ng r a p h sa n di t e r a t i v ed e c o d i n gw h o s ep e r f o r m a n c ei sv e r yc l o s et ot h e s h a n n o nl i m i tw i t hl o wc o m p l e x i t ya n dh a v es t r o n ge r r o rc o n t r o ls t r e n g t h ，s o t h e y w i l l b ea b l et o a d a p t t o h i g h s p e e d d a t at r a n s m i s s i o na n d h i g h - p e r f o r m a n c er e q u i r e m e n t so ft h ef u t u r es y s t e m s a l t h r o u g hn o tu s e di n 3 g p p ，l d p cc o d e sw i l lb e e na d o p t e da st h ee r r o r - c o r r e c t i n gc o d i n gs c h e m ei n 4 gm o b i l ec o m m u n i c a t i o ns y s t e m c u r r e n t l y ，e n c o d e ra n dd e c o d e rw i t hl o w c o m p l e x i t yh a v eb e c o m eo n eo ft h em o s ta t t r a c t i v ei s s u e si nl d p cc o d e ss t u d y t h eh a r d w a r ei m p l e m e n t a t i o no fl d p ce n c o d e ra n dd e c o d e ra r cd e a l e d w i t hi n t h i s p a p e r f i r s t l y ，b a s e do nt a n n e rg r a p h ，t h er e p r e s e n t a t i o n a n d c o n s t r u c t i o no fl d p cc o d e s ，e s p e c i a l l yq u a s i c y c l i cl d p c ，a r ei n t r o d u c e d s y s t e m a t i c a l l y s e c o n d l y ，t w oe n c o d i n ga l g o r i t h m s f o rl d p cc o d e sa r e m e n t i o n e d ，a n dt h ec o m p l e x i t yo fa l g o r i t h m sa r ed i s c u s s e d a n dt h e nt w o d e c o d i n ga l g o r i t h m s f o rl d p cc o d e s i e s u m - p r o d u c ta l g o r i t h ma n d m i n - s u ma l g o r i t h ma r ed i s c u s s e d ，t h el a t t e rc a ns i m p l i f yt h ec a l c u l a t i o no ft h e c h e c kn o d ef o rh a r d w a r ei m p l e m e n t a t i o n f i n a l l y ，t h eh a r d w a r ei sd e s i g n e db y u s i n gt h es e l e c t e da l g o r i t h mo fl d p ce n c o d i n ga n dd e c o d i n g s o m ei m p r o v e d s c h e m e sh a sb e e np r o p o s e di ne a c hm o d u l e t h es t r u c t u r eo fs h i f t r e g i s t e ri nt h e e n c o d e rd e s i g ni s i m p r o v e d ，a n dt h em u l t i p l i c a t i o n o fm a t r i xh a sb e e n s i m p l i f i e d a l s ot h es e m i p a r a l l e ld e c o d i n ga r c h i t e c t u r eo ft h el d p cd e c o d e r h a sb e e ns t u d i e d i nt h ed e s i g n t h e “t o p - d o w n a n d “f r o mb o t t o mt ot o p m e t h o d s h a v eb e e nu s e ds y n t h e t i c a l l y l d p ce n c o d e ra n dd e c o d e rh a v e b e e nm a d e b e t t e rf l e x i b i l i t yb yd e v i d e du pt h ef u n c t i o nm o d u l e ，s e tu pt h es y s t e m a t i c p a r a m e t e rr e a s o n a b l y ，a n db y t r a n s f o r e dt h e p a r a m e t e r s b e t w e e nt h e m o d u l e s f i n a l l ye n c o d e rw a si m p l e m e n t e di nx i l l i n xv e r t e x l iv 6 0 0 0b yu s i n g v e r i l o gl a n g u a g e k e yw o r d s ：q u a s i c y c l i cl d p c ，m i n - s u ma l g o r i t h m ，e n c o d e r ，d e c o d e r 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庆 邮电太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者躲弘签字眺矽年石月f 日 学位论文版权使用授权书 本学位论文作者完全了解重废蛆虫盔堂有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权重废邮电太堂可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位擞作者躲红 签字日期：如0 7 年6 月r 日 导师躲垆叙 签字e t 期：。乡年月石e t 签字期：删年6 月a 9 重庆邮电大学硕士论文 第一章绪论 第一章绪论 通信的目标是实现消息从信源到信宿的可靠传输。消息包括语音、图像、视 频、数据等多种类型，在数字通信系统中，所有不同类型的消息都被转换成比特 流的形式。信道可以是无线电链路，也可以是电话线、光纤、电缆等传输介质。 在这些例子中，消息是从一个地方传输到另外一个地方，也就是我们通常意义上 的通信。除此之外，有时还需要将消息从一个时间转移到另外一个时间，即所谓 的存储问题，其典型的例子是磁记录系统。信宿通常在给定信道输出的情况下， 简单而可靠地再现信源端发送的消息。 1 1 数字通信及信道编码 通信系统的基本目的在于将信息由信源高效、可靠、有时还需安全地传送到 信宿。有扰通信信道中的噪声会不可避免地对传输信息产生不同程度的干扰，从 而可能降低通信可靠性。所以通信系统设计的核心问题就是在存在随机噪声的信 道中如何克服干扰，减小信息传输的差错，同时又不降低信息传输的效率，即如 何解决系统的有效性与可靠性之间的矛盾。一般地，通信系统的可靠性用误比特 率( b e r ) 来衡量，其有效性则用信息传输速率r 比特，信道符号来衡量。早期的入 们普遍认为【l 】【3 j ：通信系统的可靠性与有效性之间是一对不可调和的矛盾，一方的改 善总是以牺牲另一方为代价，并指出当功率受限时，在有扰通信信道上实现任意 小错误概率的信息传输的唯一途径就是把信息传输速率降低至零。s h a n n o n 的信息 和编码理论的奠基性论文“通信的数学理论”于1 9 4 8 年发表之后f 2 l ，改变了这一观 点。他首次阐明了在有扰信道上实现可靠通信的方法，指出有效而可靠地信息传 输的途径就是通过编码。根据s h a n n o n 的信息理论，数字通信系统的基本组成结 构如图1 1 所示。 s h a n n o n 的信息理论从通信系统的整体最佳化来研究信息的传输和处理。比特 是一种通用的信息表示形式，它本身并不依赖于信源或信道特征。这就允许我们 重庆邮电大学硕士论文 第一章绪论 分别设计图1 1 所示的两个阶段的信息处理，即信源编码和信道编码。s h a n n o n 不 失最佳性地证明了这种分离性。 s h a n n o n 的编码定理仅仅是一个存在性定理，它只告诉我们存在信息传输率 无限接近信道容量的好码，并没有说明如何构造这样的码，但定理却为寻找这样 的码指明了方向。也正是在此定理的指引下，经过几代人的不懈努力，已经发现 可许多性能优良的码及相应的译码方法，且所需的信噪比越来越接近s h a n n o n 限，使得信道编码理论和技术研究取得了一连串辉煌成功。 从信道编码定理可知，随着分组码的码长或卷积码的约束长度的增加，系统 可以获得更好的性能，而且译码的最优算法是最大似然译码算法。但是最大似然 译码算法的复杂性随码长或编码的约束长度的增加呈指数形式增加，因而，导致 最大似然译码算法在物理上成为不可实现的。因此我们研究纠错编码，使其在保 持一定的信息传输效率条件下，通过编译码来降低误码率，实现可靠通信，并且 译码器要尽可能的简单。 信道编码中用到的码类可以按很多种方法来分，而且各类别又有交叉，因此， 用图1 2 来了解它们之间的关系。 图1 2 纠错码的分类 在过去的5 0 多年里，各国专家对信道纠错编码进行了深入的研究，得到了许 多性能良好的纠错码。在分组码方面，最重要的一类码就是b c h 码，而由b c h 码演化而来的扩展b c h 码、缩短b c h 码、r s 码等，其中r s 码大量应用于如 n a s a 深空通信标准、c d 播放器及c d p d ( c e l l u l a rd i g i t a lp a c k e td a t a ) 标准等中。 如今，在通信领域中有两种纠错码尤其让人瞩目，一种是t u r b o 码，另一种是 l d p c 码，这两种码的出现，是信道编码理论在通信领域中一次大的飞跃。t u r b o 码是由法国的c b c r r o u 等人在卷积码和级联码的基础上，于1 9 9 3 年提出来的一 种新的码型，它的提出标志着信道编码理论进入一个新的阶段【4 】ot u r b o 码又称为 并行级联卷积码，它巧妙地将卷积码和随机交织器结合在一起，有效地实现了随 机型编译码的思想，并通过交织器实现了由短码构造长码的方法，在性能方面也 达到了接近s h a n n o n 理论极限的性能。 l d p c 码是一类线性纠错码，是著名学者r gg a l l a g e r 于1 9 6 2 年就提出的一 6 重庆邮电大学硕士论文 第一章绪论 种低密度奇偶校验码【5 】，通常称为g a l l a g e r 码。这种编码由于校验矩阵的稀疏性， 使得译码的复杂度只与码长成线性关系，当码长较长时，仍然可以进行有效的译 码。虽然l d p c 码很早就被提出，但是由于当时计算机水平不够，硬件实现困难， 导致l d p c 码曾一度被认为是一种不实用码，很长的一段时问内被人们所忽视。 m a c k e y 于1 9 9 9 年证明了性能优异的l d p c 码是存在的，并给出了一些构造l d p c 码的方法【6 】之后，人们对l d p c 码的研究日益深入，涌现出各种构造方法。1 9 9 8 年以前的研究主要集中在如何构造正则的或者是近似正则的二分图，在1 9 9 8 年以 后，l u b y 等人推广了g a l l a g e r 码，提出了可以改善l d p c 码性能的非正则l d p c 码i v 。2 0 0 1 年以后，l d p c 码与通信领域的其它先进技术相结合成为了一个热门话 题。 b e nl u 等人提出了基于l d p c 码的空时编码o f d m 系统【8 】 该系统结合了 空间分集技术、选择性衰落分集技术，以较低的计算复杂度达到了较高的系统性 能。 1 2l d p c 码研究的发展动态 l d p c 码自1 9 9 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 码时必须避免较短闭合环路的出现。现有的构造方法主要有两 种：一种是进行类似构造随机码那样的大范围搜索。搜索方法是根据r i c h a r d s o n 等人提供的局部优化和全局优化搜索方法【9 l ，它们的搜索量相当大，需要借助计算 机完成，更完善有效的搜索算法有待迸一步的研究；另一种l d p c 码设计方法是 利用一些已有的数学结论进行构造，主要有组合构造法【埘、有限几何构造法1 1 l 】、 群论构造法【1 2 1 和图论构造法【1 3 】。这些方法可以克服短循环的产生，具有确定的结 构，生成的l d p c 码是循环码或准循环码，可以实现线性时间编码和简单译码， 而且可以设计g i r t h 较大的码，纠错性能达到随机校验矩阵生成的码。另一方面， 当m a c k a y 、l u b y 把l d p c 码的概念推广到非规则l d p c 码1 1 4 1 1 5 j 时，发现非规则 l d p c 码的性能不仅优于规则l d p c 码，甚至还优于t u r b o 码的性能，是目前己知 的最接近香农限的码1 1 6 1 。如果考虑u ) p c 码在非g f ( 2 1 上的构造，也就是对信息 的编码不再仅限于0 1 ，而是在有着多个元素的有限域上编码，如g f ( 4 ) ，g f ( 8 ) 等。m a c k a y 和d a v e y 等在此方向作了很多尝试和探索【1 7 1 ，结果非常令人鼓舞。 7 重庆邮电大学硕士论文第一章绪论 精心的构造多元域上的校验矩阵，可以使性能有很大的提高。针对这一领域的研 究方兴未艾，拥有广阔的前景。 二、译码算法的改进 g a l l a g e r 曾经提出了两种译码算法：一种是硬判决译码，另一种是概率译码。 而后，人们提出了置信传播算法，或称为消息传递方法( b p 算法) 、和积算法( s p 算法) ，这种算法的译码复杂度是比较低的，而且是可实现的。硬判决算法虽然性 能比b p 算法差，但译码复杂度很低，十分适合在光纤通信等信道条件较好的系 统中应用。后来，人们又为了简化计算，降低译码复杂度，又提出了基于b p 算法 的最小和算法 1 8 】和修正最小和算法，在硬件实现时只涉及到加法和比较运算，省 掉了查表运算，从而大大降低了硬件实现的复杂度。另一方面，l d p c 码在非高斯 的低质量信道，如瑞利衰落信道【1 9 】、部分响应信道1 2 0 l 、和i s i 信道【2 1 】等，其译码 算法的性能的研究还需要不断在深入。 三、l d p c 码与其它通信技术的结合 这些技术包括l d p c 码与调制技术( 如q a m ，t c m ) 的结合、l d p c 码与均衡技 术的结合( l d p c 码均衡1 、l d p c 码编码与调制的结合i 冽、l d p c 码译码与接收检 测的结合等等。l d p c 码与o f d m 系统结合【2 3 】、差分检测技术相结合，具有较高 的频率利用率，可有效地抑制短波信道中多径时延、频率选择性衰落、人为干扰 与噪声带来的不利影响。 四、l d p c 码的应用 尽管l d p c 码在d v b s 2 系统和d m b t h 等各项标准中有成熟应用，而且也 被接收到1 0 g b p s 以太网标准“1 0 g b a s e r 的草案中，但是从l d p c 码的理论解释、 关键技术改进到在相关领域应用的具体化仍然有很多研究需要做。这些领域包括 l d p c 码在无线通信领域、d s l a d s l 领域、深空通信领域、传输图像系统、数 字水印系统及磁记录介质中的应用，特别是在第四代移动通信的应用等等。 五、l d p c 码编译码器的硬件实现 l d p c 码基于可信度传播的译码算法本质上是并行算法，它用t a n n e r 图表示， 在变量节点和校验节点之间传递置信消息，非常容易实现以这两个节点为单元进 行并行实现，可以达到很高的译码速度。a n d r e w j b l a n k s b y 和c h r i s j h o w l a n d 2 4 i 在2 0 0 2 年就采用全并行结构实现了码长为1 0 2 4 码率为1 2 、译码速 率达到1g b i t s 的l d p c 译码器，译码器的时钟频率为6 4 m h z 。正如论文所说， 尽管译码速度很快，但是是以巨大的硬件资源消耗为代价的。而m a r i a nk 2 s l 提出半并行结构在译码器硬件实现中的资源消耗和吞吐量之间找到折中。将变量 节点和校验节点分成几组，每组之内并行实现，每组之外进行串行实现。 而l d p c 码编码器的实现相对译码器就要复杂得多。l d p c 码所面临的一个 8 重庆邮电大学硕士论文 第一章绪论 主要问题是其较高的编码复杂度和编码延时。如果采用普通的编码方式，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 在文献【2 6 l 中给出了一种利用校验矩阵的稀疏性对校验矩阵进行一定 的预处理后，通过行列的置换将码的校验矩阵变换成下三角或近似下三角形式， 进行线性编码的有效算法，在很大程度上减轻了随机构造的l d p c 码在编码上的 巨大运算量需求和存储量需求。s l i n 等在m 中提出一种具有循环码特性的l d p c 码，它同样具有稀疏的校验矩阵，编码可以通过线性移位反馈寄存器来完成，实 现了具有线性复杂度和线性延时的编码。在这些基础上，z h i y o n gh e 和p a u l f o r t i e r t 2 8 】提出一类低编码复杂度的准循环码，它的校验矩阵具有下三角形式和双对 角线形式，这类码具有很低的编码复杂度，较高的编码速度。 尽管工业界也已经有l d p c 编译码芯片问世，如f l a f i o n 公司，a l i a 公司、 d i g i t a lf o u n t a i n 公司，但从其编译码器的性能来看，在硬件设计实现方面还有可以 改进的地方。 1 3 本论文的研究任务和内容 本论文主要对l d p c 码构造方式、编译码算法和编码器结构进行了详细分析， 并根据分析结果选出硬件实现方案，用f p g a 进行设计并实现。后面各章的具体 内容安排如下： 第二章介绍了l d p c 码的基础知识。先系统地介绍了l p d c 码的定义和t a n n e r 图表示以及l d p c 码构造方法，重点在准循环l p d 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 码的译码器的硬件设计。采用 半并行结构，最小和译码算法，对l d p c 译码器的硬件结构进行了研究。 第五章主要是l d p c 码的编码器的硬件实现，先介绍包括开发流程，开发工 具，所选f p g a 芯片参数等等，而后采用上章所提出的新结构的l d c p 码编码器是 采用v e f i l o g 语言，用x i l i n xi s e 6 x 作为开发工具，并在x i l i n x 公司的v i r t e xx c v 3 0 0 成功实现相应功能。 最后对全文进行了总结。 9 重庆邮电大学硕士论文第二章l d p c 码简介 第二章l d p c 码简介 弗一旱 w 引刮7 l 2 1l d p c 码的定义和t a n n e r 图表示 简单的说，e d p c 码是一种线性分组码，具有稀疏校验矩阵的纠错码，其定义 通常有两种方式：一种是用校验矩阵h 来定义，另一种是用t a n n e r 图( 也叫二分图) 来定义。首先我们来介绍一下第一种定义方法。 2 1 1l d p c 码的定义 一个码长为n 、信息位个数为k 的线性分组码可以由一个生成矩阵g 。，来定 义，信息序列墨。通过g 被映射到码字c s g 。线性分组码也可以由一个校验矩 阵h 似t h 。来等效描述，所有码字均满足c h 7 0 。校验矩阵的每一行表示一个校 验约束c i ，其中所有非零元素对应的码元变量v 。构成一个校验集，用一个校验方程 表示；校验矩阵的每- - n 表示一个码元变量参与的校验约束，当列元素不为零时， 表示该码元变量参与了该行的校验约束。码元变量与校验方程之间的关系称为结 构。下面的( 21 ) 式是一个5 x 1 0 的校验矩阵及其对应的校验方程，其中码字 c 一“，c 2 ，c 3 ，c 4 ，c 5 ，c 6 ，c 7 ，c 8 ，c 9 ，c 1 0 ) c ，h c 。一0 h 一 1111o 0 0 o 0 0 10 o o1 11o o o 010 o1o 0110 o o10 01o101 0 0 010 01o11 巧手吩+ 吩+ 埒1 0 - 弓 h + 屹+ + 屿0 c 2 也+ 坞+ + v 9 1 0 一c 3 ( 2 1 ) b + k + + h o - 0 - c 4 v 4 + b + b + u o 一0 - c 5 u ) p c 码是一种线性分组码，得名于其校验矩阵的稀疏性，即校验矩阵中只有 数量很少的元素为1 ，大部分都是0 。g a l l a g e r 最早给出了正则l d p c 码的定义， 具体来讲一个正则l d p c 码( n ， ，p ) 的校验矩阵h 满足下面三个条件： ( 1 ) 、h 的每行有p 个1 ； ( 2 ) 、h 的每列有a 个1 ，| ；l 3 ； ( 3 ) 、与码长和h 矩阵的行数相比，p 和a 都很小。 矩阵h 的每列各自包含a 个“1 ”，即列重，表示每个码元变量受到相同数目的 校验约束，；每行也各自包含p 个1 ，即行重，表示每个校验方程对相同数目的码 元变量进行校验约束：由于p 和a 都很小，校验矩阵h 具有很低的“密度”，因此由 校验矩阵h 所确定的码称为l d p c 码。g a l l a g e r 证明了当a 大于等于3 时，这类码 具有很好的汉明距离特性【5 l 【2 9 1 。 1 0 重庆邮电大学硕士论文 第二章l d p c 码简介 正则l d p c 码通常用0 ，a ，i d ) 来表示，其中n 为码长，a 和p 的含义不变。如 果校验矩阵h 是满秩的，则m = ，l k ，码率为r = f 以一m ) n = 1 - m n 。有时矩 阵h 的行不是线性无关的，此时h 的秩小于m ，k ，即m 甩一k ，码率r 1 一i n n 。 当校验矩阵h 各列( 行) 中“1 ”的个数不全相同时，就得到了非正则l d p c 码。 非正则l d p c 码通常用度序列分布函数来表示，我们会在给出l d p c 码的t a n n e r 图描述之后具体介绍非正则l d p c 码的度序列表示。 2 1 2l o p c 码t a n n e r 图定义 任何一种线形分组码，t a n n e r 在【删中提出了一种简单的表示形式：二分图 ( t a n n e r 图) 。设一个( n ，a ，p ) 正则l d p c 码c 具有校验矩阵日a 魄，) 胂。，列重为a ， 行重为p ，则其相应的t a n n e r 图模型可以表示为一个二分图。其中码字向量 ，= “，y 2 ，v n ) 表示为一组变量节点( v a r i a b l en o d e ) 饥，f = 1 2 ，l ，分别对应于 校验矩阵的各列，而校验约束则表示为一组校验节点( c h e c kn o d e ) c f ，j = 1 ，2 ，m 对应于校验矩阵的各行。仅当噍，= 1 时，变量节点v i 与校验节点 c ，之间有一条边相连，节点v i 与c ，之间互称邻接节点，其间的连接边称为两个节 点的邻接边。对于( ，l ，a ，p ) 正则l d p c 码，每个变量节点与a 个校验节点相连，称 该变量节点的度为a ；每个校验节点与p 个变量节点相连，称该校验节点的度为 p ，度表示与节点相连的边的数目。校验矩阵的行重和列重与节点的度一致，t a n n e r 图与校验矩阵也是一一对应得。图2 1 给出了式( 2 1 ) 所示的校验矩阵对应的t a n n e r 图表示，其中有1 0 个变量节点和5 个校验节点，每个变量节点的度是2 ，每个校 验节点的度是4 。 c 1c 2c 3 c 4c s v iv 2v 3 v 4v 5v 6v 7v sv 9v 1 0 校验节点 变量节点 图2 1 校验矩阵的t a n n e r 二分图 在t a n n e r 图上从某个节点出发沿着边，又回到此节点称之为一循环，所经过 的边的个数称之为循环长度，其中最短的循环的长度称为环。同样可以直接从校 验矩阵上描述循环的概念。如果校验矩阵的两行( 列) 同时有两个非零元素处于相同 的行( 列) ，构成一个长度为4 的闭合路径，称为循环，如式( 2 2 ) 中日，所示。循环 中非零元素的个数就是循环的长度。吼的循环长度是4 ，致的循环长度是6 。因 重庆邮电大学硕士论文第二章l d p c 码简介 此，如果用垂直和水平的箭头线能够把校验矩阵中的若干个非零元素连接起来形 成闭合路径，且垂直线不同列、水平线不同行，就可以形成循环。 ( 2 2 ) 当t a n n e r 图没有循环时，b p 译码在有限迭代后可以实现错误概率最小时的最 佳译码p ”，但是b e r 性能差。而有环图的b p 译码是次最佳的。图的环表明了节 点传出的消息又回到它本身所需要的最小迭代次数，而t a n n e r 图中的短循环使译 码不充分，使节点之间传递的外部消息的独立性减小，降低抗干扰能力。特别是 环为4 的循环，使节点的消息经过两次迭代就传回给本身。如果消息是错误的， 会产生错误传播，导致译码速度减慢甚至无法正确译码。因此，在构造校验矩阵 时，要消除矩阵中环为4 的循环。也就是要求校验矩阵的任何两行( 列) 的相同位置 处的非零元素最多是1 个。 2 1 3 正则l d p c 码和非正则l d p c 码 前面我们己经了解到，l d p c 码可以用校验矩阵和二分图来表示，我们根据校 验矩阵h 中各列1 的个数是否相同，把l d p c 码分为正则码和非正则码。在介绍 正则码和非正则码之前，我们首先来了解一下行重和列重的定义。所谓的行重就 是校验矩阵中每行非零元素的个数，即就是校验节点的度数，用二分图来描述一 下的话，是指与某个校验节点相连的边数；同理，列重是指校验矩阵中每列“1 ”的 个数，即变量节点的度数，在二分图中，就是指于某个变量节点相连的边数。如 果一个码的校验矩阵每一行中非零元素的个数是相同的，我们就称这种码为正则 l d p c 码，且用( 珂，a ，p ) 来表示该码字，其中，n 为码长，a 为每列非零元素的个 数，p 为每行非零元素的个数。 对于非正则l d p c 码，相应的t a n n e r 图中各变量节点或校验节点的度并不相 同，通常用序列 1 ，屯， 和 所，p ：，p 办) 来表示其中边的度分布，其中t 表 示与度为j 的变量节点相连的边占总边数的比率，n 表示与度为i 的校验节点相连 的边占总边数的比率，西和d ，分别表示变量节点和校验节点的最大度数。 显然：如一1 ，及d 问rn ，1 ， 即部分之和等于全部。这里之所以用边的度分布，而不用节点的度分布来描述 l d p c 码是因为l d p c 码的译码采用的是基于置信传播( b e l i e fp r o p a g a t i o n ) 的软输 1 l 1 _ l l l j _ 1 _ ； 重庆邮电大学硕士论文第二章l d p c 码简介 出迭代译码算法( s o f to u t p u ti t e r a t i v ed e c o d i n ga l g o r i t h m s ) ，如和积译码算法 ( s u m - p r o d u c ta l g o r i t h m ) ，在译码过程中，信息的传递是在边上进行的，采用边的 分布来描述l d p c 码有助于分析其在给定译码算法下的实际性能和理论性能的上 下界。 边的度分布序列可以用多项式来表示，即； 西 a ) 一艺和卜1 ； ( 2 3 ) d ， p ) - 肛x “ ( 2 4 ) 西d ， 其中a ( 1 ) 。艺- - 1 ，p o ) 一艺n 一1 。 这里d ，和d ，分别是变量节点和校验节点的最大度数，a ，和n 分别表示与度数 为j 的变量节点和与度数为i 的校验节点相连的边数在总边数中所占的比例。 2 2l d p c 码的构造方法 众所周知，一个l d p c 码的好坏完全由它的校验矩阵来确定，也就是说校验 矩阵的结构对于码的性能有着决定性作用，所以我们有必要先对码的构造作一个 了解。u ) p c 码是用一个稀疏校验矩阵来定义的，因此l d p c 码的构造方法也就是 校验矩阵h 的构造。它不仅决定了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 构造的校验矩阵都是随机生成的，虽 然纠错性能好，但是由于校验矩阵的随机性，无法实现简单编码，译码时校验矩 阵的存储复杂度高，不利于实现。而结构化校验矩阵一般可以通过代数几何、组 合构造【1 0 , 1 1 , 1 2 , 1 3 】等方式生成，可以克服短循环的产生，具有确定的结构，生成的 l d p c 码是循环码或准循环码，可以实现线性时间编码和简单译码，而且可以设计 g i r t h 较大的码，纠错性能达到随机校验矩阵生成的码。本节就分别介绍两种构造 法的代表g a l l a g e r 构造法和准循环l d p c 码。 2 2 1g a li a g e r 的构造法 1 9 6 2 年，g a l l a g e r 在文献1 5 】中提出了一种构造，a ，p ) 正则l d p c 码的方法， 我们把这种方法构造出来的l d p c 码称为正则码又称为g a l l a g e r 码。该方法的具 体思想是：首先构造一个每列只有一个i ，每行有p 个i 的子矩阵凰，然后对 r 0 进行似一1 ) 次随机的列置换，分别得到( a 一1 ) 个子矩阵，利用这a 个子矩阵得到校 重庆邮电大学硕士论文第二章l d p c 码简介 验矩阵h ，这样得到的校验矩阵码长为n ，行重为p ，列重为l ，其结构如下所示 ( 2 5 ) 其中，玎为矩阵h o 的列置换。我们给出一个( 2 0 ，3 ，4 ) l d p c 码的矩阵形式，如图2 2 ， 从矩阵的结构我们可以更清楚地理解g a u a g e r 的构造方法a 图2 2g a l l a g e r 构造的( 2 0 ，3 ，4 ) l d p c 码的校验矩阵 2 2 3 准循环l d p c 码 准循环l d p c 码是一类结构化的的l d p c 码的子码，它比其他的码有很强的 编码优势。设计好的准循环l d p c 码和计算机随机产生的i x ) p c 码，不管是正则 l d p c 码还是非正则l d p c 码在各方面都具有同样好的比特纠错性能，块纠错性 能，差错地板性能以及译码迭代收敛率特性【3 2 】【3 3 l 。准循环l d p c 由同样大小的稀 疏的循环行列式排列成的校验矩阵定义【3 4 1 。其校验矩阵可表示为： 凹- 乩 h 2 1 ： h h h 1 , 2 h 2 ，2 ： h j 。2 日，是一个基于o f ( 2 ) 的q x q 的循环子矩阵，可以零矩阵或是单位矩阵。 日；，l lj ( c ；，) ，其中1 ，j ，1 f 工，j ，是正整数，日f ，的每一行都是上面一 行的循环移位，第一行是最后一行的循环移位，其中c ，是移位因子，1 c ，5 目 表示h ；，子矩阵的行相对于单位子矩阵向右移位的数量。 由于其结构的特殊性，准循环l d p c 码只要有一个小环，就至少有q 个同样大 小的环，小环对码的性能影响很大，因此构造时要避免小环的存在。准循环l d p c 码的环的分布只与c ；，的取值有关，因此利用它来对环进行的分析。 1 4 j p 风；艘 正 石 - h 毗如；肌 重庆邮电大学硕士论文第二章l d p c 码简介 将校验矩阵的各个小矩阵的循环右移位数列成一个矩阵为 c c l j c l , 2 o l 工一j c l ， c 2 , 1c 2 2 c 2 上j c 2 正 c j lc j 2 c j l d c jl ( 2 7 ) 如图2 3 ，我们可以简要而清楚地看到移位因子与环的关系。在环4 的图中， 设移位因子差为c l j ：- q 。一c 1 ，：- 1 0 - 1 ，沿着环的方向，垂直移位因子差之 和为：，a c a q 加：，：+ c 2 j 吨- 一一3 + 3 - 0 ；而水平移位因子差之和 。a c - a c u 啦+ c l ，：叫一l + ( 一1 ) - 0 。同理，在环6 的图中，也可以得到类似 的结论。 i 二) 圆圈中的数字代表垂直方向的移位值差 口方框中的数字代表水平方向的移位值差 图2 3 含4 环和含6 环的l d p c 码的移位值 因此为避免h 矩阵中有复的环，我们可以只需要判断垂直方向或水平方向的 移位因子差之和就可以了。在文章f 3 5 有详细的充分必要条件的论证，在这里我们 把结论列出来，如下： 罗( a c ) _ k , q ，k o ，1 ，2 ，f ( 2 8 ) 7 对于相同码长和码率的消去4 环后随机构造的准循环l d p c 码的性能基本相 同。消除4 环方法也很简单，只需保证循环移位矩阵中任意画一个矩形的两个对 角线元素和不相等( 模q ) ，见图2 3 。因此本文后面采用的码就是通过消除4 环后随 机构造再择优选取的，具体构造准循环l d p c 码的算法如下： 1 初始化：将所有子矩阵循环右移的位数初始化为0 。 2 从第2 行第2 列开始按先列后行的顺序，在1 到q - 1 之间产生随机数，每产 生一个新随机数就与已经产生的所有随机数迸行比较，若有相同的就重新产生一 个该位置的随机数并重新进行比较，直到该随机数与已经产生的所有随机数都不 同为止。 重庆邮电大学硕士论文第二章l d p c 码简介 3 从第2 行开始，让其与后面各行开始逐行检查两行所构成的所有矩形的两个 对角线元素模p 和是否相等( 无需检查第1 列) ，若发现有相等的，返回步骤2 。 2 2 本章小结 本章介绍l d p c 码的校验矩阵定义和t a n n e r 图定义，并介绍正则l d p c 码和 非正则l d p c 码。同时，介绍了l d p c 码的两种常见的构造方法，g a l l a g e r 构造法 和准循环l d p c 码以及消除4 环的算法。 1 6 重庆邮电大学硕士论文第三章l d p c 码编码器设计 第三章l d p c 码编码器设计 l d p c 码是一种渐进好码，在长码时其性能甚至超过了t u r b o 码。此外，l d p c 码的译码采用具有线性复杂度的和积算法，译码复杂度大大低于t u r b o 码，其应用 前景广阔。但是其复杂度相对于卷积码等可以即时编码的码来说很大，尤其在码 长很长时，由于必须在接收到所有的信比特后才能够进行编码，这就会给编码带 来一定的时延。因此，降低l d p c 编译码器的硬件实现复杂度也是其的应用的重 要问题。 3 1l d p c 码的确定 2 0 0 4 年4 月i n t e l 公司为i e e e8 0 2 1 6 提交了l d p cf e c 码的编码方案【“， 该码的h 矩阵可以分成两个部分，系统部分的列重是4 ，校验部分是双对角线矩 阵，列重是2 。论文【2 8 魄出的l d p c 码是一种准循环的l d p c 码，也是类似于i n t e l 码，系统部分的列重也是4 ，校验部分采用了下三角和双对角线结构，仿真表现出 非常接近香农( s h a n n o n ) 极限的性能，尤其对高斯信道下的突发错误有很强的纠错 能力，而且比只有双对角线结构的l d p c 码的错误平层要晚，在1 0 9 以下才出现。 本文设计所用的是准循环l d p c 码高速率二进制l d p c 码，采用的是论文 的构造方法。为了便于硬件实现，循环小矩阵的q 值可取1 2 8 和2 5 6 ，其校验矩阵 形式如下： h i 【4 , l 啡】 oo 00 11 ( 2 5 5 ) ii f j ( 4 6 ) j ( 2 4 ) j ( “) j ( 8 5 ) j 0o0 l = i1 0 4 ) i ( 1 0 5 ) i ( 6 9 ) 1 0 0 8 ) 1 ( 6 7 ) ，00 l l