（通信与信息系统专业论文）短ldpc码bp算法的改进.pdf

摘要1 9 6 2 年，g a l l a g e r 提出了l d p c 码【卜2 】，并证明它是一种性能非常好的线性分组码，只是由于当时人们的认识水平和计算机技术的限制，并没有引起人们的重视。直到1 9 9 3年，法国工程师b e r r o u 等人发明了t u r b oc o d e s 3 】后，人们又开始注意和研究它。1 9 9 6 年，m a c k a y 和n e m 发现l d p c 长码能够达到t u r b oc o d e s 的性能【4 。5 】，引起了人们的重视。文献【6 - 7 1 研究表明，l d p c 码的性能非常接近s h a n n o n 限，在a w g n 信道中采用b p 迭代译码算法时，非规则l d p c 码的性能与s h a n n o n 极限仅有0 0 0 4 5 d b 的距离【6 】。l d p c 码之所以有良好的性能，主要原因之一是在译码时采用了b p 算法【l 锄。近年来，随着l d p c 码技术的日趋成熟，l d p c 码的应用越来越广泛，不仅应用到通信系统，而且应用到数字信号处理，人工智能等领埘8 。9 1 。但是在实际应用时，码长较短l d p c 码【1 0 】的性能成为关注的问题之一。本文主要研究的是短l d p c 码的b p 译码算法及其改进算法。首先，介绍了纠错码的发展状况，l d p c 码的提出及其发展，有关l d p c 码译码的国内外研究状况。其次，介绍了一些必须的基础理论和编译码结构原理，并在此基础上对l d p c 码的编、译码的提出及发展进行了研究，对其性能也进行了简要的分析。接着对短l d p c 码的b p 译码算法进行了研究，并且对短l d p c 码和r s 码两种线性分组码进行了基于b p 算法的性能比较；然后对改进的b p 译码算法进行了深入的研究，提出了一种基于b p 短l d p c 码的改进级联算法，译码复杂度降低，译码性能得到很大提升。虽然l d p c 码的理论和应用研究己取得不少进展，但仍有不少问题需要解决。例如：b p 算法的简化与译码性能下降的矛盾等。l d p c 码优异的性能表现是不可否认的，它是继t u r b o 码之后纠错码领域掀起得又一研究热潮。l d p c 码的应用前景是非常广阔的，在许多需要高可靠性的通信和数字存储系统中，l d p c 码成了t u r b o 码的有力竞争者。关键词：短l d p c 码，b p 算法，改进b p 算法i va b s t r a c tg a l l a g e rp r o p o s e dl d p c i l - 2 ，a n dp r o v e dt h a ti tw a sav e r yg o o dk i n do fl i n e a rb l o c kc o d e si n19 6 2 ，b u ta tt h a tt i m eb e c a u s eo fp e o p l e sl e v e lo fa w a r e n e s sa n dc o m p u t e rt e c h n o l o g yl i m i t a t i o n s ，i tw a sn o ta t t r a c t e da t t e n t i o n u n t i l19 9 3 ，t h ef r e n c he n g i n e e rb e r r o ui n v e n t e dt u r b oc o d e st 3 1 ，p e o p l eb e g a nt op a ya t t e n t i o nt oi ta n dr e s e a r c hi t i n19 9 6 ，m a c k a ya n dn e a lf o u n dt h a tl o n gl d p cc a na c h i e v et h ep e r f o r m a n c eo ft u r b oc o d e s 4 - 5 1 ，a n di tw a sa r o u s e da t t e n t i o n l i t e r a t u r e s 6 - 7 s h o wt h a t ，l d p c sp e r f o r m a n c ei sv e r yc l o s et os h a n n o nl i m i t i nt h ea w g nc h a n n e lu s i n gb pi t e r a t i v ed e c o d i n ga l g o r i t h m ，t h ed i s t a n c eb e t w e e nt h ei r r e g u l a rl d p c sp e r f o r m a n c ea n dt h es h a n n o nl i m i ti so n l y0 0 0 4 5 d b 【6 】t h er e a s o nw h yl d p ch a v eag o o dp e r f o r m a n c e ，o n eo ft h em a i nr e a s o mi st h eu s eo ft h eb pd e c o d i n ga l g o r i t h m 1 - 2 i nr e c e n ty e a r s ，w i t hl d p ct e c h n o l o g ym a t u r i n g , t h ea p p l i c a t i o n so fl d p ca r em o r ea n dm o r ew i d e r , i ti sn o to n l ya p p l i e dt oc o m m u n i c a t i o n ss y s t e m s ，a n da l s oa p p l i e dt od i 百t a ls i g n a lp r o c e s s i n g ，a r t i f i c i a li n t e l l i g e n c ea n do t h e rf i e l d s 8 - 9 h o w e v e r , i np r a c t i c a la p p l i c a t i o n s ，t h es h o r t e rl d p c ，s 【l o 】p e r f o r m a n c eb e c o m e so n eo f t h em a i nc o n c e r n s ，t h i st h e s i sm a i n l ys t u d i e st h es h o r tl d p cb pd e c o d i n ga l g o r i t h ma n di t si m p r o v e da l g o r i t h m s f i r s to fa l l ，w ei n t r o d u c et h ed e v e l o p m e n to fe r r o r - c o r r e c t i n gc o d e s ，t h ed e v e l o p m e n to fl d p c ，a n dt h el d p cd e c o d i n gs i t u a t i o na th o m ea n da b r o a d s e c o n d l y , w ei n t r o d u c es o m eb a s i ct h e o r ya n dc o d es t r u c t u r ep r i n c i p l e s ，a n db a s e do nt h i s ，w es t u d yt h ed e v e l o p m e n to fl d p c sc o d i n ga n dd e c o d i n ga n dh a v eab r i e fa n a l y s i so fi t sp e r f o r m a n c e t h e nt h es h o r tl d p cb pd e c o d i n ga l g o r i t h m sh a v eb e e nr e s e a r c h e d a n db a s e do nb pa l g o r i t h m ，w eh a v eap e r f o r m a n c ec o m p a r i s o nb e t w e e nt h et w ot y p e so fl i n e a rb l o c kc o d e so fs h o r tl d p ca n dr sc o d e s w ec a r r yo u tad e e ps t u d yo ni m p r o v e db pd e c o d i n ga l g o r i t h m s ，t h e nw ep r o p o s eas h o r tl d p cb a s e do nb pi m p r o v e m e n tc a s c a d ed e c o d i n ga l g o r i t h mw i t hal o w e rd e c o d i n gc o m p l e x i t ya n di t sd e c o d i n gp e r f o r m a n c eh a sb e e ng r e a t l yu p g r a d e d a l t h o u g ht h et h e o r ya n da p p l i c a t i o no fl d p cc o d e sh a v eg e ta l o n gw e l l ，t h e r ea r em a n yp r o b l e m sn e e dt ob es o l v e d ，s u c ha st h ec o n f l i c tb e t w e e ns i m p l i f i c a t i o na n dr e d u c e dp e r f o r m a n c eo fb pd e c o d i n ga l g o r i t h m i tm u s tb ea d m i t t e dt h a tl d p cc o d e sh a v ee x c e l l e n tp e r f o r m a n c e t h e ya r ea n o t h e ru p s u r g ei ne r r o r - c o r r e c t i n ga r e aa f t e rt u r b oc o d e s t h e yh a v ew i d ep r o s p e c t a n dl d p cc o d e sa r ep o w e rc o m p e t i t o ro f t u r b oc o d e si nm a n yc o m m u n i c a t i o n sva n dd i g i t a lm e m o r ys y s t e m sw h i c hr e q u i r eh i g hr e l i a b i l i t y k e y w o r d s ：s h o r tl d p cc o d e s ，b pa l g o r i t h m ，t h ei m p r o v e db pa l g o r i t h m sa w g na p pb e rb pb p s k缩略语词汇l i s to fa b b r e v l 姐i o n sa d d i t i v ew h i t eg a u s s i a i ln o i s e加性白高斯噪声ap o s t e r i o r ip r o b a b i l i t y后验概率b i te r r o r r a t i ob e l i e fp r o p a g a t i o nb i n a r yp h a s es h i f tk e y i n gb p - b a s e db p b a s e db p o s d fb p o s d fb p o s d jb p o s d - jd a gf e rl d p cl l rm i n s u md i r e c t e da c y c l i cg r a p hf r a m ee r r o rr a t e误比特率置信度传播二相相移键控基于b p 简化算法，又称最小和算法f o s s o r i e r l 6 4 提出的级联算法j i a n g m i n g 6 3 】提出的级联算法非循环有向图误帧率l o wd e n s i t yp a r i t yc h e c k 低密度奇偶校验码c o d el o g - l i k e l i h o o dr a t i o对数似然比m i n i m u m s u m最小和( 算法)m i n - s u m o s d hm i n - s u m - o s d h作者提出的改进级联算法m l dm a x i m u ml i k e l i h o o d 最大似然译码o s ds n rd e c o d i n go r d e r e ds t a t i s t i c sd e c o d i n gs i g n a ln o i s er a t i ov i i统计排序译码信噪比南京邮电大学学位论文原创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。研究生签名：日期：南京邮电大学学位论文使用授权声明南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。研究生签名：南京邮电大学硕士研究生学位论文第一章绪论1 1 纠错码的发展及现状第一章绪论1 9 4 8 年，s h a n n o n 在他的开创性论文“通信的数学理论 1 l 】中，首次阐明了在有扰信道中实现可靠通信的方法，提出了著名的有扰信道编码定理，奠定了纠错码的基石。自此以后汉明( h a m m i n g ) 、斯列宾( s l e p i a n ) 、普兰奇( p r a n g e ) 等人在5 0 年代初，根据s h a n n o n的思想，给出了一系列设计好码和有效译码的方法。以后，纠错码受到了越来越多的通信和数学工作者，特别是代数学家的重视，使纠错码无论在理论还是在实际中得到飞速发展。迄今，纠错码已有五十多年的历史，其发展过程大致可以分为以下几个阶段。5 0 年代至6 0 年代初，主要研究各种有效的编、译码方法，奠定了线性分组码的理论基础；提出了著名的b c h 码编、译码方法以及卷积码的序列译码；给出了纠错码的基本码限；还出版了纠错码的第一本专著。自6 0 年代至7 0 年代初，这是纠错码发展过程中最为活跃的时期。不仅提出了许多有效的编译码方法，如门限译码、迭代译码、软判决译码等。而且注意到纠错码的实用化问题，讨论了与实用有关的各种问题，如码的重量分布、译码错误概率和信道模型化等，为纠错码的实用打下了坚实的基础。7 0 年代初至8 0 年代，在理论上以戈帕( g o p p a ) 为首的一批学者，构造了一类g o p p a码，其中一类子码能达到s h a n n o n 在信道编码定理中所提出的码s h a n n o n 码所能达到的性能，这在纠错码历史上具有划时代意义。自8 0 年代初以来，戈帕等人从几何观点讨论分析码，利用代数曲线构造了一类代数几何码。代数几何码是一类范围非常广的码，在理论上已经证明它具有优越的性能。现在，对代数几何码的研究方兴未艾。9 0 年代出现的t u r b o 码【3 】，使人们可以在很低的信噪比下而得到较高的通信可信度。t l l r b o 码，又称并行级联卷积码，它巧妙地将卷积码和随机交织器结合在一起，实现了随机编码的思想，同时，采用软输出迭代译码【1 2 】来逼近最大似然译码。它是一种实用的纠错码，其性能非常逼近s h a n n o n 的性能界。它的出现，标志着信道编码理论与技术研究进入了一个崭新的阶段，具有里程碑的意义。作为提高数字传输可靠性的技术之一，信道编码在数字通信中得到了广泛的应用。如在移动通信系统中，g s m 系统采用了奇偶校验码和卷积码，a m p s 及t a c s 系统采用了l南京邮电大学硕士研究生学位论文第一章绪论b c h 码；在卫星通信系统中，i n t e l s a t - t d m a 系统采用了扩充的( 1 2 8 ，l1 2 ) b c h 码【6 7 】；在计算机通信中，采用了简单检错码和循环码；在数字微波系统中，尤其是大容量数字微波系统，采用了高码率的自正交卷积码。因此说，在许多通信系统中，假设没有信道编码的存在，就无法顺利的完成通信任务。正因为信道编码在现代数字通信系统中占有重要地位，长期以来，各国专家对信道编码进行了深入的研究，得到了许多性能良好的纠错码。在分组码方面，最重要的一类码是b c h 码，而由b c h 码演化而来的扩展b c h 码、缩短b c h 码、r s 码在通信系统中应用极其广泛。近年来，g o p p a 码受到编码学术界的重视，因为其性能可达到s h a n n o n 码所要求的性能。g o p p a 是一种交替码，可以用几何的观点进行分析，它的出现标志着代数几何码的产生；另一类潜在的高性能码是多级分组码，主要有乘积码和级联码，j u s t e s e n 码是一种特殊的级联码，其性能也能达到s h a n n o n 码所要求的性能。在卷积码方面，除了一般卷积码外，还有为纠突发错误而设计的交错码、扩散卷积码及加格拉尔码等。近年来，分组码与卷积码的研究不再是截然分开的，如级联码，它不一定是单纯的分组码，现在实用的级联码多以卷积码为内码，以r s 码为外码。性能比单纯用分组码要好。与其对应的是译码方法的多样性。一般来说，分组码多采用大数逻辑译码和捕错译码，卷积码多采用维特比译码和序列译码。为了提高译码性能、降低译码复杂度，人们设计了多种译码方法：( 1 ) 软判决译码【1 3 1 。软判决译码可以降低译码中信息的损失，最先在b c h码的译码中得到应用，近来在卷积码的维特比算法中也采用了软判决译码，性能大大提高；( 2 ) 迭代译码【i4 1 。迭代译码有助于降低译码复杂度，也是首先在b c h 码中得到应用。有关迭代译码的文献已日益增多，因为研究表明，合理构造迭代算法，即使是原来性能较差的码( 如奇偶校验码) ，也能得到比较好的性能；( 3 ) 频域译码与快速译码【l5 1 。现有的译码方法多局限于时域译码，谱技术的发展，使频域译码成为可能：快速译码是从快速算法中得到的，选用适当的快速算法，将大大提高译码速度。虽然信道编码经发展产生了多种纠错编码方法，纠错码的性能也越来越好，但各种码的性能与s h a n n o n 在信道编码定理中给出的性能限仍有较大的距离。即使前面提到的g o p p a 码，也存在着很大的局限性。g o p p a 码没有一般的规律来构造好码，尤其是当码长较长时：并且它还没有很好的译码算法，因此，它不是很实用的码，但是通过它可以对好码的设计提供一种新的思路。所以说，如何设计逼近s h a n n o n 性能极限值的、实用的纠错码，是长期困扰信息与编码学术界的难题。t u r b o 码的出现，引起全世界广泛关注。正是人们对t u r b o 码的深入研究，才发现它其实就是一种l d p c ( l o wd e n s i t yp a r i t yc h e c k ) 码【l 】。l d p c 码是g a l l a g e r 于19 6 2 年提出2妻室坚皇奎兰堡圭堑壅竺兰篁堡茎笙二兰堑堡的一种基于稀疏校验矩阵的线性分组码。由于种种原因，在当时并没有得到正确的认识，并且之后的几十年，对它的研究几乎是停止的。现在l d p c 码所表现出的优异性能，已经重新引起学者们的热切关注，成为新的研究热点。1 2l d p c 码的提出及发展1 9 6 2 年，g a l l a g e r 提出了基于稀疏校验矩阵的线性分组码，即低密度分组校验码，并给出了l d p c 码的构造方法，迭代译码算法和其性能在理论上的证明。由于当时计算机水平发展有限，硬件实现困难，l d p c 码并没有得到正确的认识，而是被长期的遗忘了，直到1 9 9 3 年b e r r o u 等人【3 】提出了t u r b o 码，人们研究发现t u r b o 码其实就是一种l d p c码，l d p c 码才又重新引起人们的研究兴趣。后来，m a c k a y 和n e a l 4 , 5 】重新发现l d p c 码和t u r b o 码有着相似的优秀性能，而且在某些方面已经超过了t u r b o 码，之后l d p c 码得到大家的关注，成为新的研究热点。需要指出的是，在l d p c 码被遗忘的这3 0 多年中，z y a b l o v 和p i n s k e r 以及t a n n e r 却在不同的领域直接或间接的对l d p c 码做着研究【1 6 , 1 7 】，这些研究成果，对于l d p c 码今天的研究进展【1 8 】，起着举足轻重的作用。比如，t a n n e r提出的用二分图来表示一个低密度线性分组码的方法，成为了l d p c 码的主要分析工具 1 9 - 2 3 o目前，对l d p c 码的研究主要集中在以下几个方向。( 1 ) 考虑l d p c 码在非g f ( 2 ) 上的构造，也就是对信息的编码不再仅限于0 1 ，而是在有着多个元素的有限域上编码，如g f ( 4 ) ，g f ( 8 ) 等。m a c k a y 和d a v e y 等在此方向作了很多尝试和探索【2 4 1 ，结果非常令人鼓舞。精心的构造多元域上的校验矩阵，可以使性能有很大的提高。并找到了性能优于t u r b o 码的l d p c 码。( 2 ) g a l l a g e r 提出的l d p c 码，其校验矩阵的行重和列重是固定的，通常称其为规则的l d p c 码( 本文中我们用g a l l a g e r 码来称谓) ；l u b y 等人提出【2 5 】，放松对行列重量的限制，构造不规则的l d p c 码，也就是每行( y 0 重量不再相同。信息比特所在的列越重，所参与的校验式就越多，译码时就越容易纠错，从而可以帮助译码器更容易的纠正其它错误。研究结果表明，这对于g a l l a g e r 码，性能也有了较大改进。r i c h a r d s o n 等人构造的非规则l d p c 长码【2 6 1 ，性能要优于规则l d p c 码，并且也要优于t u r b o 码。文献【2 7 1 的研究表明，对非规则l d p c 码利用和积算法( s u m p r o d u c t ) 迭代译码后，在高斯白噪声信道中可以逼近信道容量，仅有0 0 0 4 5 d b 的距离。现在这两个研究方向j 下在不断结合，来寻找性能更优的非g f ( 2 ) 上的不规则l d p c 码。3南京邮电大学硕士研究生学位论文第一章绪论同时发展的还有其它的一些构造方法【2 8 2 9 1 。由于译码算法相对简单和硬件水平的提高，l d p c 码的硬件实现正在成为一个研究热点【3 2 1 。l d p c 码具有的巨大应用潜力【3 3 - 3 5 , 6 5 。6 6 l ，使其将在深空通信、光纤通信、卫星数字视频和声频广播、磁光全息存储、移动和固定无线通信、电缆调制解调器和数字用户线( d s l ) 等中得到广泛应用。我们相信其进入实用领域是指日可待的【3 6 】。1 3 有关l d p c 码译码算法的研究g a l l a g e r 提出了l d p c 码，并给出了两种l d p c 码的译码算法：硬判决和软判决算法。后者性能要好，但太复杂。算法应用了迭代思想，应该说g a l l a g e r 是最早提出迭代译码算法的。已经证明迭代消息传送算法对于高性能低复杂度的编码方案是可行的。从完全硬判决到软判决算法，有很多迭代算法被用于低密度校验码的译码。每一种算法提供了不同的性能与复杂度的均衡。文献【3 7 】提出的消息传递算法可以认为是比较好的折衷算法，消息传递算法也就是我们说的置信度传播( b e l i e fp r o p a g a t i o n ) 算法。迭代算法可以很自然的描述为沿着一个二分图的边传送消息，代表码字通过一个校验方程。迭代译码算法每一次迭代包含沿着图的边：( 1 ) 从变量节点到校验节点；( 2 ) 从校验节点到变量节点的两列传送消息。迭代译码算法在实际仿真中展现了极其优越的性能，但在理论上却很难有准确的性能分析。加州理工大学的教授r o b e r tj m a c e l i e c e 提出理论【3 8 】：迭代译码算法为在人工智能领域内著名的可信度传播算法( b p ) 的实例。而b p 算法是一种广泛应用于人工智能领域的推理算法。对l d p c 码采用b p 算法迭代译码后，可以获得非常好的性能。以b p 算法为基础的多种改进的迭代译码算法亦非常接近b p 算法的性能。b p 迭代译码算法迭代更新码序列每一比特的后验概率。从某种程度上来说，它就是一种和积算法【3 9 1 。作为一种通用的消息传递算法，和积算法实际上包含了大量的实际译码算法，如前向后向算法、v i t e r b i 算法、快速傅立叶变换算法【加】。l d p c 码译码可以采用硬判决译码也可以用软判决译码或二者兼有。b f ( b i tf l i p p i n g )算法是一种低复杂度的硬判决译码方法，其性能要比软判决的b p 算法差些，但是实现要简单。而w b f ( w e i g h t e db i tf l i p p i n g ) 在纠错性能和译码复杂度之间提供了很好的均衡【4 1 】。它联合了b f 算法的简洁和由于在消息中包含一些可靠度( 软信息) 而改善了性能。我们知道算法的简化、复杂度的降低一般是以信噪比为代价换取的。综上所述，l d p c 码采用迭代译码算法。这种算法的优点有：算法完全是并行的，因此译码速度极高；译码算法的复杂性较低【4 2 ，4 3 1 ，其运算量不会因为码长增加而急剧增加，4塑室坚皇奎堂堡圭婴壅竺堂垡堡茎一一墨二兰丝笙这是卷积码及其它分组码所不可比拟的。在复杂度和性能上可以得到很好的折中，既可以选择实现简单、性能稍逊的b f 算法，也可以选择实现复杂、性能优越的b p 算法，也可选择趋于中间的w b f 。即使对同一种译码算法，也可依据信道的条件【州6 1 ，以及系统的要求，选择不同的迭代次数，非常灵活。1 4 本文主要工作及论文安排l d p c 码优越的性能引起人们广泛的研究兴趣，许多学者对其进行了深入的研究。我们也对其进行了研究，尤其在译码方面。本人对短l d p c 码b p 译码算法及其改进算法作了一些研究。具体内容安排如下：( 1 ) 第1 章和第2 章，介绍了本文的研究背景和基本的理论。( 2 ) 第3 章介绍了l d p c 码的基础知识。( 3 ) 第4 章主要研究了短l d p c 码的b p 译码算法及其改进算法，对译码算法进行了分析，归纳和总结，提出了一种基于b p 短l d p c 码的改进级联算法，译码复杂度降低，译码性能得到很大提升。总之，对l d p c 码的研究是继t u r b o 码之后纠错码领域掀起的又一研究热潮，它向逼近s h a n n o n 限的目标又跨进了一步。l d p c 码应用前景非常广阔，在许多需要高可靠性的通信和数字存储系统中，l d p c 码成了t u r b o 码的有力竞争者。南京邮电大学硕士研究生学位论文第二章信道编码2 1 数字通信系统的组成第二章信道编码通信的目的是把消息及时可靠地从一方传到另一方，这必然要求通信系统传输消息必须可靠快速，在数字通信系统中可靠与快速往往是一对矛盾。若要求快速，则必然使得每个数据码元所占的时间缩短、波形变窄、能量减少。从而在受到干扰后产生错误的可能性增加，传送消息的可靠性降低。若要求可靠，则使得传送消息的速率变慢。因此，如何合理解决可靠性与速度之间的矛盾，是正确设计一个通信系统的关键问题之一。通信理论本身也正是在解决这对矛盾中不断发展起来的。所有的数字通信系统，如通信、雷达、遥控遥测、数字计算机的存储系统和内部运算以及数字计算机之间的数据传输等等，都可归纳为图2 1 的模型表示：图2 1 数字通信系统模型图2 - 1 中，信源编码是把信源发出的消息如语言、图像等转换成为- - ( 多) 进制形式的信息序列，为了使传输有效，通过信源编码器去掉一些与传输无关的多余度。而为了抗击传输过程中的各种干扰，往往要人为地增加一些多余度，使其具有自动检错或纠错能力，这由图中的信道编码器来完成。发射机是把纠错码送出的信息序列通过调制器变换成适合于信道传输的信号。数字信号在信道传输过程中，总会遇到各种干扰而使信号失真，这种失真信号传输到接收端的接收机，进行解调，变成- - ( 多) 进制信息序列。经过信道译码器，对传输中产生的错误进行纠正，再通过信源译码器恢复成原来的消息送给用户。我们关心的是图中的信道编、译码器两个方框，为了研究方便我们可以将图2 1 模型简化为图2 2 。6童室坚皇奎堂堡主堡壅竺堂篁丝茎蔓三兰笪望塑塑在此模型中，信源是指原来的信源和信源编码器，其输出是- - ( 多) 进制信息序列。信道是包括发射机、实际信道( 或传输媒质) 和接收机在内的广义信道( 又称编码信道) ，它的输入是- - ( 多) 进制信息序列，输出一般也是二( 多) 进制信息序列。信宿可以是人或计算机。图2 2 数字通信系统简化模型信道编码的目的是克服信道传输特性不理想和各种噪声的影响，使信号码元在信道上传输的误码率尽可能地降低，提高通信可靠性。信道编码的任务就是研究各种编码和译码方法，检测和纠正信号传输中的误码。信道编码的实现方法是在发送端将信号码元附加上一些监督码元，在接受端根据监督码元与信号码元之间的关系进行译码，找出接收到的信号码元与发送的信号码元之间的不同，并加以纠正。2 2 差错控制系统与纠错码分类在数字通信系统中，利用纠错码或检错码进行差错控制的方式大致可分为三种【4 7 4 8 】：( 1 ) 检错重发( a r q ：a u t o m a t i cr e t r a n s m i s s i o nr e q u e s t ) ：在接收端根据编码规则进行检查，如果发现规则被破坏，则通过反向信道要求发送端重新发送，直到接收端检查无误为止。a r q 系统具有各种不同的重发机制：如可以停发等候重发、x 2 5 协议的滑动窗口选择重发等。a r q 系统需要反馈信道( 反向信道) ，且只能在双向信道采用，效率较低，但是能达到很好的性能。( 2 ) 苜i j 向纠错( f e c ：f o r w a r de r r o rc o r r e c t i o n ) ：发送端发送能纠正错误的编码，在接收端根据接收到的码和编码规则，能自动纠正传输中的错误。不需要反馈信道，实时性好，但是随着纠错能力的提高，编译码设备复杂。( 3 ) 混合方式：上述两种差错控制方法可以结合使用，如检错和纠错结合使用。当出现少量错码并在接收端能够纠正时，即用前向纠错法纠正；当错码较多超过纠正能力时，就用a r q 法。结合前向纠错和a r q 的系统，在纠错能力范围内，能自动纠正错误，超出纠错范围则要求发送端重新发送。它是一种折中的方案。信道纠错码中的码字分类：信道编码中用到的码类有很多种，为了清楚起见，我们用图2 3 表示。7南京邮电大学硕士研究生学位论文第二章信道编码2 3 信道编码定理图2 - 3 纠错码分类信道编、译码器是用来提高信道的可靠性措施之一，它们的基础是信道编码。信道编码大致可分两大类问题：一类是信道编码定理，解决编码器和译码器的存在问题；另一类是编码方法和性能界限。2 3 1 信道容量信道能无错误地传送信息的最大信息率称为信道容量。对于单用户信道它是一个数，以比特每秒或符号每秒来表示。它代表每秒能传送的最大信息量。小于这个数值必能无误地传送。信道容量是由输入集x 、输出集】，和条件概率( 或称为传输概率) p ( yix ) ，y y ，x x所规定的。如果x 和】，是离散集，信道的传送信息率就是x 和y 间的互信息。即：c = m a x i ( x ；y )( 2 1 )互信息与夕( x ) 和p ( ylx ) 有关，若能改变p ( x ) ( p ( x ) ) 使互信息最大，就能充分利用信道的传输能力。从数学上说，求信道容量就是对平均互信息i ( x ；y ) 求极大值的过程，但对于一般信道而言，信道容量的计算相当复杂。我们就对最易于解出信道容量的两种信道进行说明。( 1 ) - - 元对称信道，简记为b s c输入集x 、输出集y 取值于( o ，1 ) ，所以p ( yix ) = pp ( yix ) = l - p ，其中，p 为信道的转移概率。而b s c 信道的误码率s = p 。二元对称信道容量【4 9 1 为：南京邮电大学硕士研究生学位论文第二章信道编码c = 1 - h ( e ) ( b i t s )( 2 2 )式中h ( x ) 为熵函数，一般表示为：胃( x ) = 一x l o g x 一( 1 一z ) 1 0 9 ( 1 一x )( 2 3 )( 2 ) 高斯信道我们来看无记忆的二元输入高斯白噪声信道( b i a w g n ) ，y = i + z ，x 1 ) ，z 是服从均值为0 ，方差为仃2 的正态分布，其密度函数为：b i a w g n 信道的容量为：p ( z ) 5 丽1p 寺一z( 2 4 )c ( 盯) = 一忙( 训。g ：丸( x ) 出一圭l 0 9 2 ( 2 z e o - 2 ) ( 2 - 5 )这里，丸( x ) ：1 专( g 一等+ e 一百( x - i ) ) 。4 8 z o 2我们一般定义高斯信道的容量为：c = 肌9 2 ( 1 + 彘) ( 砌s )( 2 - 6 )o 为单边带功率谱密度( 矿舷) ；f 为信道所能提供的带宽( 舷) ；s 为信号功率( 形) 。若令信道信息率r c ，并令。s点62 一r为每比特的信号能量，将式( 2 7 ) 代) k x - - 戈( 2 6 ) 可得万r 型( 2 9 )n or、。乓o 和，是设计数字通信系统的两个重要参数。式( 2 8 ) 给出了带宽和平均功率都受限的高斯信道( a w g n ) 传信率的上限。当平均功率受限而带宽不受限时，可令f 专o o ，此时有厂专0 ，可得：鲁 型 l n 2 ：- 1 - 5 9 ( d b )( 2 1 0 )o，、这是通过功率受限a w g n 信道传送1 比特信息必须保证的瓦o 下限，称为s h a n n o n限，是软判决译码所能达到的最好结果。这也就是说，当色o - i 6 d b 时，就可实现高斯信道下的无误传输，是带窗无限高斯信道的极限传输能力。表2 1 给出了几种常用编码所能得到的编码增益，可以看出这些编码离s h a n n o n 限还有一定的距离。表2 - ib p s k 或q p s k 的编码增益【6 8 】所有编码编码增益( d b )编码增益( d b )数据率b e r = 1 0 。b e r = 1 0 5理想编码1 1 21 3 6级联码( r s 与卷积码6 5 - 7 58 5 - 9 5适中v i t e r b i 译码)卷积码序列译码( 软判6 0 7 o8 0 9 0适中决)分组码( 软判决)5 0 6 o6 5 7 5适中级联码( r s 与分组码)4 。5 5 56 5 7 5很高卷积码v i t e r b i 译码4 o 5 55 o 6 5i 葡卷积码序列译码( 硬判4 0 5 o6 o 7 o局决)分组码( 硬判决)3 0 4 04 5 5 5高分组码门限译码2 0 4 o3 5 5 5同卷积码门限译码1 5 - 3 o2 5 4 o很高l o堕室堕皇奎堂堡圭堡壅竺堂垡堡塞蔓三童笪望箜里要实现s h a n n o n 的这一理论结果是相当困难的，而且为了确定信道的极限能力需要知道信道干扰的统计特性。但实际情况下信道干扰的分布很少可能是已知的，而且可能随时问而变化。若按主观上预先定的干扰分布设计差错控制系统会带来很大的问题。所幸的是，我们并不一定需要确知信道统计特性才能动手设计。通常采用的方法是取某一特定的码，分析在一、两种确知干扰类型下的性能，并与未编码的结果进行比较，也与其它编码方法的结果进行比较，来得到有用的结论。这种方法在不涉及通信系统的设计者和它的有关信道知识条件下，就可以给出明确的结果，从而使纠错码得到广泛的应用。2 3 2 信道编码定理s h a n n o n 信道编码定理：对于一个给定的有扰信道，若信道容量为c ，只要发送端以低于c 的速率r 发送信息( 尺为编码器的输入二进制码元速率) ，则一定存在一种编码方法，使编码错误率p 随着码长甩的增加，按指数下降到任意小的值，即p 8 埘足( 2 1 1 )这里e ( r ) 称为误差指数，它与r 、c 的关系如图2 - 4 所示。图中，c l ，g 为信道容量。0图2 4e ( r ) 与尺的关系这条定理告诉我们：( 1 ) 在码长及发送信息速率一定的情况下，为减小p ，可以增大信道容量。由图2 - 4可知，e ( r ) 随信道容量的增加而增大。由式( 2 1 1 ) 可知，错误概率随e ( r ) 而指数下降。( 2 ) 在信道容量及发送信息速率一定的条件下，增加码长，可以使错误概率指数下降。从实际的角度来看，这时设备复杂性和译码延时也随之增加。反之，如果r c ，必定不存在这种编码方法，当n 趋于无限大时，差错概率将接近l 。我们称此为反定理。l l堕室堕皇奎堂堡主翌壅竺兰垡堡苎蔓三雯笪望塑塑s h a n n o n 编码定理仅仅是一个存在性定理，它只告诉我们存在满足式( 2 1 1 ) 、信息传输率无限接近信道容量的好码，并没有说明如何构造这样的码，但定理却为寻找这样的码指明了方向。也正是在此定理的指引下，经过几代人的不懈努力，已经发现可许多性能优良的码及相应的译码方法，且所需的信噪比越来越接近s h a n n o n 限，使得信道编码理论和技术研究取得了辉煌的成功。2 4 分组码分组码是信息序列以k 个码元分组，通过编码器将每组的k 元信息按一定的规律产生，个冗余码元( 称为校验元或监督元) ，输出长为厅= k + r 的一个码字( 组) 。因此，每一码组的，个校验元仅与本组的信息元有关而与别组无关。分组码用( ，z ，k ) 表示，n 表示码长，k表示信息位数目，r = k n 称为分组码的编码效率，也称为编码率或码率。，z 长序列的可能排列总共有2 ”种( 每一n 长序列称为刀重) ，一个( ，z ，k ) 分组码( 以q = 2为例) 的码字集合只有2 种，分组编码其实就是以一定的规则从2 ”个，l 重选择其中的2 个n 重构成一个许用码的码集c ，而其余的2 ”一2 个n 重为禁用码组。2 4 1 线性分组码的基本概念任何一个( ，z ，后) 分组码，如果其信息元与监督元之间的关系是线性的，即能用一个方程来描述的，则称为线性分组码。线性分组码在所有可能的分组码中只占很少的一部分，然而，他却几乎是唯一具有实际价值的分组码。线性分组码是所有纠错码中最基本最容易的一类码，概念清楚，易于理解，而且能方便地引出各类编码中广为使用的一些基本参数和名称。因此，线性分组码成了讨论其他各类码的基础。( ，z ，k ) 线性分组码的每个码字有胛一k 个监督元，要从k 个信息元中求出，z k 个监督元，必须有刀一k 个独立的线性方程，根据求监督元的不同线性方程，就得到不同的( 以，k )线性分组码。1 2南京邮电大学硕士研究生学位论文第二章信道编码2 4 2 生成矩阵和一致校验矩阵( r , k ) 线性分组码的编码问题就是如何根据已知的k 个信息元求得0 一k ) 个监督元。由于是线性码，它们一定是由( 刀一k ) 个线性方程构成的方程组。( ，z ，k ) 线性分组码的2 个码字组成，l 维向量空间的一个k 维子空间，而线性空间可由其基底张成，因此( 咒，k ) 线性分组码的2 个码字完全可由k 个独立的向量所组成的基底张成。设k 个向量为g l = ( g ll g l 2 g i t g i 女+ i g i h )9 2 = ( 9 2 1 9 2 2 9 2 女9 2 女+ t 9 2 。)& = ( g t l g k 2 g 胜g k 女+ l g 砌)将它们写出矩阵形式：f ，g - - g - z g t t g - ，t + t g t 一、g ：i9 2 1 9 2 2 9 2 k 9 2 k 1 9 2 ni l g t l g 2 g 触g k ，t + l c = 鹏= ( 鸭一。一：) =( 2 - 1 2 )( 2 1 3 )式中m = ( 一。一：m o ) 是k 个信息元组成的信息组。每给定一个信息组，通过式( 2 一1 3 )便可求得相应的码字。故称这个由k 个线性无关矢量组成的基底所构成的k v 阶矩阵g为( 力，七) 码的生成矩阵。一般而言，( 咒，k ) 线性码有，= 甩一k 个校验元，故必须有，个独立的线性方程，所以( 刀，j i ) 线性码的校验矩阵由，行和刀列组成，每一行代表一个线性方程的系数。可表示成：1 3鼠溉溉黔砧雌涵艚膳舒够苫拉舱鼠鼠蜀瓯南京邮电大学硕士研究生学位论文第二章信道编码r ，啊。鼻：日：j 冬- k由矩阵可以建立码的，个线性方程：简写为h c 7 = 0 r 或