第4章信道编码技术.ppt

《第4章信道编码技术.ppt》由会员分享，可在线阅读，更多相关《第4章信道编码技术.ppt（83页珍藏版）》请在课桌文档上搜索。

1、第4章 信道编码技术,4.1 离散信道模型4.2 差错控制编码的基本概念4.3 分组码4.4 卷积码,4.1 离散信道模型,4.1.1 离散无记忆信道通常通信系统可以分为发信机、物理信道或传输介质、接收机三大部分,如图4-1所示。发信机由信道编码器和调制器组成,接收机由解调器和信道译码器组成,在图4-1中,c和g之间是编码信道,属于离散信道；d和f之间是调制信道,属于模拟信道。对于加性噪声信道,噪声和干扰会使传输的数据发生错误,因而对数据传输的可靠性产生影响。,图4-1 通信系统模型,对于输入和输出均为离散符号的离散信道,当信道中不存在干扰时,离散输入符号X与输出符号Y有一一对应的关系。但若信

2、道中存在干扰,则输入符号与输出符号之间就不存在一一对应的关系了,而是具有一定的统计相关性。这个统计特性取决于输入符号xi和输出符号yj之间的转移概率P(yj/xi)或P(xj/yi)。假设发送的符号集为X=xi，i=1,2,L,有L种符号；接收符号集为Y=yj，j=1,2,M,有M种符号。这时离散无记忆信道(DMC,Discrete Memoryless Channel)如图4-2所示。DMC的转移概率可以用以下矩阵表示：,图4-2 离散L输入m输出信道,(4-1),所谓无记忆信道,是指每个输出符号值取决于当前的输入符号,而与其他输入符号无关。若DMC的输入选自X符号集的n个符号u1,u2,u

3、n的序列,相应的输出选自Y符号集的n个符号v1,v2,vn的序列,则联合条件概率为P(Y1=v1,Y2=v2,Yn=vn/X1=u1,X2=u2,Xn=un)=,(4-2),这个表达式正是无记忆条件的数学表述。上述DMC的一个特例就是所谓的无记忆二进制对称信道(BSC,Binary Symmetric Channel),其结构如图4-3所示。对于BSC可能的符号输入值的集合X=0,1,可能的符号输出值的集合Y=0,1,对应的转移概率可以表示为这里，P(1/0)=P(0/1)=p，P(1/1)=P(0/0)=1-p。,(4-3),图4-3 二进制对称信道,4.1.4 信道容量设离散信道模型如图4

4、-2所示，发送符号xi的概率为P(xi)，这里i=1，2，L；接收符号yj的概率为P(yj)，这里j=1，2，M；P(yj/xi)或P(xj/yj)表示转移概率。在DMC信道中，输入与输出不再是一一对应关系，而是一种随机对应的统计关系，这种统计关系可以用信道上的转移概率进行描述，因此，我们可以利用信道的转移概率来合理地描述信道受到的干扰和信道的统计特性。,信道容量定义为：,(b/s),以上为著名的香农(Shannon)定理表达式，它表明当信号和作用在信道上的起伏噪声的平均功率给定时，在一定频带宽度B的信道上，理论上单位时间内可能传输信息量的极限值。这样我们可以看出，信道受B、n0和S三要素的影

5、响，只要这三要素确定，信道也随之确定。,从式(4-24)可以容易地看到，当n0=0或S=时，信道容量C=。这是因为n0=0意味着信道无噪声，而S=意味着发送功率达到无穷大，显然这在任何实际系统中都是很难实现的。不过，这个关系也告诉我们：若要使信道容量增大，理论上可以通过减小n0或增大S来实现。,那么，增大带宽B是否可行?下面就此问题进行分析。首先将式(4-24)改写为当B时，上式变为,(4-25),(4-26),式(4-26)中的近似利用了关系式：。通过上述论述表明：保持S/n0一定，即使信道带宽B，信道容量也是有限的，这是因为信道带宽B时，噪声功率B n0也趋于无穷大。通常，把实现了上述极限

