（通信与信息系统专业论文）ldpc码译码研究与fpga实现.pdf

浙江工业大学硕士学位论文 l d p c 码译码研究与f p g a 实现 摘要 在当前通信业务剧增的背景下，人们对通信系统的有效性和可靠性的要求也进一步提 高。而信道编码技术是解决通信系统内信道传输过程中信息损失的重要手段。作为被重新 受到关注的l d p c 码具有接近香农极限的优良信道编码性能。能广泛的应用在通信系统和 数字存储系统中。所以l d p c 码的实现研究是研究的热点，同时也具有重大的实际意义。 本文基于l d p c 码对其构造和编码做了简单介绍，主要对于q c l d p c 码的几种软判 决译码算法进行了详细的推导。然后在m a t l a b 环境中进行仿真。最后选取修正最小和算法 作为本文的译码算法。并对算法中的参数进行了仿真，确定了译码实现中算法的最大迭代 次数、偏移因子值以及数据量化位宽。 然后基于x i l i n xv e r t e x i ip r o 系列f p g a 对修正最小和算法进行算法实现。对实现整 体架构中的各个功能模块设计进行详细介绍，并基于m o d e l s i m 给出了主要功能模块的时 序仿真图。最后在i s e l 0 1 环境中进行综合，并根据综合报告分析了算法的性能。基本达 到设计要求。 最后基于x i l i n xe d k 嵌入式开发工具搭建了一个针对译码器的s o c 测试平台。通过 p c 产生编码数据，经串口给s o c 系统进行译码。然后再由串1 5 1 将译码后的数据返回p c ， 进行数据对比分析其误比特率。 关键词：l d p c 码译码器，修正最小和算法，f p g a ，s o c 浙江工业大学硕士学位论文 r e s e a r c ho i ld e c o d i n g a l g o r i t h m sf o r l d p cc o d e sa n d f p g a i m p l e m e n t a t i o n a b s t r a c t u n d e rt h eb a c k d r o po fd r a m a t i ci n c r e a s ei nt h ec u r r e n tc o m m u n i c a t i o nb u s i n e s s ，t h e d e m a n d so fv a l i d i t ya n dr e l i a b i l i t yo ft h ec o m m u n i c a t i o ns y s t e mh a db e e nf u r t h e re n h a n c e t h e c h a n n e lc o d i n gt e c h n i q u e sa r ea ni m p o r t a n tm e a n st os o l v et h ei n f o r m a t i o nl o s si nt h ep r o c e s so f c h a n n e lt r a n s m i s s i o nd u r i n gc o m m u n i c a t i o ns y s t e m t h el d p cc o d e sh a sag o o dc h a n n e l c o d i n gp e r f o r m a n c en e a rt h es h a n n o nl i m i t i tc a nb ew i d e l yu s e di nc o m m u n i c a t i o ns y s t e m sa n d d i g i t a ls t o r a g es y s t e m s t h u si t i sah o tt o p i cr e s e a r c ho ni m p l e m e n t a t i o na b o u tl d p cc o d e s ， m o r e o v e rt h er e s e a r c hh a sag r e a tp r a c t i c a ls i g n i f i c a n c e f i r s t l y ，t h i st h e s i sh a sab r i e fi n t r o d u c t i o no nt h eh m a t r i xc o n s t r u c t e da n dl d p cc o d e s e n c o d i n g t h e ns e v e r a ls o f t d e c i s i o nd e c o d i n ga l g o r i t h m sa b o u tq c l d p cc o d e s a r ed e t a i l e d p r e s e n t e d ，a n ds i m u l a t e di nt h em a t l a b f i n a l l ys e l e c tt h eo f f s e tm i n s u ma l g o r i t h m sa st h i s t h e s i s sa l g o r i t h m a n ds o m ep a r a m e t e r so ft h i sa l g o r i t h ms u c ha st h em a x i m u mn u m b e ro f i t e r a t i o n s ，t h eo f f s e tn u m b e ra n dt h ed a t aw i d t ho fq u a n t i z a t i o na r ed e c i d e db ys i m u l a t i o n s e c o n d l y ，i m p l e m e n tt h eo f f s e tm i n s u ma l g o r i t h mb a s e do nt h ef p g a o fx i l i n xv e r t e x 。i i p r os e r i e s p a r t i c u l a rd e s c r i b eo fe a c hf u n c t i o nm o d u l ed e s i g na n dm a i n l yt i m i n gs i m u l a t i o n d i a g r a m t h e ni m p l e m e n tt h e mb yi s e 10 1 ，a n da n a l y z e dt h ep e r f o r m a n c eo fa l g o r i t h mf r o m s y n t h e s i sr e p o r t t h er e s u l ts h o w s i tm e e tt h ed e s i g nr e q u i r e m e n t s f i n a l l y ，s e tu pas o c t e s tp l a t f o r mf o rl d p cd e c o d e rb yx i l i n xe d k t h r o u g ht h es e r i a l p o r t ，t r a n s m i tt h ed a t at h a te n c o d e db yp c t os o ct e s ts y s t e mt od e c o d i n g a n dt h e nt h ed e c o d e d a t ab a c kt op ct h r o u g hs e r i a lp o r t l a s t l y ，a n a l y z e dt h eb i te r r o rr a t eb yc o m p a r i n gt h eo r i g i n a l d a t aw i t hd e c o d ed a t a k e yw o r d s ：l d p cd e c o d e r ，o f f s e tm i n - s u m ，f p g a ，s o c 浙江工业大学硕士学位论文 第1 章绪论 随着数字通信技术的发展和人们对多媒体信息日益增多的需求，高带宽、高容错能力 的通信系统显得日趋重要。从模拟通信时代过渡到数字通信时代后，大量的通信新技术被 采用，以根据应用的需求平衡通信中一对矛盾，即有效性与可靠性。针对现代的多媒体通 信，既需要高的有效性来满足大信息量传输的要求，同时也需要高的可靠性来满足复杂环 境下可靠传输的要求。信道编解码技术就是解决这一问题的关键部分之一。 1 1 研究背景及意义 数字通信系统可以方便的进行差错控制，可以应用现代数字信号处理，可以综合传输 各种信号。其基本的组成结构为信源、信源编码、信道编码、调制、信道加噪、解调、信 道解码、信源解码、信宿，其模型如图1 1 所示。在实际应用中，不仅移动通信系统、数 字电视以及数字广播、无线或有线因特网接入属于数字通信系统，数字计算机的存储系统 及内部运算等也属于数字通信系统。 图1 1狮字诵信系缔 在图1 1 模型中，信源提供的消息可为连续的信号也可为离散的序列信号。通常信源 信息为随机的，可由随机变量或随机过程来描述。信号经采样量化后形成数字信号给予后 续模块处理。信源编码是为了减少信源输出信号的剩余度、提高符号的平均信息量而对信 源输出序列进行的变换。信道编码为了对抗信道中的噪声和衰减，通过增加冗余来提高抗 浙江工业大学硕士学位论文 干扰能力与纠错能力。为了更适应信道的传输形式，需通过调制将基带信号调制到载波上 进行传输。解调、信道解码、信源解码即为调制、信道编码、信源编码反过程。信宿为接 收经传输后的信息的终端。 香农1 9 4 8 年在一篇论文【l 】中证明，只要信息传输速率低于信道容量，通过对信息适当 进行编码，可以在不牺牲信息传输或存储速率的情况下，将有噪信道或存储媒质引入的差 错减到任意低的程度【2 】。根据香农的这一理论，众多学者对一系列编码算法简单的好码以 及优秀的译码方法展开了研究。 在信道编码技术中，如果将信源的信息序列按照独立分组进行处理和编码，那么这种 编码方式叫做分组码。否则叫非分组码，卷积码是其中最主要的一类。线性分组码中，最 主要、最有用的一类是循环码，它是1 9 5 7 年由p r a n g e 首次提出并进行研究的。可以用反 馈线性移位寄存器方便地实现编码以及伴随式的计算是循环码最大的特点，且因为循环码 拥有众多的固有代数结构，因此可以找到各种简单实用的译码方法【3 】。由于循环码的这些 特点，在理论和实践中都得到了重要应用。主要的循环码有b c h 码、r s 码、g o l a y 码等。 作为传统编码技术的卷积码由e l i a s 于1 9 5 5 年最早提出，随后w o z e n c r a f t 于1 9 5 7 年 提出了序列译码方法。真正让卷积码从理论走向实用的是m a s s e y 于1 9 6 3 年提出的门限译 码方法。1 9 6 7 年，v i t e r b i 提出了最大似然译码算法，即如今被广泛应用在现代通信中的维 特比算法。卷积码因为在编码的过程中通过寄存器增加了码元间的相关性，因此相比其它 编码能在相同复杂条件下表现出更高的编码增益。结合维特比译码算法，卷积码得到了更 广泛的实际应用。但在实际的通信信道中，为了对付既不是单纯随机独立也不是明显单个 突发差错的混合差错时，级联码是非常有效的。级联码是由短码构造长码的一类有效方法， 最早由f o m e y 提出。通常它由外编码器和内编码器组成，外编码器一般采用r s 码，内编 码器一般采用卷积码。采用这种构造方法使得构造出来的长码不需要复杂译码设备。 虽然随着级联码技术的成熟和其译码算法的完善，以及各改进技术的提出，让编码系 统的编码系统不断提升。但受限于编码性能界限，这些编码技术在性能上总不能逼近香农 极限。直到1 9 9 3 年，b e r r o u 等人在i c c 国际会议上提出一种采用重复迭代译码算法的并 行级联码，即t u r b o 码。通过伪随机交织器并行级联构造伪随机长码和采用两个软输入 输出译码器之间进行多次迭代实现伪随机译码，使t u r b o 码性能接近s h a n n o n 极限。正因 为有如此好的性能，t u r b o 码受到了移动通信领域的广泛重视，特别是在非实时数据通信 领域以及第三代移动通信中得到广泛应用。 在t u r b o 码拥有众多优点的同时，也有一些制约性的缺点。如其译码设备很复杂，译码 浙江工业大学硕士学位论文 延时太大，无法应用于实时通信系统等。也正是由于这些原因，让人们开始重新关注起 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 码获得了人们的重视并持 续成为研究热点。 1 2l 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 k ) 码实质是一种纠错性能优良，接近香农极限的线性分 组码。其编解码基本原理及迭代解码算法最早由g a l l a g e r 于1 9 6 2 年在他的博士论文中提出 并做了详细的描述【4 】。但在当时的时代背景下，由于硬件实现能力的限制，l d p c 码并未 得到人们的重视。1 9 9 3 年，b e r r o u ，g l a v i e u x 和t h i t i m a j s h i m a 提出了t u r b o 码的信道编码 方案，展现了高的编码效率和低的编码复杂度，在其后的发展中也得到了广泛的应用。1 9 9 6 年，m a c k a y 和n e a l 对l d p c 的研究成果使得l d p c 码重新得到了重视，并让l d p c 跨入 了一个新的研究阶段。其间于1 9 8 1 年，t a n n e r 引入了l d p c 码的图描述，即后来称为的 t a n n e r 刚5 | 。1 9 9 8 年，l u d y 等人提出了不规则l d p c 码，将l d p c 码的研究从规则码推 进到了不规则码，不规则码表现出来的性能高于规则码。1 9 9 9 年，r i c h a r d s o n 等研究者在 研究中发现l d p c 码在码长足够长的情况下，a w g n 环境中不规则l d p c 码的性能只跟香 农极限差0 1 3 d b 6 i 。2 0 0 1 年，c h u n g 等研究设计的l 2 码率的l d p c 码非常接近于香农极 限，仅相差0 0 0 4 5 d b 【7 1 。而最近几年g f ( q ) ( q = 2 p ) ( 多元域) 的l d p c 码研究，更是体现 了其极高的性能，在文献【8 】中有相关论述。另外基于传统l d p c 码改进的研究也随着应用 不断被推进。如k u e n t s a i rl a y2 011 年在论文 9 1 中提出的一种n h l d p c ( n o n h o m o g e n e o u s l d p c ) 码，在保密通信中能表现出很高的性能。 随着l d p c 码的研究重新得到重视，其重点研究点表现在以下两个方面。 其一，在编码端的研究热点主要体现在h 矩阵的构造和在编码过程中g 矩阵的生成或 直接利用h 矩阵编码上。 l d p c 码的优良特点主要来自于在其稀疏校验矩阵上，要构造一个好的l d p c 码编译 码系统其关键和难点就是构造一个好的h 矩阵。目前关于l d p c 码h 矩阵的构造在国际 上研究很火热，一些国际权威杂志上也有一些相应很好的文章和研究课题。但目前关于这 个方面的研究难度还是很大。现有的h 矩阵主要构造方法有随机构造和代数构造。在实际 1 浙江工业大学硕士学位论文 应用系统中应用较多的是准循环( q u a s i c y c l i c ) 码。因其性能优越，更为关键的是非常适合硬 件实现。另外一个研究的热点是非g f ( 2 ) 且i ig f ( q ) 上的l d p c 码构造。在非o f ( 2 ) 上，好的 校验码能让l d p c 码表现出了更高的性能。在此方面的研究，m a c k a y 和d a v e y 有很多的 探索与尝试，并取得了相应的一些成果1 8 。 在编码过程中，主要研究点体现在两个方面。一方面是校验矩阵变换为生成矩阵过程 中，往往校验矩阵具有良好的稀疏性，而生成矩阵失去了这种良好的稀疏性。目前解决此 问题的主要方法主要为高斯消元法。另一方面同时也是目前编码的主要应用和研究点是怎 样通过校验矩阵直接进行编码而不经过校验矩阵生成矩阵的变换。目前相关的主要算法研 究基本上都是基于r u 算法和r a 算法而展开的。除此之外，跨层联合编码的构造方法及 编码算法也将会成为未来的研究重点【1 们。 其二，l d p c 码译码端的研究主要体现在译码算法研究和硬件的实现上。从判决方法 上译码算法分为硬判决译码和软判决译码以及两者相结合的译码。下节将对译码算法及硬 件实现现状做简要介绍。 1 3l d p c 码的译码算法研究与硬件实现现状 l d p c 码自g a l l a g e r 提出以来，之后的几十年之所以没有得到很好的研究与应用很重 要的原因是其译码算法研究没有得到很好的进展，同时也受限于当时的硬件实现水平。 g a l l a g e r 在提出l d p c 码的同时也提出了相应的译码算法，这种译码算法是基于校验和统 计迭代的硬判决译码算法( b i tf l i p p i n g ) 。其思想是将译码输入的数据进行硬判决，得到0 ，1 序列后直接代入校验方程计算校验结果，然后将校验方程不成立最多的变量节点所对应的 比特数翻转，完成一次迭代，接下来重复这个过程，直到所有校验方程都成立。其硬件实 现运算量小，复杂度低，但是性能差。因此基于此的改进算法及实现方法仍在研究中，目 前此译码算法只适合在信道条件较好或者做算法估计的情况下应用。 另外一种研究最多也是应用中所常采用的译码算法是软判决译码算法。这种算法是基 于概率的置信传播( b e l i e f p r o p a g a t i o n ) 迭代译码算法。该算法充分利用了信道输出波形的信 息，通过基于置信传播的迭代算法【l ，能将l d p c 码的性能无限接近香农极限。但是在该 算法取得高性能的同时，也给译码器的硬件实现带来了困难。因为在该算法中有大量的乘 法运算，不利于硬件的实现。为此基于b p 的各种改进算法被提出。基本的b p 算法是在概 率域上进行运算，存在大量的乘法运算，复杂度高。而如果将其转换到对数域上进行b p 4 浙江工业大学硕士学位论文 算法( l l rb p ) 则可将概率域上的大量乘法运算转换为加法运算，从而减少计算时间和复杂 度。c h e n 和f o s s o r i e r 等提出了基于对数似然比的置信传播算法【1 2 】，有利于硬件的实现。 虽然在l l rb p 算法的实现中乘法运算的复杂度消除了，但是在算法迭代的过程中，部分 函数的实现需要采用查表的方式进行运算。这样虽在运算精度上得到了尽量的保证，但同 时也消耗着大量的硬件逻辑资源。鉴于此，一些改进算法被提出，如最小和算法，改进最 小和算法( m i n s u n 、n o r m a l i z e dm i n 。s u m 和o f f s e tm i n s u m ) 等。在这些改进的算法中，在 不损失过多性能的前提下，大大的简化了硬件实现的复杂度。也正因为如此，最小和算法 得到了广泛的实际应用。本文所研究和采用的译码算法也是基于最小和算法而展开的。另 外除了置信传播算法，目前还有各种基于其它原理的算法。比如基于差分的译码算法【l3 1 ， 这种算法避开了目前常见的对数似然比算法，在特定的加法域进行运算。还有借鉴t u r b o 码解码算法的软输入软输出( s i s 0 ) 算法，及在此基础上的改进算法等【l4 | 。还有在实时低功 耗方面，基于s i m d 处理器架构的软解码算法【15 | 。 理论的研究最终以应用为目的。l d p c 码的优良性能近些年来得到重新的重视和研究 也促使其硬件实现快速发展。目前，l d p c 的编译码芯片已经问世，并应用在了一些领域。 如f l a r i o n 公司已推出的基于a s i c 的v e c t o r - l d p c 解决方案，大约使用2 6 0 万门，就可以 支持高达5 0 0 0 0 的码长，码率为0 9 ，最大迭代次数为1 0 ，译码器的吞吐量可以达到1 0 g b p s 。 这样的性能已经可以满足大多数的通信应用。虽然因为l d p c 码的发展滞后导致未能在第 三代移动通信中应用，但是就目前它的应用领域和未来的发展趋势，l d p c 码的广泛使用 已是趋势。因此l d p c 码的硬件实现研究也持续成为热点。根据不同的硬件载体，硬件实 现的研究主要分为两个方向，一个是以f p g a 或v l s i 为基础的纯逻辑实现，一个是以处 理器( c p u 或g p u ) 为基础的架构实现。其中以f p g a 或v l s i 为基础的硬件实现是目前大 多数研究的方向。很多的硬件实现算法都是在f p g a 平台上进行实现和验证的。一些企业 和研究机构也在基于此开发相应的i p 核和编解码芯片。如a h a 公司和意大利半导体公司 已具有d v b s 2 中l d p c 码的i p 核和编解码芯片。x i l i n x 公司也提供了支持d v b s 2 信道 编码的l d p c 码编码器的i p 核。近几年复旦大学专用集成电路与系统国家重点实验室针对 c m m b 、d t m b 多模应用基于t d m p 算法所实现的v l s i 在0 1 3 u r n 工艺下，实现了逻辑 等效门7 5 万门，存储器容量为3 5 9 4 2 4 b i t ，最高时钟频率可达2 0 0 m h z ，2 0 次迭代情况下 数据吞吐率可达3 0 0 m b p s 【l6 | 。对于基于处理器为基础的方案，g a b r i e l 等人提出的基于流的 l d p c 译码算法l l 川，采用s i m d 处理，分别在c p u 和g p u 上进行了实现，取得了好的效 果。 浙江工业大学硕士学位论文 目前l d p c 码在实际应用上很广泛，除 $ d b c h 码联合应用在d v b s 2 标准信道编码中 外，i e e e 8 0 2 1 6 e 标准( w i m a x ) 和u w b 的信道编码也采用了 l d p c 码。此外在卫星通信、深 空通信、光通信、第4 代移动通信系统、高速与甚高速率数字用户线、分布视频压缩编码 及联合编码、光和磁记录系统等方面也得到广泛应用。信道编码领域的急切需要也进一步 促进了l d p c 码编译码和硬件实现的研究。 1 4 主要工作和内容安排 由于时间和个人能力有限，本文主要的创新点体现在l d p c 译码f p g a 实现过程中迭 代的处理上，以及最后将l d p c 译码器作为i p 核搭建基于硬件的s o c 通信系统，为以后 将此i p 核应用到实际中做了初步的试验工作。 本文具体结构安排如下： 第一章绪论。作为绪论的本章主要介绍了在通信系统中信道编码的地位、l d p c 码发 展历史与研究现状以及主要的研究点、l d p c 码的译码算法及硬件实现现状、l d p c 码的 应用状况及研究意义。 第二章主要介绍l d p c 码的基本概念原理及表述方式。讨论本文译码部分对对应的 校验矩阵构成及编码原理。 第三章主要介绍l d p c 码的典型译码算法实现原理，包括硬判决译码和软判决译码。 重点介绍了软判决译码中对数似然比算法及其改进算法进行性能仿真。并根据系统要求对 影响l d p c 码译码性能的参数进行论证与仿真分析。最后通过仿真确定译码所采用的译码 算法及相关参数，以便f p g a 的实现。 第四章主要介绍了f p g a 开发的主要流程，根据系统要求进行了l d p c 码译码算法 实现架构的分析并最终给出设计方案。详细介绍了f p g a 实现整体架构中的各个主要功能 模块的划分及时序逻辑的设计。给出各模块的功能介绍、设计框图及主要模块仿真波形。 最后结合i s e 综合报告分析算法性能。 第无章主要介绍了基于s o c 测试验证系统的搭建与l d p c 码译码验证步骤。包括测 试方案的确定，s o c 系统的搭建，下板测试与验证。 第六章最后对全文进行总结，分析论文中存在的问题，并给出未来还需要进一步研 究的方向。 浙江工业大学硕士学位论文 第2 章l d p c 码基础理论 l d p c 码是一种线性分组码，具有线性分组码的所有性质。由第一章知道，l d p c 码 根据不同的分类准则可分成不同的类别。在本章，先介绍线性分组码的一些理论基础，这 些理论基础也是研究其它各类编码的基础。然后介绍l d p c 码的基本概念及描述方式。最 后介绍一些主流的l d p c 编码方法及本文所研究的译码器对应的编码方案。 2 1 线性分组码基础 线性分组码是分组码中最重要的一类码，是研冗各类编码的基石出。凶在通信及存储系 统中编码主要是以二进制0 和1 为主，所以在此讨论的线性分组码是在二元域g f ( 2 ) i 拘基 础上进行的。在非二元域上，二元域上所得出的结论可进行直接推广。 线性分组码的定义为：一个长度为n ，有2 。个码字的分组码，当且仪当其2 。个码字构 成域g f ( 2 ) 上所有，2 维向量组成的向量空问的一个k 维子空间时被称为线性p 码【翻。从 线性空间以及物理意义来看，线性分组码实际是利用了线性空间的扩展。即由k 维扩展到 聆维，利用被扩展的，2 一k 维来进行发现以及纠正信道传输中的差错。 线性分组码可以通过生成矩阵g 或者校验矩阵h 来描述。码字通过生成矩阵g 来生 成。设生成矩阵g 2g 胁，则生成的码字集合可以表示为： c = 忙碍”删，) 亿， l l j 公式中，g 。为生成矩阵g 中的第i 列。由于g 矩阵与h 矩阵有如下转换关系： g = 陬。圳 ( 2 2 ) h = = i 弓一t ) 。t i ( 。一。) 。( 。一t ) ( 2 3 ) 所以生成的码字也可由校验矩阵表示为： c = z 碍ix , 红= o ，i = 1 ，2 ，2 一k ( 2 4 ) 公式中，h i 为校验矩阵h 的第i 行，船为码长，k 为信息比特数。当校验矩阵h 确定 浙江工业大学硕士学位论文 了，线性分组码也就确定了。 由上可知生成矩阵g 与校验矩阵h 还有以下关系： g h t ：0 或h g t = 0 t ( 2 5 ) 设一个长度为七的信息序列u ，要将其编码为长度为，z 的码字c ，由前面的表达式可知 编码方法是将信息序列与生成矩阵相乘，如下： c ：u g ( 2 6 ) 编码后的码字c 满足如下关系式： h c t ：0 t 或c - h t = 0 ( 2 7 ) 在线性分组码的译码中，最常用的是最小汉明距离准则。汉明距离由两个码之间的汉 明重量来定义，如下式。 a ( c 。o c ：) = 形( c 。o c ：) = ：。( c 。，o c 2 ，) ( 2 8 ) 在接收端，设接收到的信号为： y = ( y o y l y n 一1 ) ( 2 9 ) 且：y = c o e 其中c 2 ( c o o l 气) ，e = e o e e ) 。c 表示发送的码字，e 表示传输中的差错。 由h c t = 0 t 可得，如果码字在传输中没有差错( e = 0 ) ，则此校验式一定成立。若传输中 有差错( e o ) ，则有： h y t = h ( c o e ) 1 = h c t h e t = h e t = s t ( 2 1 0 ) 且：s = s t ) t = ( h y t ) t = y h t = c 。e ) h 7 = c h t 。e h t = e h t 其中，s 仅与e 有关，故被称为校正子。由上可知，因h 矩阵是一个亿一助行胛列的矩 阵，则s 是一个( n 一幼维矢量。由s 可以得出( 一幼个独立方程，而e 是一个n 维矢量，有玎 个待定值，所以上面两个伴随式的解不是唯一的。因此在译码中，为了找到最佳的错误图 样，采用最小汉明重量来判断，使译码平均错误概率最小。 2 2l d p c 码基础理论 本节先简单介绍关于图描述的理论，然后介绍l d p c 码的定义及描述方法。并讨论不 浙江工业大学硕士学位论文 同分类的l d p c 码的特点。 为了描述l d p c 码及后面编码原理的介绍，先简单介绍t a n n e r 图。m i c h a e lt a n n e r 利 用t a n n e r 图的迭代方法发现了t u r b o 码，因此这种图被命名为t a n n e r 图【1 8 】。l d p c 码可以 通过t a n n e r 图得到很好的表示和形象的描述，而且l d p c 码的编码与译码也同样可以通过 t a n n e r 图分析。t a n n e r 图是一种双向图，由两种节点和边组成，其中每条边仅连接两个节 点。这两种节点分别为变量节点和校验节点，也可相应的表示为v 节点和c 节点，如下图 2 1 。其中校验节点对应于编码后的校验方程，其个数等于校验方程的个数，即校验矩阵的 行数。类似的变量节点对应编码后的比特，其个数等于码长，即校验矩阵的列数。t a n n e r 图的画法是若校验矩阵h 的第f 行第列为i ，那么t a n n e r 图中第个变量节点与第i 个校 验节点相连。 以n = 1 0 ，k = - 5 ，m = n 。k = - 5 ，行重为2 ( 即对应校验矩阵一行中1 的个数) ，列重为4 ( 即 对应校验矩阵一列中1 的个数) ，即w 。= 2 ，w w ：( n m ) = 4 的线性分组码为例。其校验 矩阵h 如下所示。 h = 1l ll00000 0 lq0olllo0 o o 重o0 重oo 耋l0 0olool0 l0 l oo0 盖eo 堇oll h 矩阵对应的t a n n e r 图如下图所示： f of i f 2f 3蠡 图2 1 中厂为校验节点，c 为变量节点。在t a n n e r 图中节点的度( d e g r e e ) 等于与每个节 点连接的边的个数。循环( c y c l e ) 表示为从某一个节点出发又回到此节点的过程，在此过稗 9 c ee 6 e 图 锡 咐协 锯 纠 图 ， e eeo e 浙江工业人学硕士学位论文 中所经过边的个数为循环长度( c y c l el e n g t h ) ，其中最小的循环长度即为此t a n n e r 图的围长 ( g i r t hl e n g t h ) 。 由图2 - 1 可以看到c o ，c l ，c 2 ，c 3 都连在矗上，对应于h 矩阵h o o = h o l = h 0 2 = h 0 3 = l ，而 第l 行的其它元素为0 。从行来看，厂对应着各个行，即满足c h t = 0 。类似的，从列来看， 矗，石连接着c 0 。对应h 矩阵的第一列h o o = h l o = l 。 从图2 1 中可以注意到：每个变量节点v n o d e 有两条边相连，每个校验节点c n o d e 有四条边相连。对应于w e = 2 ，w r = 4 ，且满足m w r = n w 。 对于规则的l d p c 码，其w 。，w ，是固定的，对应t a n n e r 图的度也是固定的。而对于 非规则l d p c 码，其w 。，w ，是不固定，对应t a n n e r 图的度也不是固定的。变量节点对应 的度a ) 可以通过下面的因式确定。 其中，乃表示连接度为d 的变量节点的所有边，吼表示变量节点的最大度。类似， 校验节点对应的度p ( x ) 可以通过以下因式确定。 以 p ( x ) = 伪x 出1 d = l ( 2 1 2 ) 其中，仍表示连接度为d 的校验节点的所有边，d 。表示校验节点的最大度。 在图2 1 中了，除了可以看出度外，关于l d p c 码还有一个重要的参数就是围长? ( g i r t h l e n g t h ) 。如图2 - 1 ，其中加黑的边构成一个循环，其循环长度y ( c y c l el e n g t h ) 为6 。对于双 向图，显然其最小的循环长度为4 ，即围长】，4 。对应于h 矩阵，即有四个l 存在于两行 两列的四个交叉点上。在码的构造和分析时，需要关注t a n n e r 图中的环，特别是短环。由 前面的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 提出的。在规则码的校验矩阵中每一行每一 列”1 ”的个数是相等的，分别为曰和p ，即行重和列重是固定的。其t a n n e r 图中变量节点和 校验节点的度是固定的【1 9 】。表示为( 玎，防g ) 。 对l d p c 码中的每个变量节点而言，当其被越多的校验方程包含时( d ，越大) ，就意味 1 0 o x 孰捎 = x兄 浙江工业大学硕士学位论文 着每个变量节点可以从更多的校验节点处获得信息来更准确的判断其正确性。同理当每个 校验节点约束的变量节点越少( d 。越小) 时，其相关变量节点的状态就越能被准确的估计出 来。对于规则的l d p c 码来说，这两种对弈的情况是一对难以解决的矛盾。因此，为了更 好的处理好这对矛盾，l u b y 等人引入了非规则l d p c 码。 由前面描述可知。对于非规则l d p c 码，其变量节点和校验节点的度在t a n n e r 图的表 述中有些节点的度大、有些节点的度小，不再是固定的了。在非规则的l d p c 码迭代译码 中，可知度数越高的变量节点接收到的置信信息也越多，实现正确译码也越快。同时在信 息传递过程中可以将更有效的信息传递给相邻校验节点。而这些校验节点相应的又可以将 更多的信息反过来传递给相邻度数更小的变量节点，从而产生波浪效应【2 0 】【2 1 1 。由于波浪效 应使得译码能按度数高低在变量节点和校验节点间交替译码，从而让非规则码的性能高于 规则码的性能。本文系统中所采用的l d p c 码就是非规则l d p c 码。 2 3l d p c 码构造 l d p c 码的编译码器都是根据校验矩阵h 来进行操作的，而稀疏校验矩阵中的非零元 素的排列和稀疏性直接影响着编码与译码的复杂度及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 等人也是采用随机化构造的稀疏校验矩阵。其中典型的随机构 造方法有c a m p e l l o 等人提出的基于参数的比特填充( b i t 6 l l i n g ) 构造算法【2 2 】， h 等人提出 的p e g ( p r o g r e s s i v ee d g e g r o w t h ) 算法【2 3 】。 比特填充算法是直接构造h 矩阵的算法，主要是先给定变量节点和校验节点的度，然 后将一个一个”1 ”按照一定的规则填入到校验矩阵中，使校验矩阵在构造过程中环最小。具 体操作是先将h 矩阵初始化为空，接着随机地生成列信息，判断其添加的列若满足了规则， 就将此列加入h 矩阵中，然后依此重复操作，直到整个h 矩阵的完全生成。 p e g 算法是一种直接构造t a n n e r 图的构造方法，主要是在变量节点与校验节点之间按 照一定规则逐步添加相连的边的方式构造l d p c 码。具体操作是根据所给定变量节点和校 验节点的数目以及变量节点校验节点的度，在尽可能保持最大环的条件下，通过逐步在变 量节点与校验节点问搜索选择加边，直到整个t a n n e r 图的完成。 1 l 浙江工业大学硕士学位论文 虽然各种改进的随机构造算法还在不断被提出，且随机构造的l d p c 码具有良好的编 码性能。但是一般来说，随机构造的l d p c 码较复杂，不利于硬件的实现。 结构化构造的共同点是h 矩阵采用分块矩阵法，然后通过几何、组合子矩阵构成。对 于规则的l d p c 码，结构化构造的主要算法有基于有限几何学【2 4 】的构造方法和均衡不完全 分组设计【l 列( b i b d ) 的构造方法。对于非规则l d p c 码结构化构造，最基础的就是准循环代 数结构，即现在被称为的q c l d p c 码。由g a l l a g e r 在他的博士论文中提出。因这类码的 特点是h 校验矩阵由一组分块矩阵按照一定的规则排列而成。因此构造这类准循环码的基 本思路是确定h 矩阵的总体框架，然后根据整体架构选择分块矩阵。这些分块矩阵一般由 零矩阵、单位矩阵以及单位矩阵的循环移位矩阵组成。 由以上原理，可以设结构化的l d p c 码校验矩阵h 维数为m n ，由聊。个z z 的 标准循环移位矩阵以及零矩阵构成。诈z ，xz ，则h 矩阵可以表示为： h = r 哦r 墙r 如r j 右 r 墙r 碥r 维r r 吃。r b r b ：r 堍助 一d h 6 一 ( 2 1 3 ) 其中，h u b o ，1 z l ，) ，r 瑶是标准矩阵i 经( 瑶m 。d z ) 次循环右移所得的移位矩阵。 r 。表示z z 全零矩阵，r o 表示z z 标准矩阵i 。r 是一个z z 标准循环移位矩阵。其中h 。 为： h 6 = h 乞。h l h 麓：h 乞 ( 2 1 4 ) 在结构化构造的过程中，校验矩阵h 可以由h 。来表示。称其为基本矩阵。其中碟表 示h 矩阵中不同子矩阵对应单位矩阵的循环移位值。z 为扩展因子，构造好基本矩阵h 。后， 通过改变z 即可得到码率一定，码长可变的结构化l d p c 码。 结构化构造的l d p c 码有利于硬件的实现，在中、短码长时有较好的性能。但是码长 和码率在参数选择上不够灵活，因此导致标准问的兼容性差。所以在目前的已经实际应用 1 2 6 o 6 h h h 6 吆6 他 h h 6 叭6 h h 屹吆 浙江工业大学硕士学位论文 l d p c 码的相关标准中都是采用的相应固定的h 矩阵。本文中采用的l d p c 码是通过结构 化方法构造的。 2 4l d p c 码编码 在前两节的描述中，可知l d p c 码是一种线性分组码，且是通过构造校验矩阵h 来进 行编码的。而在前面的知识中己知要生成编码码字，需要将待编码码字与生成矩阵g 进行 运算。因此在l d p c 码的编码中，按照线性分组码的规律需要进行h 矩阵到g 矩阵的转 换。但在硬件实现时，这种转换是不利的。目前解决编码中矩阵转换等问题的算法有多种， 基本满足了实现的需要。本节简单介绍一下主要的编码算法。 2 4 1l u 分解编码算法 l u 分解的算法是n e a l 于1 9 9 9 年提出的一种编码算法。目前c m m b 标准中提出的 l d p c 码采用的编码算法就是l u 分解算法。设编码后的码字表示为c ： ps ，h 表示为 h ： ab ，g 表示为g ： di 。其中s 是信息序列，p 是校验序列，a 是h 矩阵中校验 位对应的部分，d 是g 矩阵中校验位对应的部分。由本章第一节可知： a p t = b s t ( 2 1 5 ) a d t = b( 2 1 6 ) l u 分解算法的思路是将a 分解成l u 两个部分，a = l u ，其中l 表示下三角矩阵，u 表示上三角矩阵。则以上公式可以表示为： l y t ：b s t ( 2 1 7 ) u p t = y t ( 2 1 8 ) 由以上第一个方程式可得向量y ，在代入下面公式，得到校验序列p 。即完成编码。 虽然此算法充分利用了三角结构，能降低编码复杂度和提高编码效率。但是这种算法要求 码字为系统码形式。且h 矩阵需要满足一定条件。因此有一定的局限性。 浙江工业大学硕士学位论文 2 4 2r u 分解编码算法 r u 分解算法是由r i c h a r d s o n 和u r b a n k e 提出的一种近似下三角矩阵的编码算法。目 前i e e e 8 0 2 1 6 e 标准中的l d p c 码编码算法采用的此算法。 为了使矩阵保持稀疏性，将矩阵进行列变换，尽量使h 矩阵变换为下图2 - 2 中的格式。 由图可知整个矩阵由六个部分组成，其中对于此算法重点的是一个下三角矩阵的t 部分。 设l d p c 码编码后的信息序列中前胛m 个信息比特仍然为初始需发送的信息序列k 。然后 将h 矩阵左边乘一个矩阵，便可以得到一个用于递推校验比特的矩阵。 一三。? 会言三 = 一e t 三爻+ c e t 三+ 。吾 c 2 一，9 ， 卜k 粑曼粑虼| 、 、 a b 、