（通信与信息系统专业论文）dmbth系统中ldpc码的编解码算法研究与实现.pdf

北京邮电人学硕i ：学位论文 d m b t h 系统中l d p c 码的编解码算法研究与实现 摘要 在通信系统中，纠错码被用来提高信道传输的可靠性和功率利用 率。1 9 6 2 年，g a l l a g e r 首次提出了l d p c 码的古典模型，即规贝, u ( r e g u l a r ) 的l d p c 码。但由于当时计算机水平发展有限，硬件实现困难，l d p c 被长期的遗忘了，直到1 9 9 5 年才成为学界的焦点。l d p c 码是目前 最逼近香农限的一类纠错码，它具备比t u r b o 码更接近香农限的误码 率性能和完全并行的迭代译码算法，因此也比t u r b o 码具有更广泛的 应用前景。当前众多新兴领域中都采用了l d p c 码，如无线局域网 i e e e 8 0 2 1 1 、地面广播传输系统d v b s 2 和中国移动多媒体广播 c m m b 等等。现今中国出台的数字电视地面传输标准中的多载波系 统d m b t h 的信道编码方案中也采用了l d p c 码作为其内码。 本文重点对d m b t h 系统中采用的l d p c 码的编解码算法和性 能进行研究和分析，并采用f p g a 自主设计和实现了该系统的l d p c 编码器。为了使读者有一个清晰的思路，更好地理解d m b t h 系统 中的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 d p c 码，即具有准循环特 性的l d p c 码( q c l d p c ) ，详细阐述了这种码的特点，并由此切入到 d m b t h 系统中采用的q c l d p c 码。针对d m b t h 系统，本文给 出了其所采用的三种码率的q c l d p c 码的具体参数，又详细介绍了 这种码的构造方法- 基于两信息符号的r s 码构造法。从第四章开 始，本文进入l d p c 码的实现部分，总结了利于硬件实现的q c l d p c 码的编解码算法，并采用m a t l a b 软件对d m b t h 系统的l d p c 码进 行了性能仿真，验证了其优越的误码性能。本文最后一章是对研究生 阶段所做课题的归纳和总结，给出了d m b t h 系统中能够支持 q p s k 、16 q a m 和6 4 q a m 三种调制方式的l d p c 编码器的设计思路 和实际的f p g a 设计结构，并由时序仿真结果验证所设计的编码器的 有效性。 关键词 低密度奇偶校验码，奇偶校验矩阵，t a n n e r 图，准循环码，和积 算法，最小和算法 北京邮电大学硕上学位论文 t h er e s e a r c ha n df p g ar e a l i z a t i o n o fl d p ci nd m b t hs y s t e m a b s t r a c t a si sk n o w nt oa 1 1 e r r o rc o r r e c t i n gc o d ew a su s e di nc o m m u n i c a t i o ns y s t e mt o i m p r o v et h er e l i a b i l i t ya n dp o w e ru t i l i z a t i o no fc h a n n e lt r a n s m i s s i o n l o wd e n s i t y p a r i t y - c h e c kc o d e s ( l d p cc o d e ) ，ak i n do fe r r o rc o r r e c t i n gc o d e ，w a si n v e n t e db y r o b e r tg a l l a g e ri n19 6 2 g i v e nt h ed e v e l o p m e n tc o n d i t i o no fc o m p u t e rt e c h n o l o g ya t t h a tt i m e t h ec o m p l e x i t yo fl d p ch a r d w a r er e a l i z a t i o nw a so u to ft h eq u e s t i o n , s o t h ec l a s s i c a lm o d e lo fl d p c ，i no t h e rw o r d sr e g u l a rl d p c ，w a sl a r g e l yf o r g o t t e n u n t i l19 9 5 i tf i n a l l yc a m eb a c kt ot h ef i e l do fr e s e a r c ha n db e c a m et h ef o c u s i th a s b e e ns h o w nt h a tl d p cc a np e r f o r mv e r yc l o s et ot h es h a n n o nc a p a c i t yl i m i t l d p c h a sas i g n i f i c a n t l yl o w e rc o m p l e x i t yt h a nm oc o d e sa tt h ec o d e1 e n g t h s p e r f o r m a n c ea n ds n b e s i d e s l d p cd e c o d e r i ss u i t a b l ef o r f u l l yp a r a l l e l i m p l e m e n t a t i o n t h i sh a ss i g n i f i c a n ta d v a n t a g e sw h e nc o n s i d e r i n gl o n gc o d e s i ti s s a f et os a yt h a tl d p cs u r e l yh a sam o r ep r o m i s i n gf u t u r e t h et r u t hi sl d p ch a sb e e n a d o p t e da ts om a n yr e s e a r c ha c h i e v e m e n t sc u r r e n t l y ：s u c ha sw i r e l e s sl a ni e e e 8 0 2 1 1 t e r r e s t r i a lb r o a d c a s t i n gt r a n s m i t t i n gs y s t e md v b s 2a n dc h i n am o b i l e m u l t i m e d i ab r o a d c a s t ( c m m b ) i nc h i n at e r r e s t r i a ld t vs t a n d a r d ( g b 2 0 6 0 0 2 0 0 6 ) w h i c hw a sr e l e a s e dr e c e n t l y , t h ec h a n n e lc o d i n gs c h e m eo fi t sm u l t i c a t t i e rs y s t e m ( d m b t h ) a l s ou s el d p c t t l i sp a p e l m a i n l yf o c u s e so nt h er e s e a r c ha n da n a l y s i so ft h ec o d e ca l g o r i t h m a n dt h ep e r f o r m a n c eo fl d p cu s e di nd m b - t hs y s t e m i na d d i t i o n , ac o d e ro ft h e d m b t hs y s t e mi sr e a l i z e dw i t l lf p g a i no r d e rt om a k ei te a s yt ou n d e r s t a n d ，t h ef i r s tc h a p t e ro ft h i sp a p e l g i v e st h e i n t r o d u c t i o no fl d p cc o d e t h es e c o n dc h a p t e rw i l lt a l ka b o u tt h ep r i n c i p l eo fl d p c c o d e ，i n c l u d i n gt h ed e v e l o p i n gh i s t o r y , d e f i n i t i o n ，a n a l y s i so ft a n n e rg r a p h ，r a n d o m c o n s t r u c t i o nm e t h o d ，a r i t h m e t i cc o n s t r u c t i o nm e t h o d ，c l a s s i c a ld e c o d es c h e m ea n d c o n t e m p o r a r yd e c o d es c h e m e b a s e do nw h a tw ei n t r o d u c e da b o v e t h et h i r dc h a p t e r w i l l t a l ka b o u tt h ec h a r a c t e r i s t i co fav e r ys p e c i a lk i n do fl d p cc o d e n a m e d q c - l d p cc o d e ( q u a s i - c y c l i cl d p cc o d e ) f u r t h e r , t h i sp a p e rg i v e st h ep a r a m e t e r s a n dt h ec o n s t r u c t i o nm e t h o do ft h eq c - l d p cu s e di nd m b t hs y s t e m f r o mt h e f o u r t hc h a p t e ro n w em o v ei n t ot h er e a l i z a t i o no ft h el d p cc o d e t h ec o d e c a l g o r i t h mo fq cl d p cw h i c hi ss u i t a b l ef o rh a r d w a r er e a l i z a t i o ni sc o n c l u d e d a d d i f i o n a l l y ，m a t l a bi su s e dt oc o n d u c tt h ep e r f o r m a n c es i m u l a t i o no ft h el d p cc o d e u s e di nd m b - t 。hs y s t e m ，a n dt h e s i m u l a t i o nr e s u l t p r o v e s t h a tt h ec o d e s p e r f o r m a n c ei sp r e t t yg o o d i nt h el a s tc h a p t e r , 1w i l lt a l ka b o u tt h ed e s i g ni d e aa n d ! i i 北京邮电人学硕上学位论文 f p g ad e s i g ns t r u c t u r eo ft h el d p cc o d e rf o rd m b - t hs y s t e mw h i c hc a l ls u p p o r t q p s k , 16 q a ma n d6 4 q a mm o d u l a t i o nm o d e s t h ev a l i d i t yo ft h i sc o d e rw i l lb e d e m o n s t r a t e db yt h et i m i n gs i m u l a t i o nr e s u l t k e y w o r d s l d p c ，p a r i t yc h e e km a t r i x ，t a n n e rg r a p h ，q c - l d p c ，s p a ( s u m - p r o d u c t a l g o r i t h m ) ，m i n s u ma l g o r i t h m i v 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：幽日期：竺堕：童! ! 足 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 日期： 瑚：垒：1 8 日期：么盈弘务巧l 北京邮电人学硕士学位论文 1 1d m b t h 系统简介 第一章绪论 d m b t h 是我国自主知识产权的数字电视地面传输国家标准，它的制定和 提出对我国高新技术产业的发展和相关民族产业的振兴有着深远的影响。该标准 定义了在5 2 m h z 8 6 6 m h z 频段中，每8 m h z 数字电视频带内，地面数字电视广 播无线传输信号的规范。该系统不但具有传统电视广播服务的基本功能，还具有 适应新一代多媒体广播服务的可扩展功能，可支持固定( 含室内、外) 接收和移动 ( 含便携手式) 接收两种模式。在固定接收模式下，可以提供标准数字电视业务、 高清晰度电视业务、数字声音广播业务、多媒体广播和数据服务业务；在移动接 收模式下，可以提供标准数字电视业务、数字声音广播业务、多媒体广播和数据 服务业务。 系统发送端完成从m p e g t s 传送码流到地面电视传输信道的基带信号的转 换。输入数据码流经过扰码器( 随机化) 、前向纠错编码( b c h + l d p c ) ，然后进行 比特流到符号流的星座映射，再进行交织后形成基本数据块。基本数据块与系统 信息组合( 复用) 再经过帧体数据处理形成帧体。帧体与相应的帧头( p n 序列) 复接 为信号帧( 组帧) ，最后经过基带后处理形成输出信号( 8 m 带宽内) 。该信号经变频 形成射频信号( 5 2 m h z 8 6 6 m h z 频段范围内) 【1 】。 图1 1 所示为d m b - t h 系统发送端原理框图。 图1 1d m b - t h 系统发送端原理框图 1 2 差错控制技术 差错控制编码也称为纠错编码。在实际信道上传输数字信号时，由于信道传 输特性不理想及噪声的影响，接收端所收到的数字信号不可避免地会发生错误。 为了在已知信噪比情况下达到一定的比特误码率指标，首先应该合理设计基带信 北京邮l u 人学硕_ i j 学位论文 号，选择调制解调方式，采用时域、频域均衡，使比特误码率尽可能降低。但实 际上，在许多通信系统中的比特误码率并不能满足实际的需求。此时则必须采用 信道编码( 即差错控制编码) 才能将比特误码率进一步降低，以满足系统指标要 求。 差错控制随着差错控制编码理论的完善和数字电路技术的飞速发展，信道编 码已经成功地应用于各种通信系统中，并且在计算机、磁记录与各种存储器中也 得到r 益广泛的应用。差错控制编码的基本实现方法是在发送端将被传输的信息 附上一些监督码元，这些多余的码元与信息码元之间以某种确定的规则相互关联 ( 约束) 。在接收端，一旦收到的数据发生差错，信息码元与监督码元之间既定的 关系就会遭到破坏，接收端就可以发现错误乃至纠正错误。因此，研究各种编码 和译码方法是差错控制编码所要解决的问题。编码涉及到的内容也比较广泛，线 性分组码、交织码，卷积码、t u r b o 码等都是差错控制编码的研究范畴。 1 2 1 信道编码理论及其发展 根据香农( s h a n n o n ) 信息论【2 】 3 】提出的信道编码定理，任意离散输入无记忆 平稳信道存在信道容c ，它标志着信道传输能力的上限，只要信息传输速率r 小 于c ，就存在一种编码方式，当平均码长足够大时，译码错误概率可以做到任意 小；反之，则无论采用何种编码方式也不可能保证错误概率任意小。该定理虽然 没有明确指出如何对数据信息进行纠错编码，也没有给出这种具有纠错能力通信 系统的具体实现方法，但它莫定了信道编码的理论基础，从理论上指出了信道编 码的努力方向。 随着纠错编码理论的不断完善和超大规模集成电路( v l s i ) 的迅速发展，信道 编码已成功应用于各种通信系统中，而且在计算机、磁记录和数据存储等方面也 得到了同益广泛的应用。 信道编码的基本思想是：通过对发送端信息序列作某种变换，使原来彼此独 立，相关性极小的信息码元产生某种相关性，在接收端利用这种相关性来检查并 纠正信息码元在信道传输中所发生的差错。 在差错控制系统中使用的信道编码可以有多种。按照纠错编码的不同功能， 可以将其分为检错码、纠错码和纠删码；按照信息码元和附加监督码元之间的关 系可分为线性码和非线性码；按照信息码元在编码后是否保持原来的形式不变， 可划分为系统码和非系统码；按照纠正错误类型的不同，可分为纠正随机错误的 编码和纠正突发错误的编码；按照信息码元和监督码元之间的约束方式不同可划 分为分组码( b l o c kc o d e ) 和卷积码( c o n v o l u t i o n a lc o d e ) 。 北京邮电大学硕上学位论文 1 2 2l d p c 码的发展 l d p c 码是一种基于稀疏矩阵的奇偶校验码。g a l l a g c r 于1 9 6 2 年首先发明 了这种码，故又称g a l l a g e r 码 4 】。由于当时的计算机处理能力与相关理论的薄弱， 这种优良的码型没有在科学界引起足够的重视。随着八十年代未，应用迭代译码 思想的t u r b o 码展现出优良的性能，科学家开始重新审视l d p c 码。1 9 9 5 年 m a c k a y 和n e a l 【5 发现l d p c 码的性能足可以和t u r b o 码【6 相比，并且它描述 和实现简单，对严格的理论分析具有可验证性，译码复杂度低于t u r b o 码，可并 行计算，适合于硬件实现，具有高速译码潜力，于是他们重新介绍了l d p c 码， 这种沉寂了多年的码字很快成为了热点。1 9 9 8 年，m a c k a y 和s p i e l m a n 又发明 了不规则的l d p c 码，性能好于规则l d p c 码。 目前，l d p c 在国际上已经形成了较为完备的理论体系。t a n n e r 图 7 】与和积 算法 8 为l d p c 提供了图论模型，成为l d p c 的现代解释工具。通过图形优化 l d p c 成为一个新的研究角度。译码算法引用人工智能领域中的b p 算法【9 】，成 为l d p c 码的一个亮点。科技人员已经开始全力研究如何更有效的应用l d p c 码。目前，l d p c 码已被应用在多个领域内，如无线局域网i e e e 8 0 2 1 1 、地面广 播传输系统d v b s 2 1 0 和d m b t h 1 等等。可以预见，在未来的几年里，l d p c 码将成为纠错领域中的一个里程碑。 1 3f p g a 设计方法介绍 自从1 9 8 4 年美国x i l i n x 公司率先发明f p g a ( 现场可编程门阵列) 器件以来， f p g a 技术随着c m o s 工艺的提高而同渐成熟。f p g a 的结构类似于掩膜可编 程门阵列( m p g a ) ，由逻辑功能块排列成阵列组成，并由可编程的内部连线连接 这些逻辑功能块来实现不同的设计。f p g a 器件集成度不断增大，器件价格不断 下降的趋势，以及其现场设计、现场修改、现场验证、现场实现的可达数百万门 级的数字系统单片化的应用优势，逐渐受到各国电子系统应用领域的设计工程师 广泛的关注和欢迎。时至今日，f p g a 技术已不再是a s i c ( 专用集成电路) 技术领 域的一个点缀和补充。f p g a 技术不仅可以避免通常a s i c 单片系统设计周期长， 前期投资风险大的弱点，而且克服了过去板级通用数字电路应用设计的落后、繁 琐和不可靠性，而跃之为电子应用( 包括通信技术、计算机应用、自动控制、仪 器仪表、a s i c 设计) 领域广受欢迎的技术，成为数字系统的科研实验、样机测试、 小批量产品的即时实现的最佳途径。正式在这样的技术应用背景下，f p g a 及其 应用技术在全世界范围内，成为了电子系统设计领域的热门技术。 本论文在f p g a 设计中采用了a l t e r a 公司s t r a t i xi i 系列中的e p 2 s 9 0 f 1 0 2 0 c 5 北京邮i 【1 人学硕l ：学位论文 芯片，图1 2 给出了本论文在f p g a 设计实现过程中的流程以及在设计的各个阶 段所用到的e d a 工具。 r t l 设汁 功能仿真m o d e l s i m ) 有纠题 综台i o u a r t u si i 布局稻线( q u a r t u si i l 后仿真( m o d e l s i m ) 肯纠题 码流文件f 载( w e b p a c k l 硬件调试 图l - 2f p g a 设计流程 1 ) 对应用数字系统的设计思想进行描述( 本设计采用v c r i l o g h d l 语言) ，具 体的就是描述要实现的功能和技术要求。 2 ) 进行逻辑功能仿真，验证已描述的系统功能的可实现性。若功能不能实 现，需重新修改描述文件。 3 ) 对数字系统的逻辑功能描述进行综合，产生门级的逻辑电路图，并对其 进行逻辑化简和优化。 4 ) 制定约束文件，对具体f p g a 器件进行布局布线，得到包含延时信息 的s d o 文件。 5 ) 使用布局布线后的器件给出的模块和连线的延时信息s d o 文件作时序仿 真，在最坏的情况下对电路的功能作出更准确的估计。如果功能不能实 4 北京邮电人学硕士学位论文 现，需重新修改描述文件。 6 ) 生成码流文件，进行硬件调试。 从图1 2 中可看出，f p g a 模块设计流程主要由两大主要功能部分组成： 1 ) 设计开发：即从编写设计文件一综合_ 布局布线- 下载生成这一系列步 骤。 2 ) 设计验证：也就是进行各种仿真的一系列步骤，包括编写设计文件后的 功能仿真以及布局布线后的时序仿真，如果在仿真过程中发现问题应返 回设计输入进行修改。 1 4 设计目标和论文组织 本论文主要研究了d m b t h 系统中的l d p c 码的编解码算法，并研究使用 f p g a 来对以上算法进行硬件实现，利用a l t e r a 公司的s t r a t i xi i 系列器件 e p 2 s 9 0 f 1 0 2 0 c 5 芯片完成硬件测试。 本文的第二章讲述了l d p c 码的基本原理，这样可以便于以后几章的理解。 第三章阐述了d m b t h 系统中l d p c 码的特点，并分析了其构造方法。 第四章对d m b t h 系统中l d p c 码的编解码算法进行了研究，并对算法采 用m a t l a b 软件进行性能仿真和分析。 第五章设计了一种支持多种调制方式的l d p c 编码器的f p g a 硬件结构。 第六章是对全文的总结。 北京邮 乜人学硕十学位论文 第二章l d p c 码基本原理 l d p c ( l o wd e n s i t yp a r i t yc h e c k 低密度奇偶校验) 码最初由g a l l a g e r 在1 9 6 2 年提出【4 】，它是基于稀疏校验矩阵的线性分组码。由于当时技术条件的限制， 人们的兴趣大都集中在有实现可能的编码方式上，如卷积码、级联码等，以致 l d p c 码在很长一段时间内几乎被人们遗忘。直到1 9 9 6 年，m a c k a y 和n e a l 5 随机构造出的l d p c 码当码长很长时在性能上超过了b e r r o u 6 等人提出的t u r b o 码，而且在实现上更有优势，从而激起了编码界对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 码的译码方法和消 息传递策略。 2 1l d p c 码的定义 l d p c 码是一种线性分组码，可以用生成矩阵g 和校验矩阵h 来表示。l d p c 码又是一类特殊的线性分组码，特殊性就在于它的奇偶校验矩阵h 中非零元素 的个数远远小于零元素的个数。 g a l l a g h e r 定义的l d p c 码，其校验矩阵中每- n 包含谚，个非零元素，每一 行包含以个非零元素，若码长为，则可记为( ，谚，以) 。在校验矩阵h 中， 每一行和每一列中1 的数目是固定的。任意两行( 或两列) 之间l 的重叠数目小于 等于l ，这称为行列约束( r o w c o l u m nc o n s t r a i n t ，r c 约束) 。图2 1 是由g a l l a g h e l 构造的一个( z o ，3 ，4 ) l d p c 码的校验矩阵，它的“i 。= 6 ，设计码率为1 4 ，实际码 率为7 2 0 。 6 北京邮电人学硕一i ：学位论文 砚黾砖x i 一”譬i 0 0 00 ：00 00 ：0000 ：00 0 0 1111 ：0000 ：0000 ：0000 i1 0000 111 1 ；000 0i0000 0 000 00 00 0000 ；1111i0 000 0 000 0000 00 00 0000 1111 1000i10 00 ；1000 ；1000i0000 0100 ；0100 ；0100 ；0000 1000 0 010 0010i00 00i0100 0100 0001 ：0000 ：0010 ：0010 ：0010 0000 00 01 0001 0001 00 01 1000 01o 石i00 01 00o0010 0 0100 ：0010 ：0010 ：0001 ：00 0 0 0 010 ；00 01 ；00 00 ；1000 ；0010 0001l0000 10 00i0100 10 0 0 0 000 10 0 0i010 0j0010f0001 图2 1n = 2 0 、d v - 3 、d c = 4 规则l d p c 码校验矩阵 这种校验矩阵每行和每列中l 的数目( 汉明重量) 相同的l d p c 码称为规则 l d p c 码( r e g u l a rl d p cc o d e ) 。 2 2l d p c 码t a n n e r 图表示 l d p c 发展到9 0 年代，出现了新的表示方式：因子图表示，即t a n n e r 图。 设l d p c 码的校验矩阵h 为一个m x n 阶的矩阵，该矩阵可以由t a n n e r 图表示。 图的下边有n 个节点，每个节点表示校验矩阵的列，称为变量节点( v a r i a b l e n o d e ) ；上边有m 个节点，每个节点表示一个校验集，称为校验节点( c h e c kn o d e ) ； 与校验矩阵中1 ，元素相对应的上下两个节点之间存在连接边，我们将这条边称 为两端节点的相邻边，相邻边两端的节点称为相邻点。每个节点相邻边数称为该 节点的度数。 对于规则的l d p c 码来说，校验矩阵中每一行和每- n 中1 的个数各自相 同，对应的t a n n e r 图中上边节点度数和下边节点度数分别对应着一个固定值。 图2 2 为( 2 0 ，3 ，4 ) 的t a n n e r 图表示。下边的比特节点的度数为3 ，上边校验节点的 度数为4 。 7 孤 砭 硌 “ 砘 北京邮电人学硕上学位论文 z lz 2z 3z i z m x 1x 2 x n 图2 - 2 ( 2 0 ，3 ，4 ) 规则l d p c 码的t a n n e r 图表示 上图的下方每一个节点x n 代表的是变量节点，上方每一个节点z m 代表 的是校验节点。在校验矩阵h 中，某列x n 中有若干个非零元素，例如对于x 2 列，这列中三个1 ，分别对应于z i 、z 7 和z 1 2 行，这样就在t a n n e r 图中把x 2 和 z l 、z 7 和z 1 2 连接起来。从行的角度考虑，把某一行z m 中非零点处的x f - 相 连，得到同一个t a n n e r 图。在规则l d p c 码中，与每个变量节点相连边的数目 是相同的，校验节点也具有相同的特点。在译码端，把与某一个校验节点z i n 相 连的x n 求和，结果若为0 ，则无错误发生。 与规则l d p c 码相对应的是非规则l d p c 码( i r r e g u l a rl d p cc o d e ) 11 ， 其校验矩阵h 中每行中1 的个数不同，每列中1 的个数也不一样。其编码方法 与规则l d p c 码基本相同，非规则l d p c 码的t a n n e r 图中变量节点之间、校验 节点之间的度有可能不同，是一个变化的值。非规则码的性能要好于规则码，最 近几年的研究表明，对于在g f ( 8 ) 构造的非规则码，它的性能要比t u r b o 码还好， 能够显著提高码字性能，其性能非常接近于s h a n n o n 限。 2 3l d p c 码的构造 l d p c 码是一种随机码，没有特定的生成多项式和校验多项式。描述该码的 参数为码长和稀疏校验矩阵中变量节点和校验节点的度分布。构造方法是根据通 信系统中要求的码长和码率来确定校验矩阵的维数，然后通过线性编程工具等获 得性能优异的度分布表达式，最后根据优异的度分布填充非零元素的位置。目前 已有多项技术来具体构造校验矩阵，主要分为代数构造和随机构造两类。 2 3 1l d p c 码的随机构造 北京邮电大学硕十学位论文 l d p c 码分为两种：规则l d p c 码和非规则l d p c 码的构造。对于规则l d p c 码，由于度分布是确定的，因此构造规则的校验矩阵。 1 最早的l d p c 码g a l l a g c r 码 最早的l d p c 码是g a l l a g e r 码。g a u a g e r 码是线性分组码，它是由校验矩阵 h 定义的。由于h 对应唯一的生成矩阵g ，所以校验矩阵的构造是编码的关键。 由于检验矩阵是非系统形式的，所以g a l l a g e r 码是非系统码。 g a l l a g e r 码的校验矩阵构造规则如下： 可以把g a l l a g e r 码的校验矩阵按行划分为j 个部分( 每部分包含相同的行数) ， 每个部分的每一列中包含一个l 。 第一部分的构造很有规律：第一行中，第1 k 个元素为1 ，其余为0 ；第 二行中，第k + l 到第2 k 个元素为1 ，其余为 0 ；以此类推，第i 行中，第( i 1 ) k + l 到i l 【个元素为1 ，其余为一0 。 其余( j 1 ) 个部分的构造是在第一部分的基础上，对第一部分进行列的随机 重排。 g a l l a g e r 码的好处之一是可以保证每行有k 个1 ，每列有j 个l 。按上述方法 很容易构造一个稀疏矩阵，且满足每行每列含有固定数目的1 元素。一旦确定 了k 、j ，则相应也确定了g a l l a g e r 码的码速r ： ，：( 一m ) n ：n - j - ( n k ) ：1 一歹七 式( 2 1 ) v 其中，n 为编码后的比特数，m 为校验比特数，j 为列重，k 为行重。 上述码的另一个好处是，在构造其余i 1 部分时，为编码引入了一定随机性， 符合s h a n n o n 证明信道编码定理引用的三个必要条件之一：采用随机编码。( 其 余两个条件分别是编码长度l 哼0 0 和译码采用最佳的最大似然译码方法) 。 图2 1 是g a l l a g e r 码的检验矩阵的一个例子。g a l l a g e r 码为我们寻找好的纠 错编码打开了一扇新的窗户，但它由于处在发展的初期，本身是粗糙的。为进一 步提高码的性能，人们的研究更加的深入，继承并发展了g a l l a g e r 的思想。 2 r a d f o r dm n e a l 的构造方法 r a d f o r dm n e a l 的构造方法【1 2 】在构造h 时，有列均匀方式( e v e n c 0 1 ) 和 行列均匀方式( e v e n b o t h ) 两种。标准的规则l d p c 码的行和列中1 的个数都是 均匀的，但是为了避免长为4 的环，采用行列均匀构造会增加很多系统时延，因 此，有时候选择列均匀的方式。在这种方式下，如果检测到有长为4 的环，则删 除一个l ，这样这一行1 的个数将会少一个，但这种方式下构造速度就会快得 多。 构造h 的步骤如下： 9 北京邮电火学硕l ：学位论文 系统先生成一个全0 的矩阵。 用e v e n c o l 或者e v e n b o t h 方式构造一个原始校验矩阵。 搜索只有0 个l 或只有1 个1 ，的行。若某一行为0 个l ，则表明此行 是冗余的，则在此行随机选择两列置l ，若某一行为1 个1 ，则表明此 码元始终为0 ，则随机的另找l 列置l 。 如果上两步得到的矩阵的每一列都有偶数个1 ，则随机的给其中1 列加 入一个l ，这样可以在编码时避免行相加得0 ，即避免出现冗余的校验 方程。 检测是否出现4 环，即任选两行两列，交叉点上的元素都为1 ，的情况。 如有4 环存在，则将其中的一个1 ，在其所在列随机地上下移动到另外一 个位置，由此将4 环消除。对于整个矩阵来说，可以一直进行消除4 环 的操作直到所有的4 环都被删除，或者规定消除次数，如果大于这个数 还没有删除所有的4 环则放弃。 在得到校验矩阵h 后，就可以由g h7 = 0 得到了相应的生成矩阵g 。 设信息源为s ，则编码生成的码字u = s g 。 2 3 2l d p c 码的代数构造 随机构造l d p c 码虽然具有优越的性能，但是它没有特定的结构，并且编 码方法不利于硬件实现；相比之下，代数构造的l d p c 码虽然受码长和码率的限 制，但是由于具有特定的结构，有利于硬件实现编码。因此，最近几年大量文献 研究了如何采用代数方法构造l d p c 码。 在代数构造中，典型的方法是有限几何构造l d p c 码，又分作欧式几何和 投影几何两种： 1 欧式几何( e u c l i d e a ng e o m e t r y ，e g ) 法 设e g ( m ，2 5 ) 是有限域g f ( 2 5 ) 上的m 维欧氏几何，该几何容纳2 脚个点， 每一点又是g f ( 2 ) 上的m 重，全0 的m 重o ：( 0 ，o ，0 ) 称为几何空间的原点。 在g f ( 2 。) 上的m 重形成了2 舢上的m 维矢量空间，在e g ( m ，2 5 ) 上的一条线要 么是一维子空间，要么是一维子空问的陪集。因此，e g ( m ，2 5 ) 上的每一条线均 包含2 5 个点。在e g ( m ，2 ) 里共有2 1 ”- i ) , ( 2 ”一1 ) ( 2 一1 ) 条线，每条线均有 2 研- 1 n l 条线与之平行，每个点均有( 2 ”一1 ) ( 2 5 一1 ) 条线相交于此。 设g f ( 2 ”) 是g f ( 2 5 ) 的扩域，在g f ( 2 ”) 罩的每一个元素都可以表示成 l o 北京邮f 乜人学硕上学位论文 g f ( 2 5 ) 上的m 重。因此，在g f ( 2 ”) 里的2 舢个元素可以用来表示e g ( m ，2 ) 上 的2 脚个点，有限域g f ( 2 ”) 可以表示欧氏几何e g ( 脚，2 ) 。设口是g f ( 2 ”) 里的 本原元素，那么0 = a 。，a o ，a 1 ，a 2 ，a 2 ”。2 就构成了欧式几何e g ( m ，2 5 ) 上 的2 雕个点。设a ，a j 是e g ( m ，2 5 ) 里的两个线性独立的点，那么下面点的集合 a + 励7 ) 口 a + 励7 ：g f ( 2 5 ) ) 就是e g ( m ，2 5 ) 里通过点口的一条线。两条线 没有交点就是平行的，如果有交点也只能有一个交点。 以e g l d p c 码( 1 0 2 3 ，7 8 1 ) 为例说明e g - l d p c 码的构造过程如下： 1 ) 首先，知道e g ( 1 0 2 3 ，7 8 1 ) 码是欧氏几何e g ( 2 ，2 5 ) 上的码，即m = 2 ，s = 5 。 e g ( 2 ，2 5 ) 里的点是由g f ( 2 ”) = g f ( 2 m ) 中的元素表示的，我们可以先构 造伽罗华域g f ( 2 m ) 。我们知道g f ( 2 1 0 ) 是由本原多项式 p ( x ) = l + x 3 + 工1 0 生成的，由域元素生成电路可得到g f ( 2 1 0 ) 中每一个元 素在g f ( 2 ) 上的l o 重表示。 2 ) 其次，需要求出经过某一点的任意一条不过原点的直线上的所有其它点。 已知通过点a 的一条线上的点具有 a + p a 7 ) 口 a + p a 7 ：g f ( 2 5 ) ) 形式，如果要求解经过点a m 2 2 的线，就需要求满足形式为 a 1 0 2 2 + f l a 7 ) 的 点，取厂= a 2 ”一1 h r 一1 = a ”，则 0 ，1 ，厂，厂2 ，y 3 0 ) ，根据运算可以得到 一条含3 2 个点的一条直线。 3 ) 再次，由所得的直线去求出该直线的关联矢量。该矢量由1 0 2 3 个点( 不 包含原点在内) 组成，如果某点在直线上，则关联矢量该点处的值为l ， 不在此直线上则为0 。 4 ) 最后，由所得的关联矢量作为校验矩阵的第一行，对该矢量向右循环移 位1 0 2 2 次，每次得到的矢量均作为校验矩阵的一行，就得到了二维欧氏 几何l d p c 码的校验矩阵。 2 射影几何( p r o j e c t i v eg e o m e t r y , p g ) 法 同欧氏几何一样，可以由伽罗华域中的元素构造射影几何，只是每条线上的 点数和每个点包含在的直线数目不同；得到一条直线上的点后，求出其关联矢量， 和构造e g l d p c 码的校验矩阵一样，将其作为第一行，循环移位得到其它所有 行。需要说明的是，e g - - l d p c 、p g - - l d p c 均是循环码或准循环码，循环码或 北京邮电大学硕十学位论文 者准循环码的编码复杂度由于和码长成线性关系，它们的编码复杂度最低；从性 能上考虑，具有大的最小距离的码字有很多都落在准循环码这个集合罩。因此， 用好的方法找出这些具有较大最小距离的准循环码是l d p c 码研究的一个热点。 利用平衡不完全区组设计( b a l a n c e di n c o m p l e t eb l o c kd e s i g mb i b d ) 构造 l d p c 码也是一种非常有效地方法。 由于对任一个区组设计，其关联矩阵a 的转置可对应于l d p c 码韵稀疏矩 阵。即把区组设计中的v 元集与校验矩阵的列对应；区组的个数与校验矩阵的行 对应；区组长度对应于校验矩阵的行重。若