6、信息速率的通信系统称为理想通信系统。但是香农定理只证明了理想系统的“存在性”，却没有指出这种通信系统的实现方法。因此，理想系统只能作为实际系统的理论极限。另外，上述讨论都是在信道噪声为高斯白噪声前提下进行的，对于其他类型的的噪声，香农公式需要改进。,4.2 差错控制编码的基本概念,4.2.1 差错控制方式常用的差错控制方式主要有三种：前向纠错（简称FEC）、检错重发（简称ARQ）和混合纠错（简称HEC），它们的结构如图4-4所示。图中带阴影的方框图表示在该端检测错误。,图4-4 差错控制方式(a)前向纠错（FEC）；(b)检错重发（ARQ）；(c)混合纠错（HEC）,前向纠错系统中，发送端经信

7、道编码后可以发出具有纠错能力的码组；接收端译码后不仅可以发现错误码，而且可以判断错误码的位置并予以自动纠正。因此，前向纠错编码需要附加较多的冗余码元，影响数据传输效率，同时其编译码设备比较复杂。但是由于不需要反馈信道，实时性较好，因此这种技术在单工信道中普遍采用，例如无线电寻呼中采用的POGSAG编码。,检错重发方式中，发送端经信道编码后可以发出具有检错能力的码组；接收端收到后经检测如果发现传输中有错误，则通过反馈信道把这一判断结果反馈给发送端。然后，发送端把前面发出的信息重新传送一次，直到接收端认为已经正确为止。典型系统原理方框图如图4-5所示。常用的检错重发系统有三种，即停发等候重发、返回

8、重发和选择重发。,图4-5 ARQ系统组成方框图,停发等候重发系统的发送端在某一时刻向接收端发送一个码组，接收端收到后经检测若未发现传输错误，则发送一个认可信号(ACK)给发送端，发送端收到ACK信号后再发下一个码组；如果接收端检测出错误，则发送一个否认信号(NAK)，发送端收到NAK信号后重发前一个码组，并再次等待ACK和NAK信号。这种方式效率不高，但工作方式简单，在计算机数据通信中仍在使用。在返回重发系统中，发送端无停顿地送出一个又一个码组，不再等待ACK信号，一旦接收端发现错误并发回NAK信号，则发送端从下一个码组开始重发前一段N组信号，N的大小取决于信号传递及处理所带来的延迟，这种系

9、统比停发等候重发系统有很大的改进，在许多数据传输系统中得到应用。,在选择重发系统中，发送端也是连续不断地发送码组，接收端发现错误发回NAK信号。与返回重发系统不同的是，发送端不是重发前面的所有码组，而是只重发有错误的那一组。显然，这种选择重发系统传输效率最高，但控制最为复杂。此外，返回重发系统和选择重发系统都需要全双工的链路，而停发等候重发系统只需要半双工的链路。,由上述分析可知，ARQ的优点主要表现在：（1）只需要少量的冗余码，就可以得到极低的输出误码率；（2）使用的检错码基本上与信道的统计特性无关，有一定的自适应能力；（3）与FEC相比，信道编译码器的复杂性要低得多。同时ARQ也存在某些不

10、足，主要表现在：（1）需要反向信道，故不能用于单向传输系统，并且实现重发控制比较复杂；（2）当信道干扰增大时，整个系统有可能处在重发循环当中，因而通信效率低；（3）不大适合于严格实时传输系统。,混合纠错方式是前向纠错方式和检错重发方式的结合。在这种系统中接收端不但具有纠正错误的能力，而且对超出纠错能力的错误有检测能力。遇到后一种情况时，系统可以通过反馈信道要求发送端重发一遍。混和纠错方式在实时性和译码复杂性方面是前向纠错和检错重发方式的折衷。,4.2.2 差错控制编码分类在差错控制系统中，信道编码存在着多种形式，同时信道编码也有多种分类方法。（1）按照信道编码的不同功能，可以将它分为检错码和纠

11、错码。检错码仅能检测误码，例如，在计算机串口通信中常用到的奇偶校验码等；纠错码可以纠正误码，当然同时具有检错的能力，当发现不可纠正的错误时可以发出出错指示。（2）按照信息码元和监督码元之间的检验关系，可以将它分为线性和非线性码。若信息码元与监督码元之间的关系为线性关系，即满足一组线性方程式，则称为线性码；否则，就称为非线性码。,（3）按照信息码元和监督码元之间的约束方式不同，可以将它分为分组码和卷积码。在分组码中，编码后的码元序列每n位分为一组，其中k位信息码元，r个监督位，r=n-k。监督码元仅与本码组的信息码元有关。卷积码则不同，虽然编码后序列也可以分为码组，但监督码元不但与本信息码元有关

