（通信与信息系统专业论文）基于代数构造的结构化ldpc码译码算法及其校验矩阵结构研究.pdf

摘要 本文主要针对l d p c 码的校验矩阵构造、译码算法和性能分析及错误平层消 除等问题进行了学习和研究。文章采用比对的方法，说明了代数构造的结构化 l d p c 码与随机构造的l d p c 码相比，其循环或准循环的结构具有更低的编码复杂 度。同时，其大列重和冗余校验等特性也确保其在迭代译码时具有与后者相同或 更优的性能。文章通过大量的仿真数据进一步验证了各种改进的迭代译码算法能 够以较小的性能损失换取译码复杂度的有效降低。同时我们得到，针对结构化 l d p c 码，采用基于硬判决的比特翻转译码，在保证性能的同时使译码复杂度更低， 更适合高速译码及硬件实现。另外，本文引入密度进化和高斯近似的方法，对译 码性能进行了分析，其仿真结果与上述译码性能相吻合，也验证了密度进化方法 可实现准确、高效的性能评估。 l d p c 码的错误平层现象，制约着其在高速通信、深空通信、磁存储和光通信 等领域的进一步发展。本文通过对产生错误平层的原因环、陷阱集等结构的 学习和研究，在查找到t a n n e r 图中的环、集结构的基础上，引入消环和陷阱集辅 助译码等方法，改善了错误平层。通过仿真，在码长不长、校验矩阵结构不复杂 的情况下，两种方式均可将错误平层从l o 。5 降到1 0 。8 或更低。 关键词：结构化l d p c 代数构造迭代译码密度进化错误平层陷阱集 a b s 仃a c t i nt h i sp a p e r , w em a i n l yr e s e a r c ho nl d p cc o d e s c o n s u l l c t i o no f c h e c km a t r i x 、 d e c o d i n ga l g o r i t h m 、p e r f o r m a n c ea n a l y s i sa n de l i m i n a t i n ge r r o rf l o o r i ti s i l l u s t r a t e d t h a tt h es t r u c t u r e dl d p cc o d e sc o n s t r u c t e da l g e b r a i c a l l yh a v em u c hl o w e re n c o d i n g c o m p l e x i t yf o rt h e i rc y c l eo rq u a s i - c y c l ec o n s t r u c t i o n sc o m p a r e dw i t ht h el p d cc o d e s c o n s t r u c t e dr a n d o m l y , w h i l et h e i rl a r g er o ww e i g h ta n dm o r er e d u n d a n c yc h e c k sk e 印 t h es r n l eo rb e t t e rp e r f o r m a n c e i nt h i sp a p e r , w ef h r t h e rv e r i f y , u s m gm a n yo f s i m u l a t i o nd a t a , t h a tv a r i o u sm o d i f i e dd e c o d i n ga l g o r i t h mc a nr e d u c et h ed e c o d i n g c o m p l e x i t ye f f e c t i v e l y 、) l ，i t l l s m a l lp e r f o r m a n c el o s s ，a n dw ec o u l dg e tt h a tt h e b i t - f l i p p i n gd e c o d i n ga l g o r i t h mb a s e do nh a r d d e c i s i o ni ns t r u c t u r e dl d p cc o d e s d e c o d i n gh a v em u c hl o w e rd e c o d i n gc o m p l e x i t ya n dn e a r l ys a m ep e r f o r m a n c e ，w h i c hi s s u i t a b l ef o rh i l g hs p e e dd e c o d i n ga n dh a r d w a r ei m p l e m e n t a t i o n b e s i d e s ，t h ed e n s i t y e v o l u t i o na n dg a u s s i a na p p r o x i m a t i o na r ei n t r o d u c e di n t oa n a l y s i n gt h ed e c o d i n g p e r f o r m a n c e t h es i m u l a t i o nd a t aa r ei d e n t i c a l 谢也t h eb e f o r e - m e n t i o n e dr e s u l t s ，a n di t a l s od e m o n s t r a t e st h a tt h ed e n s i t ye v o l u t i o ni saa c c u r a t ea n de f f i c i e n tm e t h o df o r p e r f o r m a n c ee v a l u a t i o n t h el d p cc o d e s e r r o rf l o o rr e s t r i c t st h e i rf l l r t h e rp r o g r e s si nh i g hs p e e d c o m m u n i c a t i o ns y s t e m 、d e 印s p a c ec o m m u n i c a t i o ns y s t e m 、m a g n e t i cs t o r a g ea n d o p t i c a lc o m m u n i c a t i o ns y s t e me t c i nt h i sp a p e r , w es t u d ya n dr e s e a r c ht h ec o n s t r u c t i o n o fc y c l e sa n dt r a p p i n gs e t sw h i c ha r et h ep r i n c i p a lc m i n a 】f o re r r o rf l o o r w h e nw e f i n dt h ec y c l e sa n dt r a p p i n gs e t si nt a n n e rg r a p h , t w om e t h o d sa r eu s e df o re l i m i n a t i n g e r r o rf l o o r , o n ei se l i m i n a t i n gt h ec y c l e si nc h e c km a t r i x ；t h eo t h e ri sm a k i n gu s eo f t r a p p i n gs e t sf o ra u x i l i a r yd e c o d i n g t h r o u g ht h es i m u l a t i n g ，w h e nt h el e n g t ho fc o d e s i sn o tl o n g ，a n dt h ec o n s t r u c t i o n so ft h ec h e c km a t r i xa r en o tc o m p l e x ，b o t ho ft h et w o m e t h o d sc a ne l i m i n a t et h ee r r o rf l o o rf r o m10 - st oi0 - so rm u c hl o w e r k e y w o r d ：s t r u c t u r e dl d p c c o n s t r u c t e da l g e b r a i c a l l yi t e r a t i v ed e c o d i n g d e n s i t ye v o l u t i o n e r r o rf l o o r t r a p p i n gs e t 第一章绪论 第一章绪论弟一早三；百化 本章首先简要介绍了信道编码理论与技术的发展历程，阐述了信道编码技术 在数字通信系统中的重要作用然后概述了l d p c 码的提出发展和研究方向， 最后给出全文的研究重点及章节安排 信道编码理论与技术 通信的目的是要把消息及时可靠的从发送方传递到接收方。所有的数字通信 系统，如移动通信、卫星通信、雷达探测、遥控监测、光纤通信、数字存储系统 等都可以用图1 1 所示的系统模型统一描述。 编码信道 图1 1 数字通信系统框图 在数字通信系统中，待传输信息序列由信源出发进入信源编码器后，去掉传 输信息序列中冗余的信息以增强信息传输的有效性( 为增强信息的保密性，对信 息的加密编码可在信源编码器后进行) ；为了降低传输过程中信道内各种干扰造成 的影响，信息序列在信道编码器内被人为地增加一些冗余度，使其具有自动检错 或纠错能力，提高信息传输的可靠性：经过信道编码后的信息序列经调制器后将 离散的编码序列转化为适合于在信道中传输的波形信号。传输信号在传输过程中 因各种干扰及自身能量损失等原因，必然产生失真，这种失真信号到达接收端后 首先由接收机送到解调器进行解调，恢复为包含信息的离散序列，然后经过信道 译码器，对错误信息进行纠正或者进行可靠性译码，恢复出发送的信息序列，再 2 基于代数构造的结构化l d p c 码译码算法及其校验矩阵结构研究 经过信源译码器转换成原来的待传输信息序列发送给用户。信道编码理论正是研 究通过何种有效的编码和译码方法，使信息序列可以有效的完成抗信道干扰等问 题，最大限度的提高信息传输的可靠性。 美国贝尔实验室的c e s h a n n o n 在1 9 4 8 年发表的权威论文通信的数学理论 ( t h em a t h e m a t i c a lt h e o r yo fc o m m u n i c a t i o n s ) 1 】中提出了著名的有噪信道编码定 理，从而为信道编码奠定了理论基础。该定理指出：对于一个给定的有噪信道， 存在一个确定的信道容量c ，如果信息传输速率r 小于c ，则当码长n 足够大并 且使用最大似然译码时，总存在一种编码方法，可使译码的错误概率任意小。反 之，如果信息传输速率r 大于信道容量c ，则不可能实现无差错通信。但s h a n n o n 在该定理中并没有给出具体的编码方法来实现无差错通信。半个多世纪以来，信 道编码研究者们一直致力于寻找接近s h a n n o n 限，而复杂度又较低的信道编码方 案。 发展最早的一类纠错码是线性分组码【2 1 ，它以代数中群、环、域和几何理论为 基础，利用各种代数方法构造出码结构简单、编译码复杂度相对较低的码，如汉 明码、r m 码、b c h 码、r s 码等，被广泛应用于通信系统中。但是线性分组码的 译码是以帧为单位的，当帧较长时就会产生较大的时延，同时分组码的译码复杂 度与码长成指数关系，码长越长译码复杂度越大，所以在实际应用中需要对性能 和译码复杂度做出平衡。 另一类重要的信道编码方法是由e l i a s 等人于1 9 5 5 年提出的卷积码p j ，在编码 过程中，使前后的码元之间产生相关性，通过相关性对各码元进行检验。在相同 复杂度条件下可以获得比分组码更高的编码增益，同时它的编译码可以连续进行， 降低了处理时延。尤其是1 9 6 7 年v i t e r b i 提出了v i t e r b i 译码算法【4 】后，卷积码逐渐 得到广泛的应用，而后出现的网格编码调制( t c m ) 技术，使得卷积码可以应用 于带宽受限的通信系统中。 1 9 9 3 年，法国c b r r o u 等人充分利用了s h a n n o n 信道编码定理中随机编码的 条件，将卷积码的并行级联和随机交织器结合起来，提出了t u r b o 码 5 1 1 6 1 ，同时采 用软输出迭代译码算法( m a p 、l o g - - m a p ) 来逼近最大似然译码，为编码领域 带来了一次突破性的革命。目前t u r b o 码已经被用于第三代移动通信系统，并作为 l t e 的协议之一。然而，t u r b o 码也存在一些缺点：如译码复杂度高，译码时延长， 存在错误平层现象等。 1 9 6 2 年，g a l l a g e r 就提出了一种特殊的线性分组码低密度奇偶校验码1 7 】 ( 1 0 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 码，并提出相应的迭代译码概念瞵儿9 。 此后在基于图模型的编译码和迭代译码的研究【lo j 【l l j 过程中，m a c k a y ，n e a l 和 w i b e r g 注意到了l d p c 码与t u r b o 码相比，具有更低的译码复杂度，更强大的纠 错能力和更低的错误平层等优点，尤其在长码时具有超越t u r b o 码的性能。同时由 第一章绪论 于l d p c 码迭代译码算法为并行算法，译码时延远远小于t u r b o 码，这些都为l d p c 码的应用提供了广阔的前景，从而成为目前信道编码理论中新的研究热点。 1 2l d p c 码的发展及主要研究内容 1 9 6 2 年，g a l l a g c r 提出l d p c 码时，就对l d p c 码的编码方法、码的距离特 性分析、概率迭代译码算法、误码性能分析、g f ( q ) 域编码的内容进行了详细的论 述，并证明了这类码具有很好的距离特性，经过迭代译码码字的比特错误概率随 码长呈指数降低，同时给出了在二进制对称信道( b s c ) 、加性高斯白噪声( a w g n ) 信道和瑞利衰落信道下的仿真结果，其性能几乎超过了当时所有的其他信道编码。 但是因为当时计算能力和存储能力的限制，l d p c 码在实际应用中几乎是不可能实 现的，所以没有引起当时人们的关注。 1 9 8 1 年t a n n e r 从图的观点出发重新研究了l d p c 码，提出的l d p c 码的双向 图表示【l 引，从t a n n e r 图上可以直观的理解l d p c 码的译码过程。到上世纪9 0 年代， m a c k a y 和n e a l 等人在深刻理解l d p c 码的基础上，利用随机构造的t a n n e r 图研 究了l d p c 码的性能，证明了l d p c 码确是一种好码，并进一步推广g a l l a g e r 的 概率迭代译码算法，同时论述了采用和积译码算法( s p a ) 的规则l d p c 码具有和 t u r b o 码相似的译码性能，长码时甚至超过了t u r b o 码，极大推动了l d p c 码的发 展。1 9 9 7 年m i c h a e lg l u b y 等人提出了非规则的l d p c 码，并证明了一些非规则 l d p c 码比规则码具有更好的纠错性能。t h o m a sj r i c h a r d s o n 等人在总结了l u b y 的分析方法后，进一步提出了密度进化理论，分析了消息传递译码下l d p c 码的 容量，设计出了接近s h a n n o n 限的非规则l d p c 码，对l d p c 码的构造和设计等 做出了巨大贡献。 自l d p c 码复兴以来，引起越来越多的研究人员的关注，其研究主要集中于 以下四个方面：校验矩阵的构造、译码算法的优化、译码性能的分析及l d p c 码 的实际应用等。 4 基于代数构造的结构化l d p c 码译码算法及其校验矩阵结构研究 1 2 1 校验矩阵的构造 在l d p c 码校验矩阵构造方面，主要分为随机构造和结构化构造两大类。 随机构造方法是根据一定的设计准则和围长、度分布、止集等条件用计算机 随机搜索出所需要的校验矩阵。研究表明一个随机构造的t a n n e r 图以很大的概率 为好的扩展图，而由好的扩展图构造的线性纠错码是渐进好码，从而证明了采用 随机t a n n e r 图构造的l d p c 码以很大概率是渐进好码。g a l l a g e r 采用随机置换的 方法来构造校验矩阵【9 】，m a c k a y 提出的随机l d p c 码构造方法可以使码所对应 t a n n e r 图中环数目较少【1 3 】【1 4 1 ，码字具有很好的纠错性能。为了减少随机构造的矩 阵中环的数量，提高译码性能，x i a o y uh u 等学者采用逐步最优思想，使用 e d g e - b y - e d g e 的方法，提出了一种称为p e g ( p r o g r e s s i v ee d g eg r o w t h ) 的构造方 法【1 5 l ，该算法可以在给定度序列条件下构造较大围长( g i r t h ) 的l d p c 码。事实 上，影响迭代译码性能的因素，不仅有环的长度，还有环的连通性，因此t a ot i a n 等提出了a c e 构造方法【1 6 1 ，在构造l d p c 码时抑制掉连通性差的环，提高了译码 性能。但是随机码的缺点就是编码复杂度比较高。 结构化构造方法是利用代数方法或组合方法构造出所需要的校验矩阵。代数 方法中包括基于循环置换矩阵的方法( 如s h ul i n 等学者提出的准循环低密度奇 偶校验码q c l d p c t l 7 ) 和基于有限几何的构造方法( 如e g 、p g l d p c 码【2 】) 。采 用结构化构造方法构造的循环码或准循环码具有较好的距离特性，能有效消除 t a n n e r 图中的长为4 的环，获得较好的译码性能，同时硬件实现也相对简单。此 外，基于r s 码构造的q c l d p c 码也具有良好的最小距离特性。 1 2 2 译码算法的优化 目前l d p c 码的译码主要分为两大类。一类是g a l l a g e r 基于概率提出的消息 传递算法( m e s s a g ep a s s i n ga l g o r i t h m ，m p a ) ，也称置信传播( b e l i e f p r o p a g a t i o n ) 迭代译码算法，这类算法属于软判决译码，在码长较大时性能可逼近香农限，但 它的译码复杂度较高。为了简化b p 译码算法，先后产生出和积算法( s u m - p r o d u c t a l g o r i t h m ，s p a ) 、b p b a s e d 算法( 也称最小和算法( m i n s u ma l g o r i t h m ) ) 、 n o r m a l i z e db p b a s e d 算法和o 髋e tb p b a s e d 算法等一系列的改进算法，使软判 决译码在实践中得到广泛利用。另一类是基于校验和统计迭代的比特翻转 ( b i t - f l i p p i n g ，b f ) 译码算法，此类算法属于硬判决译码，算法操作简单易于实 现，但性能较差。因此对其改进的算法如加权b f 算法( w b f ) 等，通过结合接收 符号可靠性、引入“环检测和比特翻转约束机制等措施，使其译码性能逐步接 第一章绪论 5 近b p 算法，不过这样也使算法的复杂度有所增加。 1 2 3 译码性能分析 目前l d p c 码的译码性能分析主要分为密度进化( d e n s i t ye v o l u t i o n ) 、高斯近 似( g a u s s i a na p p r o x i m a t i o n ) 和e x i t 图( e x t r i n s i ci n f o r m a t i o nt r a n s f o r mc h a r t ) 三种模式。 g a l l a g e r 在研究规则码硬判决译码时发现，在l d p c 码的迭代译码中存在一种 阈值现象，在信道噪声水平低于阈值时，随着码长趋于无穷大，码的错误概率可 以任意逼近零，反之错误概率将大于一个正的常数而不能逼近零。r i c h a r d s o n 等人 在g a l l a g e r 研究的基础上提出了密度进化理论【l 引，通过分析传递信息的概率密度 的进化情况，发现在和积译码算法的每次迭代信息传递中出现错误的信息部分可 以递归地表示成l d p c 码的度分布序列和信道参数的函数。通过迭代计算节点间 传递的信息的概率密度函数，证明了阈值现象的存在性并给出了一种搜索好的节 点度分布对的数值优化技术。但密度进化算法复杂度相当大，为提高密度进化算 法的计算速度，c h u n g 等人采用了高斯近似的方法【1 9 】，即根据中心极限定理可以 近似认为节点间迭代的信息的概率密度函数是符合高斯分布的，这样就将计算多 维问题转化为更新高斯密度均值的一维问题，大大简化了分析和计算信道参数阈 值的复杂度。 e x i t 图由b r i n k 首次提出，与密度进化方法类似，e x i t 图也可以用于分析 l d p c 码集合的阈值现象【2 0 l f 2 l j 。将l d p c 码的译码过程看作是变量节点译码器和 检验节点译码器之间外部信息的迭代，用e x i t 图在迭代的过程中跟踪的是互信息 的值。这样可以比密度进化方法的计算量小得多。 1 2 4l d p c 码的应用 由于l d p c 码与t u r b o 码相比具有三大优势：首先，l d p c 码具有一整套较为 系统的优化设计方法、更强大的纠错能力和更低的错误平层；其次，l d p c 码的迭 代译码算法为并行算法，可以实行并行操作，易于硬件实现；第三，l d p c 码本身 具有抗突发差错特性，不必引入交织器，减小了处理时延。因此，l d p c 码可以在 信道条件较差的无线移动通信中使用，并可在光纤通信、卫星数字视频和声频广 播、磁光全息存储、数字用户环线中得到广泛应用。 6 基于代数构造的结构化l d p c 码译码算法及其校验矩阵结构研究 1 3 本文研究内容和行文安排 本文主要研究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 码的代数构造方法 7 第二章l d p c 码的代数构造方法 本章首先系统地介绍了l d p c 码的定义和图、环等基本概念，针对校验矩阵 的r c 准则介绍几种构造校验矩阵的方法重点是各类代数构造方法 2 1l d p c 码的定义 一个码长为甩，信息位个数为k 的线性分组码可以由一个生成矩阵q 砌来定义， 信息序列s 通过生成矩阵g 被映射到码字x - - $ g 。线性分组码也可以由其一致 校验矩阵q 。t 来描述，所有码字均满足x h r = 0 。校验矩阵的每一行代表一个 校验方程，校验矩阵的每一列表示一个码元变量参与的校验方程运算。当列元素 不为零时，表示该码元变量参与了该行的校验约束。码元变量与校验方程之间构 成了结构。 l d p c 码也是一种普通线性分组码，同样可以用生成矩阵和校验矩阵来唯一确 定。g a l l a g e r 最早定义规则l d p c 码就是基于校验矩阵h ，具体来讲校验矩阵h 要满足以下条件： ( 1 ) 每一行有p 个1 ； ( 2 ) 每一列有价l ； ( 3 ) 任何两列( 或两行) 之间位置相同的1 的个数( 以九来表示) 不大于l ， l i 0 x = 0 或者x - - 1 ； ( 4 ) 与码长和h 的行数相比，p 和榔非常小； 其中条件( 1 ) 和( 2 ) 表明奇偶校验矩阵h 具有不变的行重p 和列重y ：( 3 ) 表明h 中没有任何两行或两列具有超过一个相同位置的l ，我们称之为行列约束 条件( r cc o n s t r a i n t ) ；( 4 ) 说明行重p 和列重郝小于码长和h 的行数。所以h 矩 阵中l 的数量很少，这也是h 被称为低密度奇偶校验矩阵( 1 0 w - d e n s i t yp a r i t y - c h e c k m a t r i x ) 的原因。校验矩阵的密度，定义为h 中l 的总数与h 中元素总数的比值， 即，= p i n = y i j ，j 为h 的行数。由定义可知，h 是一个稀疏矩阵。如定义给出 的，行重p 和列重涸定不变的l d p c 码称为规则( r e g u l a r ) l d p c 码，否则称为非 规则( i r r e g u l a r ) l d p c 码。 3 基于代数构造的结构化l d p c 码译码算法及其校验矩阵结构研究 2 2t a n n e r 图表示l d p c 码 除了用一致校验矩阵h 定义l d p c 码外，还可以用双向的图模型来表示l d p c 码，t a n n e r 图是其中最方便的一种。利用t a n n e r 图可以形象地刻画l d p c 码的编 译码特性。 2 2 1t a n n e r 图 t a n n e r 图可以用g = ( y ，e ) 表示，其中y 是节点的集合，包括变量节点k 和校 验节点圪，即v = 圪uk 。变量节点圪= ( 6 i ，b 2 ，色) 对应着h 的列，校验节点 圪= ( c l ，c 2 ，气) 对应着h 的行。对于m x n 维的校验矩阵h ，有m 个校验节点和n 个变量节点。e 是节点之间相连的边的集合，变量节点与变量节点之间、校验节 点与校验节点之间没有相连的边，只在两类节点之间存在边。如果t a n n e r 图的第， 个变量节点6 ，与第f 个校验节点q 之间有一条边相连，记为( q ，6 ，) e ( q ，6 ，) ，则表 示校验矩阵的第砰i ：第，列元素是非零的，即h 中红，= 1 。如式( 2 1 ) 所示校验矩 阵： h = l00 l 101 o0l1lo0 l1o0o11 o1l0olo 则与它相对应的t a n n e r 图可表示为： v l 吃bk 鸭v 7 c lc 2 c 3 c 4 图2 1 校验矩阵的t a n n e r 图表示 ( 2 - 1 ) 第二章l d p c 码的代数构造方法 9 2 2 2 度分布 在t a n n e r 图中，节点的度数( d e g r e e ) 定义为与此节点相连的边的数目。因 此变量节点的度数即与该变量节点相连的校验节点的数目，校验节点的度数即与 该校验节点相连的变量节点的数目，分别用五和p 表示。对应于校验矩阵，变量节 点的度等于h 矩阵中对应列的重量，校验节点的度等于对应行的重量。如果一个 l d p c 码的t a n n e r 图中所有变量节点的度相同( 同为名) ，并且所有校验节点的度 也相同( 同为p ) ，则称该l d p c 码为( 名，p ) 规则l d p c 码；如果变量节点的 度不同或者校验节点的度不同，则称该l d p c 码为非规则l d p c 码。 对于非规则l d p c 码，由于变量节点之间和校验节点之间的度数不相同，故 通常采用度分布序列来表示其度分布情况，即用序列 五，五，丸) 和 a ，岛，氏 来分别表示。其中五( p ，) 表示与度为f 2 的变量节点( 校验节点) 相连的边数 占总边数的比率。如果用吐，和以分别表示变量节点和校验节点的最大度数，则可 构造多项式 如 砸) = 1 f = 2 4 p ) = 乃x 一 ( 2 2 ) t j 一 并规定2 ( 1 ) = 夕( 1 ) = l 且磊= l 砣p j = 1 。五 ) 、p ) 称为度数分布如图2 1 f = 2 j - - 2 中，其变量节点的度均为2 ，校验节点的度均为4 ，因此它是( 2 ，4 ) 规则l d p c 码。 2 2 3 环 在t a n n e r 图中，从某个节点出发沿某条路径( p a t h ) 前进，最终又回到该节 点就构成一个环( c y c l e ) ，环中包含的边的个数称为环的长度( 或环长) ，其中最 短的环长称为该t a n n e r 图的围长 3 ，职m 时，h 。中将不存在长为4 的环。 例2 1 令m = 刀= 4 ，则按照式( 2 - 6 ) ，可以得到一个m x n 的矩阵s ( k ) ，作 为校验矩阵日的位置矩阵。 s ( ) = 0 1 23 4691 3 581 21 7 7l l1 62 2 位置矩阵s ( ) 中的元素即为单位阵进行循环移位的次数口：l 。在得到与吩对应的 循环置换矩阵后，将所有循环置换矩阵替换s ( ) 中相应位置的元素，即得到 h 喇。 2 4 2 基于r s 码构造的l d p c 码 此方法是基于具有两个信息符号的缩短的r s 码的构造方法。因为r s 码是极 大最小距离码，具有良好的纠正突发错误的性能，并且结构简单，实现容易，因 此在无线通信、移动通信、光通信磁介质存储等方面得到广泛应用。而基于r - s 码 构造的l d p c 码不但继承了r s 码的优点，更使编译码复杂度进一步降低。 令口为伽罗华域g f ( q ) ( q = p 5 是一个素数的幂) 上的一个本原元。令p 是一 个正整数且2 p g ，则在伽罗华域g f ( q ) 上，长度为q - i ，维数为q - p + l ，最 小距离为p 一1 的循环( g 一1 ，q - p + l ，p 一1 ) r s 码c 的生成多项式为： g ( x ) = ( x 一叻( x 一) ( z 一矿- 2 ) = g o + 蜀x + 9 2 x 2 + x 户- 2 ( 2 - 7 ) 其中爱g f ( q ) 。然后我们通过删除c 的每个码字的q - p - 1 个信息符号来缩短c ， 则我们将得到只有两个信息符号的，2 ，p - 1 ) 缩短的i 峪码g 。该缩短码的生成矩 阵为： g = 一象g 蜀2 , oo 协8 ， g 中的非零码字有夕和p - 1 两种重量，且g 的最小距离为p - 1 ，则g 中的两个 码字至多只有一个位置具有相同的码符号。g 6 的两行在g f ( q ) 上的所有线性组合 就给出了c 的所有9 2 个码字。 第二章l d p c 码的代数构造方法 1 5 从g 中找到一个重量为p 的非零码字1 ，则g 中的g 个码字的集合 c b o ) = 卯：c g f ( q ) ) 构成了g 的一个子码，最小距离为p 。基于子码c b n ，我们将c 6 划分为g 个陪集， c b n 、c b 孙、c b 钉。将一个陪集c b d 中的g 个码字组成一个g p 阵列m ，则 此阵列任意一列的所有q 个元素各不相同。 我们定义元素的位置向量为g f ( 2 ) 上的g 维向量， z ( ) = ( o ，0 ，0 ，1 ，0 ，o ，0 ) ( 2 - 9 ) 其中只有第f 个位置为1 ，其他位置为0 。将陪集c b 。中的每个码字中的户个元素 都用它的位置向量表示，则阵列m 将变成g p g 的新阵列，我们成为陪集g 的 位置阵列骂。若我们在所有g 个陪集中选择厂个陪集( 1 y 中。我们把g f ( 2 4 ) 看做是g f ( 2 2 ) 的欧式几何 第二章l d p c 码的代数构造方法 1 9 e g ( 2 ，2 2 ) ，则下面的点 4 = 一+ 0 口，= 4 + 1 口，矿= 4 + 夕口，o = 4 + 夕2 口 构成一条通过点4 的直线。欧式几何e g ( 2 ，2 2 ) 中其他几条过4 的直线为： 4 ，3 口，矿 ， 4 ，扩，矿， ， 4 ，矿，扩，