第十章_卷积码

1、第十章,卷积码,1,第十章,卷积码,内容提要,:,差错控制系统中使用的纠错码，除前面已,学过的分组码之外，还广泛使用着卷积码。本,章首先介绍卷积码的基本概念，重点论述卷积,码的定义及其矩阵描述。在此基础上，介绍一,种目前被广泛应用的概率译码算法：维特比（,Viterbi,）译码算法。,2,本章重点：,1.,卷积码的基本概念；,2.,维特比译码算法。,3,10.1,卷积码的基本概念,卷积码是纠错码中的又一大类。由于分组码码字,中的,n,k,个校验元仅与本码字的,k,个信息元有关，与,其它码字无关，因此分组码的编译码是对各个码字,孤立地进行的。从信息论的观点看，这种做法必然,会损失一部份相关信息，

2、而卷积码的出现使人们有,可能利用这部份相关信息。,4,10.1.1,卷积码概述,卷积码在编码不仅与本子码的,k,个信息,元有关，而且还与此前,m,个子码中的信息,元有关，因此卷积码的编码器需要有存储,m,组信息元的记忆部件。,5,图,10.1,给出了一个二进制卷积码的编码器例子。,当输入信息元为,m,j,时，,D,0,、,D,1,中分别存放着此前输,入的,m,j,1,和,m,j,2,，,经运算可得到两个校验元,p,j,，,1,和,p,j,，,2,，即,p,j,，,1,m,j,m,j,1,p,j,，,2,m,j,m,j,2,图,10.1,（,3,，,1,，,2,）卷积码编码器,6,在编码器输出端

3、，由旋转开关实现并串转换显然，,c,j,中,的校验元,p,j,，,1,和,p,j,，,2,不仅与,m,j,有关，同时还与,m,j,1,和,m,j,2,有,关，即与此前,m,2,个子码中的信息元有关。称,m,为,编码存,贮,，表示信息组在编码器中的存贮周期（时钟周期）。,编码器输出的每个子码，,信息位数,k,1,，码长,n,3,，码率,k,n,1,3,，,编码存贮,m,2,，表示为,（,3,，,1,，,2,）卷积码。,信息元,m,j,把,c,j,，,c,j,1,和,c,j,2,三个子码联系在一起，这,三个子码之间存在相关性。,用编码约束度,N,表示子码,之间的约束关系，显然,N,m,1,。,7,

4、综上所述，一个（,n,，,k,，,m,）卷积码具有以下重要参数：,码长,n,，子码的信息元个数,k,，校验元个数,n,k,；,码率,k,n,，表示卷积码传输信息的有效性；,编码存贮,m,，表示信息组在编码器中的存贮周期；,编码约束度,N,，表示子码之间的约束程度。,编码约束长度,N,A,nN,，表示相互约束的码元个数。,8,10.1.2,卷积码的矩阵描述,描述卷积码的方法很多，如矩阵方法、多项式方,法、状态图和网格图方法等。本节仅介绍矩阵方,法。,入的信息序列（,以图,10.1,给出的（,当编码器清零后开始工作时，输出得到的子码如下：,m,3,，,1,，,2,）卷积码编码器为例进行分析。设输,

5、0,，,m,1,，,m,2,，,，,m,i,，,）是一个有头无尾的序列，,c,0,（,（,m,m,0,，,p,0,，,1,，,p,0,，,2,）,其中,其中,p,p,0,，,1,m,0,，,p,0,，,2,m,c,0,1,1,，,p,1,，,1,，,p,1,，,2,）,1,，,1,m,1,m,0,，,p,1,，,2,m,c,1,2,（,m,m,2,，,p,2,，,1,，,，,p,p,2,，,2,）,其中,p,2,，,1,m,2,m,m,1,，,p,2,，,2,m,2,m,c,0,c,3,（,（,m,3,，,p,p,3,，,1,3,，,2,）,其中,p,3,，,1,m,3,2,，,p,3,，,2