12、，而且与前面码组的信息码元也有约束关系。（4）按照信息码元在编码后是否保持原来的形式，可以将它分为系统码和非系统码。在系统码中，编码后的信息码元保持原样不变，而非系统码中的信息码元则发生了变化。除了个别情况，系统码的性能大体上与非系统码相同，同时非系统码的译码较为复杂，因此，系统码得到了广泛的应用。,（5）按照纠正错误的类型不同，可以将它分为纠正随机错误码和纠正突发错误码。前者主要用于发生零星独立错误的信道，而后者用于对付以突发错误为主的信道。（6）按照信道编码所采用的数学方法不同，可以将它分为代数码、几何码和算术码。其中代数码是目前发展最为完善的编码，线性码就是代数码的一个重要的分支。除上述

13、信道编码的分类方法以外，我们还可以将它分为二进制信道编码和多进制信道编码等等。同时，随着数字通信系统的发展，可以将信道编码器和调制器统一起来综合设计，这就是所谓的网格编码调制(TCM，Trellis Coded Modulation)。,4.2.3 检错与纠错的基本原理信道编码的基本思想就是在被传送的信息中附加一些监督码元，在两者之间建立某种校验关系，当这种校验关系因传输错误而受到破坏时，可以被发现，甚至将错误予以纠正，这种检错与纠错能力是用信息量的冗余度来换取的。下面我们将介绍几个与信道编码有关的基本概念。码长：码组中码元的数目；码重：码组中非0位的数目。对于二进制码来讲，码重W就是码元中1

14、的数目，例如码组10100的码长n=5，码重W=2。码距：两个等长码组之间对应位不同的数目，有时也称做这两个码组的汉明距离，例如码组10100与11000它们之间的码距d=2。,最小码距：在码组集合中全体码组之间距离的最小数值。对于二进制码组而言，两个码组之间的模2相加，其不同的对应位必为1，相同的对应位必为0，因此，两个码组之间模2相加得到的信码组的重量就是这两个码组之间的距离。码组之间的最小距离是衡量该码组检错和纠错能力的重要依据，因此，最小码距是信道编码的一个重要的参数。在一般情况下，对于分组码的最小汉明距离d0与检错和纠错能力之间满足下列关系：（1）当码组用于检测错误时，如果要检测e个

15、错误，那么d0e+1(4-27),这个关系可以利用图4-6(a)予以说明。在图中用A和B分别表示两个码距为d0的码组，若A发生e个错误，则A就变成以A为球心，e为半径的球面上的码组，为了能将这些码组分辨出来，它们必须距离其最近的码组B有一位的差别，即A和B之间最小距离为d0e+1。(2)当码组用于纠正错误时,如果要纠正t个错误,那么d02t+1(4-28)这个关系可以利用图4-6(b)予以说明。在图中用A和B分别表示两个码距为d0的码组,若A发生t个错误,则A就变成以A为球心,t为半径的球面上的码组；若B发生t个错误,则B就变成以B为球心,t为半径的球面上的码组。为了在出现t个错误之后,仍能够

16、分辨出A和B来,那么,A和B之间距离应大于2t,最小距离也应当使两球体表面相距为1,即满足不等式(4-28)。,（3）如果码组用于纠t个错,同时检e个错时,那么d0t+e+1(4-29)这个关系可以利用图4-6(c)予以说明。在图中用A和B分别表示两个码距为d0的码组,当码组出现t个或小于t个错误时,系统按照纠错方式工作；当码组出现大于t个而小于e个错误时,系统按照检错方式工作；若A发生t个错误,B发生e个错误时,既要纠A的错误,又要检B的错误,则A和B之间距离应大于t+e,也就是满足式(4-29)。,图4-6 纠（检）错能力的几何解释,通常,在信道编码过程中,监督位越多纠错能力就越强,但编码

17、效率就越低。若码组中信息位数为k,监督位数为r,码长n=k+r,则编码效率Rc可以用下式表示：Rc=k/n=(n-r)/n=1-r/n(4-30)信道编码的任务就是要根据不同的干扰特性,设计出编码效率高,纠错能力强的编码。在实际设计过程中,需要根据具体指标要求,尽量简化编码实际的复杂度,节省设计费用。,4.3 分组码,4.3.1 线性分组码当分组码的信息码元与监督码元之间的关系为线性关系时,这种分组码就被称为线性分组码。线性分组码是建立在代数群论基础之上的,各许用码的集合构成了代数学中的群,它们的主要性质如下：(1)任意两许用码之和（对于二进制码这个和的含义是模2和）仍为一许用码,也就是说,线

