（信息与通信工程专业论文）基于欧氏几何的ldpc码构造研究.pdf

浙江大学硕士学位论文 摘要 低密度校验l d p c 码( l o w d e n s i t yp a i l 廿c h e c kc o d e s ) 是除t u r b o 码之外，又一 类近香农限的码字。由于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 码的简化迭代译码算法，随后在基于a w g n 信道下采用d v b s 2 标准的 l d p c 码进行仿真，给出了仿真的结果在分析仿真结果的基础上了解了它们近香农极 限的特性。接着我们介绍了利用欧氏几何构造出的具有结构特性的l d p c 码，在介绍 构造方法的同时，根据欧氏几何的结构特性，我们给出了l d p c 码的最小距离- 卜限。 接着对利用欧氏几何构造的l d p c 码在a w g n 信道和二进制调制下进行性能仿真，并 与p e g 随机构造和d v b s 2 标准中的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 码的t a n n e r 图结构，提出了一种改进 的广义迭代译码算法，在t a n n e r 图符号节点没有多重边的情况下，该算法可以对校验 节点的更新进行简化，即进行归一化和对数域运算。在这个基础上，本文提出了基于 欧氏几何构造的非多重边l d p c 码，它可以采用改进的迭代译码算法进行译码。在 a w g n 信道下，采用1 6 q a m 调制方式对构造的可分解和非多重边l d p c 码进行仿真。 最后我们还根据非多重边l d p c 码性能曲线，分析其特点以及影响译码性能的参数， 并通过仿真进行验证。 关键字：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 yc h e c kc o d e s ( l d p c ) ，i na d d i t i o nt u r b oc o d e s ，f o r ma n o t h e rc l a s s o fs h a n n o nl i m i t ( o rc h a n n e lc a p a c i t y ) - a p p r o a c h i n gc o d e s n o w a d a y s ，t h er e s e a r c ho nt h e l d p cc o d e sb e c o m e sah o tt o p i cd u et ot h e i rb o r d e rp r o s p e c t s v a r i o u sm e t h o d sf o r c o n s t r u c t i n gl d p cc o d e sh a v eb e e np r o p o s e da n dd e v i s e d t h e yc a nb ec l a s s i f i e di n t ot h r e e m a j o rc a t e g o r i e s ：e x p e i m e n t a ld e s i g nw i t hr a n d o ma p p r o a c h ，g r a p h t h e o r e t i ca p p r o a c ha n d g e o m e t i c i ng e n e r a l ，l o n gr a n d o m - l i k el d p cc o d e sp e r f o r mb e r e rt h a ns t r u c t u r e dl d p c c o d e so fc o m p a r a b l ep a r a m e t e r s ；h o w e v e r , t h e yu s u a l l yd on o th a v es u f f i c i e n ts t r u c t u r et o a l l o ws i m p l ee n c o d i n g n o wm o s to f r e s e a r c h e r so f t h el d p cc o n s t r u c t i o np r e f e rt h eb i n a r y m o d u l a t i o nr a t h e rt h a nm a r ym o d u l a t i o nd u et ot h eh i 曲c o m p l e x i t yi n d e c o d i n g c o m p u t a t i o nw h i l eu s i n gm a r ym o d u l a t i o n 1 1 1 i sp a p e rp r o p o s e st w oc l a s s e so fm a r y m o d u l a t e dl d p cc o d e sw h i c hu s es i m p l i f i e dd e c o d i n gi m p l e m e n t a t i o n t h i sp a p e rs u m m a r i z e st w og e n e r i ci t e r a t i v ed e c o d i n ga l g o r i t h m sf o rm - a r ym o d u l a t e d l d p cc o d e sa n dd e d u c e sd e c o d i n ga l g o r i t h mb a s e do nb p s km o d u l a t i o n b a s e do nt h e a w g nc h a u n e la n dt h eb p s km o d u l t i o n t h es h a n n o nl i m i t a p p r o a c h i n gi ss h o w ni n s i m u l a t i o nw i t hl d p cc o d e si 1 1d v b - s 2s t a n d a r d s u b s e q u e n t l y , t h e c o n c e p t i o no f e u c l i d e a ng e o m e t r ya n df o u rc l a s s e se g l d p cc o d e sc o n s t r u c t i o na r ep r e s e n t e d i na d d i t o n , al o w e rh a m m i n gd i s t a n c el i m i t a t i o ni si n 仃o d u c e da c c o r d i n gt og e o m e t r yc h a r a c t e r i s t i c f i n a l l y , b a s e do nt h ea w g nc h a n n e la n dt h eb p s km o d u l t i o n t h es i m u l a t i o no fl d p c c o d e sc o n s t r u c t e db ye u c l i d e a ng e o m e t r yi sg i v e na n di nt h i sp a p e r , t h ee g l d p cc o d e sa r e c o m p a r e dw i t ht h ec o d e sw h i c ha r ei nd v b s 2s t a n d a r da n dp e g - t h i sp a p e rf o c u so nt h ea p p r o a c h e s w h i c hc o n s t r u c t i n gm a r ym o d u l a t e dl d p cc o d e s b yb ye u c l i d e a ng e o m e t r y i ti n t r o d u c e st a n n e rg r a p ho f m a r ym o d u l a t e dl d p cc o d e sa n d i n v e s t i g a t e s i nd i f l u l f i t i e so nt h eg e n e r i ci t e r a t i v e d e c o d i n g t h et w ol d p cc o d e s c o n s t r u c t e db ye u c l i d e a ng e o m e t r ya r ep r o p o s e da f t e r t h e s et w oc o d e sc a nb ed e c o d e d w i t hs i m p l i f i e dd e c o d i n gi m p l e m e n t a t i o nw h e nt r a n s m i t t e dw i t hm a r ym o d u l a t i o n “e 1 6 q a m ) o n eo fl d p cc o d e sa r ed e c o m p o s a b l ea n dc a l lb ec o d e da n dd e c o d e dw i t h m u l t i l e v e lc o d i n g ( m l c ) a n dm u l t i s t a g ed e c o d i n g ( m l d ) e a c hd e c o d i n gs t a g ei nm l d u s e sb i n a r yi t e r a t i v ed e c o d i n ga l g o r i t h mw h i c hr e d u c e sm u c hc o m p u t a t i o n f u r t h m o r e ， v a r i o u sb i tl e v e lh a v eu n e q u a le l f r o rp r o t e c t i o n t h i 8p a p e r , b a s e do nt h et a n n e rg r a p ho f m a r ym o d u l a t e dl d p cc o d e s ，p r o p o s e sa ni m p r o v e da l g o r i t h mf o rg e n e r i ci t e r a t i v e a l g o r i t h m ，w h i c hs i m p l i f i e dt h ep r o c e s so fu p d a t i n gc h e c kn o d e sw h e nt h ec o d e sa r e n o n m u l t i e d g e ，a n dp r o v i d e sac l a s so fn o n m u l t i ，e d g el d p cc o d e s ，b a s e do nt h ea w g n c h a n n e la n dt h e1 6 q a mm o d u l a t i o n ，as i m u l a t i o nf o rd e c o m p o s a b l ea n dn o n - m u l t i - e d g e l d p cc o d e sa r es h o w n f i n a l l yw ei n v e s t i g a t ed i f i e r e n tc o n s t r u n c t i o np a r a m e t e r sw h i c h i n f l u e n c et h ep e r f o r m a n c eo ft h en o n - m u l t i e d g el d p cc o d e sa n das i m u l a t i o ni sg i v e nt o v a l j d a t e k e y w o r d s ：l d p c ，g e n e t i ci t e r a t i v ed e c o d i n g ，m a r ym o d u l a t i o n ，e u c l i d e a ng e o m e t r y , m u l t i l e v e lc o d i n ga n dd e c o d i n g i l 浙江大学硕士学位论文 图目录 图1 1 数字通信系统基本组成1 图2 1 线性分组码的t a n n e r 图1 0 图2 2 典型的m i n s u m 和s u m p r o d u c t 译码算法应用1 2 图2 3d v b s 2 标准的( 1 6 2 0 0 ，3 2 4 0 ) l d p c 码s u m p r o d u c t 译码性能2 1 图2 - 4d v b s 2 标准的r 1 6 2 0 0 ，3 2 4 0 ) l d p c 码m i n s u m 译码性能2 1 图2 5d v b s 2 标准的( 1 6 2 0 0 ，6 4 8 0 ) l d p c 码s u m p r o d u c t 译码性能。2 2 图2 - 6d v b s 2 标准的f 1 6 2 0 0 ，6 4 8 0 ) l d p c 码m i n s u m 译码性能2 2 图2 7d v b s 2 标准的( 1 6 2 0 0 ，1 0 8 0 0 ) l d p c 码s u m p r o d u c t 译码性能2 3 图2 8d v b s 2 标准的( 1 6 2 0 0 ，1 0 8 0 0 ) l d p c 码m i n s u m 译码性能2 4 图3 1 不同的校验方程数目对e g l d p c 码的译码性能影响3 6 图3 2 不同的迭代次数对e g l d p c 码的译码性能影响3 7 图3 3 基于e g ( 3 ，2 3 ) 构造的四类e g l d p c 码译码性能仿真3 8 图3 _ 4e g l d p c 码和p e g l d p c 码译码性能比较3 8 图3 5e g l d p c 码和p e g l d p c 码平均迭代次数比较3 9 图3 - 6e g l d p c 码和d v b s 2 标准中的l d p c 码译码性能比较3 9 图4 1 一个典型u n g e r b o e c k 的8 p s k 符号分割集4 3 图4 2 可分解l d p c 码采用多级编码和多级译码的实现框图5 1 图4 3 原始l d p c 码交织前后的性能仿真图5 2 图4 4 采用多级译码后不同等级比特的误比特率性能5 3 图4 5 译码算法修正前后第一和第二等级比特的误比特率性能一5 4 图4 6 译码算法修正前后第三和第四等级比特的误比特率性能5 5 图4 7 非多重边码在1 6 p s k 调制下的t a n n e r 图局部示意图5 6 图4 8 非多重边l d p c 码的仿真平台框图5 9 图4 9 两种不同映射方式的1 6 q a m 星序图一6 0 图4 1 0 非多重边( 4 0 9 6 ，2 8 0 0 ) l d p c 码在1 6 q a m 格雷映射下的译码性能仿真6 1 图4 1 1 非多重边( 4 0 9 6 ，2 8 0 0 ) l d p c 码在1 6 q a m 格雷映射下的平均迭代次数6 l 图4 1 2 非多重边( 4 0 9 6 ，2 8 0 0 ) l d p c 码在1 6 q a m 规则映射下的译码性能仿真6 3 图4 1 3 非多重边( 4 0 9 6 ，2 8 0 0 ) l d p c 码在1 6 q a m 规则映射下的平均迭代次数6 3 图4 1 4 三个非多重边l d p c 码在1 6 q a m 格雷映射下的译码性能仿真6 8 图4 1 5 三个非多重边l d p c 码在1 6 q a m 格雷映射下的平均迭代次数6 9 图4 1 6e g ( 4 ，3 ，3 ) 码在不同最大迭代次数下的译码性能仿真7 0 图4 1 7 最大1 0 次迭代情况下e g ( 4 ，3 ，3 ) 码的平均迭代次数7 1 图4 1 8 最大5 0 次迭代情况下e g ( 4 ，3 ，3 ) 码的平均迭代次数7 1 图4 1 9 发送全零码字下e g ( 4 ，3 ，3 ) 码的译码性能仿真7 2 图4 2 0 两种方法构造的非多重边( 4 0 9 6 ，1 11 2 ) l d p c 码译码性能仿真7 3 图4 2 1 两种方法构造的非多重边( 4 0 9 6 ，111 2 ) l d p c 码平均迭代次数7 4 v 浙江大学硕士学位论文 第1 章绪论 本章介绍了论文工作的丰要研究背景和方向。首先介绍数字通信的基本模型和信 道编译码理论发展过程，随后对低密度校验码概念以及其在国内外的研究现状进行简 单的概述，最后介绍了本论文的研究工作和整体结构。 1 - l 数字通信模型 在最近几年里，对于有效、可靠的数字信息传输以及存储系统的需求越来越大。 由于在商业、政府机构和军事等领域中，用于交换、处理、和存储数字信息的大规模、 高速率数据网络的出现，这种需求就更加迫切。因此如何能够控制错误，提高信息传 输的可靠性和有效性成为了现代通信领域研究和追求的目标。 1 9 4 8 年，香农发表了题为“am a t h e m a t i c a lt h e o r yo f c o m m u n i c a t i n g ”l i j 论文。文 章中指出，只要信息速率不大于信道容量，则通过对信息适当的编码，由噪声信道或 者存储媒介产生的错误可以降低到任意小，即无差错传输，而不需要牺牲信息传输或 者存储的速率。香农的著作奠定了现代信息论的基础，它的发表标志着信息与编码理 论学科的创立。 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 鍪兰塑型兰 i = 留固 塑亟口三士丽萄磊 编码信道 图1 1 数字通信系统基本组成 图1 - 1 给出了数字通信系统的方框图和基本组成【2 】。信源产生需要传输的信息，输 出的信息既可以是连续波形( 模拟信号) ，也可以是离散符号序列( 数字信号) 。信源 编码器将信源输出的信号转换为一个二进制比特序列。如果信源产生的是模拟信号， 则信源编码器还需要一个模拟一数字( a d ) 的转换操作。由于信源产生的信号往往包 含了大量的冗余度，因此信源编码器的目的就是希望找到一种信源的表示方式，最大 程度的消除信源冗余度，同时要能根据编码后的序列无差错的重建信息。 信源编码后的二进制比特序列称为信息序列，它被送往信道编码器。信道编码器 将信息序列转换为离散编码序列，称之为码字。信道编码的目的是通过对信息序列引 入一定冗余度的方法，来消除信道加性噪声的影响n 从而可以使接收机不受噪声和干 扰的影响，正确还原发送的信息序列。信道编码可以在信号功率，系统带宽和硬件复 l 浙江大学硕士学位论文 杂度受限的情况下，使通信的可靠性增加。与未编码系统相比，信道编码会导致数据 传输速率的下降或者信道带宽需求的增加。 离散符号是不适合在物理信道或者数字存储媒介卜传输和记录的，这就需要数字 调制器。数字调制器的作用是使码字序列转换成能够适应信道传输的连续波形信号。 根据调制方式的4 i 同可以在物理信道上单位时间内传递不同数量的信息比特，从而提 高信息的传输速率。 经过数宁调制器产生的连续波形进入信道中，并且被叠加上信道中的噪声和干扰。 典型的传输信道如电话线，射频无线电，微波，卫星传输，光缆等等。每种信道具有 不同的噪声分布。 在接收端，数字解调器对加噪以后的连续波形进行处理，并且将每个单位时问内 的波形还原成为比特序列，以表示对所发送数据码元的最优估计。然后将估计值输出 到信道译码器中。 信道译码器对于数字解调器输出的数字序列进行译码，将接收到的比特序列转换 为信息估计序列。信道译码器的译码准则是根据信道编码和信道噪声特性而制定的， 其目的是使信道噪声所造成的信号判决错误晟小化。在理想的情况下，尽管由于噪声 的影响会导致信道译码器接收到的并不是码字，但是通过信道译码，信道译码器输出 的信息估计序列应该同经过信源编码后的信息序列完全一致也就是说信道译码器的 输出序列应该和信道编码器的输入序列完全一致。评价调制器和编码器性能好坏的度 量是译码序列中出现错误的频率。 信源译码器从信道译码器中接收信息估计序列，重新构造原始信号，并最终输出 一个信源的估计序列，将估计序列传送到信宿。由于信道译码出现的错误，以及信源 编码器中可能引入的失真，使得信源译码器输出的信号很可能只是原始信源信号的近 似。原始信号和重构信号间的差别代表了数字通信系统引入的失真程度。 1 2 信道编码 香农告诉我们任何通信信道的传输能力都可以用一个参数c ( 定义为信道容量) 来描述，如果通信系统所要求的传输速率r 小于c ，则一定存在一种编码方式，当码 长充分长并且应用最大似然译码的时候，系统可以实现信息无差错的传输。然而，香 农并没有告诉我们具体的编码方式，而且他的证明也是当码长趋近于无穷时，随机码 书上的平均效果。自香农的信道编码定理提出几十年以来，信道编码技术成为了数字 通信技术研究的核心问题之一，编码学者们不断在寻找各种各样的编码方式，取得了 丰硕的成果。 迄今为止，信道编码技术已经有了半个世纪的历史，从开始的理论分析到现在的 具体实现，已经取得了众多辉煌的成果，而信道编码近六十年的发展历史可以划分成 2 浙江大学硕士学位论文 下面几个时期 4 j - 8 ： 在信道编码理论提出后的十年里，h a m m i n g ，s l e p i a n ，p r a n g e 等人根据香农的思 想，给出了一系列设计好码和有效译码的方法。这一时期最著名的码字是汉明码，格 雷码和r e e d m u l l e r 码。这些码都是针对随机错误，因此他们仅仅适用于a w g n 信道， 而不是衰落信道；它们的译码都是采用硬判决译码，冈此在译码性能上有很大的损失。 这一时期奠定了线性分组码的理论基础，给出了纠错码的基本码限，这是信道编码从 无到有得到迅速发展的年代。 二十世纪六十年代是信道编码发展过程中最为活跃的时期。这一时期不仅提出了 许多有效的编译码方法，如门限译码，迭代译码，软判决译码和v i t e r b i 译码等，而且 注意到了纠错码的实用化问题，讨论了与实用有关的各种问题，如码的重量分布，译 码错误概率和不可检错概率的计算、信道的模型化等。各种好的分组码结构纷纷被提 出。在这个时期，h o e q u e n g h e m 、b o s e 和r a y c h a u d u r i 提出了b c h 9 i ”】码，它是循环 码的一个非常重要的了集，有着较好的编码增益性能。将b c h 码扩展到多元的情况， r e e d 和s o l o m o n 得到了r s l 码。其非二元特性可以有效的纠正突发错误。著名的低 密度校验码也是在同时期首次被m i t 的g a l l a g e r 提出【1 ”i t 3 ，虽然在当时的条件下，人 们忽略了它的重要性，但现今的事实已经证明这是接近香农极限的好码之一。 二十世纪七、八十年代是信道编码发展史中具有重要意义的时期。在理论上以 g o p p a 为首的一批学者，构造了一类g o p p a 码【j ”，其中一类子码能达到香农在信道编 码定理中提出的香农码性能，这在纠错码的历史上具有划时代意义。在这期问大规模 集成电路和微机的迅速发展，为纠错码的实现打下了坚实的物质基础，因而与实用相 关的各种技术以及有关问题得到了极大地关注。网格编码调制技术( t r e l l i sc o d e d m o d u l a t i o n ，t c m ) 最早是由u n g e r b o e c k 在1 9 7 6 年的一篇文献中提出的i t s l ，不久他 把这种思想分别用三篇文献i i - 1 1 8 给与了明确的阐述。这种将编码和调制相结合的方法 有效的解决了传统信道编码中提高系统可靠性的同时也降低了系统传输有效性的弊 病。这种技术的主要思想是在不增加系统带宽要求的条件下，通过扩展符号映射空间 来达到提高编码增益的目的。t c m 技术奠定了带限信道上编码调制技术的研究基础， 被认为是信道编码发展史中的一个里程碑。另一种编码调制技术由i m a i 提出【，称为 多级编码调制技术( m u l t i l e v e lc o d i n g ，m l c ) ，它在移动衰落信道下具有广泛的应用 前景。f o m e y 在这个时期提出了用两个短码级联构造长码的方法来提高纠错能力 2 0 】。 1 9 7 2 年，j u s t e s o n 用级联思想构造了j u s t e s o n 码，这是一类性能接近于香农限的好码。 这个时期，软判决译码也飞速发展【2 1 】【埘。b a h l ，c o c k e ，j e l l n e k 和r a v j v 共同提出了 f o r w a r d - b a c k w a r d 最大后验概率m a p 译码算法幽1 ( b c j r 算法) ，h a r t m a n 和r u d o l p h 提出了逐位译码算法( h r 算法) ，w e l d o n 提出了重量删除译码算法( w e d 算法) 这 些都是符号错误概率最小的逐位软判决算法。另外，c h a s e 还提出了使码字错误概率最 小的一类逐组软判决译码方法( c h a s e 算法) 。 浙江大学硕士学位论文 然而经过几十年来的努力，人们发现，离香农极限的距离依旧很遥远，直到1 9 9 3 年，在日内瓦举行的i c c 国际通信会议上，法国学者c b e r r o u ，a g l a v i e u x ，p t h i t i m a j s h i m a 提出了一类新的编码t u r b o 码1 2 4 2 5 。t u r b o 码将卷积码和随机交织器 相结合，同时利用软输出迭代译码来逼近最大似然译码，在性能上与香农极限仅相差 o 7 d b 。这个结果轰动了编码界，开创了编码研究的新时代。随后，在1 9 9 6 年，m a c k a y 等人重新发现了g a l l a g e r 在六十年代提出的低密度校验码( l o wd e n s i t yp a r i t yc h e c k l d p c ) ，发现l d p c 码也是接近香农极限的编码，它的译码性能同样可以逼近香农信 道容量限。实际上这两种码都是基于图构造的低密度码，译码算法都是采用迭代译码 算法，因此二者在基于图模型的编译码研究中得到了统一口。 1 3l d p c 码的历史和现状 l d p c 码于1 9 6 2 年由g a l l a g e r 提出【1 2 1 ，因此它也被称为g a l l a g e r 码，它是t u r b o 码之外的另外种近香农极限的码字。虽然g a l l a g e r 证明了l d p c 码是渐进好码，但 是限于当时的计算能力，l d p c 码一度被认为是一种无法实现的信道编码方式，在很长 一段时间内没有受到人们的重视。 1 9 8 1 年随着t a n n e r 著作的出现【2 7 1 ，l d p c 码可以用图论的角度进行新的理解和诠 释，然而不章的是这一理论成果仍然没有得到人们的关注。直到9 0 年代初，随着t u r b o 码的出现，这才引发了众多学者对l d p c 码的研究兴趣。m a c k a y 和n e a l 在上世纪九 十年代中期利用随机构造的t a n n e r 图研究了l d p c 码的性能，采用b e l i e fp r o p a g a t i o n 译码算法的l d p c 码字具有了与t u r b o 码相似的译码性能，长的l d p c 码在基于b e l i e f p r o p a g a t i o n 译码算法上甚至超过了t u r b o 码【2 8 l 【2 9 1 ，它可以达到离香农限只有o 1 d b 的 距离，这个发现使得l d p c 码比t u r b o 码在需要高度可靠性的通信和数字存储系统纠 错中更具有竞争力。从此之后，有关l d p c 码的文献大量涌现。 l d p c 码有着许多t u r b o 码没有的特性和优点【3 0 ：它们并不像t u r b o 码那样为了达 到很好的纠错性能而需要一个很长的交织器；它们具有更好的分组纠错性能( f e r ) ；误 码平层( e r r o rf l o o o 发生在更低的误比特率等级上；描述简单，对于严格的理论分析具有 可验证性；译码的复杂度一般都要低于t u r b o 码，可实现完全的并行操作，硬件复杂 度低：提出的时间早，相关专利少，利于在实际通信系统的应用中规避国际专利陷阱。 现在对于l d p c 码的研究主要集中在以下几个方面： 1 码字结构的设计： 由于l d p c 码是根据校验矩阵所定义的，因此对于码字的设计实际上就是对稀疏 校验矩阵的设计。校验矩阵的设计既要满足矩阵所定义码字的良好结构特性，如最小 汉明距离，同时校验矩阵还要尽可能减少t a n n e r 图中环的数量。 结构化的l d p c 码可采用几何方法，图论方法，群论方法，实验设计方法，置换 4 浙江大学硕士学位论文 方法等来设计构造。无论是哪种方法，其目的都是为了增大t a n n e r 图中的环，优化码 的节点度数分布，在具有良好译码性能的同时还要有较小的实现复杂度。 d a v e y 和m a c k a y 从减少t a n n e r 图i 二的小环有利于改善译码特性的思想出发，提 出了基于g f ( q ) 的多进制l d p c 码，它能进一步提高l d p c 码的译码性能p ”。l u b y 等 人也提出了一类基于级联二分图的l d p c 码p “，用于可删除信道，它不仅可线性时间 编码，而且也可实现线性时间译码。c o m p e l l o 等人提出采用扩展的b i t f i l l i n g 算法来 设计具有高码率，高g i r t h 和误比特性能良好的l d p c 码【3 3 1 。近来，人们对r i c e 信道， m i m o 信道，o f d m 等系统中的l d p c 码的设计也进行了研究“- t 3 s 。 k o u ，l i n 和f o s s o r i e r 3 9 1 4 2 1 第一次系统的用代数方法提出了基于有限几何 ( f i n i t e g e o m e t r y ) 的l d p c 码构造方法。这一大类有限几何l d p c 码具有相对好的最小 汉明距离，而且其t a n n e r 图是具有不包含短环特性的，尤其是四环。这些码可以用多 种方式进行译码，随着译码复杂度的增加，得到的纠错性能也大幅度提高。更进一步 来说，这些码可以构造出循环或者准循环的特性，因此它们的编码只需要若干个线性 移位寄存器即可以实现编码。部分基于有限几何的长码具有近香农限的出色性能。本 文设计的基于多进制调制下可分解和非多重边l d p c 码就是利用有限几何的方法。 2 快速编码方法的研究 尽管g a l l a g e r 提出了l d p c 码，但是他并没有具体的提出如何构造具有良好性能 的l d p c 码，就像b c h ，r s ，和有限几何码那样具有明确的结构；然而他提出了一个 构造一类伪随机l d p c 码的总体方法，一些好的l d p c 码可以通过计算机产生，尤其 是长码，但是他们由于缺少结构化特性，因此编码实现十分的复杂。为了解决该问题， 许多学者提出了不少好的l d p c 码构造和编码方法，目的在于减少编码时间和降低编 码器复杂度【4 3 1 。【4 8 l 。 m a c k a y 等人提出了对非规则码采用先选择轮廓再选择结构的两步选择法，验证了 s u p e r - p o i s s n n 结构具有较好性能，并指出：能快速编码的l d p c 码的校验矩阵通常具 有下三角形结构1 4 ”。r i c h a r d s o n 和u r b a n k e 探讨了要获得高效编码器应如何确定校验 矩阵稀疏度的问题，以及如何构造码，使编码时间与码长符合线性关系，而非通常认 为的平方关系【4 6 1 。李平等人提出的准随机l d p c 码 4 7 l ，可直接利用稀疏的校验矩阵进行 编码，从而大大降低了编码的复杂度。该文献对具有循环或准循环结构的l d p c 码的 编码方法进行了研究，给出了电路实现结构，指出在利用简单移位寄存器实现编码的 时候，其复杂度与码长呈线性关系。 3 码字结构的优化： 对于码结构的优化可以通过优化码的度分布来实现。采用的方法是首先利用线性 规划，密度进化e x i t 等工具优化设计l d p c 码的度分布，然后按照该分布生成相应 的校验矩阵1 5 0 】- 【5 ”。r i c h a r d s o n l 5 川等人通过优化非规则图的度结构来寻找逼近容量的非 5 浙江大学硕士学位论文 规则l d p c 码。l u b y 5 ”等人采用线性规划和密度进化方法来优化度分布，构造出的非 规则l d p c 码在a w g n 信道和r a y l e i g h 衰落信道下，与规则l d p c 码相比，性能有极 为显著的提高。近来学者们还提出了大量密度进化的改进形式【5 4 l 【5 5 】。最新的研究表明， 非规则l d p c 码在高斯信道下，当码长为1 0 7 时，距离香农极限只有0 0 0 4 5 d b ，大大 超过了t u r b o 码的性能。 4 译码算法性能的研究 g a l l a g e r 1 3 在最初的文献中提出两种译码算法，即硬判决译码和概率译码。后者虽 然有良好的性能，但复杂度高。文献提出的s p a ( s u m 。p r o d u c t a l g o r i t h m ) 算法【5 6 】【5 刀可以 认为是二者的折衷，它也被称为置信传播b p ( b e l i e f p r o p a g a t i o n ) 算法。 r i c h a r d s o n 等人，在前人的基础上，总结归纳出消息传递m p ( m e s s a g ep a s s i n g ) 算 法类。它包括了g a l l a g e r 的硬判决译码，而且当其译码消息为连续变量的时候，就成 为了b p 算法，其思想与s p a 算法是一致的。r i c h a r d s o n 等人还提出了分析译码消息对 应的概率密度函数演进过程的密度进化d e l 5 6 l ( d e n s i t ye v o l u t i o n ) 分析算法。为了达到译 码复杂度和译码性能的最佳折中，f o s s o f i e r 【57 在b p 算法的基础上，提卜n 了两种 b p - b a s e d 译码算法，大大降低了译码复杂度，并保持了较好的译码性能。其算法思想 与m a x l o g m a p 算法足一致的。c h e r t s s 等人比较了b p b a s e d 和b p 算法，对前者提 出了两种改进策略：采用归一化的近似最佳通用b p b a s e d 译码算法( 也称为n o r m a l i z e d b p b a s e d 算法) 和通过降低可靠性值来改善外部信息精度的o f f s e tb p b a s e d 算法，从而 进一步提高了b p b a s c d 算法性能。 5 l d p c 的应用和实现 l d p c 码具有广阔的应用前景，在光纤通信、卫星数字通信、磁，光全息存储、移 动和固定无线通信中将得到广泛的应用。v o c a l 公司推出了一种用于w l a n 的 l d p c t u r b o 不对称解决方案，即下行链路采用l d p c 码，上行链路采用t u r b o 码。该 方案用于i e e e8 0 2 1 1 a b gw l a n ，移动终端的电池使用时间可以延长4 倍。 d v b s 2 1 5 9 ( 欧洲新一代数字卫星广播标准) 最引人注目的革新在于信道编码方式，它将 l d p c 码作为内码，b c h 码作为外码，构成级联码作为其纠错方案，新的编码调制方 案十分接近香农极限，在离香农限仅仅o 7 l d b 的情况下可以得到准无误码的接收， 比d v b s 标准提高了3 d b ，以至于d v b 官员认为这已经是卫星广播信道误码的终极 标准，不需要再开发d v b s 3 了。同样的，在我国数字电视地面传输标准中【删l d p c 码也成为了信道编码的唯一解决方案。 l d p c 码的实现通常要考虑到性能、复杂度和灵活性等因素。研究人员已经提出了 一些基于d s p ，f p g a 和v l s i 的l d p c 码的实现方案。f l a r i o n 公司已经开发出称为 v e c t o r - l d p c 的编译码产品【”j 。l u c e n t 技术公司也已经实现了一款用于光通信网络的 l d p c 码编译码器，其吞吐量为1 0 g p s ，码率为o 9 3 。 6 浙江大学硕士学位论文 1 4 本文的组织结构 本文的组织结构如下： 第2 章介绍了l d p c 码。首先介绍了l d p c 码的基本概念，然后引入了多进制调 制下l d p c 码的两种广义迭代译码算法s u m p r o d u c t 算法和m i n s u m 算法。接着根 据广义迭代译码算法，推导了二进制调制下迭代译码算法的简化形式。最后对二进制 调制下d v b s 2 标准中的l d p c 码进行仿真，给出了性能曲线。 第3 章丰要介绍了基于一类有限几何欧氏几何的l d p c 码构造方法。根据欧 氏几何空阃l | 各种不同了空间和存在于子空间上的点之问的关系，构造出四类欧氏几 何l d p c 码，其中很多码字具有循环或者准循环的特性，从而使得编码实现仪仪需要 若干移位寄存器。同时，根据欧氏几何的特点，本文给出l d p c 码的汉明距离限。最 后对二进制调制下的欧氏几何l d p c 码进行仿真，并给出性能曲线。 第4 章主要提出了两种适合在多进制调制下传输的基于欧氏几何构造的l d p c 码， 这两种码都是可以通过其构造特点，在译码过程中简化广义迭代译码算法。其中第一 种码字能够根据调制方式的不l 司进行分解，称为可分解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 码的构造，除了码字的仿真结果外，我们对构造参数的选择进行 分析，最终通过仿真图进行了验证。 第5 章是本文的总结与展望。 浙江大学硕士学位论文 第2 章l d p c 码及广义迭代译码算法 低密度校验码( l o w d e n s i t yp a r i