6、,m,3,m,1,4,4,，,4,，,1,，,p,4,，,2,）,其中,p,4,，,1,m,4,m,3,，,p,4,，,2,m,4,m,2,9,令输出的码序列,c,m,0,p,0,1,p,0,2,m,1,p,1,1,p,1,2,m,2,p,2,1,p,2,2,m,3,p,3,1,p,3,2,m,4,p,4,1,p,4,2,表示成矩阵形式：,?,?,m,0,?,m,0,?,?,m,0,?,?,?,m,0,?,?,?,c,T,?,?,?,?,m,0,?,?,?,?,?,?,?,?,?,?,?,m,1,?,m,1,m,1,m,1,m,1,m,2,?,m,2,?,m,2,m,2,m,2,?,m,3,?

7、,m,3,?,m,3,m,3,?,?,?,1,?,?,1,?,?,?,?,?,?,1,?,0,?,?,?,1,?,?,?,?,0,?,?,0,?,?,?,?,?,0,?,?,1,?,?,?,?,0,?,?,?,?,0,m,?,?,?,0,4,?,?,0,?,m,4,?,?,?,m,?,?,?,0,4,?,0,?,?,?,?,?,0,0,0,0,0,0,1,0,1,0,1,0,0,1,1,1,0,1,0,0,0,1,1,0,0,0,0,0,0,1,?,?,1,0,1,0,1,0,0,1,1,1,0,1,?,?,?,?,?,?,?,?,?,?,?,?,?,m,0,?,?,?,m,?,?,1,?,m

8、,?,?,?,?,?,2,?,?,?,?,m,3,?,0,?,?,m,4,0,?,?,?,?,?,?,?,?,?,?,0,?,0,?,?,0,?,0,?,?,?,?,?,10,c,?,?,m,0,m,1,m,2,m,3,m,4,?,1,1,1,0,1,0,0,0,1,0,0,0,0,0,0,?,0,0,0,1,1,1,0,1,0,0,0,1,0,0,0,?,?,0,0,0,0,0,0,1,1,1,0,1,0,0,0,1,?,?,?,?,?,1,1,1,0,1,0,?,?,?,?,?,?,?,?,?,?,?,?,0,0,0,1,1,1,?,0,0,0,0,0,0,即,c,mG,?,?,?,?,?

9、,?,G,?,被称作（,3,，,1,，,2,）卷积码的,生成矩阵,：,?,?,111,010,001,000,000,?,?,?,111,010,001,000,?,?,G,?,?,?,111,010,001,?,?,?,?,?,111,010,?,?,?,?,?,111,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,11,仔细观察（,3,，,1,，,2,）卷积码的生成矩阵,G,?,可发现：,（）,G,?,中的每一行都是前一行右移右移,3,位的结果，,可以由矩阵的第一行完全确定。将第一行取出并表为,g,?, 111 010 001 000 000 ,g,?,称作,基本生成

10、矩阵,。,（）基本生成矩阵,g,?,只有前（等于该卷积码的编码约束,度,N,m,1,3,）数字有意义，以后各组数字全部为零。分,别用,g,0,，,g,1,，,g,2,表示各组，即,g,0, 111 ,，,g,1, 010 ,，,g,2, 001 ,，,g,0,，,g,1,，,g,2,称作,生成子矩阵,。,g,?,?,?,g,0,g,1,g,2,0,0,?,?,?,（,3,）现在，,G,?,可表为,?,D,g,?,?,0,g,g,g,?,0,?,?,?,0,1,2,?,?,?,G,?,?,2,?,?,D,g,?,?,?,0,0,g,0,g,1,g,2,?,?,?,?,?,?,?,?,?,?,?,

11、?,?,?,?,?,上式中,D,是延时算子，表示一个时钟周期的延迟。,12,把以上对（,3,，,1,，,2,）卷积码的矩阵描述推广到一般。,对于任意一个（,n,，,k,，,m,）卷积码，其生成矩阵,G,?,是一个,半无限矩阵：,?,g,?,?,?,g,g,g,?,0,1,g,2,?,m,0,0,?,?,G,?,D,g,?,?,?,g,0,g,1,g,2,?,g,0,?,?,m,?,?,?,?,D,2,g,?,?,?,0,?,?,0,g,0,g,1,g,2,?,g,?,m,?,?,(10,?,?,?,?,0,?,?,?,?,?,?,?,?,?,?,?,?,式中,g,?,g,0,g,1,g,2,g

12、,m,0, (10,2),称作,基本生成矩阵,。,13,1),下面举一个（,3,，,2,，,1,）卷积码的例子：,由,n,3,，,k,2,，,m,1,，可知该码的基本生成矩阵,g,?,形,式如下,g,?,g,0,g,1,0, ,其中生成子矩阵,g,0,g,1,都是,2,?,3,阶矩阵，设,g,?,1,0,1,?,0,?,?,则（,3,，,2,，,1,）卷积码的生成矩阵,?,0,1,?,g,?,0,0,1,?,0,?,1,?,?,?,0,0,1,?,?,?,?,101,001,000,000,?,?,?,010,001,000,000,?,?,?,101,001,000,?,?,?,G,?,?,

