第十章卷积码.ppt

第十章第十章 卷积码卷积码1 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）卷积码编码器 当输入信息元为mj时， D0、D1中分别存放着此前输入的mj－1和mj－2， 经运算可得到两个校验元pj，1和pj，2，即 pj，1＝mj＋mj－1 pj，2＝mj＋mj－26 在编码器输出端，由旋转开关实现并／串转换显然，cj中的校验元pj，1和pj，2不仅与mj有关，同时还与mj－1和mj－2有关，即与此前m＝2个子码中的信息元有关称m为编码存编码存贮贮，表示信息组在编码器中的存贮周期（时钟周期）编码器输出的每个子码，信息位数k＝1，码长n＝3，码率k／n＝1／3，编码存贮m＝2，表示为（3，1，2）卷积码 信息元mj把cj，cj＋1和cj＋2三个子码联系在一起，这三个子码之间存在相关性用编码约束度N表示子码之间的约束关系，显然N ＝m＋1 7综上所述，一个（n，k，m）卷积码具有以下重要参数：码长n，子码的信息元个数k，校验元个数n－k；编码约束度N，表示子码之间的约束程度码率k／n，表示卷积码传输信息的有效性；编码约束长度NA＝nN，表示相互约束的码元个数。

编码存贮m，表示信息组在编码器中的存贮周期；810.1.2 卷积码的矩卷积码的矩阵描述阵描述 描述卷积码的方法很多，如矩阵方法、多项式方法、状态图和网格图方法等本节仅介绍矩阵方法以图10.1给出的（3，1，2）卷积码编码器为例进行分析设输入的信息序列（m0，m1，m2，…，mi，…）是一个有头无尾的序列，当编码器清零后开始工作时，输出得到的子码如下：c0＝（m0，p0，1，p0，2） 其中 p0，1＝m0， p0，2＝m0c 1＝（m1，p1，1，p1，2） 其中 p1，1＝m1＋m0， p1，2＝m1c 2＝（m2，p2，1，p2，2） 其中 p2，1＝m2＋m1， p2，2＝m2＋m0c 3＝（m3，p3，1，p3，2） 其中 p3，1＝m3＋m2， p3，2＝m3＋m1c 4＝（m4，p4，1，p4，2） 其中 p4，1＝m4＋m3， p4，2＝m4＋m2 ……9令输出的码序列c＝[m0 p0,1 p0,2 m1 p1,1 p1,2 m2 p2,1 p2,2 m3 p3,1 p3,2 m4 p4,1 p4,2 …]表示成矩阵形式：10即 c＝mGG被称作（3，1，2）卷积码的生成矩阵生成矩阵 ：11（3）现在，G可表为上式中D是延时算子，表示一个时钟周期的延迟。

