第十章_卷积码

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第十章,卷积码,1,内容提要,:,差错控制系统中使用的纠错码，除前面已学过的分组码之外，还广泛使用着卷积码。本章首先介绍卷积码的基本概念，重点论述卷积码的定义及其矩阵描述。在此基础上，介绍一种目前被广泛应用的概率译码算法：维特比（,Viterbi,）,译码算法。,第十章 卷积码,2,本章重点：,1.,卷积码的基本概念；,2.,维特比译码算法。,3,10.1 卷积码的基本概念,卷积码是纠错码中的又一大类。由于分组码码字中的,n,k,个校验元仅与本码字的,k,个信息元有关，与其它码字无关，因此分组码的编译码是对各个码字孤立地进行的。从信息论的观点看，这种做法必然会损失一部份相关信息，而卷积码的出现使人们有可能利用这部份相关信息。,4,10.1.1 卷积码概述,卷积码在编码不仅与本子码的,k,个信息元有关，而且还与此前,m,个子码中的信息元有关，因此卷积码的编码器需要有存储,m,组信息元的记忆部件。,5,图10.1给出了一个二进制卷积码的编码器例子。,图10.1 （3，1，2）卷积码编码器,当输入信息元为,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,6,在编码器输出端，由旋转开关实现并串转换显然，,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,13，,编码存贮,m,2，,表示为（3，1，2）卷积码。,信息元,m,j,把,c,j,，,c,j,1,和,c,j,2,三个子码联系在一起，这三个子码之间存在相关性。用编码约束度,N,表示子码之间的约束关系，显然,N,m,1。,7,综上所述，一个（,n,，,k,，,m,）,卷积码具有以下重要参数：,码长,n,，,子码的信息元个数,k,，,校验元个数,n,k,；,编码约束度,N,，,表示子码之间的约束程度。,码率,k,n,，,表示卷积码传输信息的有效性；,编码约束长度,N,A,nN,，,表示相互约束的码元个数。,编码存贮,m,，,表示信息组在编码器中的存贮周期；,8,10.1.,2,卷积码的矩阵描述,描述卷积码的方法很多，如矩阵方法、多项式方法、状态图和网格图方法等。本节仅介绍矩阵方法。,以图10.1给出的（3，1，2）卷积码编码器为例进行分析。设输入的信息序列（,m,0,，,m,1,，,m,2,，,m,i,，）,是一个有头无尾的序列，当编码器清零后开始工作时，输出得到的子码如下：,c,0,（,m,0,，,p,0,，,1,，,p,0,，,2,）,其中,p,0,，,1,m,0,，,p,0,，,2,m,0,c,1,（,m,1,，,p,1,，,1,，,p,1,，,2,）,其中,p,1,，,1,m,1,m,0,，,p,1,，,2,m,1,c,2,（,m,2,，,p,2,，,1,，,p,2,，,2,）,其中,p,2,，,1,m,2,m,1,，,p,2,，,2,m,2,m,0,c,3,（,m,3,，,p,3,，,1,，,p,3,，,2,）,其中,p,3,，,1,m,3,m,2,，,p,3,，,2,m,3,m,1,c,4,（,m,4,，,p,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,表示成矩阵形式：,10,即,c,m,G,G,被称作,（3，1，2）卷积码的,生成矩阵,：,11,（3）现在，,G,可表为,上式中,D,是延时算子，表示一个时钟周期的延迟。,仔细观察（3，1，2）卷积码的生成矩阵,G,可发现：,（）,G,中的每一行都是前一行右移右移3位的结果，可以由矩阵的第一行完全确定。将第一行取出并表为,g, 111 010 001 000 000 ,g,称作,基本生成矩阵,。,（）基本生成矩阵,g,只有前,（等于该卷积码的编码约束度,N,m,13）,数字有意义，以后各组数字全部为零。分别用,g,0,，,g,1,，,g,2,表示各组，即,g,0, 111 ，,g,1, 010 ，,g,2, 001 ，,g,0,，,g,1,，,g,2,称作,生成子矩阵,。,12,把以上对（3，1，2）卷积码的矩阵描述推广到一般。对于任意一个（,n,，,k,，,m,）,卷积码，其生成矩阵,G,是一个半无限矩阵：,(101),式中,g,g,0,g,1,g,2,g,m,0, (102),称作,基本生成矩阵,。,13,下面举一个（3，2，1）卷积码的例子：,由,n,3，,k,2，,m,1，,可知该码的基本生成矩阵,g,形式如下,g,g,0,g,1,0, ,其中生成子矩阵,g,0,g,1,都是2,3,阶矩阵，设,则（3，2，1）卷积码的生成矩阵,14,当已知卷积码的生成矩阵,G,时，作,c,mG,运算即可实现编码。 如输入信息序列为,m,（1011010100）,时，求（3，1，2）卷积码的输出码字序列为,计算得,c,（ 111 010 110 101 011 ）,15,10.2 卷积码的概率译码,10.2.1 状态图和网格图,在维特比译码算法中，可以利用状态图来描述卷积码的编、译码过程。,卷积码的译码可分为代数译码和概率译码两大类。卷积码的代数译码方法完全依赖于码的代数结构。而概率译码不仅根据码的代数结构，而且还利用了信道的统计特性，因此能用增加译码约束长度来减少译码的错误概率。,本节介绍一种目前被广泛应用的概率译码算法：维特比（,Viterbi,）,译码算法。,16,以（3，1，2）卷积码为例。它有四种可能的状态（,D,0,D,1,）：00，01，10和11，分别用,S,0,，S,1,，S,2,和,S,3,表示。编码器的工作过程可以通过各移存器的状态转移情况来描述，这就是如图10.2所示的状态转移图，简称,状态图,。,图10.2 （3，1，2）卷积码状态转移图,17,状态图只反映了各状态之间的转移关系，却不能表示出状态转移与时间的关系。为了表示状态转移与时间的关系，我们以时间为横坐标轴，以状态为纵坐标轴，将一个平面划分成网格状，得到了,网格图,表示。在网格图中，以时钟周期作为时间的计量单位，称为节点，用,L,表示，即在一个节点时间内完成卷积码编码器一个信息组的输入及相应子码的输出。,18,10.2.2 极大似然译码,设输入至二进制（,n,，,k,，,m,）,卷积码编码器的信息序列为,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,|,c,1,),p,(,y,L,m,1,|,c,L,m,1,),即,(104),19,对式(104)两边取对数得,(105),式中：当,y,j,c,j,时，,p,(,y,j,c,j,),就是,BSC,信道的误码率,p,e,。,当接收端收到,Y,后，译码器的任务就是按照极大似然译码准则，在2,kL,个码序列中找出一个与,Y,最相似的，称为发送序列,C,的,估值序列,。就是要找到使,p,(,Y,C,),最大的 。称,log,p,(,Y,C,),为,C,序列的,似然函数,。,对于二进制对称信道（,BSC,），,码序列,C,的似然函数可写成：,(106),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,),表示。由此可得,(107),对于码序列中前,l,个分支的部分路径，其部分路径度量为,(108),对于,BSC,信道，由于极大似然译码就是最小汉明距离译码，因此可用,d,（,Y,C,）,代替似然函数,log,p,(,Y,C,),作为路径度量，即,(109),21,10.2.3 维特比译码算法,极大似然译码准则译码方法在实际应用中能否实现与每一帧的节点数,L,有关。随着节点数,L,的增大，例如,L,50，,k,2，,则网格图上可能的路径就有2,kL,2,100,10,30,条。显然，将接收序列,Y,与如此多的路径（码序列）进行比较是不现实的。因此必须寻找一种新的极大似然译码算法,维特比（,Viterbi,）,译码算法不是在网格图上一次比较所有可能的2,kL,条路径，而是采取接收一段，计算比较一段，选择一段最可能的码段，从而达到整条路径是一条有最大度量的路径。维特比译码算法使节点,L,的多少与译码的复杂性无关，,L,只与译码时间成线性关系。,22,用维特比算法译码的具体步骤如下：,（1）从第,m,节点（设,l,m,）,开始，计算并存贮进入网格图中每一状态的部分路径及其度量值；,（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），,包含有三个错误。利用维特比译码算法求译码器输出的估值信息序列 和估值码序列 。,24,首先，图示出了经过前,m,2,个时刻，共产生2,km,4,条路径，分别对应,S,0,、,S,1,、,S,2,和,S,3,等4个状态的情况。,图10.4,l,2,时（3，1，2）卷积码的网格图,25,图10.5,l,3,时（3，1，2）卷积码的网格图,图表示了,l,3,时的网格图。进入每一状态的部份路径各有两条。为每个状态挑选出一条与,Y,之间的汉明距离较小的部分路径作为选留路径。,26,用同样的方法可以得到,l,4,和,l,5,时的网格图 :,图10.6,l,4,时（3，1，2）卷积码的网格图,27,译码的最后,m,2,个时刻，即第6，7两个节点，是用来使网格图最终返回到,S,0,状态的。,图10.7,l,5,时（3，1，2）卷积码的网格图,28,图10.8,l,6,时（3，1，2）卷积码的网格图,29,图10.9,l,7,时（3，1，2）卷积码的网格图,本例的最后结果是：路径（,111 010 110 101 100 011 001,）是一条与,Y,有最小汉明距离的路径，而 （1011100）。这就是说，接收序列,Y,中的错误得到了纠正。,30,关于维特比译码的全过程可以看到：,（1）每一状态在每一时刻都有一条自已的选留路径，而且该路径在该时刻是一条度量值最大的部分路径，但最后应选择一条汉明距离最小者作为译码器输出的估值码序列。,（2）卷积码的纠错能力取决于码的距离特性，这一点与线性分组码是相同的。,（3）维特比译码算法的复杂性只与编码器的状态数,2,km,有关，与,L,无关，,L,只与译码时间成线性关系。,31,卷积码是纠错码中又一个大类。由于卷积码利用了各信息组之间的相关性，它的性能一般要优于分组码。尽管对卷积码的理论研究尚不够成熟，它仍然是一类很有前途的纠错码。本章的主要内容有：,本 章 小 结,（1）卷积码的定义及重要参数：卷积码的定义，卷积码的,结构特点，描述卷积码的重要参数，各参数的含义。,32,（4）维特比译码算法：维特比译码算法是一种最大似然译码算法，维特比译码算法的步骤，维特比译码算法的特点。,（2）卷积码的矩阵描述：卷积码的生成矩阵，生成矩阵的半无限性质，基本生成矩阵和生成子矩阵，系统卷积码矩阵的特点。,（3）卷积码的状态图和网格图：卷积码的状态图，从状态图到网格图。,33,34,