13、?,?,010,001,000,?,?,?,?,?,101,001,?,?,?,010,001,?,?,?,?,?,?,?,14,?,111,010,001,?,?,?,111,010,001,?,?,?,c,?,?,1,0,1,1,0,1,0,1,0,0,?,?,?,?,111,010,001,?,?,111,010,001,?,?,?,?,?,?,?,计算得,c,（,111 010 110 101 011 ,）,当已知卷积码的生成矩阵,G,?,时，作,c,mG,?,运算即可实现编码。,如输入信息序列为,m,（,1011010100,）时，求（,3,，,1,，,2,）卷积码,的输出码字序列为

14、,15,10.2,卷积码的概率译码,卷积码的译码可分为代数译码和概率译码两大类。卷,积码的代数译码方法完全依赖于码的代数结构。而概率译,码不仅根据码的代数结构，而且还利用了信道的统计特性，,因此能用增加译码约束长度来减少译码的错误概率。,本节介绍一种目前被广泛应用的概率译码算法：维特,比（,Viterbi,）译码算法。,10.2.1,状态图和网格图,在维特比译码算法中，可以利用状态图来描述卷积码的,编、译码过程。,16,以（,3,，,1,，,2,）卷积码为例。它有四种可能的状态（,D,0,D,1,）：,00,，,01,，,10,和,11,，分别用,S,0,，,S,1,，,S,2,和,S,3,表

15、示。编码器的工,作过程可以通过各移存器的状态转移情况来描述，这就是如图,10.2,所示的状态转移图，简称,状态图,。,图,10.2,（,3,，,1,，,2,）卷积码状态转移图,17,状态图只反映了各状态之间的转移关系，却不能表示出状,态转移与时间的关系。为了表示状态转移与时间的关系，我们,以时间为横坐标轴，以状态为纵坐标轴，将一个平面划分成网,格状，得到了,网格图,表示。在网格图中，以时钟周期作为时,间的计量单位，称为节点，用,L,表示，即在一个节点时间内完,成卷积码编码器一个信息组的输入及相应子码的输出。,18,10.2.2,极大似然译码,设输入至二进制（,n,，,k,，,m,）卷积码编码器

16、的信息序列为,M,（,m,0,，,，,m,i,，,，,m,L,1,，,0,，,，,0,）,经编码后，编码器输出的码序列为,C,（,c,0,，,，,c,i,，,，,c,L,+,m,-1,）,若码序列,C,通过无记忆的,BSC,信道传输，设译码器收,到的接收序列为,Y,（,y,0,，,，,y,i,，,，,y,L,+,m,-1,）,（,c,0,，,，,c,i,，,，,c,L,+,m,-1,）（,e,0,，,，,e,i,，,，,e,L,+,m,-1,）,对于,BSC,信道，输入的码序列,C,经传输变成接收序列,Y,的条,件概率是,p,(,Y,|,C,),p,(,y,0,|,c,0,),p,(,y,1,

17、|,c,1,),p,(,y,L,m,1,|,c,L,m,1,),即,n,(,L,?,m,),?,1,L,?,m,?,1,p,(,Y,|,C,),?,?,p,(,y,i,|,c,i,),?,?,p,(,y,j,|,c,j,),(10,4),i,?,0,j,?,0,19,对式,(10,4),两边取对数得,L,?,m,?,1,log,p,(,Y,C,),?,?,log,p,(,y,c,),?,?,i,i,i,?,0,j,?,0,n,(,L,?,m,),?,1,log,p,(,y,j,c,j,),(10,5),式中：当,y,j,c,j,时，,p,(,y,j,c,j,),就是,BSC,信道的误码率,p,

