（通信与信息系统专业论文）基于置换多项式的ldpc码研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 随着移动通信技术的快速发展，特别是3 g ，4 g 技术的快速发展，作为物理层关 键技术的信道编码技术逐渐成为研究的热点。1 9 9 6 年l d p c ( l o w d e n s i t yp a r i t y - c h e c k ， 低密度校验) 码被重新发现，由于其接近香农限的纠错性能，较低的译码复杂度，使其 逐渐成为信道编码领域研究的热点，并不断被各种标准所采纳。本文对基于置换多项 式的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 码的各种构造方法，如g a l l a g e r 构造法，m a c k a y 构造法等；l d p c 码各种编码 算法，如高斯消去算法，基于下三角的编码算法：以及l d p c 码的软判决b p ( b e l i e f p r o p a g a t i o n ，置信传播) 译码算法和对数域b p ( l l rb p ) 译码算法。 然后，详细介绍了i e e e8 0 2 1 6 e 标准中提供的l d p c 码的结构和递归编码方法， 并基于该编码方法和b p 译码算法，用c 语言对多种码长和码率的l d p c 码进行仿真， 相关的仿真结果表明i e e e8 0 2 1 6 el d p c 码具有优异的纠错性能。 再后，研究了l d p c 校验矩阵的短环检测算法。文章先介绍了基于校验矩阵的检 测算法和j u nf a n 等人提出的基于排列组合的检测算法；然后结合j u nf a n 等人提出的 基于排列组合算法的一些分析，提出了一种改进的短环检测算法，并对两种算法进行 了仿真。仿真结果表明，改进后的算法能够检测出比排列组合算法更多的6 ，8 ，1 0 环 数。 最后，本文对基于置换多项式对l d p c 码构造进行了研究。首先介绍了置换多项 式的基本概念和判定条件。o s c a r y t a k e s h i t a 首次使用二阶置换多项式构造l d p c 码， 本文将构造l d p c 码的方法推广到m 阶，然后通过仿真用改进的短环检测算法剔除存 在小环的l d p c 码，选择出纠错性能优越的l d p c 码。本文对二阶，三阶和四阶置换 多项式构造出的无小环l d p c 码进行仿真分析，结果表明由置换多项式构造的l d p c 码具有略优于m a c k a yl d p c 码以及略差于i e e e8 0 2 1 6 el d p c 码的纠错性能。 关键词：l d p c 码，高斯消去法，递归编码，环检测算法，置换多项式 西南交通大学硕士研究生学位论文第1 i 页 量鼍曼皇曼量曼曼皇暑曼曼舅舅鼍罾鼍舅i i i i i 曼 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fm o b i l ec o m m u n i c a t i o nt e c h n o l o g y , e s p e c i a l l y3 g , 4 g t e c h n o l o g y sr a p i dd e v e l o p m e n t ，c h a n n e lc o d i n gw h i c hi sak e yt e c h n o l o g yo fp h y s i c a ll a y e r h a sb e c o m eah o tr e s e a r c ht o p i c s i n c e19 9 6l o w - d e n s i t yp a r i t y - c h e c k ( l d p c ) c o d e sh a v e b e e nr e d i s c o v e r e d b e c a u s eo fi tc l o s et ot h es h a n n o nl i m i te r r o rc o r r e c t i o np e r f o r m a n c ea n d l o w e rd e c o d i n gc o m p l e x i t y , a l lt h e s em a k el d p cc o d e sb e c o m eah o tr e s e a r c hi nc h a n n e l c o d i n gf i e l d ，a n da d o p t e db yv a r i o u ss t a n d a r d s i nt h i st h e s i s ，w er e s e a r c hl d p cc o d e s w h i c ha r eb a s e do np e r m u t a t i o np o l y n o m i a l s ，t h e ns e l e c tt h el d p cc o d e sw i t h o u ts m a l l c y c l e sb ym e a n so fs h o r tc y c l ed e t e c t i o na l g o r i t h m ，a n dg e tl d p cc o d e sw i t hs u p e r i o r e r r o r - c o r r e c t i o np e r f o r m a n c e f i r s t l y , t h et h e s i si n t r o d u c e st h eb a s i cp r i n c i p l e so fl d p cc o d e s ，w h i c hi n c l u d i n gt h e d e f i n i t i o no fl d p cc o d e sa n dt a n n e rg r a p h ；v a r i o u sc o n s t r u c t i o nm e t h o d so fl d p cc o d e s ， s u c ha sg a l l a g e rc o n s t r u c t i o nm e t h o d ，m a c k a yc o n s t r u c t i o nm e t h o de t c ；v a r i o u sc o d i n g a l g o r i t h m so fl d p cc o d e s ，s u c ha sg a u s s i a ne l i m i n a t i o n ，c o d i n ga l g o r i t h mb a s e do nl o w e r t r i a n g u l a r ；a n da l s ol d p cc o d e s s o f td e c i s i o nb pd e c o d i n ga l g o r i t h ma n dl l rb p d e c o d i n ga l g o r i t h m s e c o n d l y , t h et h e s i se l a b o r a t e st h es t r u c t u r ea n dr e c u r s i v ec o d i n gm e t h o do fl d p c c o d e sp r o v i d e db yi e e e8 0 2 16 e u s i n gt h es t a n d a r dp r o v i d e d e n c o d i n gm e t h o d ，b p d e c o d i n ga l g o r i t h ma n dcl a n g u a g ef o rs i m u l a t i o n f r o mt h es i m u l a t i o nr e s u l t so fv a r i o u s c o d el e n g t ha n dr a t e ，w ec a ns e et h ee x c e l l e n tp e r f o r m a n c eo fi e e e8 0 2 16 el d p c t h i r d l y , t h et h e s i sr e s e a r c h e st h es h o r tc y c l ed e t e c t i o na l g o r i t h mo ft h el d p cc o d e s f i r s t ，w ei n t r o d u c e st h ed e t e c t i o na l g o r i t h mb a s e do nc h e c km a t r i xa n dt h ed e t e c t i o n a l g o r i t h mb a s e do np e r m u t a t i o n sw h i c hp r o p o s e db yj u n f a ne t c t h e n ，c o m b i n i n gs o m e a n a l y s t so ft h ed e t e c t i o na l g o r i t h mw h i c hp r o p o s e db yj u nf a ne t c ，a ni m p r o v e da l g o r i t h m f o rs h o r tc y c l ed e t e c t i o nh a sb e e np r o p o s e d t h et h e s i ss i m u l a t e st w oa l g o r i t h m s ，a n dt h e r e l a t e dr e s u l t ss h o wt h a tt h ei m p r o v e da l g o r i t h mc a nd e t e c tm o r en u m b e ro f6 ，8 ，10 c y c l e s f i n a l l y , t h et h e s i sr e s e a r c h e st h el d p cc o d e sc o n s t r u c t e db yp e r m u t a t i o np o l y n o m i a l s f i r s t ，w ei n t r o d u c e dt h eb a s i cc o n c e p t so fp e r m u t a t i o np o l y n o m i a l sa n dd e t e r m i n ec o n d i t i o n s o fp e r m u t a t i o np o l y n o m i a l s o s c a ryt a k e s h i t af i r s tc o n s t r u c t e dl d p cc o d e su s i n g2 - o r d e r p o l y n o m i a lp e r m u t a t i o n t h et h e s i sc o n s t r u c tl d p cc o d e se x t e n d e dt om - o r d e rp e r m u t a t i o n p o l y n o m i a l s t h e n ，w eu s i n gt h ei m p r o v e dc y c l ed e t e c t i o na l g o r i t h mr e m o v el d p cc o d e s 西南交通大学硕士研究生学位论文第1 i i 页 曼曼鼍曼曼量邑曼曼曼曼曼曼皇量曼曼曼量曼曼曼皇笪曼邑曼曼曼曼曼曼曼曼量曼量曼曼舅量曼量鼍曼舅曼量曼曼i 一；i ii | 曼曼曼曼曼曼皇曼 w h i c he x i s ts m a l lc y c l e s ，c h o o s es u p e r i o re r r o r - c o r r e c t i o np e r f o r m a n c el d p cc o d e s f r o m t h es i m u l a t i o na n a l y s i so fl d p cc o d e sc o n s t r u c t e db y2 - o r d e r , 3 - o r d e ra n d4 - o r d e r p e r m u t a t i o np o l y n o m i a l sw es e l e c t e d ，w e c a ns e et h a tl d p cc o d e sc o n s t r u c t e db y p e r m u t a t i o np o l y n o m i a l sh a v es l i g h t l yb e t t e rp e r f o r m a n c ec o m p a r ew i t hm a c k a yl d p c c o d e sa n d s l i g h t l yw o r s ep e r f o r m a n c et h a ni e e e8 0 2 1 6 el d p c c o d e s k e yw o r d s ：l d p cc o d e s ，g a u s s i a ne l i m i n a t i o na l g o r i t h m ，r e c u r s i v ec o d i n g ，c y c l e d e t e c t i o na l g o r i t h m ，p e r m u t a t i o np o l y n o m i a l s 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 低密度校验码( l o w - d e n s i t yp a r i t y - c h e c kl d p c ) 是一种高性能的信道编码，其具 有接近香农限的编译码性能。在本章中首先介绍了数字通信系统和信道模型，然后阐 述了信道编码的发展历史和现状，最后给出了本文做的主要工作和内容安排。 1 1 数字通信系统 通信的目的是传输信息，通信传输的信息可以是多种多样的，例如：符号、话音、 文字、音乐、数据、图像、图片等。通信系统中将信息由信息源传递给受信者的过程 中，要求通信传输同时具备可靠和快速的特点。但是通信系统中可靠和快速是相互矛 盾的，在评价整个通信系统性能指标时我们用有效性指代信息传输的“速度”问题， 用可靠性指代信息传输“可靠”的问题。从研究信息的传输角度来说有效性和可靠性 是一对主要矛盾，当然期间也要考虑适应性、标准性、经济性及使用维护等 1 1 。 通信系统根据信道中传输的是模拟信号还是数字信号可以分为模拟通信系统和数 字通信系统。与模拟通信相比数字通信更能适应通信技术越来越高的要求，数字通信 具有抗干扰能力强、传输差错可控制、易于做到高保密的加密处理等诸多优点，因此 目前出现了数字通信代替模拟通信的趋势【l 】。 图1 1 数字通信系统框图 点对点的数字通信系统模型，一般可用图1 1 表示，其中没有给出同步环节，因 为同步的位置往往是不固定的。图中信息源产生待传输的信息，受信者是信息最终要 传达的目的地；信源编码是为了减少信源输出符号序列中的剩余度、提高符号的平均 信息量，对信源输出的符号序列所施行的编码，信源译码是其反过程将信号还原传输 给受信者；信道编码，信道译码是为提高信息传输的可靠性而进行的编译码 2 1 。随着人 们对高速率通信和高可靠性通信的要求不断提高，信道编码以及译码逐渐成为当代学 者研究的热点。 西南交通大学硕士研究生学位论文第2 页 1 2 信道编码及其发展情况 在有噪声干扰的信道中传输信息，人们总是希望传输快捷可靠，但是由于信道容 量有限和不可避免的噪声干扰，所以我们要通过各种编码尽可能的提高信息传输率， 并将传输误差控制在刻意接受的范围内【3 1 。信道的形式多种多样，如：大气层、电缆线、 微波等，而信道编码的主要目的是提高传输的可靠性。 1 2 1 香农定理 1 9 4 8 年，香农( c e s h a n n o n ) 发表经典论文：“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 o n ”用数理统计和测度的方法系统地讨论了通信的基本问题【4 】。香农在文 章中指出：不论任何信道都存在一个传输速率的上限，我们称这个上限速率为信道容 量，用符号c 表示，在不超过信道容量的上限传输速率下传输，随机产生的足够长的 传输码字可以获得任意小的传输错误率。即对于信息传输速率r ，只要r c 就可以找 到一种信息编码方式实现无错误的传输，对于r c 则不可能实现无误传输【5 】，这个信 道的传输速率的上限我们称之为香农限。 另外根据香农定理，信道的信道容量为式( 1 1 ) ： c c = b l 0 9 2 ( 1 + - 善r ) ( 1 1 ) v 式中，曰代表假设信道的带宽，s 代表输出的信号功率，单位为职 r 为输出加性 高斯白噪声的功率，单位也是形。这个公式表明在给定频带宽度曰的信道上，当信号 和作用在信道上的起伏噪声的平均功率给定时，单位时间上可以传输的信息量的极限 值也就确定了【1 1 。 香农限和香农定理是编码理论的基础。在现代数字通信系统中，尤其是无线通信 领域，异常复杂的信道特性，用户不断提高的对于数字通信业务传输速度和质量要求， 以及不断多样化的通信业务和对服务质量的更高的要求，加之新技术的不断涌现，以 及一些高速率，高移动性，高突发性的业务的出现，对信道传输的速率和可靠性提出 了更高更新的要求，纠错编码技术正变得越来越重要，日益成为通信新技术领域研究 的热点。 1 2 2 信道编码的历史及发展现状 信道编码又称为纠错编码，按照编码规则的不同，又可以分为分组码和卷积码。 1 9 4 8 年香农在a m a t h e m a t i c a lt h e o r y o f c o m m u n i c a t i o n ”一文中，仅仅只是证明了逼近 容量限的码的存在性，并没有给出具体的编码方法和构造方法。受香农定理的启示几 十年来，编码界一直在寻找各种各样的编译码方法，并取得了丰硕的成果。其中包括 格雷码、汉明码、循环码和b c h 码，r s 码和卷积码，以及c b e r r o u 等人提出了t u r b o 西南交通大学硕士研究生学位论文第3 页 曼曼鼍曼曼曼曼量皇兰皇曼鼍曼曼曼曼量曼皇量曼_ i nm 一量曼曼量曼曼曼曼曼曼量詈曼昌曼! 曼曼曼曼! 曼曼 码的编译码方案，g a l l a g e r 提出的l d p c 码编译码方案等。 线性分组码是以代数中的群、域、环以及其它有关的几何理论为基础设计的一类 纠错编码，也是发展最早的一类纠错编码【6 1 。其中包括汉明码、b c h 码、o o p p a 码、 g o l a y 等，其中b c h 码由于其结构简单，编译码设备也不复杂，因此在通信系统中应 用广泛。 卷积码是另一类重要的纠错码，卷积码在编码过程中采用寄存器，增加了码元之 间的相关性，从而或得了更高的编码增益，随着2 0 世纪六十年代维特比, ( v i t e r b i ) 译码 算法和其他译码算法【7 】的涌现，使得卷积码在工程领域得到广泛应用，日后随着 t c m ( 网络编码调制) 技术的出现【8 】以及新的理论不断提出，卷积码得到了更大的发展和 应用。 1 9 9 3 年，法国学者c b e r r o u 等人在瑞士日内瓦召开的国际通信会议上第一次提出 了t u r b o 码的编译码方案【1 4 1 ，c b c r r o u 等人很好的运用在s h a n n o n 信道编码定理中给 出的随机性编码和译码条件，获得了与s h a n n o n 理论极限十分相近的译码纠错性能。 t u r b o 码采用一种在低信噪比条件下性能优异的级联编码方案，译码采用m a p 算法、 l o g m a p 算法、m a x l o g m a p 算法、s o v a 算法等。仿真结果表明，在一定的参数条 件下，t u r b o 码可以达到比s h a n n o n 限仅差0 7 d b 的优异性能。t u r b o 码的出现标志着 构造接近s h a n n o n 限好码的开始，打开了一个崭新的研究领域。 1 9 6 2 年，g a l l a g e r 在他的博士论文【9 】里面提出了二元正贝u l d p c ，但限于当时的计算 能力，l d p c 码被认为不是实用码，在很长一段时间没有受到编码界的重视。直到1 9 9 6 年，m a c k a y 和n e a l 等人的通过大量的研究表明，如果采用l d p c 码的长码，可以达到 与t u r b o 码相似或更好的性能【l o 】【1 1 】。m a c k a y 和n e a l 的这个研究成果立即吸引了几乎所 有信息论界学者的目光，这些学者们重新认识到l d p c 码所具有的优越性能和巨大实用 价值，从而使l d p c 码的研究跨入了一个新的阶段。经过近十几年的发展l d p c 码日渐 成熟并且被各个主流的通信标准所采用，如d v b s 2 【1 2 1 ，i e e e8 0 2 1 6 e 1 3 】等。 1 2 3l d p c 码的国内外研究现状 l d p c 码以其优越的编译码性能，良好的应用前期吸引了各国学术界和科技界的眼 光。因此在过去的十多年中对l d p c 码的研究取得了丰硕的成果，为l d p c 码在光通 信、深空通信、磁光全息存储、图像压缩传输、第四代移动通信系统等的广泛应用铺 平了道路。 l d p c 编码具有很大的复杂度，r i c h a r d s o n 和u r b a n k 1 4 , 1 5 】在编码算法方面，做出 了异常巨大的贡献。2 0 0 1 年由他们提出的一种新的编码算法，在很大程度上解决了随 机构造的l d p c 码在编码时所需的巨大存储量和运算量的问题。在前人研究的基础上 y k o u 和s l i n 等人根据有限几何理论方面的知识，同时将有限域空间和几何空间对应 西南交通大学硕士研究生学位论文第4 页 起来【l6 1 ，大大简化了l d p c 码的编码复杂度，构造出了性能优异的l d p c 码。 在l d p c 码译码研究方面，l d p c 目前的译码算法主要有两类。第一类是置信传 播( b e l i e f p r o p a g a t i o n ) 译码迭代算法【1 7 】，该算法属于软判决译码算法，在l d p c 码长较 大时容易逼近香农限，实现复杂度高，为了简化译码算法，我们衍生出b p b a s e d 、o f f s e t b p b a s e d 、l o g - b p 等译码算法。第二类是比特翻转( b i tf l i p p i n g ) 译码算法，该算法属 于硬判决算法，实现复杂度低，性能较差，目前提出了加权b f 算法及其改进的形式， 使译码性能有所提高。 l d p c 码的构造方法有很多，对于长码、中长码有不同的构造方法，主要可分成随 机构造和结构化构造两类别。g a l l a g e r 在其文章【1 8 】提出了种随机生成，l d p c 码校验 矩阵的行重和列重都均匀分布，且列重大于等于3 的l d p c 码构造方法。m a c k a y 发现 了通过稀疏矩阵日编码的优势，提出了4 种可以避免所构造的校验矩阵中存在四环的 构造方法，并在其网站上【1 9 j 公布了大量由他自己设计的l d p c 码。近年来，x i a o y u h u 等提出了一种p e g ( p r o g r e s s i v ee d g e g r o w t h ) 的l d p c 码构造方法【2 0 。2 2 】，该方法按照边 对边的方式在变量节点和校验节点之间建立边的连接，增加新边可以使l d p c 码双向 图的砌达到最大。s l i n 和b a m m g 等人提出了一种利用平衡不完全区组设计 ( 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 n ，b i b d ) 方法构造纠错性能优越的l d p c 码的方、法【2 3 1 。 由于这类码的循环或准循环结构，使得对这类码距的性能分析变的更加容易。 1 9 9 8 年，m a c k a y 和d a v e y 提出了基于g f ( q ) 域的l d p c 码【2 4 ，使得l d p c 码的 研究进入了一个全新的领域。多进制l d p c 码的性能在相同码率下要优于t u r b o 码和 二进制的l d p c 码，但是其要求更高的编码复杂度。于此同时，c h u n g 等人设计了1 2 码率的不规则l d p c 码，其错误门限值离香农限仅仅0 0 0 4 5 d b 2 5 1 ，成为迄今为止最接 近香农限的编码。 1 3 本文主要研究工作及内容安排 本文采用理论分析和计算机软件仿真相结合的方法，对l d p c 码的构造方法进行了 深入的研究，希望构造出性能优越的l d p c 码。通过研究了j u nf a n 等人提出的基于排列 组合的短环检验算法，在此基础上进一步改进短环检验算法，加入数学比较和统计的 方法使得这种环检测算法性能得到了巨大的提高，能够检测出比j 1 l nf a n 等人提出的基 于排列组合的短环检验算法更多的6 ，8 1 0 环。 2 0 0 6 年o s c a r y t a k e s h i t a 首次使用二阶置换多项式构造出性能优异的l d p c 码，由于 其对校验矩阵的存储上，只需要存储置换多项式的几个系数，相比于传统l d p c 码需要 对校验矩阵的存储具有很大的优势，因此本文结合置换多项式的概念和判定条件，获 得基于m 阶置换多项式的高性能l d p c 码构造方法，使得构造出的l d p c 码有大g r t h 的 西南交通大学硕士研究生学位论文第5 页 量量量曼曼曼曼曼皇曼曼曼曼鼍曼曼皇曼曼皇曼量曼曼曼曼曼曼蔓曼皇鼍皇曼曼曼曼鼍鼍量鼍寡詈i； 一一i 曼曼曼鲁量曼鼍曼曼 特点和优越的编译码性能。 全文共分为五章，具体安排如下： 第一章是绪论部分，主要介绍信道编码的发展情况和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 码性能的重要因素环；最后简要的介绍了 l d p c 码的编码和译码算法，其中编码算法主要阐述了高斯消去法和基于近似下三角的 编码算法，译码算法主要阐述了b p 译码算法和l l rb p 译码算法。 第三章详细介绍了i e e e8 0 2 1 6 e 标准提供的l d p c 码，包括其校验矩阵结构和标准 提供的递归编码算法。同时使用软件对标准中给出的多种码长和码率i e e e8 0 2 1 6 e l d p c 码进行了仿真。 第四章在基于j u nf a n 等人提出的排列组合的短环检验算法的基础上，提出一种新 的改进的环检测算法，通过对两种算法的软件仿真和对比，我们可以看出改进的短环 检测算法能检测到比排列组合的短环检验算法更多的6 ，8 ，1 0 环。 第五章中结合数学中置换多项式的概念，将其引入至u l d p c 码的构造上来，o s c a r y t a k e s h i t a 首次使用二阶置换多项式构造性能优异的l d p c 码，本文根据此构造方法的 启示，获得一种基于m 阶置换多项式的高性能l d p c 码构造方法，并通过短环检测算法 对构造出的l d p c 码进行筛选，留下s h ：g i r t h 的l d p c 码，结合对编译码性能的分析获得 具有优越纠错性能的l d p c 码。 西南交通大学硕士研究生学位论文一第6 页 第2 章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 码的定义及其t a n n e r 图表示方法 g a l l a g e r1 9 6 2 年在他的博士论文中提出了一种基于稀疏校验矩阵的线性分组码， 我们称为低密度奇偶校验码。g a l l a g e r 在他的论文中阐述了l d p c 码的基本构造方法、 简要的编码方法、分析最小汉明距离的方法以及译码算法的纠错性能分析方法等，但 是由于当时计算条件的限制，缺乏相应的分析工具，l d p c 码并不被人们所重视，l d p c 码在很长一段时间内被人遗忘了。 直到1 9 9 3 年c b e r r o u 等人提出了t u r b o 码的编译码方案，特别是1 9 9 6 年m a c k a y 等人发现l d p c 的长码具有与t u r b o 码相差无几的性能，并在实现上更有优势。从此 l d p c 码引起了学术届的关注，成为编码领域研究的热点。 2 1 1l d p c 码的定义 l d p c 码是线性分组码，对于线性分组码一个码长为n ，信息位为k 的码，可以 由一个生成矩阵q 。来定义，同样也可以由一个q 心细的一致校验矩阵来定义。假设 信息序列x m ，通过生成矩阵可以映射得到码字x 。= x m , o k 。同时所有码字也满足 只枞姗( 写。) 7 = 0 。 l d p c 码校验矩阵具有稀疏特性因此也叫低密度奇偶校验码，二元l d p c 码的校 验矩阵有大量的“o ”和少量的“1 ”组成。g a l l a g e r 最早给出的正则l d p c 码的校验矩 阵日满足下列3 个条件【1 8 】： ( 1 沮的每行中含有p 个“1 ，其他均为“0 ”； ( 2 ) h 的每列中含有力个“l ，其他均为“0 ”，并且2 3 ； ( 3 ) 与日的行数和列数相比，p 和五都很小。 g f ( 2 ) 上的l d p c 码是一种线性分组码( 月，露) ，其码长为n ，信息序列长度为k ，这 个l d p c 码校验矩阵日是个维数为( n k ) n 的矩阵。这个校验矩阵每一列对应码 字的一位，每一行对应一个校验方程。校验矩阵中每一行中非零元素的个数称为行重， 记为w r ：每一列中非零元素的个数称为列重，记为w c 。式( 2 1 ) 是一个5 2 0 的校验矩 西南交通大学硕士研究生学位论文第7 页 阵及其他所对应的校验方程。其中码字y = ( x ，k ，) 符合日y r = 0 r 1 1 1 looooooooooooooo o - lf 肖喘喘喘= o l oooo1 l1 1oooooooooooo li 城喘饯= o 叫o oooooool1 11oooooooo h 城城城：o 舢、 ooooo00000001 11 l oo o o li 气城域城= 0 p ooooooooooooooo1 11 l j 城嗡蜗= 0 2 1 2 l d p c 码的t a n n e r 图表示 1 9 8 2 年t a n n e r 首次使用双向图来表示l d p c 码 2 6 】，因此我们把这种表示l d p c 码 校验矩阵的双向图叫做t a n n e r 图，每一个l d p c 码的校验矩阵可以相应的对应一个 t a n n e r 图。l d p c 码的校验矩阵以。代表了n 个校验方程和n 个变量方程，据此校验 节点集合可由m 个校验方程，变量节点集合可由刀个变量方程确定，如果校验矩阵日 的第f 行和第j 列为“1 ，则第f 个校验节点和第，个变量节点之间有一条边相连。 在t a n n e r 图中处于下边的有意个节点，我们称之为变量节点，可以表示为： y ，= l ，2 ，刀 ；上边肌个节点，我们称之为校验节点，每一个代表一个校验方程， 可以表示为： s ，i = 1 ，2 ，m 。在校验矩阵中h ( i ，) = 1 的位置，表示第f 个校验节点 和第，个变量节点之间有一条边相连，相邻节点就是指这条边连接的两个端节点，该节 点的度( d e g r e e ) 就是指该个节点连接边的条数。对于校验行重为p ，列重为五，变量节 点为n 的l d p c 码，我们可以表示为：( 玎，五，p ) 。 在图2 1 中给出y ( 1 0 ，2 ，4 ) l d p c 码的校验矩阵，图2 2 给出t ( 1 0 ，2 ，4 ) l d p c 码对应 的t a n n e r 双向图，从图中我们可以看出改校验矩阵的变量节点度数为2 ，而其中校验 节点度数为4 。 xe匕k匕虼e墨kx 。 五 11 11oooooo 逻 1000 111ooo s0 1001oo 11o 5 1 i001oo 1o1o1 鼍000 1oo 1o11 图2 - 1 ( 1 0 ，2 ，4 ) l d p c 码的校验矩阵 西南交通大学硕士研究生学位论文第8 页 图2 - 2 ( 1 0 ，2 4 ) l d p c 码的t a n n e r 双图模型 2 2l d p c 码的构造方法 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 燃、d a v e y 构造法、砌分布构造法【2 7 1 、p e g 构造法、准循环的l d p c 码构造等，下面主要介绍几种常用的l d p c 码构造方法。 2 2 1 g a l l a g e r 构造法构造的l d p c 码 g a l l a g e r 构造的l d p c 码具有如下特点：校验矩阵口中的元素随机生成，日有固定的 行重和列重，且列重w c 大于等于3 ；矩阵按行分成w c 个水平子矩阵，每个子矩阵的列 重为1 ，第一个子矩阵第f 行( i - 1 ) 陟h 1 列到f 腑列的元素为1 ，其中肝为行重。其余子矩 阵均是第一个子矩阵的随机列变换。 图( 2 3 ) 给出了i 扫g a l l a g e r 构造的码长为2 0 ，列重w e = 3 ，行重为w r - - 4 的l d p c 码的校 验矩阵。 西南交通大学硕士研究生学位论文第9 页 曼曼曼曼曼曼皇曼曼量曼皇皇曼曼曼曼置量量量是曼曼曼曼曼鼍鼍罡曼曼曼黑曼曼曼曼皇曼曼量曼曼曼曼曼曼曼曼曼曼曼皇曼量皇皇曼量量皇量舅g lm m 曼 q q q q 一旦鱼0 00 000 0 00 0111 1 l0 0 0l0 0 01o o o1o 0 0 0 0 0 0 0l000l0 0 01o o o o o o1o o o 0 0l0 001o o ooo o1o o o10 0 0 0 0100 0 0 0 01o o o1o 0 010 0 0 00 00 010 0 01o o o 1o 0 01 1ooo o olo o o 0 o1o o o o o1o oo +o o1 oo10 o o oo0o o o o oo olooo o oo o1 图2 - 3 ( 2 0 。3 ，4 ) l d p c 码的校验矩阵 2 2 2 m a c k a y 的构造方法 m a c k a y 提出了四种关系密切的矩阵构造方法，得到的校验矩阵不存在长度为4 的 短循环。4 种构造方法依次如下： 构造1 a ：这是一种随机构造校验矩阵的方法，m n 的校验矩阵由随机构造得到， 在列重为腑固定的情况下，尽量使行重腑在每行中均匀分布，而且两列最多只有一个 共同的l ，即不存在长度为4 的环。如图( 2 4 ) 所示 图2 - 4 ： m a c k a y 构造法1 a 示意图 构造2 4 ：矩阵i - i 中，同样假设其中矩阵围数m ，我们使m 2 列的列重为2 ， 这些列重为2 的列是由两个m 2 m 2 的单位矩阵上下叠放组成。如图( 2 5 ) 所示。 o o o 0 o o o o o o o o o o o o o o o 1 0 0 o l o o o 1 o o o 1 o o 1 o o o 1 0 0 0 1 o o o l o 0 1 o o o l o o o 1 o o o 1 o o 1 o o o l o 0 o 1 o o 0 1 o o 0 o o o o 1 o o o l o o o 1 o o 1 o o o o 0 1 o 0 o o o o o 1 o o o 1 o o o 1 o o o 1 o o o 1 o o o o 西南交通大学硕士研究生学位论文第1 0 页 。 图2 - 5 ： m a c k a y 构造法2 a 示意图 构造1 b ，2 b ：适当删除1 彳和明所构造出的l d p c 码校验矩阵中的某些列，使 得校验矩阵的t a n n e r 图中没有周长为政例如庐6 ) 的短环，如图( 2 6 ) 所示。 。专 。 过 图2 - 6 ： m a c k a y 构造法1 b ，2 b 示意图 2 2 3 准循环l d p c 码的构造法 准循环的l d p c 码校验矩阵日由一系列的z x z 小方阵组成，这些小方阵是标准置 换矩阵、全零矩阵或是基于有限几何的矩阵。 h = 昂o )昂1 )昂国 昂坞- 2 )昂怕- 1 ) 昂o j昂 1 )昂2 ) 昂坞- 2 )昂拂- 1 ) 昂o ) 尼，1 )尼2 ) 昂坞- 2 )昆，- 1 ) 州1 1 ) 岫- l 如- 2 ) 讥- 1 ) ( 2 2 ) 上式中日是由一个m b x n b 的基础矩阵，校验矩阵中的只= 口表示平移口位后的大 小为z x z 的单位阵，选用不同的口的构成规则，可得到不同的编码方法。由于准循环码 具有准循环的环特性，因此可以得到系统形式的同时具有准循环特性的生成矩阵，这 样我们只需要采用移位寄存器便可以实现输入码字和生成矩阵的相乘。 对于l d p c 码的构造还有许多其他的方法，它们也能够构造出性能十分优越的 l d p c 码，比如p e g 构造法、d a v e y 构造法、g i r t h 分布构造法等，这里就不一一介 绍。 2 3l d p c 码中的环 西南交通大学硕士研究生学位论文第1 1 页 在l p d c 码中所谓的环是指t a n n e r 图中的一条路径，由一些边和节点构成，在 t a n n e r 图中任选一个节点作为起点，这条路径经过每个节点、每条边都只有一次，最 后到返回所选的起始节点。而环长是指环上所经过的边的条数，也可以是所经过的节 点的个数。t a n n e r 图上的环的长度只能是偶数，如：4 、6 、8 、1 0 等。如图( 2 7 ) 和( 2 8 ) 中红线画出的位置描述了校验矩阵和t a n n e r 图中的四环【2 8 1 。 环对l d p c 码的编译码性能有巨大的影响，l d p c 校验矩阵中的四环实际上就是 有两个信息节点都同时参与两个校验方程之中，由于l d p c 码采用的是迭代译码算法， 不论b p 还是其衍生译码算法，其推导的基点都是基于所有节点之间传递的信息统计独 立的，当l d p c 码的校验矩阵所对应的t a n n e r 图总共存在四环，六环等短环时，某一 个节点的概率信息在译码过程中经过一个环长的传递就会被传回本身，造成自身信息 的叠加，破坏了译码过程中信息统计独立的假设，从而影响到译码的准确性。因此我 们在构造校验矩阵时应尽量避免环的存在。同时八环，十环等短环也存在同样的情况。 h = o o 1l 1o ol o o o o 1o o1 o1 1o 图2 - 7 ：l d p c 校验矩阵中的四环 o o o o 1o o 1 11 图2 - 8t a n n e r 图中的四环 在l d p c 码中，我们把最小环的长度，称为该l d p c 码的g i r t h ，例如某个l d p c 码四环数目为0 即不存在4 环，六环数目不为0 ，则这个l d p c 码的g i r t h 为6 。 2 4l d p c 码的编译码原理 西南交通大学硕士研究生学位论文第1 2 页 目前的研究证明l d p c 码是目前发现的纠错能力最强的信道编码，而且l d p c 码译码器结构非常简单，具有十分广泛的应用前景。l d p c 码的编码复杂度较高，需 要大量的硬件资源和很长的延时，因此也制约了l d p c 码的应用，但是最近 黜c h a r d s o n 和u r b a n k e 在文献【2 刿中提出了一种创新的算法在很大程度上解决了这个 问题。接下来本文将介绍l d p c 码中的编译码方法。