（通信与信息系统专业论文）线性分组码的最大似然译码研究.pdf

摘要线性分组码的最火似然译码研究摘要信道编码是现代通信中，为实现信息的可靠性传输而不可或缺的技术之一。线性分组码是信道编码中最为常见、研究最多的码字类型。包括汉明码、r m 码、r e e d s o l o m o n ( r s )码、l d p c 码等。其中l d p c 码是当前研究的热点之一。研究表明，特别设计的l d p c 码是当前最接近s h a n n o n 限的编码。线性分组码有两类译码算法，分别是代数译码和基于可靠度的最大似然译码两类。其中代数译码是根据码字的特殊代数结构，基于一定的代数方法来发现错误并纠正错误。基于可靠性的译码，也称作软译码，是利用信道的接收软信息，作为接收符号的可靠度，参与译码，从而使得译码性能要优于代数译码。本文主要致力于线性分组码的软判决译码算法的研究。首先系统的介绍了线性分组码的基本原理、线性分组码的分类、一类特殊的线性分组码- - l d p c 码，然后系统地介绍了一些软判决译码算法，如g m d 算法、c h a s e 、w e d 、k n i h 、r l s d 、o s d 算法、b m a 算法、p f s 算法等。在此基础上，为了提高线性分组码的纠错性能，本文提出了几种改进算法。一种是基于c h a s e 和o s d 的并行级联译码算法。分阶统计译码算法( o s d ) 和c h a s e 算法等都是一类最大似然译码算法( m l d ) 。o s d 算法对接收序列的k 个可信度最高的符号( m r i p s )作为消息位进行重新编码处理，产生候选码字。如果过多的错误出现在m r i p s 中，则算法不能成功；而c h a s e 算法是对接收序列的l r p s 进行比特翻转和代数译码。如果过多的错误出现在l r p s 部分，则c h a s e 译码不会成功。同时由于o s d 算法和c h a s e 算法复杂度较高，不宜直接应用于l d p c 的译码，为此我们充分利用o s d 算法和c h a s e 算法这种互补特性，并使用b p 算法作为算法的前级，设计了一种并联级联译码算法。该算法充分利用了接收比特的可信度信息。仿真结果表明，提出的c h a s e o s d 算法是有效的，可以在计算复杂度和译码性能之间进行较好的折衷。同时我们使用这种并行互补算法对r a m 码进行了仿真。本文还提出了一种b p 算法和w e d 算法的级联算法。这种级联算法也能充分利用接收符号的可靠度，相比b p 算法提高了译码性能。由于w e d( w e i g h t e de r a s u r ed e c o d i n g ) 算法也是一种软迭代译码算法，但是其运算规则，硬件实现较为简单，因此本文给出的b p w e d 级联译码算法要比b p o s d 、b p b m a 等级联算法容易硬件实现。关键词：线性分组码；软判决译码；置信度传播：级联译码算法i i ia b s t r a c t硕士学位论文a b s t r a c tc h a n n e lc o d i n gi sa i le s s e n t i a lt e c h n o l o g yi nm o d e mc o m m u n i c a t i o n st oa c h i e v et h er e l i a b i l i t yo fi n f o r m a t i o nt r a n s m i s s i o n l i n e a rb l o c kc o d e sa r et h em o s tc o m m o na n dm o s ts t u d i e dc h a n n e lc o d i n gc o d e s ，i n c l u d i n gh a n m i n gc o d e ，r e e dm u l l e rc o d e ，r e e ds o l o m o nc o d e ，l o w d e n s i t yp a r i t y c h e c kc o d e ( l d p c ) a n ds oo n t h el d p cc o d ei so n eh o tp o to fc u r r e n tr e s e a r c h s t u d i e sh a v es h o w nt h a ts p e c i a l l yd e s i g n e dl d p cc o d ei st h ec l o s e s te n c o d i n gt ot h es h a n n o nl i m i t t h e r ea r et w ot y p e so fl i n e a rb l o c kc o d e sd e c o d i n ga l g o r i t h m n a m e l y , a l g e b r a i cc o d i n g ，a n dr e l i a b i l i t y - b a s e dm a x i m u ml i k e l i h o o dd e c o d i n g a l g e b r a i cd e c o d i n gi sb a s e do nt h es p e c i a la l g e b r a i cs t r u c t u r eo fc o d ew o r d s a n dac e r t a i na l g e b r a i cm e t h o d st of i n da n dc o r r e c tm i s t a k e s r e l i a b i l i t y b a s e dd e c o d i n g ，a l s ok n o w na ss o f td e c o d i n gu s e st h es o f ti n f o r m a t i o nr e c e i v e df r o mc h a n n e la st h er e l i a b i l i t yo fr e c e i v e ds y m b o l si n v o l v e di nd e c o d i n g w h i c hm a k e st h ed e c o d i n gp e r f o r m a n c ei sb e t t e rt h a na l g e b r a i cd e c o d i n g t h i sa r t i c l ef o c u s e so nt h es o f t d e c i s i o nd e c o d i n ga l g o r i t h mo fl i n e a rb l o c kc o d e s f i r s t l y ,t h i sp a p e rs y s t e m a t i c a l l yi 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 i n e a rb l o c kc o d e s t h ec l a s s i f i c a t i o no fl i n e a rb l o c kc o d e s ，as p e c i a lc l a s so fl i n e a rb l o c kc o d e s l d p cc o d e 。a n dt h e ni n t r o d u c e ss o m ec u r r e n tm a i n s t r e a mo fs o f t d e c i s i o nd e c o d i n ga l g o r i t h m ，s u c ha st h eg m d ，c h a s e ，w e d ，k n i h ，r l s d ，o s d ，b m a ，p f sa l g o r i t h m o nt h i sb a s i s i no r d e rt oi m p r o v et h ep e r f o r m a n c eo f1 i n e a rb l o c ke r r o r - c o r r e c t i n gc o d e s t l l i sp a d e rp r e s e n t ss e v e r a li m p r o v e da l g o r i t h m 0 n ei sap a r a l l e lc o n c a t e n a t e dd e c o d i n ga l g o r i t h mb a s e do nt h ec h a s ea n do s da l g o r i t h m o r d e r e ds t a t i s t i c sd e c o d i n ga l g o r i t h m( o s d ) ，a n dc h a s ea l g o r i t h m sa r ea l lm a x i m u m l i k e l i h o o dd e c o d i n ga l g o r i t h m s ( m l d ) c h a s e - t y p ed e c o d i n ga l g o r i t h mi sb a s e do np r o c e s s i n gc e r t a i nl i 心so far e c e i v e ds e q u e n c e ，w h i l eo s da l g o r i t h mi sb a s e do np r o c e s s i n gc e r t a i nm r i p so far e c e i v e ds e q u e n c e i ft h e r ea r et o om a n ye r r o r si nm r i p s t h eo s da l g o r i t h mw i l lf a i l w h i l et h e r ea r et o om a n ye r r o r si nl r p s t h ec h a s e t y p ea l g o r i t h mw i l lf a i l w 色p r o p o s eap a r a l l e lc o n c a t e n a t i o nd e c o d i n ga l g o r i t h mb a s e do nt h a tc o m p l e m e n t a r yc h a r a c t e r i s t i c t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h mi se f f e c t i v e t h ed e c o d i n gp e r f o r m a n c ei si m p r o v e dc o m p a r e dw i t hb p o s da n db p c h a s ea l g o r i t h m t h i sa r t i c l ea l s omi sak i n do fs o f t i n s o f t o u ta l g o r i t h m m e nb pa l g o r i t h mf a i l s t h es o f tl l rr e l i a b l ei n f p r e s e n t sab pa l g o r i t h mc o n c a t e n a t e dt h ew e da l g o r i t h m b e l i e fp r o p a g a t i o nf b p ) a l g o r i t h o r m a t i o ni sq u a n t i z e da n ds e n tt ot h ew e da l g o r i t h m w e da l g o r i t h mi sav e r ya t t r a c t i v es o l u t i o nf o rp r a c t i c a li m p l e m e n t a t i o n so fl o w c o m p l e x i t yr e l i a b i l i t y b a s e da l g o r i t h m so w i n gt oi t ss i m p l i c i t y , t h e r e f o r et h eb p w e dc o n c a t e n a t i o na l g o r i t h mi sm o r ee a s yi nh a r d w a r ei m p l e m e n t a t i o nc o m p a r e dt oo t h e rc o n c a t e n a t i o na l g o r i t h m s s u c ha sb p o s d b p b m a ，e t c t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o p o s e dc o n c a t e n a t i o na l g o r i t h mi se f f e c t i v e a n dc a na c h i e v e sag o o dt r a d e o f rb e t w e e nc o m p u t a t i o n a lc o m p l e x i t ya n dd e c o d i n gp e r f o r m a n c e k e yw o r d s ：l i n e a rb l o c kc o d e s ；s o f t - d e c i s i o nd e c o d i n g ；b e l i e fp r o p a g a t i o n ；c a s c a d ed e c o d i n ga l g o r i t h mi v声明本学位论文是本人在皮德富教授的指导下取得的研究成果，尽我所知，在本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文中作了明确的说明。研究生签名：蕴园坌2 。9 年1 2 月2 0 日学位论文使用授权声明南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密论文，按保密的有关规定和程序处理。研究生签名：2 0 0 9 年1 2 月2 0 日硕上学位论文线性分组码的最大似然译码研究1 绪论通信的两个基本目标是有效性和可靠性。其中有效性是指在有限的带宽内传输更多的信息，而可靠性是指在有噪信道内，如何可靠地传输信心。因此研究如何保证信号传输的可靠性，是现代通信中的一个关键问题。信道编码技术，也称作差错控制编码的研究就成为一个重要的研究内容。1 1 本课题提出的背景和意义信道中存在各样的噪声和干扰，这些因素使得通信变得不可靠。为实现信息的可靠性传输，人们提出了很多方法，其中信道编码技术是最重要的可以纠正错误的方法。信道编码技术是二十世纪4 0 年提出、6 0 年代发展起来的一种为提高数据传输的可靠性的理论。经过6 0 多年的发展，现在已经形成了一整比较成熟的信道编码理论和技术。随着现代大容量数字通信的发展，对数据传输的可靠性提出了越来越高的要求，因此，如何在添加相对少量的冗余来提高数据传输的可靠性已经成为一个迫切需要解决的问题。由于信号在传输过程中，因为噪声和干扰，信号将会受到不可避免的干扰，从而有可能判决错误。所以必须对数字信号采用纠错技术技术，也就是能够使用一种技术，能够发现并纠正错误，以增强信号在信道中传输时的抗干扰能力。信道编码就是在信息码中增加定数量的冗余码元，这些冗余码元之间要满足一定的约束关系。由信息码元和监督码元共同组成了码字。码字在传输的过程中如果受到干扰，某些码元发生了变化，就破坏了这些比特之间的约束关系，接收方通过检验这种约束关系就可能发现错误，如果约束关系较多，则有可能能把发生的错误识别出来，从而保证通信的可靠性。信道编码一般使用代数理论为依据，使用代数理论来发现并纠正错误。如果不进行信道编码而直接把信息送入信道，收到的信息就只是可能，我们不知道接收的符号是否正确。以l d p c 码为代表的线性分组码的译码性能随着码字长度的增加而提高，但是增长的码长也意味者译码代价的提高：如果采用串行译码器，则译码器的译码延时太长，以至于超过所能容许的界限，尤其不适合实时通信系统，比如实时语音、图像传输，太空控制信号传输等；如果采用并行译码器，则译码器的硬件复杂度太高。增加了译码的延时，译码器的复杂性也随着提高。长码长的l d p c 码在b p 迭代译码算法下性能优异，但是由于硬件实现困难，因此研究中短码长l d p c 码的译码算法成为当前国内外的研究热点。b p 算法下的中短码长l d p c 码要比长码长l d p c 码性能下降很多。为解决这个问题，出现了各种级联算法，比如b p - o s d ，b p b m a 等【1 】1 2 j 。分阶统计译码算法( o s d ) 【3 】和盒匹配算法( b m a ) 等都是一类最大似然译码算法( m l d ) ，但是由于高斯消去和排序的计算复杂度较高，所以单独运用于l d p c 译码不可行。这些级联算法都是把b p 迭代后的软输出对1 绪论硕士学位论文数似然比( l l r ) 信息作为后续算法的软输入。级联算法能够在译码复杂度和性能间进行较好的折中，并且能够接近最大似然( m l ) 译码的性能。本文在研究o s d 、w e d 、c h a s e 等几种应用于线性分组码的最大似然译码算法的基础上，充分利用这几种算法的特点，设计了两种适用于中短l d p c 码的兼顾复杂性和译码性能的级联算法，这些算法可以在有限的计算复杂性的基础上，实现了性能上的提高。仿真表明，这几种级联译码算法都可以在性能和复杂度之间进行较好的折衷。1 2 国内外研究现状1 9 4 8 年仙农创立了信息论【4 6 】，第一次指明了信道编码的发展方向和研究目标。仙农指出，任意一个信道都存在一个确定的信道容量c ，当通信速率r 小于信道容量c时，总存在一种编码方法，当码长充分时，若采用最大似然算法进行译码，则信息错误率可以达到任意小。这就是著名的有噪信道编码定理。该定理没有给出构造纠错码的方法，仅是一个编码的存在性定理，但是开辟了信道编码理论这一富有活力的研究领域。仙农信道编码定理指出，系统可以随着码长的增加而获得更多的编码增益。但是，当码长较大时实现最大似然译码比较困难。因此构造实现简单实用的编码方案以及寻找有效的译码算法成了信道编码理论与技术研究的中心任务。在2 0 世纪4 0 年代，r h a m m i n g 和m g o l a y 率先提出了一个实用的信道编码方案，这极大地推动了编码理论的发展。此后，m g o l a y 提出了纠错能力更强的二元g o l a y 码以及三元g o l a y 码。在g o l a y 码之后，m u l l e r 在1 9 5 4 年提出了一种分组码，r e e d 在m u l l e r 提出的分组码的基础上又提出了一种新的分组码，叫做r e e d m u l l e r ，简称r m码。相对于汉明码以及g o l a y 码，r m 码在纠错能力以及码字长度方面具有更好的适应性。在r m 码之后，人们又提出了循环码的概念。循环码也属于线性分组码，但它的码字具有循环移位特性，循环码的这种特性大大简化了编译码结构。1 9 6 0 年，r e e ds o l o m o n 码由麻省理工学院( m i t ) 林肯实验室的1 s r e e d 和g s o l o m o n 在工业与应用数学协会学报上发表了论文p o l y n o m i a lc o d e so v e rc e r t a i nf i n i t ef i e l d ) ) ，这篇论文提出了一类多元最大距离可分( m d s ) 码，也就是r e e d s o l o m o n码的最初设想。r s 码的纠错能力令人满意，但在其诞生的早期并没有得到广泛的应用，原因是由于没有好的解码算法，在当时的条件下难以有实际意义上的工程实现。1 9 6 0年，p e t e r s o n 从理论上解决了二元b c h 码的译码问题，奠定了b c h 码译码的理论基础。稍后，g o r e n s t e n 和z i e r l e r 注意到r s 码是一类特殊的b c h 码，把p e t e r s o n 的算法推广到多元码。p e t e r s o n g o r e n s t e i n z i e r l e r 算法( p g z 算法) 非常直观、容易理解，但在译码过程中需要计算矩阵的逆，计算比较复杂。1 9 6 8 年，e r b e r l e k a m p 提出了一种可以有效地实现b c h 和r s 码解码的方法，b e r l e k a m p 将p e t e r s o n 的算法改造成迭代形式，使得可对高纠错能力的r s 码进行解码，它首次使得可以纠正多个字节错误的r s 码的解码成为可能。1 9 6 9 年，j m a s s e y 则发现2硕士学位论文线性分组码的最大似然译码研究b e r l e k a m p 算法等价于寻找到一个能生成给定序列的最短线性移位寄存器( 1 f s r ) ，并重新推导了这一算法，给出了迭代译码算法与序列的最短移位寄存器综合之间的关系。该算法现在常被称为b e r l e k a m p m a s s e y ( b m ) 算法，b m 算法使得解码复杂度从o ( n 3 ) 降到o ( n 2 ) 。1 9 7 5 年，y s u g i y a m a 、m k a s a h 锄提出了一种解关键方程的e u c l i d e a n 算法，该算法的复杂度也是o ( n 2 ) ，可以有效地对r s 码、b c h 码和g o p p a 码解码。1 9 8 3 年，由l w e l c h 和e r b e r l e k a m p 提出了一个关键方程，仅仅依赖于余式和生成多项式，不需要计算伴随式，因而我们把w e l c h b e r l e k a m p 译码算法( w b 算法) 称为余式译码算法。虽然上述分组码在数学上已经非常成熟，并且在实际通信系统中得到了广泛的应用。但是分组码存在一些固有的缺陷。首先分组码是面向分组块的，因此必须在接收完整码字之后才能开始译码，当数据块比较大时，产生很大的译码时延。另一缺点是大多数基于代数的分组码的译码都是硬判决译码，因此性能损失较大。虽然可实现码的软判决译码，但是通常译码的复杂度都比较大，基本上是随着码长的增加呈指数增加。1 9 5 4年e l i a s 等人提出了一种没有线性分组码上述缺点的卷积码。在编码时，卷积码引入了寄存器，增加了码元之间的相关性，可边输入数据边进行编码。并且，在接收了部分码元之后，就可以进行译码。特别是1 9 6 7 年维特比译码算法的出现，使卷积码在通信系统中得到了极为广泛的应用。2 0 世纪8 0 年代，信道编码进入了另一研究高潮。以前传统的编码技术都是增加系统的带宽来换取编码增益，因此不适合对带宽要求较高的系统。1 9 8 2 年u n g e r b o e c k 提出的网格编码调制( t c m ) 的概念，解决了带宽和纠错这一对矛盾。编码领域在9 0 年代初进入了一个崭新的阶段。1 9 9 3 年，t u r b o 码【5 j 作为一种新型信道编码方案被提出。t u r b o 很好地利用了仙农定理中随机编码的思想，并且使用软输入软输出( s i s o ) 的迭代译码技术，从而得到了几乎接近s h a n n o n 理论极限的译码性能。t u r b o 码的提出更新了编码理论研究中一些观念和方法。t u r b o 码的出现不仅提供了一个性能优异的编码方法，同时t u r b o 码迭代译码【6 】的思想也为众多通信系统提供了一种解决问题的方案。迭代译码思想在通信中的应用的研究也在不断的深入。最初t u r b o 码的编码是利用两个卷积编码器作为分量编码器，外加一个交织器构成。在研究前人工作的基础上，人们发现了被遗漏的重大成果，即一种能利用随机编码的思想以及实现迭代译码【7 9 】的线性分组码，这就是目前编码领域中新的研究热点低密度奇偶校验码( l o wd e n s i t yp a r i t yc h e c kc o d e ) ，简称l d p c 码【l o 】。目前l d p c 码以其优异的性能和较低的译码复杂度，获得了人们的重视。l d p c 码已经成为第四代移动通信技术中的关键技术之一，并有相关的提案被提交。l d p c 码已经成为了通信系统纠错编码中的有力竞争者。1 3 本课题的主要研究内容本文主要研究了线性分组码的各种最大似然译码算法，内容包括通用最小码距译码i 绪论硕士学位论文算法、c h a s e 译码算法、w e d 、p f s 、r l s d 、o s d 、b m a 等译码算法。主要研究内容如下：1 、充分研究了分组码的各种最大似然译码算法，比较详细地分析了其译码原理及纠错能力。2 、研究了l d p c 码及其置信传播译码算法；3 、为了充分利用接收比特的可信度信息，将c h a s e 算法与o s d 算法进行并联译码，形成了一种改进的并行算法c h a s e - o s d 算法。对中短码长的l d p c 码，以b p 算法为前级处理，c h a s e o s d 算法作为后级处理，取得了较好的译码性能；我们也使用了这种并行算法对r m 码进行了仿真验证，4 、重点分析了w e d 算法，并把w e d 算法与b p 算法进行级联，形成一种级联算法对l d p c 码进行译码；1 4 论文结构安排本文的章节做如下安排：第一章为绪论，简要介绍了纠错码的发展与现状、r s 码的发展和主要工作。第二章给出了信道编码的基本理论、线性分组码的概念以及传统的译码算法。第三章介绍了线性分组码的各种最大似然译码算法。第四章介绍了l d p c 码的发展、二分图表示，及其比特翻转算法和置信传播算法( b p ) 。第五章在分析c h a s e 算法、o s d 算法基础上，充分利用c h a s e 算法与o s d 算法的互补性，设计了一种并联互补译码算法，并使用这种互补算法对l d p c 码和r m 进行了仿真。考虑w e d 算法及其硬件实现的的简洁性，使用w e d 算法与b p 算法进行级联，形成一种级联译码算法，对l d p c 码进行译码。第六章对全文工作进行了总结，并对下一步工作进行了展望。4硕f j 学位论文线性分组码的最大似然译码研究2 信道编码概述2 1 数字通信系统的基本组成数字通信系统的基本组成如图2 1 所示 1 1 1 12 1 。! ! 墨卜一叫竺兰竺卜叫! 兰兰竺兰等效信道：离散输入，离影模拟输出盛)h信源译码器h信道译码器一图2 1 数字通信系统基本原理框图通信的过程如下：信源发出载有信息的消息，可以是模拟信号( 如视频信号或音频信号) ；又可以是数字信号，如电传机输出的信号在时间上是离散的，且具有有限个输出字符。信源编码器将信源产生的消息变换成二进制数字序列，理论上应当用尽可能少的二进制数字表示信源输出，也就是说，要寻找一种信源输出的有效表示方法，把其中的冗余全部或绝大部分消除。由信源编码器输出的二进制数字序列，我们称之为信息序列。将模拟或数字信源的输出有效地变换成二进制数字序列的处理过程称为信源编码或数据压缩。信道中存在的各种干扰和噪声是造成数字通信系统出现接收误码的主要原因。与信源编码器的减少冗余相反，信道编码器则是对离散信息序列适当地添加冗余( 或相关性) ，使译码器具有自动检查并纠正的能力，以降低信息传输的误码率。信道编码的目的是在信道带宽、译码算法复杂度和信号功率等因素的制约下尽可能地提高数据传输的可靠性，降低误率。因为信道编码器输出的数字信号一般不适合直接在信道中传送，这就需要调制器将该信号转化为模拟信号，并在信道中进行传输。调制器产生有一定时间宽度的，适合于信道传输的时间信号，这些信号组成信道符号集，信道编码器的输出被转换成该集合中相应的信号波形，然后传输。在接收端，解调器通常输出模拟或数字信号，作为对受损信号的估计，随后译码器依据特定的编码准则、信道特征来估计发送端送过来的信息。译码可以分为两种，分别为硬判决译码和软判决译码。如果将解调器输出量化成两个电平( 硬判决解调) ，相应的译码过程为硬判决译码。反之，如果将解调器的输出量化成多电平，则称之为软判决解调。与软判决解调对应的译码过程称为软判决译码。由于硬判决解调会丢失很多有用的信道信息，所以软判决译码性能要优于硬判决译码性能。52 信道编码硕士学位论文同样，信源译码器根据信道解调器的输出和码字编码的代数结构共同估计发射端所送过来的信号。2 2 差错控制系统与纠错码分类数字通信系统中有三种基本的差错控制方式n2 l ：( 1 ) 反馈校验法：接收端将收到的符号重新发回到发送端，在接收端与原发送符号相比较。如果发现错误有错误，则发送端再次进行把数据重新发送。这种方法的原理和设备都较简单，但是需要有双向信道，并且因为每一符号都至少需要传送两次，所以传输效率比较低，实际应用价值不大。( 2 ) 检错重发法：接收端如果在收到的符号中发现了错误时，即通知发送端重新发送，直到接收正确为止。发现错误是指在一些接收码元中，发现一个或多个是错误的，但还不知道这些错误的准确位置。很明显，这种差错控制方法也需要具有双向信道。( 3 ) 前向纠错法：这种方法下，接收端需要能在收到的符号序列中发现错误，并且还需要能够纠正这些错误。二进制系统下，如果知道了错误的具体位置，既可纠正。这种纠错方法不需要反向信道，也不存在由于重发而造成的延迟时间，实时性好。但是纠错设备要比检错设备复杂，硬件复杂度较高。信道编码中用到的码类有很多种，如图2 2 表示。2 3 信道容量和信道模型2 2 纠错码的分类s h a n n o n 定理是有扰信道中进行可靠信息传输的基本理论【l 】。s h a n n o n 指出任何一个有扰信道均存在一个确定的信道容量。只要信号的信息传输速率小于信道容量，则一6硕j j 学位论文线性分组码的最大似然译码研究定存在一种编码方式，当码长无穷大，且使用最大似然译码时，其译码错误概率亦一定能趋近于零。2 3 1b s c ( - - 进制对称) 信道如果把图2 1 所示的一个加性噪声信道( 调制器，信道，噪声源和解调器) 等效为一个二进制等效信道。调制器采用二进制波形，解调器使用硬判决，这样就构成了如图2 3 所示的二进制对称信道，这个信道的特点是它的输入值与输出值集合均取自 0 ，1 ) ，并且有一组表示可能输入与可能输出之间关系的条件概率e ( x r 1 ，如果因为噪声和干扰，导致传输的二进制序列发生统计独立的差错，则平均差错概率p 为：p ( y = 1fx = 1 ) = p ( r = 0ix = o ) = 1 一p( 2 1 - 1 )p ( y = 0i r = 1 ) = p ( y = 1x = 0 ) = p( 2 1 2 )这种信道称作二迸制对称信道( a s c ) ，其输入和输出均为对称的二进制。由于每个输出比特仅与对应的一个输入比特有关，所以前后输出码元是无关的，因此该信道是无记忆信道。l - p02 3 2 离散无记忆信道1 - p图2 3二进制对称信道( b s c ) 的转移概率o离散无记忆二进制对称信道( b s c ) 是广义离散输入、离散输出信道的特例。通常情况下，把多进制输入多进制输出称作离散无记忆信道( d m c ) 。如图2 。3 所示，由信道编码器输出至d m c 的m 进制符号集为x = x o 一，x 材一。 ，d m c 输出q 符号集为y = y 。，j ，l 一，y 纠) 。假设信道的转移概率为p ( y ，lx ，) ，信道输入x 和输出】，的平均互信息定义为【4 1舭；驴芝呈e ( x 腓小，) 1 0 9 等旱( 2 2 )，( x ；】，) = j ) p ( j ，小g 掣( 2 2 )x 和y 之间的平均互信息，( 】，；y ) 定义为：72 信道编码硕十学位论文，i f ；r ) 2 要地f ) l 。g 而i在输入x 已知的情况下，输出y 的条件熵h ( yx ) 定义为：以y | 柳2 荟委p ( 。只) l o g 高因此由( 2 2 ) 式所定义的互信息j ( x ；j ，) 可以表示为：，( 工；y ) = 日( y ) 一h ( y ix )它表示输入x ，x ，而输出y ，y 被观察到( 已知) 后，所减少的熵。，( x ；y ) 也可以表示为输入x ，而输出y 被观察到后所减少的熵：i ( x ；y ) = 日( x ) 一h ( xi 】，)对于一般离散信道，仙农定义信道容量为h 1( 2 3 )( 2 4 )( 2 5 a )容易知道，( 2 5 b )c2 哿黔，( x ；y )( 2 6 )如果对数是以2 为底，信道容量的单位则为比特( b i t s ) 信道符号，即每个符号所包含的最大平均比特数。图2 3 所示的二进制对称信道，其信道容量可1 主t ( 2 6 ) 和( 2 5 a ) 计算，即c _ m m a x ) h ( y ) 一n ( y ix ) ( 2 7 )令p ( x = 0 ) = p o ，则p ( x = 1 ) = 1 一p o 。由式( 2 4 ) 可得熵h ( yx ) 为l1h ( y ix ) = 一p ( x ，j ，) l o g p ( y ，ix )j = oj = o= - p l o g p 一( 1 一p ) l o g ( 1 一p )= h ( p )( 2 8 )因此在已知x 的情况下，条件熵h ( yx ) 与输入x 的先验概率分布p 。无关，所以式( 2 7 ) 的最大值即为h ( i o 的最大值。由于二进制熵函数日( p ) 在p = o 5 达到最大值1 ，因此p ( y = 0 ) = p ( y = 1 ) - - o 5 时，日( 功取得最大值，即p ( y = 0 ) = p o ( 1 一p ) + ( 1 一p o ) p = 1 2( 2 9 )易得，p 。= p ( x = 0 ) = p ( x = 1 ) = 0 5 ，即输入到b s c 的二进制符号为等概分布时，输a x 和输出y 的平均互信息最大，即信道容量为c = l 一日( p ) 。这个信道容量仅与8里l ：学垡笙壅垡丝坌丝塑塑量查型签堡塑竺塑_ _ - ，_ _ _ - _ - _ - - _ - _ - - - _ - - - _ _ - _ - _ - ，- _ _ - _ _ - - ，_ _ _ ， _ - ，_ - _ r - _ 一一一一一转移概率p 有关。类似的通过式( 2 6 ) 和式( 2 5 ) ，可以计算出多进制输入多进制输出离散无记忆信道的信道容量。2 3 3 二进制输入连续输出的a w g n 信道对于很多实际系统，一般都是二进制输入，连续信号输出，即输入x = + 彳，- a 而输出y = ( 一，悯) 。信道噪声为加性白高斯噪声。由连续型信道理论可以证明，在等概二进制输入条件下，输入x 和输出y 的v - 均互信息，( 彳；y ) 达到最大。若x x ，y y ，且加性白高斯噪声( a w g n ) 的均值为零、方差为6 2 ，随机变量y 的概率密度函数为p ( 少) = p ( x = + 彳) p ( yx = + 彳) + 尸( x = 一a ) p ( yx = 一a )= 击 e x p ( 一警卜( 一警肚亿则由式( 2 5 a ) ；g l x - - ( 2 6 ) 可得信道容量为c = 防( y ) 一h 0 lx ) 】l 尸z 。+ _ ) 。段x 一一) l l 2( 2 11 )y 的熵为叫) 2p ) 1 0 9 z 志妒一当渺) l 0 9 2g o 渺( 2 - 2 )y 在义己知下的条件熵为h ( yix ) = 一专ip ( ylx = + a ) l 0 9 2 p ( 少lx = + 彳) 砂一去i p ( yx = - a ) l 0 9 2p ( yx = 一彳) 咖扎g ：击+ 器 警h 一嘲咖引鸭z 丽+ 商丑一气广j 眈p l 一气厂尸+ 器互一警h 嗍砂扣彤胍2 心，由式( 2 1 2 ) 和( 2 1 3 ) 可得到二进制输入连续输出a w g n 条件下的信道容量为c = 一k ( y ) l 0 9 2 弓a ( y ) d y 一去l 0 9 2 ( 2 7 c p g 2 )( 2 1 4 )92 信道编码硕： ：学位论文2 3 4 带限加性白高斯噪声信道带限a w g n 信道的信道容量为hc = l i r a m a x 二，( x ；y )( 2 1 5 )t - a op ( x ) t、。、假设输入信号为x ( f ) ，输出信号为y ( r ) ，单边功率谱密度为n o 的a w g n 为刀( n 。假设接收机带宽与发射信号带宽相同，都为b ，接收机在时间间隔t 内用速率为2 b 的采样速率对接收信号行采样，得到一组n = 2 b t 个独3 一l 分散值的采样序列y = j ，y z ，y 川，与此对应的发射信号z ( ，) 的离散样值为x 2 _ ，x ：，x ) 且满足y ，= x ，+ 纪，n i 为a w g n 采样值( ，= 1 ，2 ，) 。发送信号x | v 和接收信号k 的平均互信息为：删淌) = 善n 业+ a c - i a 。( 小) l o g 础( 2 1 6 )经过相关接收后，a w g n 的噪声功率为0 2 ，故条件概率密度函数为p = 击e x p 一嘲可以证明1 3 】，当 t 为零均值、方差为g ：的独立高斯序列时，即m 一 ，一n1 ) p ( x蜘( 一割q 1 8 )p ( ，x ) = in ie x p i - 告i i( 2 时( 2 1 6 ) 所示的平均互信息i ( x ；y ) 达到最大，将( 2 1 7 ) 矛- 1 ( 2 1 8 ) 代入( 2 1 6 ) 可得黼删淌) = b t l o g ( h 彘)( 2 1 9 )其中s 。是发射信号x ( f ) 的平均功率，因此带限a w g n 信道的信道容量为c 一胁g ( “剖亿2 。，传输系统的谱效率为输入编码器的比特速率与传输信号所占用的信道带宽之比，即1 1 = b ( 比特秒，h z ) 。由于s 。，与该比特序列的功率是相同的，故有曼：l i m 盟= 1 i m ”墨( 2 2 1 )b n or n - - cb n o唯f n o、。其中e 。为单位比特能量。在带限a w o n 信道中，若 c 条件下，无论采用何种编码方式均无法实现无差错传输。jc r c 的单位为比特秒时，( 2 2 0 ) 式又可以表达为一c l i m c 崦：h 针o s ：m 矧亿2 2 ，1 0硕士学位论文线性分组码的最人似然译码研究对于一个给定的c b ，能实现无差错传输的最小e 2 c 拍一1nqc | b如果带宽b _ 0 0 ，则c b 一0( 或q 寸0 ) 。此时有0 再 b = ( c l i 占r a ) 剐2 t c i n b - 1 = l n2 - 1 5 9 ( 锄)nq 蚀、瑚cib、j2 4 随机编码理论( 2 2 3 )( 2 2 4 )纠错编码是提高信息传输可靠性的一种技术手段，为使一种码字具有检错或纠错的能力，必须对原码字增加比较多的冗余，以扩大码字之间的差别。码字到达接收端后，根据是否满足编码规则来判断有无错误。当不能满足时，则按一定规则确定错误所在位置并进行纠正。这个过程即为译码。我们主要介绍分组码【1 2 】 1 3 】。s h a n n o n 信道编码定理1 4 j ：对于一个给定的有扰信道，若信道容量为c ，只要发送端以低于c 的速率r 发送信息( r 为编码器的输入二进制码元速率) ，则一定存在一种编码方法，使编码错误率p 随着码长挖的增加，按指数下降到任意小的值，即p e 一帕月( 2 2 5 )这里e ( r ) 称为误差指数，它与尺、c 的关系如图2 4 所示。图中，c 1 、c ：为信道容量。0图2 4e ( 尺) 与尺的关系这条定理告诉我们，( 1 ) 在码长和信息速率一定的情况下，为减小误码率，可以增大信道容量。由图2 4 知，e ( g ) 随信道容量的增加而增大。由式( 2 2 5 ) 可知，错误概率随e ( 尺) 而指数下降；( 2 ) 在信道容量及发送信息速率一定的条件下，增加码长可使错误概率指数下降。但是设备复杂性和译码延时也随之增加。1 l! 笪堕堕里堡主兰堡垒壅s h a n n o n 编码定理是一个存在性的表述定理，它只告诉我们存在满足式( 2 2 5 ) 、且信息传输率无限接近信道容量的好码，但并没有说明如何构造这些好码，但为寻找这样的好码指明了方向。2 5 线性分组码简述分组码的基本思想是：以k 个信息码元为一组，对每组的k 个信息，通过一定的代数结构产生乃个校验码元，输出一个长为n = k + 的码字。长度为门的二进制分组码中，有2 ”种可能的码字，从这2 ”种码字中，可以选择m = 2 个码字( k 刀) 组成一种码。这样，一个k 比特信息分组，可以映射到长度为甩的一个码字。该码字是从由2 个码字构成的码集中选出来的。这样得到的分组码称为( ，z ，k ) 码，定义r = k n 为编码效率( 码率) 。二进制线性分组码( ”，k ) 的校验矩阵可表示成h =啊加lh 2 。 一l吃 川h l 。oh 2 o吨。因而，码字c = c 1c 2 ，c 川