（通信与信息系统专业论文）ldpc码最小距离的研究与应用.pdf

山东大学硕士学位论文 中文摘要 随着移动通信系统高速率业务需求的不断增加，前向纠错码越来越受到人们 的关注。低密度奇偶校验( l d p 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 码最小距离和码重分布的估计、l d p c 码在 m i m o o f d m 系统中的应用等方面。主要工作如下： 1 概括了信道编码从理论到实践的发展，研究了线性分组码的基本原理，包 括线性分组码的重量、距离和最小距离。在此基础上，给出了几种常用的线性分 组码的最小距离界。 2 研究了l d p c 码的构造和译码算法。在介绍l d p c 码的校验矩阵表示、 t a n n e r 图表示、度数分布的基础上，研究了构造l d p c 码校验矩阵的p e g 算法， 同时对i e e e 8 0 2 1 1 n 和w i m a x 8 0 2 1 6 e 标准中的l d p c 码的校验矩阵的构造方法 进行了研究。在译码方面，论述了l p d c 码的l l rb p 算法和最小和算法。 3 最小距离和重量分布是理论分析l d p c 码的纠错性能的重要指标，而a n c ( a p p r o x i m a t e l y n e a r e s tc o d e w o r d s ) 搜索算法是一种常用的估计l d p c 码最小距 离和码重分布的算法。本文详细论述了a n c 算法的实现过程，特别是如何搜索 最接近最小码重的码字的方法。在此基础上，给出了w i m a x 标准中的几组l d p c 码的最小距离和低码重的重量分布，利用一致界对l d p c 码在高信噪比下的纠错 性能进行分析，并给出了码字错误概率的渐进上界。结果表明，在高信噪比下 l d p c 码具有优异的纠错性能，能够满足w l m a x 标准物理层低误码率传输的要 求。 4 构造了l d p c 编码的m i m o o f d m 系统，研究了8 0 2 1 6 e 标准中的l d p c 码的性能，仿真结果与最小距离的分析结果相一致。 关键词：l d p c 码；最小距离；p e g 算法；a n c 算法；m i m o o f d m 系统 山东大学硕士学位论文 a b s t r a c t w i t ht h ei n c r e a s i n gd e m a n df o rh i g h - s p e e ds e r v i c e si nm o b i l ec o m m u n i c a t i o n s y s t e m s ，p e o p l ea r ep u t t i n gm o r ee m p h a s i so nf o r w a r d6 埴 l o rc o r r e c t i o n ( f e c ) c o d e s l d p cc o d e sa r eak i n do ff e cc o d e sw h i c hh a v et h en e a r - s h a n n o n l i m i tp e r f o r m a n c e a n dl o wd e c o d i n gc o m p l e x i t y s oi th a sb e c o m eah o ts p o ti nt h ef i e l do fc h a n n e l c o d i n g i nt h i sd i s s e r t a t i o n , s o m ei s s u e so fl d p cc o d e sa 咒i n v e s t i g a t e d , i n c l u d i n gt h e b a s i ct h e o r y , t h em i n i m u md i s t a n c ea n di t sa p p l i c a t i o n t h em a i nc o n t e n ti n v o l v e st h e r e p r e s e n t a t i o n so fl d p cc o d e s ，t h ec o n s t r u c t i o no fs p a r s ep a r i t y - c h e c km a t r i x ，l d p c d e c 脚i n gm e t h o d s ，m e a s u r e m e n to ft h em i n i n l md i s t a n c ea n dt h e c o d ew e i g h t d i s t r i b u t i o na n da p p l i c a t i o n so fl d p cc o d e si nm i m o o f d ms y s t e m s t h em a i n w o r ki sa sf o l l o w s ： 1 t h ed e v e l o p m e n to fc h a n n e lc o d i n gi ss u m m a r i z e df r o mt h e o r yt op r a c t i c e ，a n d t h ef u n d a m e n t a l so fl i n e a rb l o c kc o d e s ( l b c ) a r ei n v e s t i g a t e d ，i n c l u d i n gt h ew e i g h to f l b c ，t h ed i s t a n c ea n dt h em i n i m u md i s t a n c e o nt h a tb a s i s ，s e v e r a lc o m m o nm i n i m u m d i s t a n c eb o u n d so fl b ca r eg i v e n 2 t h ec o n s t r u c t i o na n dd e c o d i n ga l g o r i t h m so fl d p cc o d e sa r cd i s c u s s e d b a s e d o nt h ei n t r o d u c t i o no ft h er e p r e s e n t a t i o n so fl d p cc o d e s ( s p a r s ep a r i t y - c h e c km a t r i x a n dt a n n e rg r a p h ) a n dt h ed e g r e ed i s t r i b u t i o n s ，p e ga l g o r i t h mi sc o n s i d e r e dt o c o n s t r u c tl d p cc o d e s f u r t h e r m o r e ，t h ec o n s t r u c t i o nm e t h o d si ni e e e 8 0 2 1lna n d w i m a x 8 0 2 16 es t a n d a r da 坨a l s od e s c r i b e d a sf o rd e c o d i n g ，t h el l rb pa l g o r i t h m a n dm i n - s u ma l g o r i t h mo fl d p cc o d e sa r ee x p r e s s e di nt h i sd i s s e r t a t i o n 3 t h em i n i n l u l nd i s t a n c ea n dt h ec o d ew e i g h td i s t r i b u t i o na l ei m p o r t a n t i n d i c a t o r sf o ra n a l y z i n gt h ep e r f o r m a n c eo fl d p cc o d e si nt h e o r y , w h i l et h e a p p r o x i m a t e l yn e a r e s tc o d e w o r d ( a n c ) m e t h o di sac o m m o n l yu s e da l g o r i t h mt o c a l c u l a t et h em i n i m u md i s t a n c eo fl d p cc o d e s i nt h i sp a p e r , w ed e s c r i b ei nd e t a i lt h e i m p l e m e n t a t i o no ft h ea n cm e t h o d , e s p e c i a l l yh o wt os e a r c ht h ec o d e w o r dw h i c hi s a p p r o a c h i n gt h em i n i m u mw e i g h tc o d e w o r d b a s e do nt h i s ，t h em i n i n l md i s t a n c e s 2 山东大学硕士学位论文 a n dl o wc o d ew e i g h td i s t r i b u t i o n so fs e v e r a ll d p cc o d e s1 1 1w i m a x 8 0 2 16 es t a n d a r d a r eg i v e n f u r t h e r m o r e ，t h ep e r f o r m a n c eo fl d p cc o d e sa th i g hs i g n a l - t o n o i s er a t i oi s a n a l y z e du s i n gu n i o nb o u n d , a n dt h eu p p e rb o u n d so fl d p cc o d e sa r eg i v e n t h e r e s u l t sv e r i f yt h ee x c e l l e n te r r o rp e r f o r m a n c eo fl d p cc o d e sa th i g hs i g n a l - t o n o i s e r a t i o i tm e e t st h ed e m a n d so fl o w - e r r o rr a t en e e d e di nw i m a x p h y s i c a ll a y e r 4 am i m o - o f d ms y s t e mu s i n gl d p ce n c o d i n ga n dd e c o d i n gm e t h o di s d e s i g n e d , a n dt h ep e r f o r m a n c eo fs o m eg r o u p so fl d p cc o d e si n8 0 2 16 es t a n d a r di s a n a l y z e d i tr e c o n c i l e st h er e s u l t so f t h e i rm i n i m u md i s t a n c e s k e yw o r d s ：l d p cc o d e s ；1 v i n i m u md i s t a n c e ；p e ga l g o r i t h m s ；a n c ； m o o f d m 3 山东大学硕士学位论文 4 彳( x ) a n c k w g n b e r b p e i g f ( 2 历) g f ( q ) g h 6 l d p c m l 谨 m i m o m l o f d m p e g 帆 s t b c t c m u b 符号说明 重量算子 近似接近码字 加性高斯白噪声 比特误码率 置信度传播 错误脉冲 二元域的扩展 包含g 个元素的有限域 分组码的生成矩阵 基本矩阵 低密度奇偶校验码 最大后验概率 多输入多输出 最大似然 正交频分复用 渐进边增长 信噪比 空时分组码 网格编码调制 一致界 山东大学硕士学位论文 1 1 信道编码理论与发展 第一章绪论 在现代通信系统中，由于信道的衰落特性以及各种噪声的干扰，会使信息无 法正确的进行传输，从而导致信息传输质量的下降。为了保证信息可靠有效的传 输，信道编码技术就成为通信中必不可缺少的技术之一。信道编码理论的起源可 追溯到1 9 4 8 年s h a n n o n 信息论的问世。s h a n n o n 理论揭示了在通信系统中采用适 当的编码后能够实现高效率和高可靠性的信息传输。s h a n n o n 第二定理也被称为 有噪信道编码定理：设任意一个离散无记忆信道，其信道容量为c 。当信息传输 速率r c 时，则不存在这样的编码方 法【1 】【2 】。香农定理只是给出了最优码的存在定理，并不能从定理的结果直接得到 最优码的具体形式，但是却可以根据定理得到编码的性能极限。在一个通信系统 中，若实现可靠通信且信息传输速率接近或达到信道容量，此时所需要的最小的 比特信噪比称之为香农限。香农限就成为设计信道编码时试图逼近的信噪比下限。 s h a n n o n 定理提出之后，研究学者一直在致力于寻找一种编码方式，使其能 够满足译码错误概率非常小，因而信道编码理论得到了快速发展。图1 1 描述了 信道编码的发展历程。由图可见，1 9 5 0 年发现了第一个分组码1 a m m i n g 码， 此时的汉明码还只能纠正单个错误 3 】；之后又发现了g o l a y 码，r m 码，循环码 等多个短码长的分组码。2 0 世纪6 0 年代是信道编码进入较快发展的第一个阶段 【4 】。在这个阶段最先发现的b c h 码，实现了能纠正多个错误的信道编码方案。 随后在1 9 5 5 年，e l i a sp 提出了卷积码，也称为树码( t r e ec o d e s ) ，或者是格码 ( t r e l l i sc o d e s ) 【5 】。卷积码提出之后，很多学者一直致力于卷积码各种译码算法 的研究，直到1 9 6 7 年v i t e r b i 提出的最大似然译码算法( m a x i m u ml i k e l i h o o d d e c o d i n g ，m l d ) 【6 】，才使得译码算法有了重大突破。 2 0 世纪7 0 年代，信道编码进入第二个大的发展阶段。1 9 7 0 年发现了性能更 好的g o p p a 码分组码；以及在软判决译码算法中也有了新的进展，如最大后验概 5 山东大学硕士学位论文 6 图i - i 信道编码的发展历程 调制 山东大学硕士学位论文 率译码算法( m a x i m u ma p o s t 豇- i o r i ，m a p ) 【7 】的提出，它的实现复杂度虽然高， 但译码性能比v i t e r b i 算法好。随着计算机水平的提高，m a p 算法被应用到t u r b o 码，l d p c 码等译码算法中。 2 0 世纪8 0 年代信道编码进入了第三个大的发展阶段。1 9 8 2 年发现了代数几 何码，具有较高频带有效性的抗干扰方案以及网格编码调制技术【8 】( t r e l l i sc o d e d m o d u l a t i o n , t c m ) 的发展。1 9 9 3 年b e r r o u 等人提出了并行级联卷积码，将卷积 码与随机交织器相结合，并且在译码时采用迭代译码逼近m l d 译码，从而得到 了非常接近s h a n n o n 限的优异性能【9 】【10 】。 1 2 最小距离和信道编码原则 在g f ( q ) 域中，对k 维的信息序列进行编码，码长为刀。信息序列共有恂七 种排列，编码之后的序列共有矿种可能排列，可见矿掣，信息序列即码集仅是 一个子集，矿个信息序列要以什么算法或者原则对应到n 维n 重矢量空间中，这 便是信道编码需要解决的问题。被选取的矿个信息序列( 码字) 为许用码组( 许 用码字) ，其余的矿一矿个信息序列称为禁用码组【4 】【1 1 】【1 2 】。 在任意一组分组码c 中，码字的汉明重量是指码字中所含有的非零码元的个 数，又称汉明势，记为吣) ，x c 1 1 。在二元码中，码字的汉明重量即为码 字中所含1 的个数 1 1 1 2 1 。 两个码字i 和x 2 之间对应位取值不同的码元个数，称为码字之间的汉明距离， 表示为d ( x 。，x 2 ) 。在某一码集中，任意两个码字之间汉明距离的最小值，称为该码 组的最小汉明距离，简称最小距离矗i n 11 。 码率，和最小距离如i n 是信道编码最重要的两个参数。码率，用来衡量码的 有效性，最小距离蟊i i i 用来衡量码的纠错性能，也即码的抗干扰能力。然而码的 有效性和抗干扰能力是相互矛盾的，因为码率越大，码的冗余度越小，两个码字 之间的差异度也会越小，抗干扰能力就会越差。因此编码的原则就是：在可用码 组中选择最小汉明距离尽可能大的码字，即码率一定时，选择如i n 尽可能大的码， 或者当如- m 一定时，选择，尽可能高的码 1 1 1 3 。 7 山东大学硕士学位论文 1 3l d p c 码的特点及发展 l d p c 码是一类基于稀疏校验矩阵的线性分组码，它由r o b e r tg g a l l a g e r 在 1 9 6 2 年首次提出【1 4 】。但由于当时的计算机水平和信道编码技术的局限性，无法 解决l d p c 码的编码存储要求，译码复杂度高等实际问题，使得l d p c 码被人们 所忽视了将近3 0 年。直到1 9 8 1 年，t a n n e r 引入了二分图模型【1 5 】，将l d p c 码 的检验矩阵与二分图一一对应。引入t a n n e r 图还使得g a l l a g e r 提出的迭代译码算 法复杂度明显降低。之后w i b e r g 重新发现和延伸了t a n n e r 的思想，提出了更一 般的译码算法和积( s u m - p r o d u c t , s p ) 算法和最小和( m i n - s u m ) 算法【1 6 】。随 着t u r b o 码的研究，引发了人们对基于图模型和迭代译码的研究热潮【1 7 】【1 8 】【1 9 】。 于是1 9 9 5 年m a c k a y 和n e a l 再次对l d p c 码进行了深入研究 2 0 1 ，并发现它在与 置信传播( b e l i e f - p r o p a g a t i o n , b p ) 迭代译码算法相结合的条件下，性能非常逼近 s h a n n o n 限。由于l d p c 码优异的性能，使得人们越来越热衷于对l d p c 码的研 究。 目前有很多方法构造好的t a n n e r 图或者是l d p c 码，一种是应用最为广泛 的随机构造法【2 1 】，其中最重要的是p e g 构造 2 2 2 3 1 1 2 4 。还有一种是结构化构 造法【2 5 】【2 6 】【2 7 】，利于硬件实现。校验矩阵构造的目的就是构造大的环长，不规 则，简单的码。所有的这些方法在仿真中都有很好的性能，误码率达到了1 0 5 到1 0 。目前的计算能力已不能达到更低的误码率估计，只能依靠联合界限的渐 进算法来从理论上估计，而这一算法要依赖于最小距离a n l i i i 和多重最小距离 2 8 1 。 我们首先解决l d p c 码的最小距离运算问题，然后利用最小距离分析比较l d p c 码的性能，再通过实际系统仿真来验证上述基于最小距离比较的l d p c 码的性能 结果，证明最小距离运算的正确性。 研究l d p c 码的构造方法，以及译码算法的改进，目的都是构造好的l d p c 码，使得l d p c 码的性能更逼近于s h a n n o n 限。l d p c 码的纠错性能常常用m o n t o c a r l o 仿真方法来评估，但在信噪比比较高时，需要大量的计算，仿真时间非常长。 所以本文提出从最下距离的角度来分析l d p c 码的性能。最小距离计算是分组码 的一种理论分析方法，可以使得在没有构造码的前提下，分析码的纠错性能，为 8 山东大学硕士学位论文 实际中选择和设计分组码提供了参考 1 1 】【2 9 。 l d p c 码是一种性能非常好的实用的好码，已经在通信领域内被广泛应用。 例如在图像压缩传输处理中【3 0 】，信源编码方案采用j p e g 静止图像压缩标准，而 信道编码则采用的是l d p c 码编码方案；2 0 0 3 年公布了针对卫星宽带业务的第二 代标准d v b s 2 ，最终确定l d p c 码作为信道编码方案 3 1 1 。l d p c 码还可以与通 信系统中的其它先进技术相结合，例如在i e e e 8 0 2 1 6 e 3 2 标准w t r e l e s sm a n o f d m a 物理层规范中，为克服移动造成的子载波衰落，提高抗多径效应和窄带 干扰的能力，采用了前向纠错编码技术，l d p c 码是其中一种备选方案。l d p c 码还可以与空时编码( s p a c e t u n ec o d e d , s t c ) 相结合，应用于m i m o o f d m 系 统，实现高速且性能优异的通信链路系统 3 3 】。此技术在8 0 2 1 1 n 3 4 中已经得到 应用。 1 4 本文的主要内容 本文的主要内容安排如下： 第一章：绪论。首先介绍了信道编码的发展历程和最小距离的基本概念， 以及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 d p c 码最小距离的计算。介绍了测量l d p c 码最小距离的a n c 算法和全零码字的加噪方法，重点研究了a n c 算法的译码方法。 第五章：l d p c 码的应用研究。介绍了a l a m o u t i 空时分组码的基本知识， 研究了m i m o o f d m 系统的基本原理，以及l d p c 码在该系统下的编码性能。 9 山东大学硕士学位论文 第二章线性分组码 信道编码时，每七个信息符号分成段，记为m = ( 中- 2 ，) ，并称序 列m 为信息组，其中m a i = 1 ，2 ，七) 称为信息元。为了纠正信道中传输引起的差 错，编码器将每个信息组按照一定的规则增加产生，个多余的符号，从而形成长 度为刀= k + 厂的序列c ，称此序列为码字。码字中的每个符号称为码元。所增加的 厂个码元称为校验元，其中刀为码长，k 为信息元的位长，是校验元的位长。 当每个码字中所增加的，个校验元只有本组的k 个信息元按一定的规律产生 的，与其他信息组的信息元无关，这样形成的所有码字集合称为分组码，记为( 刀， 七) 码。若本组的校验码元的产生不仅与本组的信息位有关，而且与此时刻之前输 入编码器的信息位有关，译码时同样也要利用前面码组的有关信息，这种码称为 卷积码，常用( 刀，毛，) 表示卷积码的集合，为约束长度 2 1 1 11 1 。若校验元与信 息元之间呈线性关系，称其为线性码，否则为非线性码【2 】。在这里我们主要研究 的是分组码中很重要的一类码一一线性分组码，它是讨论各类码的基础 【11 1 1 3 5 3 6 3 7 1 。 定义码长为刀，有矿个码字的分组码c ，当且仅当其矿个码字构成域g f ( q ) 上所有刀维向量空间刀的一个k 维子空间时，称该分组码为i n ，明g 线性分组码， 且c c 曰，k 称为c 的维数 1 1 】。 本章主要介绍线性分组码的基本概念、重量、距离和最小距离界等。 2 1 重量和距离 设q ，勺碍是空间中的元素，若令q = ( 气，钆气) ，巳= ( c 0 ，c l 气) ，则 q 和巳之问的汉明距离定义为： l o n - i d ( q ，勺) = c j io 气 上穹o ( 2 一1 ) 山东大学硕士学位论文 式中。为模q 和运算。而q 的汉明重量为 以q ) = 撑 七：气o ( 2 - 2 ) 符号# 表示计算个数或数目。 定义了汉明距离就使得空间层成为一个测度空间，测度满足 ( 1 ) d ( q ，c j ) 0 ，当且仅当q = q 时等号成立； ( 2 ) d ( q ，c j ) = d ( c j ，q ) ： ( 3 ) d ( c f ，巳) d ( q ，c d + d ( c , ，巳) ，v c l ，c j ，q 曰。 定义设c c 碍是一个码，其最小距离为 d = d 二( c ) = i i l i n d ( q ，巳) ：q ，c j c ，q c j ) ( 2 - 3 ) 定理线性分组码的最小距离等于码集中非零码字的最小重量，即 “( c ) = l i i l 以c ，) ：c ，c ，c ，o ) ( 2 - 4 ) 定理的证明利用了群的封闭性。由于分组码是群码，任意两个码字之和仍是 码字，即如果勺c 、c tsc ，则c ，o c i = c f c ( g 迸制加法) ，因此任意两码字 间的汉明距离其实必是另一个码字的重量，表示为d ( c ，c ) = 以c 0c t ) = 似c ，) 。 因此，码的最小距离可以通过寻找最轻码字，也即计算非零码字的最小重量来获 得 2 】 1 2 】。 定理任何最小距离为的线性分组码，其检错能力为一l ，纠错能力t 为州( d 8 1 ) 2 2 1 。 最小距离表明码集中时各码字差异的程度，差异越大纠错能力越强，抗干扰 能力自然越强，因此成了衡量分组码性能最重要的指标之一。估算最小距离是纠 错码设计的必要步骤。 定理码c 的最小距离为的充要条件是：校验矩阵h 中有线性无关的列数 为矗i n l 【2 】 1 2 】。 从上述定理中我们可以看出通过计算校验矩阵的秩也可以得到最小距离。 山东大学硕士学位论文 定义设c c 碍是一个码，4 是码组中汉明重量为w 的码字的数目，o w = l ，0 ，0 ，4 ，8 ，0 ，o ，1 ， 说明在2 4 = 1 6 个码字中，除了一个全o 码( 第一个系数为1 ) ，一个全1 码( 最后 一个系数为1 ) 外，有4 个重量为3 的码字和8 个重量为4 的码字，重量谱是窄 谱。重量算子除常数项外最低次数非零项的次数就是最小距离d n ，上述( 7 ，4 ) 汉明码重量算子中非零最低次数是3 ，因此= 3 【2 1 1 2 1 。 2 2 分组码的最小距离界 码的纠错能力与该码的最小距离直接相关，最小距离是衡量分组码性能的重 要指标。在这里我们首先来介绍几种常用的最小距离界。 2 2 1 h a m m i n g ( s p h e r e - p a c k i n g ) 界 ( 讯( g ) 域上的( 刀，七) 线性分组码，共有矿个码字，把每个码字看作g f 国) 域 上刀维空问中的点，以每个码字为球心，f 为半径描绘一个球，则与这个码字汉 明距离为f 的码字就在这个球_ t 2 1 11 1 。如图2 一l 所示。在保证各个球不相交的情况 下，这组线性分组码会有一个最大的，值，而，与最小距离的关系，户姗n 一1 ) 2 1 即可得到最大的最小距离靠i l i ，且这组码的纠错能力为f 。 1 2 山东大学硕士学位论文 在半径为f 的球上，包含了汉明距离从o 到t 的所有向量，这些向量的个数 称为r g 维体积k 刖，表示为 ：【t ，n h 1 ) ， j = o ( 2 7 ) 如果o r ( q ) 域上刀维空间的体积大于等于这矿个码字的总体积，则所有的球都不 会相交。那么码字可以纠正f 个错误的条件为 或 留t 圭( ；h 一1 ) ，g j - - o q h 圭c k _ 1 ) ， j = o ( 2 8 ) ( 2 - 9 ) 变成对数形式为 础孔g 叮睁h 叫 。， = o 当分组码的刀，k 确定之后，利用( 2 1 0 ) 式可以得到f 的最大值，进而得到最小 距离的最大值。此界称为汉明球包界，它适用于所有的分组码。 图2 - 1h a m m i n g 界的说明 1 3 山东大学硕士学位论文 2 2 2 s i n g l e t o n 界 对线性分组码来说，这个界限容易求出，但是很难达至1 j 2 9 。一个非零码字 的信息位至少有一个元素非零，刀一k 个校验位最大非零个数为刀一k 。因此码字的 最小重量，也即矗妯，不可能超过行一k + l 。即 d m 刀一k + l ( 2 1 1 ) s i n g l e t o n 界公式还揭示了一个很重要的理论。把( 2 1 1 ) 公式转换成 皇i l 一生+ ! ：( 1 一足) + 1 刀( 2 - 1 2 ) 刀力刀 根据上式我们可以看出，对于很大的码长刀，d m i n f 不会超过( 1 一r ) 。由于码的纠 错能力t 满足r n v r ( a m - 1 ) 2 ，所以： 一t ( 1 一r ) 2( 2 1 3 ) 刀 即纠正一个码元的能力是冗余信息位的一半。例如，对于一个较长码长，r = 1 2 的一组码，最多只能纠正一个码字中2 5 的不正确的码元数目。 2 2 3p l o t k i n 界 假设在g f ( g ) 域上的一组( 刀，七) 线性码c ，满足g f ( g ) 域中的每个元素在矿 种组合中的每列所出现的次数正好是g b l 次。例如图2 2 所示，码字集合每列都出 现了八个1 和八个0 。那么所有码字的总的重量为刀( g 1 ) q 一1 。在这组码组中， 共有窖一1 个非零码字，每个码字的平均重量为 = _ n ( q f - 1 ) q 广q ( 2 - 1 4 ) 很显然最小的码重，也即相当于，一定小于平均码重： 冬等- 丁1 ) q q ( 2 1 5 ) 此时针对n ，k ，g 这三个参数就给定了靠洒的另一个上界。把上式变换成 1 4 山东大学硕士学位论文 望粤虹 ( q - i ) q k - l 刀一g 一i ( 2 1 6 ) 从上式可以看出，当k 很大时，玺只与( g 一1 ) g 相关，而与码率无关，因此这 刀 个界是比较宽松的，尤其是在高码率和g 值很大时。 u 0 0 0 0 0 0 0 l o o l 0 o o ll 0 1o o 0 10 l o l1 0 0 1l l l o o o 1 0 0 1 l o l 0 1 0 ll ll o o l1 0 1 ll1 0 l l l l 2 2 4g i l b e r t 界 x o o o o o o o o o o l 0 1l 0 0 1 0 1l o 0 0 111 0 1 0 1o o ll l 0 1 0 11 0 0 o l l 0 0 0 1 0 1l1 0 10 1 0 0 0 1 0 1 1 0 0 1ll0 1 0 l0 0 ll 1 0 1l o o o l1 0 0 0 1 0 ll o lo o l l l1 0 1 0 0 l lllll l 臣器j ( ： 俨p 0 0 1 0 。1 1 图2 - 2 ( 7 4 ) 线性分组码 假设我们要设计一个好的线性分组码c ，给定码长刀、要求最小距离至少为d ( 2 d 珂) ，那么如何来确定信息位七的数值。它的研究类似于汉明界，涉及到r t 维几何空间中的球的概念。我们将详细的阐述推导过程，但这个结论也适用于相 同速率要求的非线性码。 首先我们要构造一个秩为k 的生成矩阵g ，其所有行矢量的线性组合满足最 小重量为d 。在g f ( q ) 域上的n 维n 重空间中，删除所有与零矢量的汉明距离小 于d 的矢量，共有删个矢量。在剩下的空间中，选择任意的刀个数据，作为生 成矩阵g 的g l 矢量，此时也保证了蜀的重量( 即非零元素的个数) 至少为d 。它 周围的每个矢量表示# j t _ g 。，去除咄个矢量，即以q 蜀为球心，d - l 为半径所画的 1 5 山东大学硕士学位论文 球中包含的所有矢量的个数。然后从剩下的空间中选择9 2 ，要求qg l + 哆9 2 o ， 现阶段我们就组成了二维的线性码。当，哆不全为零时，这两个矢量的任意组 合构成的向量的重量都满足大于等于d 。去除与每个组合矢量距离为d - - 1 的咄 个矢量后，如果还有剩余的空间，则选择岛，继续前面的步骤，直到g ”被全部填 满。如图2 3 所示。 1 6 ( a ) 间q n 1 薹1 2 - 3g i l b e r t 舞- - , q = 3 ( a ) 选择盘前，删除了价球选择9 3 l 簟，删除了矿球 山东大学硕士学位论文 我们注意到在g ，被选择时，它之前共去除了g 个体积为咄的球。最坏的 情况下，这些球是不相交的，但一般情况下还是有些重叠的。因此当k 满足： 吁q t - i t ，t d ( - l n ) q “ 就能保证在g f ( q ) 域上存在线性分组码( 刀，七) ，最小距离为“d 。 2 2 5v a r s h a m o v 界 ( 2 - 1 7 ) 与g i l b e r t 界稍有不同，v a r s h a m o v 界是基于构造校验矩阵提出的【2 9 】。首先 给定校验符号的数目，= 刀一k ，我们要求构造的线性分组码的距离为 d ( 2 d 厂+ 1 ) 。由前面的讨论可知，如果我们构造一个r x b 的矩阵h ，且有d 一1 列线性无关，那么由h 矩阵构造的分组码就可以满足最小距离“，d 。 首先构造h 矩阵的前，列，前，列由一个r x r 的线性无关的单位矩阵组成， 第，+ l 列如果满足不是前面任意d 一2 列的线性组合构成的非零，- 维矢量，那么h 矩阵加上第r + l 列，仍然可以保持d 一1 列是线性无关的。又因为所有r 列的线性 组口厶六7 日厶d ，“- 2 r ) ( g 一1 ) ，只有当线性组合的个数小于所有非零的，维矢量的个 数时，第r + l 列才能满足上述条件。以此类推，确定h 矩阵第厅列的充分条件是 或者等价为 厶d - 2 j n ! ) ( 、g 一1 ) 7 g “一1 ( 2 1 8 ) j = l ( 2 。1 9 ) 式即为最小距离d 的线性码( 拧，n - r ) 存在的充分条件。 ( 2 1 9 ) v a r s h a m o v 界和g i l b e r t 界很相似，常称为g v 界。但二者也稍有不同： v a r s h a m o v 界是在确定校验符号，= 刀一k 的情况下，得到 l ，进一步得到k ；而g i l b e r t 界是先固定刀再来确定k 。两种界都说明了一种渐进特性。 1 7 g v | d g，i 、 、l - ， 一” 七 ，ii- m 舢 山东大学硕士学位论文 2 2 6 v a r s h a m o n g i l b e r t 界和h a m m i n g 界的渐进形式 以上讨论的界还可以由另一种形式表示。设g f ( q ) l 内，k 一表示n 维空间中 半径为t 的球的体积，则形”满足 去一 垆k 一 ( 2 2 0 ) 其中( x ) = x l o g q ( g 一1 ) - x l o g q x - ( 1 一曲l o g q ( 1 一x ) ，( 0 x q 留- 1 ) 是二进制熵 函数的q 元形式。将上式应用到g i l b e r t 界可得 等f ( 一告) 叫( 1 - ，) 刀力， 同理应用到汉明界可得 ( 2 - 2 1 ) 三 譬 ，民是 与变量节点m 相连的边的集合，矿h 表示与变量节点屹相连的第k 条边。 最开始的已有的t a n n e r 图一般为简单图，所谓简单图就是指图上的每个节点 都没有自循环，两节点间最多有一条边，且边是无方向的。在简单图中，集合e 已经确定，现在我们给出变量节点的第k 条边e 的连接算法。对于哆的第一 条边e o 巩，在所有校验节点中选择连接边数最少的校验节点与之相连。在连接剩 下的域一l 条边时，对h 进行如图3 - 2 所示的，层扩展，此时图中包含的所有校验 节点的集合用心表示，其补集为配= 圪m 。l 满足联矽，而矸1 = ，或满 足：= 喈1 且m m 。在集合k 中选择连接边数最少的校验节点与变量节点m 相连。 - i - i - i 刍一竹 d e p t h7 f 图3 - 2 任意某个变鼍节点展爿：的深度为j f 的子图 山东大学硕士学位论文 综上所述，在给定变量节点数、校验节点数从变量节点度序列见的情况 下，p e g 算法关键步骤如下： f o rf = 0t on 一1 f o rk = 0t o 吒一l i fk = 0 “，巳) je ，其中e 。o 是连接变量节点m 的第一条边，c j 是在当前集合 民u 气u u 中具有最低度数的校验节点。 e l 在当前图集合的基础上，将变量节点v 展开成深度为，的子图，直到集 合k 。 ( 3 - 3 ) ( 3 - 4 ) 8 0 2 1 6 e 标准中1 2 的码率用到的b a s e 矩阵如下： 一19 47 3 1 1 1 1 15 58 3 1 170 一l 一1 1 1 1 1 1 1 1 1 12 7 1 1 12 2 7 99 1 1 11 2 1 00 1 1 1 1 1 1 - 1 一l 一1 1 1 12 4 2 28 1 13 3 1 1 10 1 100 1 1 1 1 1 1 1 1 6 1 14 7 1 1 1 1 16 52 5 1 1 1 1 100 1 1 1 1 1 1 1 1 13 9 1 1 18 4 1 14 17 2 1 1 1 1 100 1 1 1 1 一l 一1 1 1 1 14 64 0 18 2 1 1 17 90 1 1 1 100 1 1 1 1 1 1 1 9 55 3 1 1 1 1 11 41 8 1 1 1 1 1 1 100 1 1 1 1 11 17 3 1 1 12 1 14 7 1 1 1 1 1 1 1 1 10o 一1 1 1 1 2 1 1 18 32 4 14 3 1 1 15 1 1 1 1 1 1 1 1 1o0 1 1 1 1 1 1 19 4 - 15 9 1 17 07 2 1 1 1 一l 一1 1 1 1 100 1 1 1 76 5 1 1 1 13 94 9 1 1 1 1 1 1 1 1 1 1 1 10 0 4 3 1 1 1 16 6 14 1 1 1 12 67 1 1 1 1 1 1 1 1 1 10 当n = 5 7 6 时，z = 5 7 6 2 4 = 2 4 ，从上面的数据可以看出h 6 的第一个元素为1 ，小 于零，则b o o ) 为2 4 2 4 的零矩阵。第二个元素为9 4 ，循环移位次数为j 帆9 4 2 4 9 6 = 2 3 ，即r 。1 ) 为单位矩阵向右循环移位2 3 次。 我们假设z = 8 ，下式中q 。为单位矩阵，q ，即为单位矩阵向右循环移位5 次之后 的矩阵。 山东大学硕士学位论文 q o2 10 ol o0 0o o 0 00 o 0 o0 0 o 0 0 l0 ol o 0 o o 0 0 0 0 0o 00 0o 00 lo o1 00 00 0o 0 o o 0 00 00 00 1o 0l q 52 o o o o o 0 10 01 0 0 0 0 0 o 00 0 o o0 0o o 0 lo 0l 0 0 01 oo o0 0o o0 00 00 10 0 o l0 0l 0 o 0 0 0 0 0 o 0 0 ( 3 - 5 ) 与8 0 2 1 6 e 相比，8 0 2 1 i n 标准中规定了四种码率，三种码长的l d p c 码。码率 分别为1 2 ，2 3 ，3 4 ，5 6 ；码长分别为1 9 4 4 ，1 2 9 6 和6 4 8 。8 0 2 1i n 标准中的校验矩 阵构造与8 0 2 1 6 e 中的校验矩阵构造很相似，唯一不同的是它的循环右移的次数仅 决定于z ，即公式( 3 - 4 ) 。 8 0 2 1 1 n 标准中1 2 的码率用到的b a s e 矩阵如下( 代表元素小于零) ： 0 一 一一00一 一 0 一一 010