18、性分组码具有封闭性；(2)码组间的最小码距等于非零码的最小码重。,下面通过一个例子说明线性分组码是如何构造的。设分组码(n,k)中k=4,为了能够纠正一位错误,要求r3,取r=3,则n=k+r=7。因此,可以用a6a5a4a3a2a1a0表示这7个码元,用S1、S2、S3表示由三个监督方程计算得到的校正子,并假设S1、S2、S3三位校正子码组与误码位置的关系如表4-1所示。,表4-1 校正子与误码位置,根据表4-1的对应关系,可以得到下列逻辑关系式：S1=a6+a5+a4+a2S2=a6+a5+a3+a1(4-31)S3=a6+a4+a3+a0在进行编码时,设a6、a5、a4、a3为信息码元,

19、从表4-1中可以看到,当S3S2S1=000时,就表明码组在传输过程中没有发生错误,基于这一约束,利用式(4-31),可以得到下面两种形式的线性方程组：a6+a5+a4+a2=0 a6+a5+a3+a1=0 a6+a4+a3+a0=0,(4-32),a6+a5+a4=a2 a6+a5+a3=a1(4-33)a6+a4+a3=a0根据上面两个线性关系式,可以得到16个许用码组,如表4-2所示。,表4-2 许 用 码 组,在接收端收到码组以后,就可以代入式(4-31)计算S1、S2和S3,如果全为0,则表明传输时没有发生错误,否则根据表4-1纠正错误。当然对于上述(7,4)码而言,最小码距d0=3

20、,因此,它可以纠正一个错误或检测两个错误,如果超出这个范围,纠错功能就要失败。对于式(4-32),可以用矩阵形式表示如下：,(4-34),上式可以记作：HAT=0T或AHT=0,其中,A=a6 a5 a4 a3 a2 a1 a0(4-35b)0=0 0 0(4-35c),(4-35a),或者a2 a1 a0=a6 a5 a4 a3=a6 a5 a4 a3Q比较式(4-34)和式(4-36)可以看到Q=PT,如果在Q矩阵的左边再加上一个kk的单位矩阵,就形成了一个新矩阵G：,(4-37),这里G被称为生成矩阵,利用它可以产生整个码组:A=MG=a6 a5a4 a3G(4-38)由式(4-37)表

21、示的生成矩阵形式被称为典型生成矩阵,利用式(4-38)产生的分组码必为系统码,也就是信息码元保持不变,监督码元附加在其后。在发送端,信息码元M利用式(4-38)实现信道编码,产生线性分组码A；在传输过程中有可能出现误码,设接收到的码组为B,则收发码组之差为 B-A=bn-1bn-2 b0-an-1 an-2 a0=E=en-1 en-2 e0(4-39),这里 0 bi=ai 1 biai,ei=1表示i位有错,ei=0表示i位无错。基于这样的原则,接收端利用接收到的码组B计算校正子：S=BHT=(A+E)HT=AHT+EHT=EHT(4-40)因此,校正子仅与E有关,即错误图样与校正子之间有

22、确定的关系。,在实践中经常会遇到的线性分组码主要有以下两种：1.汉明(Hamming)码汉明码既有二进制的,也有非二进制的,这里仅讨论二进制汉明码的性质。二进制汉明码可以表示为(n,k)=(2m-1,2m-1-m)(4-41)这里m可取大于等于2的任意整数,因此,汉明码的特点如下：码长n=2m-1,信息位k=2m-1-m，监督位r=m,最小码距d0=3,纠错能力t=1。如果要产生一个系统汉明码,那么可以将矩阵H转换成典型形式的监督矩阵,进一步利用Q=PT的关系,得到相应的生成矩阵G。,2.哈达码(Hadamard)码哈达码矩阵Mn是一个由“0”和“1”构成的nn维矩阵（n是偶数）,矩阵中任意两