仔细观察（3，1，2）卷积码的生成矩阵G可发现：（１）G中的每一行都是前一行右移右移3位的结果，可以由矩阵的第一行完全确定将第一行取出并表为g＝[ 111 010 001 000 000 … ]g 称作基本生成矩阵基本生成矩阵２）基本生成矩阵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 称作生成子矩阵生成子矩阵12 把以上对（3，1，2）卷积码的矩阵描述推广到一般对于任意一个（n，k，m）卷积码，其生成矩阵G 是一个半无限矩阵：(10－1) 式中 g＝[g0 g1 g2 … gm 0 … ] (10－2)称作基本生成矩阵基本生成矩阵 13下面举一个（3，2，1）卷积码的例子：由n＝3，k＝2，m＝1，可知该码的基本生成矩阵g形式如下 g＝[g0 g1 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）卷积码为例它有四种可能的状态（D0D1）：00，01，10和11，分别用S0，S1，S2和S3表示编码器的工作过程可以通过各移存器的状态转移情况来描述，这就是如图10.2所示的状态转移图，简称状态图状态图图10.2 （3，1，2）卷积码状态转移图 17 状态图只反映了各状态之间的转移关系，却不能表示出状态转移与时间的关系为了表示状态转移与时间的关系，我们以时间为横坐标轴，以状态为纵坐标轴，将一个平面划分成网格状，得到了网网格格图图表示。

在网格图中，以时钟周期作为时间的计量单位，称为节点，用L表示，即在一个节点时间内完成卷积码编码器一个信息组的输入及相应子码的输出1810.2.2 极大似然译极大似然译码码 设输入至二进制（n，k，m）卷积码编码器的信息序列为M ＝（m0，…，mi，…，mL－1，0，…，0）经编码后，编码器输出的码序列为 C ＝（c 0，…，c i，…，c L+m-1） 若码序列C通过无记忆的 BSC信道传输，设译码器收到的接收序列为 Y＝（y0，…，y i，…，y L+m-1）＝（c0，…，c i，…，cL+m-1）＋（e0，…，ei，…，e L+m-1） 对于BSC信道，输入的码序列C经传输变成接收序列Y的条件概率是 p(Y|C)＝p(y 0|c 0) p(y 1|c 1)… p(yL＋m－1|c L＋m－1)即 (10－4) 19对式(10－4)两边取对数得 (10－5) 式中：当yj ≠cj 时，p(yj︱cj) 就是BSC信道的误码率pe。

当接收端收到Y后，译码器的任务就是按照极大似然译码准则，在2 kL个码序列中找出一个与 Y最相似的，称为发送序列C的估值序列估值序列 就是要找到使p(Y︱C)最大的 称log p(Y︱C)为C序列的似然函数似然函数 对于二进制对称信道（BSC），码序列C的似然函数可写成： (10－6) 20在维特比译码中，码序列C的似然函数log p(Y︱C)称为C的路径度量，以M(Y︱C)表示而log p(yi︱ci)和log p(yj︱cj)分别称为分支度量和码元度量，分别以M(yi︱ci)和M(yj︱cj)表示由此可得 (10－7)对于码序列中前l个分支的部分路径，其部分路径度量为 (10－8) 对于BSC信道，由于极大似然译码就是最小汉明距离译码，因此可用d（Y,C）代替似然函数log p(Y︱C)作为路径度量，即 (10－9) 2110.2.3 维特比译码维特比译码算法算法极大似然译码准则译码方法在实际应用中能否实现与每一帧的节点数L有关。

随着节点数L的增大，例如L＝50，k＝2，则网格图上可能的路径就有2kL＝2100＞1030条显然，将接收序列Y与如此多的路径（码序列）进行比较是不现实的因此必须寻找一种新的极大似然译码算法 维特比（Viterbi）译码算法不是在网格图上一次比较所有可能的2kL条路径，而是采取接收一段，计算比较一段，选择一段最可能的码段，从而达到整条路径是一条有最大度量的路径维特比译码算法使节点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个时刻，共产生2km＝4条路径，分别对应S0、S1、S2和S3等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两个节点，是用来使网格图最终返回到S0状态的图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）维特比译码算法的复杂性只与编码器的状态数2km有关，与L无关，L只与译码时间成线性关系31卷积码是纠错码中又一个大类由于卷积码利用了各信息组之间的相关性，它的性能一般要优于分组码尽管对卷积码的理论研究尚不够成熟，它仍然是一类很有前途的纠错码本章的主要内容有：本本 章章 小小 结结 （1）卷积码的定义及重要参数：卷积码的定义，卷积码的结构特点，描述卷积码的重要参数，各参数的含义32 （4）维特比译码算法：维特比译码算法是一种最大似然译码算法，维特比译码算法的步骤，维特比译码算法的特点 （2）卷积码的矩阵描述：卷积码的生成矩阵，生成矩阵的半无限性质，基本生成矩阵和生成子矩阵，系统卷积码矩阵的特点 （3）卷积码的状态图和网格图：卷积码的状态图，从状态图到网格图3334。