（信号与信息处理专业论文）ldpc码的理论分析与好码设计.pdf

北京交通人学硕十学位论文 中文摘要 中文摘要 摘要；低密度奇偶校验( l o wd e i l s i t yp a f i t yc h e c k ，l d p c ) 码是一种基于图 和迭代译码的信道编码方案，性能非常接近s h 蛐o n 极限且实现复杂度低，具有 很强的纠错抗干扰能力。由于其良好的性能、接近线性时间复杂度的编码算法、 可并行实现的译码算法以及广阔的应用前景，u ) 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 码的最小距离和围长( 廖r m ) 的基础上，分析了短环的存在 对码性能的影响，并主要研究了l d p c 码在n e r 图中的环在校验矩阵中的形状， 提出了一种计算复杂度相当低的方法来统计l d p c 码中短环( 四环，六环) 的数目。 这种方法是在判断校验矩阵中任意两行( 列) 之间重叠度的基础上，来检验校验 矩阵中的短环( 四环，六环) 数。 然后，将这种环数检验方法与现有准循环码的设计思想相结合，作为约束条 件，根据环数检验结果调整校验矩阵中循环子矩阵的维数和移位因子，获得无四 环，一些情况下亦无六环的准循环码，而且设计出来的准循环码性能非常优越。 最后，本文提出两种不规则准循环l d p c 码的设计方法，第一种方法将校验矩 阵中的特定位置的子矩阵用零矩阵和循环矩阵置换，获得一非奇异的方阵，该方 阵用于构造生成矩阵。第二种方法是对设计好韵校验矩阵进行列交换，获取一主 对角线为1 的方阵，在将该方阵主对角线下的1 元素部分删除，使该方阵变为非奇 异的，然后用于构造生成矩阵。并且以实例说明所提出的设计，计算机仿真结果 验证本文设计的准循环l d p c 码具有良好的误码率性能。 关键词：信道编码；低密度奇偶校验码：校验矩阵： 环；检验算法；准循环 码 拙塞交通友堂亟堂焦论塞旦墨i 王 a b s t r a c t a b s t r a c t l o w - d s i t yp 撕t y c h e c k ( l d p c ) c o d c sa r cad 硒so fc h a n l c o d e sb a s e do n 孕a p h sa n di t e r a t i v ed e c o d i n gw h o s ep 盯f o 眦a n c ei sv e r yc l o s et ot h e s h a n n o nl i m i tw i ml o wc o f i l p l e x i t y 锄dh a v es 仃o n g 锄rs 嘶g t h b e c a u s eo ft h e i r o u t s t a n d i n gp 柏r n l a i l c e ，鲫de n c o d i n ga l g o r i t l l 】m w h i c hh 船a l m o s tl i n e a rt i m e c o m p l e x i t y ，d 。c o d i n ga l g o r i 岫w h i c hc o u i db ei m p l 锄e n t e di np a m i l da r c h i t e c t l l r c a n dt h ew i l d l ya p p l i c a t i o n 如t l i r e ，t | l e yh a v eb e c o m eo n eo ft l l eh o t t 黜tt o p i c si nc o d i n g f i e l dt o d a y i nt h i sp 印e r ，1 1 1 et h e o r y 柚dd 鼯i 印o fl d p cc o d 嚣a r es t u d i e d ，w h i c h i n v o l v 髓a l g c b r ap r i n c i l 1 b l o c kc o d e s p f i n c i p l e s ，c o d i n d e c o d i n g ， a 1 1 d c o l l s t r i l c t i o no fs p a r s ep a r i t y c hc c ：km a t r i x ，w em a i n l yd om er e s e a r c ho nt i l ee n c o d i n g o p t i m i z a t i o no f l d p c o d d e s f i r s to fa l l ，b a s c do nt h em i n i 舢md i s t 锄c e 蛐dg i m lo fl d p cc o d e s ，m i sp a p e r a n a l y z e st h ei n n u e i l c eo nt h ep 柏n n a n c eo fc o d e sb f o u g h tf o n nt h ee x i s t e n c eo fs h o r t c y c l es u c ha s4 - c y c l ea t l d6 一c y c l e ，a n dd e e p l ys t u d y st h es h a p c so f 也ec y c l e so ft gi n p 耐t yc h e c km a t r i x ，t h e np r c s e n t sak i n d o fa l g o 洲sw i t h l o wc o m p u t a t i o n a l c o m p i e x i t yf o rc o u n t i n gt h en u m b e ro f s h o r tc y c l e s t h e n ，b yc o m b i n i n gm i sa l g o r i t h mw i t ht h ep r e s e n t e dd e s i 印o fq u a s i c y c l i c ( q c ) l d p cc o d e s ，m i sp a p a p r o p o s et h ec o n s “| a i n tc o n d i t i o n sf o rt h ec o n s t n l c t i o no ft h e ( l d p cc o d e s ， i tn e e d sa d j u s tt h ed i m s i o na n dm es h mf a c t o r so ft h ec i r c u l a n t m a t r i c e so ft h eg i v e ns p a r s ep 撕t y c h e c km a t r i c e sa c c o r d i n gt 0m et 豁tr e s u i t so fs h o r t 百n h s b ym i sw a y ，w ec 蛐o b t a i n t l l eq cl d p cc o d 韶w i t h o u t4 c y c l e ，s o m c t i m e se v 、v i t l l o u t6 一c y c l e ，a l l dt 1 1 ep e r f o 啪a n c eo f t h eq cl d p cc o d 豁i sq u i t eg o o d f i n a l l y ，t l l i sp a p e rp r o p o s 嚣“v oa p p f o a c h e so fi 仃i 强l l a rq cl d p cc o d e s t 1 l e 缸t 印p r o a c hi s t or 印l a c es o m e 鳓1 b - m a 砸c e sb yz e r om a t i i c 嚣锄di d c i l t i t ym a t c e sa t s p e c i a lp o s i t i o n si nt l l e 舀v e ns p a 巧ep 撕t y c h c c _ km 删c 铭，t og c tan o n s i i l g u l a rs q u m m 删xf o fm ec o n s t n l c t i o no fg c 札啪t o rm a t r i x t h es e c o n da p p r o a c hi sp e n i l u t et h e c o l 岫n so ft h ed e s i 匦c dp 撕妒c h e c km a t r i xt oo b t a i na 鲫b m a t r i xw i t l la l l1 sa ti t s d i a g o n a ll i n e ，t l l e l ld d c t es o m elc 1 伽锄t sb e l o w t l l ed i a g o n a l1 i n et og e tan o n s i n g u l 缸 s q u a r em a t r i xf o rt h ec o i l s t r u c t i o no fg e n e r a t o rm 删x e x 锄叩l 鹤a r ep f o v i d e df o rt h e p r o p o s c dd e s i 驴o f q cl d p c o d c s ，锄dc o m p u t 盯s i m u l a t i o nr e s u l t ss h o wt h a t 圮q c l d p cc o d e sb y p r o p o s e dc 0 璐拄u 而o n sa c h i e v eg o o db e rp e 晌肋a i l c e k e y w o r d s ：c h 锄e lc o d i n g ；l o 、d 锄l s i t yp a 一呻e c k ( l d p c ) c o d e s ； j e 塞窑通叁堂甄堂位论塞 垦工丛! c h e c km a t r i x ；c y c l e ；c h e c ka i g o r i ( i 瑚；q u a s i - c y c l i c ( ( k ) c o d 嚣；c i r l a l l tm a t r i o 鹳 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：撕 签字r 期：面7 年f 月 r 铆躲协 签字目期：2 ”7 年i 硐。f 同 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：签字同期：年月日 致谢 本论文的工作是在我的导师肖扬教授的悉心指导下完成的，肖老师严谨的治 学态度和科学的工作方法给了我极大的帮助和影响。在读研究生期间，肖老师对 我严格要求，在备方面给予悉心指导和帮助，使我的科研和工作能力有了很大的 提高。对于我的论文肖老师也提出了许多的宝贵意见，在此表示衷心的感谢。 感谢我的父母，是他们的培养和支持使我取得今天的成绩。在此，深切地感 谢父母亲二十多年来的养育之恩和教导。 感谢胡伟、杨文聪、候迎宾同学在我研究生学习和生活期间给我无微不至的 关心和帮助，他们提供的建议使我受益匪浅。 感谢师姐鲁凌云，师兄赵莹、杜海峰、范俊、曹振臻、孔令军，以及众位师 弟师妹对我的支持和帮助，他们为我提供了个温暖的集体氛围，使我能更投入 的完成论文。 最后向所有关心、帮助和支持我的人致以衷心的感谢! j e 塞奎通太堂亟堂位i 金奎 压 序 本论文的研究工作是在国家自然科学基金项目( 6 0 5 7 2 0 9 3 ) 的资助下完成， 在肖扬老师的大力帮助下，本文作者对l d p c 码编译原理进行了深入研究。l d p c 码以其优异的性能在今后新一代移动通信系统中具有潜在的应用前景，因此本论 文研究内容具有理论和实用意义。 本文在分析影响l d p c 码的因素( 如坏，最小距离等) 的基础上，实现了u ) p c 码的优化设计。本文设计的码字性能在不同码长、码率下均具有优异的性能，且 设计的码字具有准循环的特性，具有硬件实现简单的特性。 北京交通大学硕士学位论文 1 引言 本章简要介绍了数字通信系统的结构，结合纠错码的发展过程介绍了l d p c 码的出现及其发展，以及l i ) p c 码的研究现状及应用背景；最后总结了作者在攻 读硕士期问所做的主要工作并给出了本文内容安排。 1 1数字通信系统结构 图1 1 所示的是一个数字通信系统的基本模块组成图 l 】。信源输出的可以是模 拟信号，如音频或视频信号；也可是数字信号，如电传机的输出，该信号在间上 是离散的，并且具有有限个输出字符。在数字通信系统中，由信源产生的消息变 换成二进制数字序列。理论上，应当用尽可能少的二进制数字表示信源输出。换 句话说，我们要寻求一种信源输出的有效表示方法，使其很少产生冗余或不产生 冗余。将模拟或数字信源的输出有效地变换成二进制数字序列的处理过程称为信 源编码或数据压缩。 图1 1 数字通信系统的基本组成部分 由信源编码器输出的二进制数字序列称为信息序列，它被传送到信道编码器。 信道编码器的目的是在二进制信息序列中以受控的方式引入一些冗余，以便于在 接收机中用来克服信号在信道中传输时所遭受的噪声和干扰的影响。因此，所增 加的冗余是用来提高接收数据的可靠性以及改善接收信号的逼真度的。实际上， 信息序列中的冗余有助于接收机译出期望的信息序列。例如，二进制信息序列的 一种平凡的形式的编码就是将每个二进制数字简单重复历次，这里坍为一个j 下整 数。更复杂的编码涉及到一次取七个信息比特，并将每个| | 比特序列映射成唯一的 弹比特序列，该序列称为码字。以这种方式对数据编码所引入的冗余度的大小是由 比率”| 来度量的。该比率的倒数，即七，一，称为码字的速率或简称码率。 引言 信道编码器输出的二进制序列送至数字调制器，它是通信信道的接口。因为 在实际中遇到的几乎所有的通信信道都自够传输电信号( 波形) 。所以数字调制的主 要目的是将二进制信息序列映射成信号波形。为了详细说明这一点，假定已编码 的信息序列以均匀速率月( 6 s ) 一次一个比特传输数字调制器可以简单地将二迸 制数字“o ”映射成波形( f ) ，而二进制数字“l ”映射成波形焉) 。在这种方式中， 信道编码器输出的每一比特是分别传输的。我们把它称为二进制调制。另一种方 式，调制器一次传输6 个已编码的信息比特，其方法是采用膨= 2 个不同的波形 5 ，( 嘎f ；o ，l ，2 ，肠，每一个波形用来传输2 6 个可能的6 比特序列中的一个序列。我 们称这种方式为m 元调制( 膨 2 ) 。注意，每6 r 秒就有一个新的6 比特序列进 入调制器。因此，当信道比特率胄固定，与一个西比特序列相应的膨个波形之一 的传输时间量是二进制调制系统时间周期的6 倍。 通信信道是用来将发送机的信号发送给接收机的物理媒质。在无线传输中，信 道可以是大气。另一方面，电话信道通常使用各种各样的物理媒质，包括有线线 路、光缆和无线微波等。无论用什么物理媒质来传输信息，其基本特点是发送信 号随机地受到各种可能机理的恶化，例如出电子器件产生的加热性嗓声，人为噪 声( 如汽车点火噪声) 及大气噪声( 如在雷暴雨时的f j 电) 。 在数字通信系统的接收端，数字解调嚣对受到信道恶化的发送波形进行处理， 并将该波形还原成一个数的序列，该序列表示发送数据符号的估计值( = 进制或彬 元) 。这个数的序列被送至信道译码器，它根据信道编码器所用的关于码的知识 及接收数据所含的冗余度重构初始的信息序列。 解调器和译码器工作性能好坏的一个度量是译码序列中产生差错的频度。更准 确地说，在译码器输出端的平均比特错误概率是解调器译码器组合性能的一个度 量。一般地。错误概率是下列各种因素的函数：羁特征、用来在信道上传输信息 的波形的类型、发送功率、信道的特征( 郎噪声的大小、干扰的性质等) 以及解 调和译码的方法 作为最后一步，当需要模拟输出时。信源译码器从信道译码器接收其输出序列， 并根据所采用的信源编码方法的有关知识重构由信源发出的原始信号。由于信道 译码的差错以及信源编码器可能引入的失真，在信源译码器输出端的信号只是原 始信源输出的个近似。在原始信号与重构信号之间的信号差或信号差的函数是 数字通信系统引入失真的一种度量。 本文关心的是图1 1 中的信道编、译码器两个方框。为了研究方便我们可以将 图1 1 模型简化为图i 一2 。在此模型中，信源是指原来的信源和信源编码器，其输出 是二( 多) 迸制信息序列。信道是包括发射机、实际信道( 或传输媒质) 和接收机在内 的广义信道( 又称编码信道) ，它的输入是二( 多) 逆制信息序列，输出一般也是二( 多) 2 j t 京交通大学硕士学位论文 进制信息序列。信宿可以是入或计算机。 国1 2 数字通信系统的简化模型 1 2纠错编码领域的相关发展 通信的目的是要把对方不知道的消息及时可靠地【l 。j ( 有时还须秘密地) 传送 给对方，因此，要求一个通信系统传输消息必须可靠与快速，在数字通信系统中 可靠与快速往往是一对矛盾。若要求快速，则必须使得每个数据码元所占的时间 缩短、波形变窄、能量减少，从而在受到干扰后产生错误的可能性增加，传送消 息的可靠性减低。若要求可靠，则使得传送消息的速率变慢。因此，如何较合理 地解决可靠性与速度这一对矛盾，提高信息传输的可靠性和有效性，是j 下确设计 一个通信系统的关键问题之一。纠错码也正是在解决这对矛盾中不断发展起来的， 它是提高信息传输可靠性的一种重要手段，已经经历了4 0 年的历史，在此期间有 了很大的进展。伴随着信息时代的到来以及微电子技术的飞速发展，今天纠错码 已不再单纯是理论上探讨的话题了，它已经成为一门标准技术而被广泛采用。在 通信领域中，c r c 校验已成为c c t 对各类线路传输建议中不可缺少的一部分；在 移动通信中，纠错码被广泛用于模拟体制的信令传输及数字体制的整个传输，以 提高传输的可靠性和节省珍贵的频谱资源：在卫星通信中，纠错码技术已成为用 来降低对高功放的要求和减少地球站天线孔径的尺寸的经济可靠的方法，v s a l 和 u s a t 的兴起，都是和纠错码技术的应用有关的；在电话网上的数据传输中，纠错 码，差错控制技术已是使高速数据传输( 9 6 k b s 以上的数据率) 成为现实的关键 技术。纠错码技术还广泛应用予计算机存储和运算系统中，此外，纠错码技术还 应用于超大规模集成电路( v l s l ，u l s i ) 设计中，以提高集成电路芯片的成品率， 降低芯片的成本。 1 9 4 8 年香农( s h a l l n ) 在他的开创性论文“通信的数学理论”中，首次阐明了 引言 在有扰信道中实现可靠通信的方法，提出了著名的有扰信道编码定理，奠定了纠 错码的基石。 几十年来，人们一直致力于能构造出能达到s h a l m o n 限的编码最佳编码方案。 5 0 年代至8 0 年代，相继出现了许多编译码方法，如汉明码( h 嬲蛐i n gc o d 船) 、 循环码( c y d i cc o d e s ) 、b c h 码( b o s 争c h a u d h i l 妒h o c q u e i l l l 咖c o d c s ) 、r s 码 ( r e e d s o l o m o nc o d e s ) 、卷积码( c o n v o l u t i o n a lc o d 懿) 、级联码( c o n c a t e n a t e d c o d 嚣) 等。大部分已经确定的码是线性分组码。线性分组码在编码方面很容易实 现，但是一般的线性码译码算法是一个n p c o m p l 咖( n o n 出e m i n i s t i cp o l y l i o m i a l c 0 唧l e t e ，是计算问题，一般来说是需要指数计算时间才能解决的问题) 。信道编 码定理指出，随着码长捍的增加，译码错误概率按指数接近于零。因此要使码有效， 就必须用长码。但是，随着码长的增加，在一个码组中要求纠错的数目相应增加， 译码器的复杂性和计算量也相应增加以致难以实现。为了解决性能与设备复杂性 的矛盾，1 9 6 6 年g d f o m e y 提出了级联码概念。级联就是能使码具有实用的译码 器的一种方法。级联码利用了交织的思想，它由两个取自不同域的子码通过交织 器串联而成。内码是约束长度较短的分组码或卷积码，采用最大似然的v “e r b i 译码， 外码是约束长度较长的多进制r s ( r o c d s o l o m o n ) 码，采用代数译码算法。级联码 不仅有极强的纠突发和纠随机错误的能力，更重要的是利用级联码的构造方法， 能达到信道编码定理所给出的码限，也就是能构造出渐近好码( s h a n n o n 码) 。 8 0 年代，信道编码的一个重大发展是网格编码调制技术( t c m ，t r c l l i s c o d e d m o d u l a t i o n ) 和多级调制技术( m l c ，m u l t i l e v e lc o d i n g ) 的提出。1 9 7 7 年i m a i 提出了将分组码同调制相结合的m l c 技术，1 9 8 2 年u n g e r b o e c k 提出将卷积码同调 制相结合t c m 技术，在a w g n 信道下t c m 为最佳抗干扰方案，这两种方案都是在 不扩频特性下将信道编码与调制技术相结合，通过对信号空间不同分配，来最大 化星座点间的最小欧式距离，从而达到最佳抗干扰的目的。 9 0 年代，信道编码理论取得了突飞猛进的进展。b e 肿等在1 9 9 3 年提出的 1 u l l 坶码【酊，在加性白噪声信道下的性能接近了s h 锄n 限，这标志着实用的接近 s h a 衄傩限的信道编码的开始。t l l r b o 码。又称并行级联卷积码( p c c c ) ，是由b e 嗍l 等在i c c 9 3 会议上提出的。他巧妙地将卷积码和随机交织器结合在一起，实现了 随机编码的思想：同时，采用软输出迭代译码来逼近最大似然译码。模拟结果表 明，如果采用大小为6 5 5 3 5 的随机交织器，并且进行1 8 次迭代，则在e ，d o 7 扭 时，码率为l 挖的t l 曲。码在a w g n 信道上的误比特率( b e r ) l 旷，达到了近 s h 柚n 限的性能( 1 2 码率的s h 枷限是o d b ) 。因此，这一超乎寻常的优异性 能，立即引起信息与编码理论界的轰动。由于t u f b o 码的上述优异性能并不是从理 论研究的角度给出的，而是从计算机仿真的结果。因此，1 b 0 码的理论基础还不 4 北京交通大学硕士学位论文 完善。后来经过不少人的重复性研究与理论分析，发现1 、u b o 码的性能确实是非常 优异的。因此，t u l b o 码的发现，标志着信道编码理论与技术的研究进入了一个崭 新的阶段，它结束了长期将信道截止速率作为实际容量限的历史。经过编码界的 不懈努力，已找出诸多各类性能最好码。 1 3l d p c 码的研究现状及应用前景 随着移动通信的发展，对纠错码不断地提出新的要求。t u r b 码虽已成为3 g 的 信道编码标准，但其译码复杂度高，时延长，难以适应最高数据速率远比3 g 要高 的后3 g ( 即b 3 g ，或4 g ) 未来移动通信系统的需求。l d p c 码在新一代移动通信 超3 g 中有着很大的用武之地，因为l d p c 码本身即有抗突发差错的特性，在许多 场合下性能优于t u r b o 码，具有较大灵活性和较低的差错平底特性：描述简单，对 严格的理论分析具有可验证性：不需要引入交织器，避免了可能带来的时延：译 码复杂度低于t u r b o 码，且可以实行完全并行的操作，便于硬件实现：吞址量大， 极具高速译码的潜力；它不仅具有接近s h a m l o n 限的优异性能，同时由于在码的 构造、译码方法上的相关成果的获得使得l d p c 码在信道条件较差的无线通信中 展现出了巨大的应用静景，非常适合于在未来的移动通信系统中的实现。因此研 究适用于未来移动通信系统的l d p c 码对改善整个系统的传输性能具有重要意义。 l d p c 码最早是由麻省理工学院的r g g a l l a 2 e r 于1 9 6 3 年发明的【4 s l 。在其论文 中，g a l l a g e r 提出了规则l 【) p c 码的构造方法、编译码算法以及最小汉明距离分析 和译码算法的性能分析。由于当时的条件限制，编译码器的硬件实现几乎是不可 能的：同时，因为没有足够计算能力的计算机，所以精确细致的仿真也不能实施， g a l l a g c r 只能给出高子l o 。的误码率。由于这些原因，尽管l d p c 码有很好的纠错能 力，但仍然被人们忽略了3 0 多年。现在看来，其的最大成就可能是提出了一种全 新的译码器，展现了一种全新的译码思想。这种译码器主要有三个显著特征； ( 1 ) 译码算法的计算复杂度随码长n 的增加丽线性的增加。 ( 2 ) 是一种软判决译码算法。 ( 3 ) 是一种迭代译码算法，具有全并行结构。 1 9 8 1 年，t a n n e r 提出的用二分图表示一个低密度线性分组码的方法成为u ) p c 码的主要分析工具l 。二分图是由比特节点和校验节点以及连接它们的边组成。 比特节点对应校验矩阵中相应的列；校验节点对应校验矩阵中相应的行。一个二 分图和一个校验矩阵完全对应。我们可以用二分图代替校验矩阵来表示l d p c 码， 从而可以从图论的角度来分析u ) p c 码的距离特性、性能限。 t i 曲。码的发明让人们重新意识到了l d p c 码。上世纪9 0 年代后期，m a c k a y ， 5 引言 n 翰l f 7 朋等人重新发现了u ) p c 码。通过大量的仿真，m a c k a y 等人表明和t u r b o 码 样，u p c 码也具有近香农艰的性质。 m a c k a y 、l u b y 提出的不规则l d p c 码将l 【) p c 码的概念推广。不规则u ) p c 码 的性能不仅优于规则l d p c 码，甚至还优于t u r b o 码的性能，是目前已知的最接近 香农限的码。 硒c h a r d s o n 和u r b a n k 也为l d p c 码的发展做出了巨大的贡献。首先，他们提出 了一种新的编码算法，在很大程度上减轻了随机构造的l d p c 码在编码上的巨大运 算量需求和存储量需求。其次，他们发明了密度进化理论，能够有效的分析出一 大类l d p c 译码算法的性能限。仿真结果表明，这是一个非常紧的性能限。最后， 密度进化理论还可以用于指导不规则l d p c 码的设计，以获得尽可能优秀的性能。 k i m 和“n 等人从代数、几何理论着手，用确定性算法构造出了性能也很好的l d p c 码。 目前，l d p c 码被认为是迄今为止性能最好的码l ”。l d p c 码是当今信道编码 领域的最令人瞩目的研究热点，近几年国际上对l d p c 码的理论研究以及工程应用 和v l s i ( 超大规模集成电路) 实现方面的研究都已取得重要进展。基于l d p c 码的优 异性能可广泛应用于光通信、卫星通信、深空通信、第四代移动通信系统、高速 与甚高速率数字用户线、光和磁记录系统等。 由于l d p c 码提出的较晚和第3 代移动通信标准失之交臂，但基于l 【) p c 编码的 方案极有可能成为4 g 移动通信系统的应用方案。目前已有很多系统采用l d p c 码。 基于l d p c 码的编码方案已经被下一代卫星数字视频广播标准d v b s 2 采纳。休斯 网络系统是首批把l i ) p c 码重新投入商用的公司之一。休斯将其u ) p c 作为可合成 核心，向半导体公司发放许可证。目前至少有一个持有许可证的半导体公司预计 最早于2 0 0 4 年下半年提供业界首款基于l 【) p c 的数字解调芯片，著将用于遵循 d v b - s 2 的机顶在我国地面数字电视传输标准建设备选的方案中，广电总局广科院 的t i m i 方案性能较好。该方案最大的技术亮点就是采用了l d p c 码信道编码技术。 据日经b p 社报道，日本产业技术综合研究所、n e c 电子和东京电力9 月6 臼宣布， 利用产综研的集群计算机“a i s 下s u p 盯c l 瑚t 一成功验证了l d p c 码的有效性。这次 验证说明，验证了l d p c 不存在e 啪r f l 0 0 r 据此，i e e e 8 0 2 3 趾工作小组全体通过， 在面向双绞线的1 0 g b i 以以太网标准“l o g b a s e t ”的草案中采用l d p c 码。在芯片 方面，c o m t e c ht e l e c o f 咖u n i c a t i o 略旗下的c 锄t e c ha h a 公司( a h a ) 近日推出一种 低密度奇偶校验码( l d p c ) 前向纠错( f e c ) 编解码器内核。该l d p c 码比其它商用 f e c 方式具有更高的误码率( b e r ) 性能。由于整合了高反复性能该l d p c 码的b e r 比现有其它纠错技术更接近香农极限。此次推出的u ) p c 内核支持多种编码、调制 格式及数据率，可动态改变以适应变化的信道条件。该内核以f p g a 实现，支持高 6 北京交通大学硕士学位论文 达3 0m b i 魄的数据率、块大小最高为3 0k b i 以，输入量化多达6 位，每块可编程反复 达2 5 6 次。此外该内核还可根据需求以a s i c 实现。a h a 的l d p c 码适用于远距离传 输或减少多种通信系统的传输功率，其应用包括无线、卫星通信、磁存储器及其 它数据通信等。 1 4本文的研究重点和所作的工作 本文采用理论分析和计算机仿真相结合的方法，对l d p c 码的优化设计进行 了深入研究。在总结l d p c 码的代数基本原理以及编译码原理的基础上，深入研 究了影响l d p c 码性能的重要因素环，提出了一种计算复杂度相当低环数检 验算法。完成了一系列准循环l d p c 码的优化设计，并且仿真结果验证本文设计 的准循环l d p c 码具有良好的误码率性能。 全文共分五章，具体安排如下。 第一章是引言，简要介绍了数字通信系统的结构，结合纠错码的发展过程介 绍了l d p c 码的出现及其发展，以及u ) p c 码的研究现状及应用背景。 第二章首先介绍了l d p c 码的理论背景，包括代数基础、纠错码和分组码的 基本原理。然后介绍了l d p c 码的定义及t a 衄e r 图表示。在此基础上，介绍了几 种主要的l d p c 码的校验矩阵的构造方法，最后给出了l d p c 码的编译码方法。 第三章首先讨论了l d p c 码的最小距离和围长( g i n h ) ，分析了短环的存在对码 性能的影响，并主要研究了l d p c 码在t a l l i l e r 图中的环在校验矩阵中的形状。然 后在此基础上提出了一种计算复杂度相当低的环数检验算法。 第四章在上一章提出的环数检验算法的基础上，结合现有准循环码的设计思 想m 舯】，作为约束条件，设计了性能非常优越的准循环码。并提出两种不规则准 循环l d p c 码的设计方法用于构造生成矩阵。以实例说明所提出的设计，并且计 算机仿真结果验证本文设计的准循环u p c 码具有良好的误码率性能。 第五章对本文的工作进行总结以及对l d p c 码的展望。 7 北京交通大学硕士学位论文 2l d p c 码的编译码原理 本章首先介绍了l d p c 码的理论背景，包括代数基础、纠错码和分组码的基 本原理。然后介绍了l d p c 码的定义及协m e r 图表示。在此基础上，介绍了几种 主要的l d p c 码的校验矩阵的构造方法，最后给出了l d p c 码的编译码方法。 2 1理论背景 2 1 1 代数基础 近代数学是纠错码理论的数学基础l ”，它主要关心代数运算本身的性质和规 律，被作为运算对象元素，可以是整数、多项式、矩阵等等。但它们对乘法、 加法等运算具有共同的性质。首先介绍一下最基本的概念，如代数系统。 定义2 1 满足一定规律或定律得系统称作代数系统。且在该系统中有： ( 1 ) 由一群元素口，6 ，c ，构成一个集合： ( 2 ) 在元素集合中有一等价关系： ( 3 ) 在集合中定义了一个或数个运算，通过运算建立起元素之间的关系； ( 4 ) 有一组假定。 分组码是建立在码的代数结构基础上的。本节介绍数论中的某些最基本的知 识，以及群、域的基本概念。下面所要介绍的群、域等都是代数系统。 定义2 2 设g 是非空集合，并在g 内定义了一种代数运算，若满足下述公理： ( 1 ) 有封闭性。对任意口、6 g ，恒有口。6 g 。 ( 2 ) 结合律成立。对任意口、6 g ，有00 6 ) o c = 口。( 6 0 c ) 。 ( 3 ) g 中有一恒等元8 存在，对任意口e g ，有p e g ，使4o e = e 。口：口。 ( 4 ) 对任意口g ，存在有4 的逆元4 一g ，使口o d = 口一0 4 ：e 。 则称g 构成一个群。 上述定义中，g 的运算“o ”可以通常的乘法或加法。若为乘法，则恒等元素为 单位元；若为加法，则恒等元记为0 ：n 的逆元记为一n 。群中元素的个数，称为 群的阶。若群中元素个数有限，称为有限群；否则，称无限群。 例g 1 ：整数全体，按通常加法构成群，这是一个无限群。但通常的乘法不构 成群。 例g 2 ：偶数整体，对加法构成群( 无限群) ，对乘法不构成群。 例g 3 ：实数全体对加法构成群。除o 元素以外的实数全体对普通乘法也构成 9 l d p c 码的编译码原理 群，此时群的单位元e = l 。这两个群为无限群。 例g 4 ：所有力阶矩阵的加法构成群，单位元为。的矩阵。对矩阵乘法，若为 满秩矩阵，则构成群：否则不是。 例g 5 ：模脚的剩余全体：- ，_ ，；五，在模，l 加法运算下构成群。一般而言， 若群中的运算式加法，则简称加群；若为乘法则简称为乘群。如例g l 、g 2 、g 3 是加群，例g 博是乘群。 若群g 中，对任何口、6 g ，有口o b = 6 。口，则称g 为交换群、可换群或阿 贝尔群( a b c l 群) 。 上述一系列群中，除例( 4 中的矩阵在乘法运算下不是阿贝尔群外，其余例中 都是可换群。 除了上面所述的群以外，域在编码理论中起着关键作用。域是定义了两种代 数运算的系统。 定义2 - 3 非空元素集合f ，若在f 中定义了加和乘两种运算，且满足下述公 理： ( 1 ) f 关于加法构成阿贝尔群。其加法恒等元记为o 。 ( 2 ) f 中非零元素全体对乘法构成阿贝尔群。其乘法恒等元( 单位元) 记为 1 。 ( 3 ) 加法和乘法间有如下分配律： 4 ( b + c ) = 口6 + 4 c ( b 十c ) a = 6 口+ 则称f 是一个域。 由此可见域是一个可换的、有单位元的，非零元素有逆元的环，且域中一定 无零因子。若在f 中有零因子，则由口、6 f ，a 0 ，6 o ，得出曲= o ，因此 o = 4 。o = 口。( 4 = 0 。口) 6 = 6 ，这与原来假设6 o 有矛盾，因此曲o 。 例f l ：有理数全体、实数全体、复数全体对加法、乘法都分别构成域，分别 称有理数域、实数域和复数域。且这3 个域中的元素个数有无限多个，所以称它 们为无限域。称域中元素的个数为域的阶。元素个数有限的域称有限域，用g f ( 目) 或c 表示q 阶有限域。有限域也称为加逻华( g a l o i s ) 域，在编码理论中起着非常 重要的作用。 例f 2o 、l 两个元素按模2 加和模2 乘构成域。该域中只有两个元素，记为 g f ( 2 ) 或e 。 定理2 1 设p 为素数，则整数全体关于模p 的剩余类：试i ，互，i = i ，在模p 运 算下( 模p 相加和相乘) ，构成p 阶有限域e ( g f ( p ) ) 。 l o 北京交通大学硕士学位论文 2 1 2 纠错码基础原理 在介绍完纠错码的数学基础之后，这里将简单浏览一下纠错码的基础原理。 首先回顾香农( s h 煳o n ) 的信道编码定理。 定理2 2 每个信道具有确定的信道容量c ，对于任何小于c 的码率定，存在 有速率为r 码长为疗的分组码及( ，七0 ，讲) 卷积码，若用最大似然译码，则随着码 长的增加其译码错误率p 可任意小，即 和 p 以g 。瓦胄 p 4 e - “+ 1 “。乓 = 4 p k 巨伸 ( 2 1 ) ( 2 2 ) 式( 2 - 1 ) 和( 2 2 ) 中，4 和4 为大于0 的系数，瓦( r ) 和t ( r ) 为正实函数，称 为误差指数，它与尺、c 的关系如图2 1 所示。图1 l 中，c 。、c 2 为信道容量， 且c l c 2 。由信息论的基础知识可知，在高斯臼噪声信道时，信道容量 c = l 0 9 2 1 + e f 嗽】( 6 打5 ) 式( 2 3 ) 中，矿是信道所能提供的带宽， r 是分组码信号的持续时间即信号宽度， 位频带的噪声功率，只“降7 y o ) 是信噪比 ( 2 3 ) 只= e r 是信号功率，e 是信号能量， 只是单位频带的信号功率，0 是单 图2 1e ( 尺) 与r 的关系 l d p c 码的编译码原理 由式( 2 2 ) 和图2 1 可看出，信道容量c ，码长n 和错误概率p 之间的转换 关系。为了满足一定误码率p 的要求，可以用以下两类方法实现。 是增加信道容量c ，从而使e ( r ) 增加。由c 的表示式式( 2 3 ) 可知，增加c 的方法可以采用如加大系统带宽或增加信噪比的方法来达到。例如，采用调频、 调相等宽带调制方法：增加发射机的功率；应用高增益天线；采用分集接收及低 噪声器件等方法。这些措施是从根本上改善信道，增加信道容量、减少误码率的 方法，是通信设计工作者经常采用的传统方法。 另一种方法是在只一定下，增加分组码长( 也就是增加分组信号持续时间 r ) ，可使p 随月的增加而呈指数下降。但由于码长一的增加，当r 保持一定时， 可能发送的码字数2 指数增加，从而增加了译码设备的复杂性。这种方法就是信 道编码定理所指出减少误码率的另一方向，它为通信设计工作者提供了一条新的 途径。 纠错编码的意义就在于：保持定的信息传输效率条件下，通过编译码来降 低误码率以实现可靠通信，并且要求译码器尽可能简单。应用纠错码后，若仍要 求传输信息的速率不变，则必然使信道的带宽矽增加。设原来的信息传输速率为 6 0 0 6 打s ，如用月= l 2 码，则要求信道传输速率为1 2 0 0 6 f f j ，一般要求信道带宽 增加倍( 通常增加伽一j i ) 七倍) 。因此，纠错码主要应用于功率受限而带宽不太 受限的信道。 在极限情况n _ 时要求带宽寸m 。根据计算，此时只要求信噪比 氏0 一1 6 扭，就可实现高斯白噪声信道下的无误传输。这就是带宽无限高斯 白噪声信道的极限传输能力，称为s h a n n o n 限。图2 2 给出了未编码的p s k 与应 用各类纠错码后，误码率与信噪比之问的关系曲线。由此图可看出：应用r = 1 ，2 的( 2 4 ，1 2 ) 分组码后，在误码率为1 0 0 时比未编码的大约可节省3 d b 的功率( 称 为编码增益) ；而用r = l 2 ，约束度为8 的卷积码软判决维特比( t e r b i ) 译码， 在误码率为l o 。5 时，大约可节省5 d b 的功率。一般情况下，应用纠错码后，大约 能得到从零点几至o 几个d b 程度不等的编码增益。 1 2 北京交通大学硕士学位论文 謇表 | _ i _ 给弋 图2 - 2 各种码的性能比较 2 1 3 线性分组码基础原理 舀：它嚣b 2 ；：它蠹r 可( d b ) 线性分组码是分组码中最重要的一类码，它是讨论各类码的基础。虽然这类 码的概念比较简单，但却非常重要，特别是有关码的生成矩阵g 和校验矩阵的 表示法，以及它们之问的关系，而日与纠错能力之问的关系则更为重要。 利用纠错码进行差错控制的数字通信系统如图2 3 所示，由此可如下定义分组 码。 定义2 4 分组码是对每段七位长的信息组，以一定规则增加r = 行一丘个校验元， 组成长为h 的序列：( + o - 2 c 。，c