23、行相比较,都存在n/2个不同的元素,矩阵中有一行是全0行,其他行都包含n/2个“0”和n/2个“1”。当n=2时,哈达码矩阵可表示为 M2=(4-42)进一步可以按照下述规律由Mn产生哈达码矩阵M2n。,(4-43)式中,Mn为Mn的互补矩阵,按上述规律M4和 就可以分别表示为,(4-44),至此,可以利用M4和 的行构成一个码长n=4的二进制线性分组码,该码由8个码组构成,最小码距为d0=2。基于这种方法构成的码称为哈达码。因此,哈达码的长度n=2m,k=lb2n=lb2m+1=m+1,d0=n/2=2m-1,这里m为正整数。4.3.2 循环码 循环码是线性码的一个重要子集,是目前研究得最成

24、熟的一类码。它有许多特殊的代数性质,这些性质有助于按所要求的纠错能力系统地构造这类码,且易于实现；同时循环码的性能也较好,具有较强的检错和纠错能力。,循环码最大的特点就是循环性,所谓循环性,是指循环码中任一许用码组经过循环移位后,所得到的码组仍然是许用码组。若(an-1 an-2 a1 a0)为一循环码组,则(an-2an-3 a0 an-1)、(an-3an-4 an-1an-2)还是许用码组。也就是说,不论是左移或是右移,也不论移多少位,其所得的码组仍然是许用的循环码组。为了利用代数理论研究循环码,可以将码组用代数多项式来表示,这个多项式被称为码多项式,对于许用循环码A=(an-1an-2

25、 a1 a0),可以将它的码多项式表示为A(x)=an-1xn-1+an-2xn-2+a1x+a0(4-45),对于二进制码组,多项式的每个系数不是0就是1,x仅是码元位置的标志,因此,我们这里并不关心x的取值设上述循环许用码组A左循环一位得到的码组记作 A（1）=(an-2an-3 a0 an-1),其码多项式可以表示为 A(1)(x)=an-2xn-1+an-3xn-2+a0 x+an-1(4-46)同理,左移i位的码组A（i）=(an-i-1 an-i-2 an-i+1 an-i),其码多项式为 A(i)(x)=an-i-1xn-1+an-i-2xn-2+an-i+1x+an-i(4-4

26、7),利用代数理论知识,A（i）(x)也可以用下式求得：xiA(x)=Q(x)(xn+1)+A（i）(x)(4-48)这里,Q(x)表示xiA(x)除以(xn+1)的商,而A（i）(x)表示所得余式。由上述分析可以得到结论：一个长为n的循环码,它必为按模(xn+1)运算的一个余式。这个结论给出了构造许用码的一种方法,即利用循环码的生成多项式可以得到全部码组。在循环码中,一个(n,k)码有2k个不同的码组,若用g(x)表示其中前(k-1)位皆为“0”的码组,则g(x)、xg(x)、x2g(x)、xk-1g(x)都是码组,而且这k个码组线性无关,因此,可以利用它们构成循环码的生成矩阵,而g(x)被

27、称为生成多项式。,可以证明,一个(n,k)循环码的生成多项式g(x),必须是一个常数项不为“0”的(n-k)次多项式,而且,这个g(x)还是(n,k)码中次数为(n-k)的惟一的一个多项式。因为如果有两个,则由于码的封闭性,把这两个码相加也应该是一个码组,且此码组多项式的次数将小于(n-k),即出现连续“0”的个数将多于(k-1)的情况,这与(n,k)循环码是线性码的特性相违背,故是不可能的。为此,可以得到一个重要的结论：一旦生成多项式g(x)确定以后,整个(n,k)循环码就被确定了。基于g(x),可以进一步写出循环码的生成矩阵如下：,显然,上式不符合G=Ik Q形式,所以此生成矩阵不是典型形

28、式,不过,可以通过简单的代数变换将它变成典型矩阵。,(4-49),根据g(x)定义可知,它是(n,k)循环码中惟一的一个(n-k)次码多项式,当然也就是该循环码的许用码组。对g(x)表述的许用码组进行k次左移,会得到同样的码组,将这一过程用式(4-48)描述将得到xkg(x)=Q(x)(xn+1)+g(x)(4-50)上式左边是一个n次多项式,因此,Q(x)=1,所以可以进一步表示为(xn+1)=xkg(x)+g(x)=g(x)(xk+1)(4-51)式(4-51)表明,生成多项式g(x)是(xn+1)的一个因式,因此,为了确定生成多项式,必须首先对(xn+1)进行因式分解,然后再用计算进行筛