18、e,。,当接收端收到,Y,后，译码器的任务就是按照极大似然译码准,则，在,2,kL,个码序列中找出一个与,Y,最相似的，称为发送序列,?,?,。称,log,C,的,估值序列,C,。就是要找到使,p,(,Y,C,),最大的,C,p,(,Y,C,),为,C,序列的,似然函数,。,对于二进制对称信道（,BSC,），码序列,C,的似然函数可写成：,log,p,(,Y,C,),?,d,(,Y,C,),?,log,p,e,?,n,(,L,?,m,),?,d,(,Y,C,),?,log(,1,?,p,e,),p,e,?,d,(,Y,C,),?,log,?,n,(,L,?,m,),?,log(,1,?,p,e

19、,),1,?,p,e,(10,6),20,在维特比译码中，码序列,C,的似然函数,log,p,(,Y,C,),称为,C,的,路径度量,，以,M,(,Y,C,),表示。而,log,p,(,y,i,c,i,),和,log,p,(,y,j,c,j,),分别称为,分支度量,和,码元度量,，分别以,M,(,y,i,c,i,),和,M,(,y,j,c,j,),表示。由此可得,(10,7),n,(,L,?,m,),?,1,L,?,m,?,1,M,(,Y,C,),?,?,M,(,y,c,),?,?,i,i,i,?,0,j,?,0,M,(,y,j,c,j,),对于码序列中前,l,个分支的部分路径，其部分路径度量

20、为,M,(,Y,C,),l,?,?,M,(,y,i,c,i,),?,?,M,(,y,j,c,j,),i,?,0,j,?,0,l,?,1,nl,?,1,(10,8),对于,BSC,信道，由于极大似然译码就是最小汉明距离译码，因此可,用,d,（,Y,C,）代替似然函数,log,p,(,Y,C,),作为路径度量，即,L,?,m,?,1,d,(,Y,C,),?,?,d,(,y,i,c,i,),?,i,?,0,n,(,L,?,m,),?,1,?,j,?,0,d,(,y,j,c,j,),(10,9),21,10.2.3,维特比译码算法,极大似然译码准则译码方法在实际应用中能否实,现与每一帧的节点数,L,有

21、关。随着节点数,L,的增大，,例如,L,50,，,k,2,，则网格图上可能的路径就有,2,kL,2,100,10,30,条。显然，将接收序列,Y,与如此多,的路径（码序列）进行比较是不现实的。因此必,须寻找一种新的极大似然译码算法,维特比（,Viterbi,）译码算法不是在网格图上一,次比较所有可能的,2,kL,条路径，而是采取接收,一段，计算比较一段，选择一段最可能的码段，,从而达到整条路径是一条有最大度量的路径。,维特比译码算法使节点,L,的多少与译码的复杂,性无关，,L,只与译码时间成线性关系。,22,用维特比算法译码的具体步骤如下：,（,1,）从第,m,节点（设,l,m,）开始，计算并

22、存贮进入网,格图中每一状态的部分路径及其度量值；,（,2,）,l,增加,1,，计算此时刻进入各状态的部分路径及,其度量值，并挑选出一条度量值最大的部分路径，称,此路径为选留路径；,（,3,）如果,l,L,m,，重复第（,2,）步；否则停止。,23,【,例,10.1,】若输入至图,10.1,所示（,3,，,1,，,2,）卷积码编,码器的信息序列,M,（,1011100,），编码器输出的码序,列,C,（,111,010,110,101,100,011,001,），通过,BSC,信道,传输后，送入译码器的接收序列,Y,（,101,010,110,101,111,011,001,），包含有三个错误。利

23、用维特比译码算,法求译码器输出的估值信息序列,C,?,和估值码序列,M,?,。,24,首先，图示出了经过前,m,2,个时刻，共产生,2,km,4,条,路径，分别对应,S,0,、,S,1,、,S,2,和,S,3,等,4,个状态的情况。,图,10.4,l,2,时（,3,，,1,，,2,）卷积码的网格图,25,图表示了,l,3,时的网格图。进入每一状态的部份路径,各有两条。为每个状态挑选出一条与,Y,之间的汉明距离,较小的部分路径作为选留路径。,图,10.5,l,3,时（,3,，,1,，,2,）卷积码的网格图,26,用同样的方法可以得到,l,4,和,l,5,时的网格图,:,图,10.6,l,4,时（,3,，,1,，,2,）卷积码的网格图,27,图,10.7,