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

西南交通大学硕士生学位论文第1 页 摘要 低密度奇偶校验码( l o w d e n s i t yp a r i t y c h e c k ，l d p c ) 是一种利用非常稀疏 矩阵或者二分图定义的线性分组纠错码。l d p c 码具有逼近香农限的良好性能， 译码复杂度低，具有较低的错误平层。其长码性能甚至优于t u r b o 码，极有可 能被采纳为第四代移动通信系统的纠错编码方案。l d p c 码已经成为纠错编码 领域的热点研究问题。 本文主要研究了l d p c 码的编译码理论及其f p g a 实现技术，主要研究工 作如下： ( 1 ) 在理论研究方面，论文首先分析了几种典型的l d p c 码校验矩阵的 构造方法，包括g a l l a g e r 码、m a c k a y 码、p e g 码、e g 码。然后通过与传统编 码算法的对比探讨了使用准循环校验矩阵的快速编码算法的性能。最后对 l d p c 译码算法进行了深入的研究，着重分析了l d p c 码在不同环境下的译码 性能。 ( 2 ) 论文根据最小和译码算法，得到了选用的q c l d p c 码字的高效译码 量化方案，该方案得到了接近浮点的译码性能。最后，运用v h d l 语言在i s e l 0 1 环境下完成了l d p c 码基于二阶编码算法的编码器和基于最小和算法的译码器 的f p g a 设计。 ( 3 ) 论文通过对译码器结构的改进提高了译码器的性能和效率。首先，实 现了两帧数据同时译码，相对于传统方法，在消耗资源略有增加的条件下使译 码效率提高了一倍；其次，存储器的每个地址空间对应多个节点，使部分并行 结构的并行度更加灵活；最后，通过变量信息和校验信息存储空间的复用，节 省了一半的外部信息存储空间。 关键词：l d p c 编译码；准循环l d p c 码；二阶编码；译码量化；循环移 位寄存器 西南交通大学硕士生学位论文第页 a b s t r a c t l d p c ( l o wd e n s i t yp a r i t yc h e c k ) c o d e si sak i n do fl i n e a rb l o c kc o d e st h a t d e f i n e db yv e r ys p a r s ep a r i t ym a t r i xo rt a n n e rg r a p h l d p cc o d e si sak i n do ft h e n e a rs h a n n o nl i m i te r r o r - c o r r e c t i n gc o d e s ，a n di t sd e c o d i n gc o m p l e x i t ya n de r r o r f l o o ra r el o w f o rl o n gc o d el e n g t h s ，l d p cc o d e sc a ne v e no u t p e r f o r mt u r b o c o d e s ，s oi ti sf a rm o r el i k e l yt ob ea c c e p t e da st h ee r r o r - c o r r e c t i n gs c h e m eo ft h e f o u r t hg e n e r a t i o nm o b i l ec o m m u n i c a t i o n ss t a n d a r d l d p cc o d e si sar e s e a r c h h o t s p o ti nt h ec o d i n gf i e l dc u r r e n t l y t h ee n c o d i n g d e c o d i n gt h e o r ya n df p g ai m p l e m e n t a t i o no fl d p cc o d e sa r e d e e p l ys t u d i e di nt h et h e s i s ，t h em a i nr e s e a r c hw o r k i sa sf o l l o w s ： ( 1 ) w i t hr e g a r dt ot h et h e o r yr e s e a r c h ，s e v e r a lc o n s t r u c t i o nm e t h o d so f p a r i t y - c h e c km a t r i x ，i n c l u d i n gg a l l a g e rc o d e s ，m a c k a yc o d e s ，p e gc o d e sa n de g c o d e sa r ea n a l y z e di nt h i st h e s i sf i r s t l y t h e nt h ep e r f o r m a n c eo ft h ee f f i c i e n t e n c o d i n ga l g o r i t h mu s i n gs p e c i a ls p a r s ep a r i t y c h e c km a t r i xi s e x p l o r e db y c o m p a r i n g i tw i t ht h ec o n v e n t i o n a l e n c o d i n ga l g o r i t h m f i n a l l y , t h ed e c o d i n g a l g o r i t h mi sd e e p l ys t u d i e d ，e m p h a s i z i n go na n a l y z i n gt h ep e r f o r m a n c eo fl d p c c o d e sa td i f f e r e n tc o n d i t i o n s ( 2 ) a ne f f e c t i v ed e c o d i n gq u a n t i z a t i o ns c h e m ef o rt h ea c c e p t e dq c - l d p c c o d ew o r di so b t a i n e db a s e do nt h em i n s u md e c o d i n ga l g o r i t h m i tr e m a i n sg o o d p e r f o r m a n c en e a rt ot h ef l o a t i n gd e c o d i n g f i n a l l y , t h ef p g ad e s i g no ft h ee n c o d e r b a s e do nt h et w o - s t a g ee n c o d i n ga l g o r i t h ma n dt h ed e c o d e rb a s e do nt h em i n - s u m d e c o d i n ga l g o r i t h mi sc o m p l e t e dw i t hv h d ll a n g u a g eo ni s e l 0 1p l a t f o r m ( 3 ) t h ed e c o d e ra r c h i t e c t u r ei si m p r o v e dt oi n c r e a s eo fe f f i c i e n c ya n dr e d u c e t h ec o s to fh a r d w a r er e s o u r c e si nt h i s t h e s i s f i r s t ，t h ed e c o d i n ge f f i c i e n c yi s i m p r o v e d t w ot i m e st h a n t h eo l dd e c o d e r b yd e c o d i n g t w of r a m e s s i m u l t a n e o u s l y ，b u tt h e c o s ti st h es l i g h t l ym o r eh a r d w a r er e s o u r c e s s e c o n d ，t h e n u m b e ro fn o d e se x e c u t e di np a r a l l e lc a nb es e l e c t e dm o r ef r e e l yb ys t o r i n gas e to f n o d a ld a t ai nas e p a r a t ea d d r e s ss p a c e ；t h i r d ，t h ee x t r i n s i cm e s s a g em e m o r ys p a c e c a nb er e d u c e d b y h a l f b ym u l t i p l e x i n g v a r i a b l e - t o - c h e c k m e s s a g e a n d c h e c k - t o - v a r i a b l em e s s a g ei n t ot h es a m em e m o r ys p a c e k e yw o r d s ：l d p ce n c o d i n g a n d d e c o d i n g ；q u a s i - c y c l i c ( o c ) l d p cc o d e s ； t w o - s t a g ee n c o d i n g ；d e c o d i n gq u a n t i z a t i o n ；c y c l i cs h i f t - r e g i s t e r 西南交通大学四南父迥大罕 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权西南交通大学可以将本论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密影使用本授权书。 ( 请在以上方框内打“4 ) 靴论文作者签名：嘲无雄指导柳签各，；宕征 日期： 乒鲈7 占中 日期：砂内罗么乒 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所 得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体 已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： 本论文在研究l d p c 码编译码理论的基础上，完成了l d p c 码编译码器的 设计。论文设计的基于两阶编码算法的编码器简单易实现，编码效率高。论文 通过对译码器结构的改进提高了译码器的性能和效率。首先，实现了两帧数据 同时译码，相对于传统方法，在消耗资源略有增加的条件下使译码效率提高了 一倍：其次，存储器的每个地址空间对应多个节点，使部分并行结构的并行度 更加灵活；最后，通过变量信息和校验信息存储空间的复用，节省了一半的外 部信息存储空间。通过以上改进，使论文的编译码器具有更高的实用价值和更 广的适用范围。 学位论文作者签名：勿杉荏 日期： 参，。7 占斗 西南交通大学硕士生学位论文第1 页 第1 章绪论 自1 9 9 3 年t u r b o 码出现以来，信道编码技术进入了一个崭新的时代，它标 志着构造性能接近s h a n n o n 限的好码的开始。1 9 9 6 年，研究人员发现：g m l a g e r 在1 9 6 2 年提出的低密度奇偶校验码【l 捌( l o w d e n s i t yp a r i t y c h e c kc o d e s ) 也是 一种接近接近s h a n n o n 限的好码，而且具有更低的线性译码复杂度。l d p c 码 是继t u r b o 码之后在纠错编码领域的又一重大发现，l d p c 码是目前信息领域 和通信界最热门的研究之一，也是现代编码理论的典型代表。 1 1 数字通信系统 通信就是信源和信宿之间信息的传输与交换，评价一个通信系统性能优劣 的主要指标是信息传输的有效性和可靠性，即要求一个通信系统传输消息必须 快速与可靠，但在数字通信系统中快速与可靠往往是一对矛盾。若要求快速， 则必然使得每个数据码元所占的时间缩短、波形变窄、能量减少，从而在传输 过程中受到干扰后产生错误的可能性增加，传输消息的可靠性降低。若要求可 靠，必然会付出时间和其他资源( 如设备复杂度) 的代价，使得传输消息的速率 变慢。因此，如何解决可靠性和速度这一对矛盾，是正确设计一个通信系统关 键问题之一。各种通信理论和技术( 包括信道编码) 也正是在解决这对矛盾中不 断发展起来的p j 。 1 2 信道纠错编码技术的发展 香农( s h a n n o n ) 1 9 4 8 年在他的开创性论文“通信的数学理论州4 j 中提出著 名的有扰信道编码定理，为纠错编码的发展奠定了坚实的理论基础。半个多世 纪以来，编码研究者们一直致力于寻找误码性能上尽可能地接近s h a n n o n 极限， 而复杂度又较低的便于实际应用的信道纠错编码方案。其发展过程大致分以下 几个阶段。 线性分组码是发展最早的一类纠错码。它是分组码中最重要的一类，是讨 论各类码的基础。线性分组码以代数中的群、域、环理论和有关的几何理论为 数学基础，利用各种代数几何方法设计好的纠错码，如汉明码、b c h 码、r s 码( 多进制的b c h 码) 、g o l a y 码、g o p p a ( 有理分式码) 码等。特别是b c h 码结 西南交通大学硕士生学位论文第2 页 构简单、编译码设备都不太复杂，在数字通信系统中应用极为广泛。 卷积码是不同于分组码的另一类重要的信道编码，于1 9 5 5 年由爱里斯提 出。卷积码在编码过程中引入了寄存器，使每个码组中本组的校验码元不仅与 本组的信息码元相关，还与其他各组信息码元相关；同样在卷积码的译码过程 中不仅从当前接收的到的码组中提取译码信息，而且还从以前接收到的各个码 组中提取信息，充分的利用了各个码组之间的相关性，通常认为在相同复杂度 的条件下卷积码可以获得比分组码更高的编码增益。随着各种卷积码的译码方 法，尤其是v i t e r b i 译码算法的出现i 引，卷积码逐渐得以广泛应用。 纠错码的另一个重大发展是网格编码调制技术( t c m ，t r e l l i sc o d e d m o d u l a t i o n ) 的提出。1 9 8 2 年u n g e r b o e c k 提出将卷积码同调制相结合的t c m 技 术1 6 1 ，在a w g n 信道下t c m 为最佳抗干扰方案，这种方案是在不扩频特性下 将纠错码与调制技术相结合，通过对信号空间不同分配，来最大化星座点间的 最小欧式距离，从而达到提高抗干扰能力的目的。这一成果对带宽受限中的编 码调制技术的发展具有划时代的意义，在现代通信系统中获得了广泛的应用。 到了上个世纪九十年代，纠错码技术又出现了革命性的发展。法国的b e r r o u 等于1 9 9 3 年提出的t u r b o 码一在a w g n 信道下的性能接近了s h a n n o n 限， 这标志着实用的接近s h a n n o n 限的信道编码的开始。在a w g n 信道中，采用 b p s k 调制的1 2 码率的t u r b o 码，用大小为6 5 5 3 5 的随机交织器进行交织和 1 8 次迭代译码的情况下，在信噪比最n 一0 7 d b 时，误码率可以达到1 0 ， t u r b o 码的性能一举超越了截止速率，并且逼近了香农限，这一超乎寻常的优 异性能，立即引起信息与编码理论界的轰动，t u r b o 码被看作是1 9 8 2 年t c m 技术问世以来，纠错码理论与技术上取得的最伟大成就。但t u r b o 码的优异性 能并不是从理论研究中得到的，而是计算机仿真的结果，因此，t u r b o 码的理 论基础还不完善。后来经过不少人的重复性研究与理论分析，发现t u r b o 码的 性能确实是非常优异的。因此，t u r b o 码的发现，标志着信道编码理论与技术 的研究进入了一个崭新的阶段，它结束了长期将信道截止速率作为实际容量限 的历史。 1 3l d p c 码的研究现状和应用前景 随着对t u r b o 码的深入研究，研究人员发现g a l l a g e r 在1 9 6 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 ) 码亦是一种能够逼近香农限，具 有渐进特性的好码。在其博士论文中，g a l l a g e r 提出了正则l d p c 码的构造方 法、编译码算法以及最小汉明距离分析和译码算法的性能分析。但受到当时的 西南交通大学硕士生学位论文第3 页 条件限制，编译码器的硬件实现和精确的性能仿真都无法实现，所以，l d p c 码一直没有引起相应的重视。直到1 9 9 6 年，m a c k a y 和n e a l i 剐利用随机构造的 t a n n e r 图研究了l d p c 码的性能，发现当采用和积译码算法时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 码都是规则 码，m g l u b y 等【9 j 将l d p c 码的概念推广到了非规则码，非规贝i l d p c 码的性 能不仅优于规则u ) p c 码，甚至还优于t u r b o 码，是目前己知的最接近香农限的 码，并且非规则码在译码时可以加快收敛速度，提高译码效率。最初的l d p c 码都是根据一定的准则由计算机搜索得到的，虽然性能较好，但结构复杂，不 利于硬件实现，实用价值不高，而y uk o u 和s h ul i n 首次用代数方法有限 几何来构造l d p c 码【l o l ，生成循环或者准循环校验矩阵，此类码字的巨大意义 在于可以实现高效快速编码，便于l d p c 码的硬件实现，对于实际应用有巨大 意义。t j r i c h a r d s o n l l l 】等人，提出了对稀疏校验矩阵的行或者列进行重排，从 而得到具有准下三角阵结构的校验矩阵，利用下三角系数线性方程可以线性时 间求解，适当处理后就可以实现线性时间编码，它的提出为高效l d p c 编码器 的实现提供了一个普遍适用的方法。m g l u b y l l 2 j 等提出的一类基于级联二分 图的l d p c 码，用于可抹( e r a s u r e ) 信道，称为纠删码( e r a s u r ec o d e ) ，不仅能实 现线性时间编码，还能实现线性时间译码，非常适合于实际应用。 纠错码的译码算法是决定编码性能和前途的一个重要因素，尤其是在长码 的条件下，译码算法的复杂度直接决定了编码的应用前途。g a l l a g e r 1 j 在其论文 中曾给出了两种 j ) p c 码的迭代译码算法：硬判决和软判决算法，前者实现简 单，但是性能太差，后者性能虽好但实现太复杂，未能引起广泛关注。1 9 8 1 年 t a n n e r 建立定义在随机双向图上的码的一般研究方法后，人们基于g a l l a g e r 给出 的两种算法提出了消息传递算法( m e s s a g e p a s s i n ga l g o r i t h m ) ，在m p 算法当中， 变量节点和校验节点的消息传递是通过双向图完成的。f r k s c h i s c h a n g 等i l 川 指出：作为一种通用的消息传递算法，和积算法6 u m p r o d u c ta l g o r i t h m ) 口- j 应用 于任何双向图，现行的各种译码算法大多都可由和积算法导出，和积译码算法 不仅性能优异，而且实现相对简单，具有很强的实际意义。s y c h u n g 等1 1 4 j 利用消息分布的高斯近似( 即假设所有消息具有不变的高斯概率密度函数) 简 化了密度演进算法，可在不降低精度前提下快速找s u f - j 限和快速、容易地优化 度分布，有助于理解和积算法译码器性能和优化非正则u ) p c 码，对构造高性 能的l d p c 码有很大帮助。 目前国内对于l d p c 码的研究，主要侧重于实际应用方面。张靖琳等提出 西南交通大学硕士生学位论文第4 页 一种高码率u ) p c 码的译码器的硬件结构优化方法i l 引，通过拆分矩阵，降低校 验节点处理单元和变量节点处理单元复杂度的不平衡，提高了译码器的时钟性 能。钟州等提出了一种基于校验节点度的分类修正最小和译码算法i l 酬，该算法 将最小和译码算法中校验节点输入外信息绝对值的最小值和次小值分类，并根 据该节点的度计算与b p 算法的偏移量，分别选择不同的阈值和修正因子对外信 息进行补偿，该算法复杂度大大低于b p 译码算法。周伟等基于多进制低密度奇 偶校验码译码过程中的振荡现象，提出了一种改进译码方法1 1 7 j ，在每一次译码 迭代过程中，使每个发生振荡的变量节点处输出的信息包含上次信息和当前迭 代后得到的信息，从而减小振荡影响。 伴随着理论研究的成熟，l d p c 码的硬件实现正成为一个研究热点，各种 编译码芯片陆续出现，其中f l a r i o n 技术公司较为成功，开发的l d p c 编译码器 产品称为v e c t o r - l d p c ，用f p g a 实现时，编码器用户数据速率可达1 9 g b i t s ， 译码器用户数据速率可以达到3 8 4 m b i t s ，当采用a s i c 实现时，译码器最高工作 速率可达至u 1 0 g b i t s 。基于l d p c 码的编码方案已经被下一代卫星数字视频广播 标准d v b s 2 采纳。虽然由于l d p c 码出现较晚，与第三代移动通信标准失之交 臂，但极有可能成为第四代移动通信标准中的关键技术。同时，基于l d p c 码 的商用芯片已经上市。可见，l d p c 码由于其优异的性能必将在提升未来通信 系统的性能方面发挥巨大的作用。 ， 虽然l d p c 码的理论研究已经取得了很大成绩，展示了巨大的应用前景， 但要大规模实际应用仍然存在很多障碍，其中，高效的编译码器设计就是亟待 解决的问题，论文将围绕此问题展开。 1 4 论文的主要内容 本文在对l d p c 码的编译码理论深入研究的基础上，完成了l d p c 码的编 译码器设计，论文通过对译码器结构的改进，在消耗资源少量提高的代价下， 换取了译码效率的大幅度提高。各章主要内容安排如下： 第一章主要介绍数字通信系统的基本原理，纠错编码的发展历程，l d p c 码的研究现状和应用前景。 第二章主要介绍l d p c 码的基本原理，主要研究l d p c 码校验矩阵的构造、 编码方法和译码性能。 第三章主要研究最小和译码算法的量化性能。首先介绍了量化的基本原理 和l d p c 码量化研究的背景，通过仿真和理论分析得到了一套基于最小和译码 算法的高效译码量化方案。 西南交通大学硕士生学位论文第5 页 第四章完成l d p c 编码器的设计与f p g a 实现。给出了基于两阶编码算法 的准循环l d p c 码的编码器设计方法。并在i s e 开发工具下采用v h d l 硬件描 述语言完成了l d p c 码编码器的f p g a 设计。 第五章完成l d p c 译码器的设计与f p g a 实现。给出了基于最小和算法的 l d p c 译码器的设计方法，并对译码器结构进行了改进，提高了译码效率。并 在i s e 开发工具下采用v h d l 硬件描述语言完成了l d p c 码译码器的f p g a 设 计。 最后对全文进行总结，针对现有研究的不足，提出了未来进一步研究的方 向。 西南交通大学硕士生学位论文第6 页 第2 章l d p c 码构造及编译码理论研究 第一章介绍t g q 错编码的发展历程和l d p c 码的研究现状，本章将在第一 章的基础上阐述l d p c 码的定义、校验矩阵的构造、l d p c 码的编码方法和 l d p c 码的译码性能。 2 1l d p c 码的定义和表示 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 ) ，校验矩阵中每行的行重和每列的列重分别相等的l d p c 码叫规则l d p c 码，否则叫非规则l d p c 码。l d p c 码是一种线性分组码，一般可以表示为 ( ，k ) ，表示码长，k 表示信息序列长度，对于规则l d p c 码还可以表示为 ( ，形，形) ，它表示此l d p c 码长为，每列有形个1 ，每行有彬个1 ，每一 个l d p c 码可以由其校验矩阵h 唯一定义。式( 2 1 ) 为( 1 2 ，3 4 ) 规则l d p c 码 的校验矩阵，其列重为3 ，行重为4 ，码率r 一1 4 。 h 一 ( 2 1 ) l d p c 码的校验矩阵可用一个二分图表示，图2 1 为( 1 2 ，3 ，4 ) l d p c 码所对 应的二分图。图的下边有1 2 个节点，每个节点表示码字的信息位，称为信息节 点或者变量节点，每个节点表示一个变量信息更新处理集，其节点个数等于码 字的比特位个数，对应于校验矩阵的各列。图的上边有9 个节点，每个节点表 示码字的一个校验信息更新处理集，称为校验节点，代表校验方程，对应于校 验矩阵的各行。与校验矩阵中1 元素对应的两种节点之间存在连接边，比如校 验矩阵中的第1 列，它的第2 、5 、7 行分别为1 ，代表二分图中第一个变量节 0 1 o 0 0 l o 1 o o o 1 0 1 0 o 1 o 0 o 1 1 o 0 0 0 1 0 o 1 o o 1 0 o 1 1 o o o 1 o o 1 0 1 o o 1 o 0 1 o o 1 o o 1 o 0 0 1 o 0 1 o o o 1 1 o o o o 1 o o 1 1 o o 1 o o 0 1 o o o 1 o 1 o 1 o o 0 o 1 o 1 o o 1 o 1 d 0 西南交通大学硕士生学位论文第7 页 点与第2 、5 、7 个校验节点有联系，同样校验矩阵中的第8 行决定了二分图中 第8 个校验节点与第6 、8 、1 1 、1 2 个变量节点有联系。这些连接边代表了l d p c 码译码时外部信息传递的路线，我们将这些边两端的节点称为相邻节点，每个 节点相连的边数称为该节点的度数。在( 1 2 ，3 ，4 ) 规则l d p c 码中，每个信息节 点与3 个校验节点相连，所以每个信息节点的度数为3 ，每个变量节点与4 个 信息节点相连，所以每个变量节点的度数为4 。 图2 - 1 ( 1 2 ，3 ，4 ) 规则l d p c 码的二分图表示 非规则u ) p c 码可以用重量分布多项式来方便的描述。假设最大列重和最 大行重分别是d 芦和d ，则h 的列重分布多项式r ( x ) 可以表示为： d ? “ ，( x ) 一以x 卜1 ( 2 - 2 ) 其中，以是重量为f 的列在总的列数中所占的比例，r 0 ) - 1 。类似的，h 的行 重分布多项式夕o ) 表示为： d ， p ( x ) = p 以 ( 2 - 3 ) 肛是重量为f 的行所占的比例，p 0 ) 一1 。此时码率满足： l f p ( x ) d x ，一1 一 一 ( 2 4 ) f r ( x 皿 西南交通大学硕士生学位论文第8 页 2 2l d p c 码校验矩阵的构造 2 21 g a i l a g e r 构造方法 巩- e b n 0 ( d m 图2 - 2 g a l l a g e - l d p c 码性能仿真图 1 i u 笋i ( 2 - 5 ) 1 丛o l p j g a l l a g c r l 9 6 2 年在其著作中1 2 】，给出了( ， ，p ) 规则l d p c 码的构造方法： 对码长为n 的n ，p ) 规则码，首先将校验矩阵按行水平地划分为几个大小相同 的子矩阵，每个子矩阵的每一列和每一行都只含有一个1 。要构造校验矩阵h ， 首先构造一个基准子矩阵，在基准子矩阵的第f 行上，所有的1 都分布在矩阵 的第o 一1 ) p + 1 n i p 列上，见式( 2 - 5 ) 。假设矾为预先构造的基准子矩阵，令石 为矩阵风的列置换函数，即珥( 巩一1 , 2 ， ) 为风的随机列置换矩阵，那么 矩阵h 可以通过式( 2 6 ) 的方式得到。 学 西南交通大学硕士生学位论文第9 页 h 一 啊( 。) j i r 2 ( h o ) ，r x ( h o ) ( 2 6 ) 上述方法构造的矩阵没有消除4 环，将极大的影响该l d p c 码的纠错性能， 所以在构造的过程中还要进行消除4 环的工作，以提高其纠错性能，图2 - 2 为 其性能仿真图，可见，去除4 环之后性能明显改善。 2 2 2m a c k a y 构造方法 为了避免4 环的存在，m a c k a y 采取的办法就是构造时要保证任意列间在相 同的行“1 的重叠不大于1 。m a c k a y 提出的校验矩阵构造方案如下f 1 8 】： o o 图2 - 3 构造方法a 构造方法a ：这是基本的方法。该方法预先设定每一列的列重为) ，随机构 造矩阵，但使每一行的行重p 大于y 并使各行的行重尽可能相等，并且每两列 之间相同行的对应位置重叠“l ”的个数不大于1 ，即避免了二分图上存在4 环。 图2 3 即为按照此方法构造的一个l d p c ( 3 ，6 ) 码。 o 图2 - 4 构造方法b 构造方法b ：在方法a 的基础上作了一些改动，其主要思想是引入一些列 重为2 的列，减少双向图中短环的数量。具体做法是将一个m 行的校验矩阵分 为两部分，前呒列、m 行为第一部分，剩下的为第二部分。第一部分又分为两 个子矩阵，每一子矩阵为一个粤号的单位阵；第二部分为一个以构造方法a 构造的子阵，如图2 4 所示。 构造方法c ：从a 、b 构造的校验矩阵中删除一些仔细选择的列，使此矩 西南交通大学硕士生学位论文第1 0 页 阵对应因子图上没有小于一定长度的环。 c k a y 构造方法仿真结果见图2 _ 5 ，可见在相同码率下，长码性能明显好 于短码。 毒= _ 二：- _ 。二_ 二= 二二二二； ，o 譬叠冀矗一：一一j 一= 三j 暑 10 2 1 矿 1 矿i =， 广= ；i 两丽一 一i 蓑勰器鞣牛- - - - 一 面 t _ 二蕊，f1 22 3p e g 构造方法 图2 - 5m a c k a y - l d p c 码性能仿真图 p e g ( p r o 掣e s s i v ee d g v g r o w t h ) 算法就是一种可以构造较大围长的双向图 的随机搜索方法，按照n o d eb yn o d e 的方式在校验节点和变量节点之间建立边 的连接，在增加新边时充分考虑避免短环的存在。 对给定的双向图参数，包括变量节点数、校验节点数肼、变量节点度序 列见，、常规p e g 算法总结如下，令第i 个变量节点h ，第，个校验节点c ，： 对于第i 个变量节点：i - 0t o 一1 增加第i 个变量节点的第k 条边：k - 0t o 以一l 其中机表示第i 个变量节点的度数。如果k - 0 ，则边以，c ，) e ，其中砭 是变量节点h 的第一条入射边。c 是在当前图集合瓦u e u u e 中具有最 低度数的校验节点之一。否则，在当前图集合的基础上，将变量节点h 展开成 深度为i 的子图，直到集合蛾的元素数目达到m ，或屁- 庐而霸1 一妒。然后， ( v l ，c ，) - 成，其中是变量节点k 第k 条入射的边，c ，是集合“- 。1 中具有最低 度数的校验节点。 西南交通大学硕士生学位论文第11 页 ，d 牟 嘲；。= 1 0 2 i 一， 1 矿i ! ： 薯薹薯蓠i 蓄蔷磊磊 i pp e g 2 5 “5 1 2h u n c o 帕 f 曩= 薹：! 重l ：量一： 一一 j。 矿卜 一吉卜 e w b i 图2 - 6 p e g - l d p c 码性能仿真图 常规p e g 算法需要对每一个变量节点都展开成树图结构，以n o d eb yn o d e 的次序添加边，这样不但耗费时间和内存资源。而且构造的矩阵也没有规律， 给编译码的硬件实现带来困难。而改进的o c - p e g l d p c 算法【1 卅构造的准循环 校验矩阵是由多个循环子矩阵构成，在构造时首先把变量节点和校验节点分成 多个小组，然后对于每组变量节点，只需对其中第一个变量节点寻找最优边， 最后根据循环矩阵的约束关系，同组其它节点相连的边也随之确定。图2 - 6 是 不同码长的q c - p e g l d p c 的性能仿真图。 2 2 4e g 构造方法 以上构造算法都是基于一定条件随机搜索的，随机构造的l d p c 码码长灵 活，性能较好，尤其是长码，但缺点是元素分布没有规律，不便于硬件实现， 缺乏实际应用价值。所以出现了基于一定数学基础的结构l d p c 码，结构l d p c 码一般具有一定的规律性，便于硬件实现，中短码长时性能较好。这里介绍基 于欧氏有限几何的欧氏有限几何l d p c ( e g l d p c ) 码i l w 。 基于欧氏有限几何构造l d p c 码就是用欧氏有限几何的点和线构造l d p c 码的校验矩阵。其基本原理就是将一个欧氏有限几何中的线作为校验矩阵中的 行，点作为校验矩阵中的列，或者与此相反，用点作为校验矩阵中的行，用线 作为校验矩阵中的列。第一种方法构成的l p d c 码被称为第1 类欧氏有限几何 西南交通大学硕士生学位论文第1 2 页 l d p c 码，第二种方法构成的l d p c 码被称为第1 i 类欧氏有限几何l d p c 码。 由于在有限几何中，任意两条线都有至多一个公共点，所以欧氏有限几何l d p c 码任意两行或两列都最多只有一个公共点，所以欧氏有限几何l d p c 码的校验 矩阵中没有4 环，保证了其纠错性能。图2 - 7 为e g l d p c 码性能仿真图。 10 。 10 1 0 缶1 0 1 0 1 0 矿# 焉! l 1 _ 二。 e b n 0 1 d b ) 图2 - 7 e g l d p c 码性能仿真图 图2 - 8 为上述几种典型的l d p c 码的性能比较，除了e g l d p c 码码字为 ( 2 0 4 4 , 1 0 2 2 ) 步t , ，其它l d p c 码的码字都为( 2 0 4 s 1 0 2 4 ) ，在相同情况下，中短 码长时，结构码性能好于随机码，在长码字时，随机码性能更好。 2 3l d p c 码的编码方法 l d p c 码是一种线性分组码，其基本编码原理和一般的线性分组码没有任 何区别。但是，不同的编码方法在硬件实现的时效性和资源利用效率方面会有 不同的结果，因此，本节将分别阐述几种典型的编码方法。 23 1 传统方法 传统编码算法就是先把校验矩阵转化为生成矩阵，再按照传统线形分组码 的方法进行编码。假设一个辨”校验矩阵日- ( q ，c 2 】，其中岛是一个m 州方 西南交通大学硕士生学位论文第1 3 页 阵，并且在二元域上是可逆的，那么生成矩阵就可以由式( 2 - 7 ) 得n ，易知得到 的生成矩阵是系统形式的。 n c ；名1 c z - ， 1 一- = u r , 2 0 d e 一 22 12 22 32 42 52 62 7282 93 s m d b ( d e ) 图2 - 8 几种l d p c 码性能仿真图 当校验矩阵日的秩小于校验矩阵的行数珊的时候，c 在二元有限域上是不 可逆矩阵，那么这时就要先通过高斯消元法消去矩阵中线性相关的行，得到新 的满秩校验矩阵，再由此校验矩阵编码，新的矩阵编码效率高于原矩阵。高斯 消元求逆过程的复杂度阶数是小i 埘。但是经这样得到的生成矩阵不是稀疏矩 阵，因此在编码时矩阵乘法的阶数是口加2 ) ，另外，由于其没有规律且不是稀疏 矩阵，生成矩阵的存储也是一个大难题。当码长较大时，其巨大的运算和存储 在硬件实现上是很困难的，所以没有实际意义，只能作为性能仿真使用。 2 3 2 近似下三角矩阵编码法 传统算法的最大弊端是高斯消元破坏了矩阵的稀疏性，不利于硬件实现。 基于近似下三角矩阵的下三角矩阵编码法可以有效的解决巨大的运算量和存储 空间消耗的问题i “捌。下三角矩阵编码法的核心是构造一个如图2 - 9 的近似下 三角矩阵，h 是一个满秩的矩阵，如果不满秩，要先消去相关行。由图可知， 西南交通大学硕士生学位论文第1 4 页 a 是一个m g ) x ( n 一研) 的矩阵，b 是一个一g ) x g 的矩阵，t 是一个 伽一g ) x ( m g ) 的下三角矩阵，c 是一个g o 一肌) 的矩阵，d 是一个g g 的 方阵，e 是一个g 伽一g ) 的矩阵。 卜一n 耵 卜叫卜_ 卜- 乎卜一m g _ 斗 abt ( 下三角矩阵) cde 图2 - 9 具有近似下三角阵形式的校验矩阵h ! 士 校验比特位分成岛和岛两块，所以编码后的码字c 一 ，a ，p ：) ，可以得到 以下关系式： f p l r 一一( 一e 丁1 口+ d ) 4 ( - e r - 1 a + c ) s r， l p 2 r - 一t 以o s r + 曰p - ) - 一u ， 上面求z 的过程中，除了( 一e r 以b + d ) 。的计算量为o ( 9 2 ) 以外，其他计算 过程都与相应的矩阵行列数长度成线性关系，所以要让g 尽可能的小。达到这 样的目的只能在原来矩阵的基础上进行或列交换，以保证矩阵的稀疏性不被破 坏，用g r e e d y 算法预处理可以很好的解决这个问题。 进行预处理后计算和存储的要求都降低了很多，编码的复杂度也大大降低。 但与结构码相比复杂度仍然偏高，同时这种预处理过程随着码长的增加也将变 得不可接受，寻找更为有效的获得下三角矩阵的方法是解决这个问题的关键。 2 3 3 准循环矩阵的编码方法 通过研究发现，基于一定数学基础的q c l d p c 码可以实现线性复杂度的 编码1 2 1 , 2 2 】，虽然这样会付出码字性能的代价，但是通过一定的方法，q c l d p c 码在易于实现的同时还能保持一定的性能【2 3 - 2 5 1 。假设这罩的校验矩阵都是满秩 的，对于满秩准循环的l d p c 码，有三种高效编码方式【2 6 】：串行编码方式、并 行编码方式和两阶编码方式，这里介绍两阶编码算法。 西南交通大学硕士生学位论文第1 5 页 h h 1 l h 2 1 h c ，1 日1 2 日2 ，2 h c 2 h l l h 2 j h c l ( 2 9 ) 设q c - l d p c 码c b t b 的校验矩阵抒如式( 2 9 ) ，其中h 。，是一：f b x b 的循 环矩阵。h 的秩厂一c 6 ，且存在一个c b x c b 的可逆子矩阵d 如式( 2 1 0 ) 。于是 此时的准循环校验矩阵h 可以等效为：h 暑【h 1d 】。再由前面传统编码算法 的思想，由式( 2 7 ) 可以得到一个p c ) b t b 的系统生成矩阵g ，如式( 2 - 1 1 ) 所示t g g 1 g 2 ： g 一。 d = h l l c n h 2 j - c + l 且h + 2 日2 f - c + 2 q ， h 2 | h c l - c n h c 1 吨n hc l g 1 1 g 2 - ： g 【- c j g 1 ： g 2 ： q 。2 ( 2 1 0 ) - - - ip 】 ( 2 1 1 ) 经典的编码方法有两个矛盾需要解决，一是信息序列与生成矩阵各列相乘 会耗费大量的逻辑资源；二是存储生成矩阵要耗费大量的存储资源。研究发现， 其实并不需要由信息序列和生成矩阵相乘得到编码结果，利用循环矩阵可以由 其生成器生成的特点，基于g 矩阵的生成器( 各个子循环矩阵的第一行或者第 - - n ) g ；来设计编码器。 因为循环矩阵的逆、乘积、求和所得的矩阵仍然是循环矩阵，所以d 。1 也是 由c c 个bx b 的循环阵构成的准循环矩阵。 矿悟吲 瓯瓯； 一 一 一 西南交通大学硕士生学位论文第16 页 嚷 ； q 。 q 1 b c l 墨c ： b c h l j h c j ( 2 1 3 ) 对于1sj sc ，令b b j ，1 岛，。】，m l 一 二以】r 。将式( 2 - 1 2 ) 的第歹行循环体乘以校验矩阵的第i 列循环体相乘可以得