29、选,计算过程通常使用计算机来完成。,对于一个(n,k)循环码,其生成多项式应该是(xn+1)的一个(n-k)次因子,任何(n,k)循环码的生成多项式g(x),乘上(x+1)后得到生成多项式,可以构造(n,k-1)循环码。以(x7+1)因式分解为例：x7+1=(x+1)(x3+x+1)(x3+x2+1)(4-52)由式(4-52)可构成如表4-3所示的(7,k)循环码。,表4-3(x7+1)因式分解构成的(7,k)循环码,由表4-3可看出不管是(7,4)循环码还是(7,3)循环码,均包含两个不同的生成多项式,因此,依据不同的生成多项式将产生不同的循环码组。上面我们讨论了循环码的基本原理,下面就系

30、统循环码的产生进行分析。,根据循环码的编码特点,所有循环码多项式A(x)都可以被g(x)整除。根据这一原理可以得到一个较简单的系统循环码编码方法：设要产生(n,k)循环码,m(x)表示信息多项式,则其次数必小于k,而xn-km(x)的次数必小于n,用xn-km(x)除以g(x),可得余数r(x),r(x)的次数必小于(n-k),将r(x)加到信息位后作监督位,就得到了系统循环码,其数学描述如下：(4-53)则系统循环码可以表示为 A(x)=xn-km(x)+r(x)(4-54),上述编码过程,在硬件实现时,可以利用除法电路来实现,这里的除法电路采用一些移位寄存器和模2加法器来构成,下面我们将以

31、(7,3)循环码为例来说明其具体实现过程。设该(7,3)循环码的生成多项式为g(x)=x4+x2+x+1,则构成的系统循环码编码器如图4-7所示,图中有4个移位寄存器,一个双刀双掷开关。当信息位输入时,开关位置接“1”,输入的信息码一方面送到除法器进行运算,一方面直接输出；当信息位全部输出后,开关位置接“2”,这时输出端接到移位寄存器的输出,除法的余项,也就是监督位依次输出。当信息码为110时,编码器的工作过程如表4-4所示。,图4-7(7,3)循环码编码器,表4-4 编码器的工作过程,对于接收端译码的要求通常有两个：检错与纠错。达到检错目的的译码十分简单,可以依据式(4-54),通过判断接收

32、到的码组多项式B(x)是否能被生成多项式g(x)整除来完成。当传输中未发生错误时,接收的码组与发送的码组相同,即A(x)=B(x),接收的码组B(x)必能被g(x)整除；若传输中发生了错误,则A(x)B(x),B(x)不能被g(x)整除。因此,我们就可以根据余项是否为零来判断码组中有无错码。需要指出的是,有错码的接收码组也有可能被g(x)整除,这时的错码就不能检出了。这种错误被称为不可检错误,不可检错误的错码数必将超过这种编码的检错能力。,在接收端为纠错而采用的译码方法自然比检错要复杂许多,因此,对纠错码的研究大都集中在译码算法上。我们知道,校正子与错误图样之间存在某种对应关系。如同其他线性分

33、组码,循环码的译码可以分三步进行：（1）由接收到的码多项式B(x)计算校正子(伴随式)多项式S(x)；（2）由校正子多项式S(x)确定错误图样E(x)；（3）将错误图样E(x)与B(x)相加,纠正错误。上述第（1）步运算和检错译码类似,也就是求解B(x)整除g(x)的余式,第（3）步也很简单。因此,纠错码译码器的复杂性主要取决于译码过程的第（2）步。,4.3.3 BCH码BCH码是循环码中的一个重要子类,它是以三个研究和发明这种码的人名Bose、Chaudhuri和Hocguenghem命名的。BCH码不仅具有纠正多个随机错误的能力,而且具有严密的代数结构,是目前研究得最为透彻的一类码。它的生

34、成多项式g(x)与最小码距之间有密切的关系,人们可以根据所要求的纠错能力t,很容易地构造出BCH码。BCH码的译码也比较容易实现,是线性分组码中应用最为普遍的一类码。,4.4 卷积码,4.4.1 卷积码的表述方式卷积码编码器的一般形式如图4-9所示,它包括：一个由N段组成的输入移位寄存器,每段有k级,共Nk位寄存器；一组n个模2相加器；一个由n级组成的输出移位寄存器。对应于每段1个比特的输入序列,输出n个比特。由图可知,n个比特编码输出不仅与当前的k个比特信息输入有关,而且与以前的(N-1)k个比特信息输入有关。整个编码过程可以看成是输入信息序列与信道编码器的卷积,卷积码即由此得名。通常把N称

35、为约束长度(注意：约束长度的定义并无统一的标准,在有的书和文献中把nN或(N-1)称为约束长度),因此,卷积码通常可以表示为(n,k,N),它的编码效率为Rck/n。,图4-9 卷积码编码器的一般形式,为了介绍几种简单的卷积码表述方法,我们将以图4-10所示的(2,1,3)卷积码为例进行分析。,图4-10（2,1,3）卷积码编码器,1.树状图在(2,1,3)卷积码编码器当中,输出移位寄存器用转换开关代替,每输入一个位信息,经编码产生两位输出。假设移位寄存器的起始状态为全0,当第一个输入位为0时,输出为00；若输入比特为1,则输出比特为11。随着第二个位的输入,第一位右移一位,此时输出比特同时受

36、当前输入位和前一个输入位的影响。第三位输入时,第一、二位分别右移一位,同时输出两个由这三位移位寄存器存储内容所共同决定的比特。当第四位输入时,第一位移出移位寄存器而消失。移位过程可能产生的各种序列可以用图4-11所示的树状图来表示。树状图从节点a开始画,此时移位寄存器状态(即存储内容)为00。,图4-11（2，1，3）卷积码的树状表示,当第一个输入位m10时,输出位x1,1x2,100；当m11时,输出位x1,1x2,111；因此从a点出发有两条分支(树叉)可以选择,也就是m10时取上面一条分支,m11时取下面一条分支。当输入第二位时,移位寄存器右移一位后,在上分支情况下,移位寄存器的状态仍为

37、00,下分支的状态则为01,把01状态记作b。当新的一位输入时,随着移位寄存器状态和输入位的不同,树状图继续分叉成4条分支,两条向上,两条向下。上分支对应于输入0状态,下分支对应于输入1状态。如此继续下去,即可得到图4-11所示的二叉树图形。树状图中,每条树叉上所标注的码元为输出状态,每个节点上标注的a、b、c、d表示移位寄存器的状态,也就是以前输入的信息,a状态表示mj-2mj-100,b状态表示mj-2mj-101,c状态表示mj-2mj-110,d状态表示mj-2mj-111。显然,对于第j个输入位,就有2j条分支,但是在j=N3时,树状图的节点自上而下开始重复出现这4种状态。,2.网格

38、图从卷积码的树状图中可以看到,树状图的节点自上而下会出现重复特性,为此,我们可以得到一种更为紧凑的图形表示方法,即网格图法,具体情况见图4-12。在网格图中,把码树中具有相同状态的节点合并在一起,码树中的上分支（对应输入0）用实线表示,下分支（对应输入1）用虚线表示。网格图中分支上标注的码元为对应的输出,自上而下4行节点分别表示a、b、c、d四种状态。一般情况下应有2N-1种状态,从第N节开始,网格图图形开始重复而完全相同。,图4-12（2,1,3）卷积码的网络图表示,3.状态图由图4-11可以看到,对于每一个节点当前状态a、b、c、d,根据不同的输入将进入不同的状态,基于这一原理,我们可以构

39、造出当前状态与下一状态之间的状态转换图,也可以称之为卷积码的状态图。在图4-13中实线表示信息位为0的路径,虚线表示信息位为1的路径,并在路径上写出相应的输出码元。当然,如果将状态图在时间上展开,便可以得到前面讲到的网格图。,图4-13（2,1,3）卷积码的状态图,假如利用图4-10所示的卷积码编码器对输入序列110111001000进行编码,我们就可以用上述3种方法当中的任意一种来分析编码器的输出序列和状态变化路径。在这里使用卷积码的网格图表示法进行分析。若起始状态为a,则可以得到图4-14所示的结论。,图4-14（2,1,3）卷积码的编码过程及路径,通过上述分析以及对具体实例的研究,我们可

40、以得到(n,k,N)卷积码的一些基本特性：（1）对于每组k位的输入,利用卷积码编码后将得到n位的输出；（2）树状图中每个节点可引出2k条分支；（3）网格图和状态图都有2k(N-1)种可能的状态,每个状态可以引出2k条分支,同时也有2k条分支从其他状态或本状态引入；（4）在任何情况下,只要卷积码编码器一确定,相应的树状图、网格图和状态图都将确定,与输入的码序列无关。,4.4.2 二进制卷积码的距离特性我们知道,在分组码中码距(Hamming距)与纠错能力有密切关系,生成一种分组码时应使码组之间的距离尽可能大。常以最大的最小码距作为纠错能力的度量。卷积码中也同样存在码距的概念,通常使用的码距有两种

41、：最小码距dmin和自由码距dfree。卷积码中长度为nN(假设约束长度为7)的编码后序列之间的最小汉明距离被称为最小码距dmin,任意长编码后序列之间的最小汉明距离被称为自由码距dfree。由于卷积码并不划分码组,因而以自由码距作为纠错能力的度量更为合适。更加确切地说,采用哪一种码距作为纠错能力的度量标准,与译码算法有关。,但当译码算法仅限于处理长度为nN的接收序列时,最小码距dmin是一个重要的参量,门限译码就是一个例子。当采用维特比译码或序列译码算法,且译码所考察的编码后序列长度大于nN时,自由码距dfree就是一个重要参量。这两种译码算法,特别是维特比译码,是目前使用最为广泛且译码效果

42、最好的卷积码译码算法。计算自由码距的一种解析方法是利用卷积码的生成函数。生成函数可以看成是卷积码编码器的传递函数,它可以利用信号流图方法来计算。,用状态图求生成函数可以得到卷积码的距离特性,特别是自由距。但在给定n,k和N时,无法得到自由距与卷积码生成多项式之间的计算公式,必须逐个计算不同卷积码的生成函数,才能得到具有最大自由距的最好码。随着k和N增大,状态图中的状态数指数增加,因而生成函数的计算变得愈来愈复杂,甚至不可能。因此,卷积码中的好码大都是用计算机搜索得到的。,4.4.3 卷积码的最佳译码维特比译码1.卷积码的最大似然译码利用最大似然序列估计器,使似然函数最大的一个参数作为估计值,鉴

43、于似然函数的性质,我们通常选择似然函数的对数最大,而不是似然函数本身最大,现在我们就根据卷积码编译码系统的特点构造似然函数。汉明距e最小相当于对数似然函数最大。求最大似然函数的对数,就相当于求X和Y之间的汉明距最小。最大似然译码的任务就是在树状图或网格图中选择一条路径,使相应的译码结果和输入码之间欧氏距离或汉明距离最小。,对于长度为L的二进制序列的最佳译码,需要对可能发送的2L个不同的序列的2L条路径似然函数累加值(即路径量度)进行比较,选取其中最大(即最小量度)的一条。显然,译码过程的计算量随L增加而呈指数增长,这在实际中难以实现,因此只能采用次最佳的译码方法。用网格图描述时,由于路径的汇聚

44、消除了树状图中的冗余度,译码过程中只需考虑整个路径集合中那些能使似然函数最大的路径。如果在某一节点上发现某条路径已不可能获得最大对数似然函数,那么就放弃这条路径。然后在剩下的“幸存”路径中重新选择译码路径,这样一直进行到最后第L级。由于这种方法较早地丢弃了那些不可能的路径,从而减轻了译码的工作量,维特比译码正是基于这种想法。,2.维特比译码卷积码的网格图中共有2k(N-1)种状态,每个节点(即每个状态)有2k条分支引入,也有2k条分支引出。为简便起见,我们讨论k1的情形,从全0状态起始点开始讨论。由网格图的前N-1条连续分支构成的路径互不相交,即最初的2(N-1)条路径各不相同,当接收到第N条

45、分支时,每条路径都有两条分支延伸到第N级上,而第N级上的每两条分支又都汇聚在一个节点上。,在维特比译码算法中,把汇聚在每个节点上的两条路径的对数似然函数累加值进行比较,然后把具有较大对数似然函数累加值的路径保存下来,而丢弃另一条路径,经挑选后第N级只留下2(N-1)条幸存路径,选出的路径连同它们的对数似然函数累加值一起被存储起来。由于每个节点引出两条分支,因此以后各级中路径的延伸都增大一倍,但比较它们的似然函数累加值后,丢弃一半,结果留存下来的路径总数保持常数。由此可见,上述译码过程中的基本操作是“加比选”,即每级求出对数似然函数累加值,然后两两比较并作出选择。有时会出现两条路径的对数似然函数累加值相等的情形,在这种情况下可以任意选择其中一条作为“幸存”路径。,