第十章卷积码

1、第十章第十章 卷积码卷积码2内容提要内容提要: 差错控制系统中使用的纠错码，除前面已差错控制系统中使用的纠错码，除前面已学过的分组码之外，还广泛使用着卷积码。本学过的分组码之外，还广泛使用着卷积码。本章首先介绍卷积码的基本概念，重点论述卷积章首先介绍卷积码的基本概念，重点论述卷积码的定义及其矩阵描述。在此基础上，介绍一码的定义及其矩阵描述。在此基础上，介绍一种目前被广泛应用的概率译码算法：维特比（种目前被广泛应用的概率译码算法：维特比（Viterbi）译码算法。译码算法。 第十章第十章 卷积码卷积码31.卷积码的基本概念；卷积码的基本概念；2.维特比译码算法。维特比译码算法。410.1 卷积码

2、的基本概念卷积码的基本概念 卷积码是纠错码中的又一大类。由于分组码码字中的nk个校验元仅与本码字的k个信息元有关，与其它码字无关，因此分组码的编译码是对各个码字孤立地进行的。从信息论的观点看，这种做法必然会损失一部份相关信息，而卷积码的出现使人们有可能利用这部份相关信息。 510.1.1 卷积码概述卷积码概述 卷积码在编码不仅与本子码的k个信息元有关，而且还与此前m个子码中的信息元有关，因此卷积码的编码器需要有存储m组信息元的记忆部件。6图10.1给出了一个二进制卷积码的编码器例子。 图10.1 （3，1，2）卷积码编码器 当输入信息元为mj时， D0、D1中分别存放着此前输入的mj1和mj2

3、， 经运算可得到两个校验元pj，1和pj，2，即 pj，1mjmj1 pj，2mjmj27 在编码器输出端，由旋转开关实现并串转换显然，cj中的校验元pj，1和pj，2不仅与mj有关，同时还与mj1和mj2有关，即与此前m2个子码中的信息元有关。称m为编码存编码存贮贮，表示信息组在编码器中的存贮周期（时钟周期）。编码器输出的每个子码，信息位数k1，码长n3，码率kn13，编码存贮m2，表示为（3，1，2）卷积码。 信息元mj把cj，cj1和cj2三个子码联系在一起，这三个子码之间存在相关性。用编码约束度N表示子码之间的约束关系，显然N m1。 8综上所述，一个（n，k，m）卷积码具有以下重要参

4、数：码长n，子码的信息元个数k，校验元个数nk；编码约束度N，表示子码之间的约束程度。码率kn，表示卷积码传输信息的有效性；编码约束长度NAnN，表示相互约束的码元个数。编码存贮m，表示信息组在编码器中的存贮周期；910.1.2 卷积码的矩阵描述卷积码的矩阵描述 描述卷积码的方法很多，如矩阵方法、多项式方法、状态图和网格图方法等。本节仅介绍矩阵方法。以图10.1给出的（3，1，2）卷积码编码器为例进行分析。设输入的信息序列（m0，m1，m2，mi，）是一个有头无尾的序列，当编码器清零后开始工作时，输出得到的子码如下：c0（m0，p0，1，p0，2） 其中 p0，1m0， p0，2m0c 1（m

5、1，p1，1，p1，2） 其中 p1，1m1m0， p1，2m1c 2（m2，p2，1，p2，2） 其中 p2，1m2m1， p2，2m2m0c 3（m3，p3，1，p3，2） 其中 p3，1m3m2， p3，2m3m1c 4（m4，p4，1，p4，2） 其中 p4，1m4m3， p4，2m4m2 10令输出的码序列cm0 p0,1 p0,2 m1 p1,1 p1,2 m2 p2,1 p2,2 m3 p3,1 p3,2 m4 p4,1 p4,2 表示成矩阵形式：4321042434313232021211010000101000110000100000010100011000010001011

6、10100010011010001001001mmmmmmmmmmmmmmmmmmmmmmmmmmmcT1100000011100001011110001011100000000010001011100000000010001011143210mmmmmc c即 cmG111010111001010111000001010111000000001010111GG被称作（3，1，2）卷积码的生成矩阵生成矩阵 ：12（3）现在，G可表为上式中D是延时算子，表示一个时钟周期的延迟。2102102102ggggggggggggG0 00 00 00 00 00 0DD仔细观察（3，1，2）卷积码的生成

7、矩阵G可发现：（）G中的每一行都是前一行右移右移3位的结果，可以由矩阵的第一行完全确定。将第一行取出并表为g 111 010 001 000 000 g 称作基本生成矩阵基本生成矩阵。（）基本生成矩阵g 只有前（等于该卷积码的编码约束度Nm13）数字有意义，以后各组数字全部为零。分别用g 0，g 1，g 2表示各组，即g 0 111 ， g 1 010 ， g 2 001 ，g 0，g 1，g 2 称作生成子矩阵生成子矩阵。13mmmDDggggggggggG21021021020 00 00 00 00 00 0g gg gg gg gg g 把以上对（3，1，2）卷积码的矩阵描述推广到一般

8、。对于任意一个（n，k，m）卷积码，其生成矩阵G 是一个半无限矩阵：(101) 式中 gg0 g1 g2 gm 0 (102)称作基本生成矩阵基本生成矩阵。 14下面举一个（3，2，1）卷积码的例子：由n3，k2，m1，可知该码的基本生成矩阵g形式如下 gg0 g1 0 其中生成子矩阵g 0, g 1都是23阶矩阵，设0101010g g1001001g则（3，2，1）卷积码的生成矩阵001010001101000001010000001101000000001010000000001101G15 当已知卷积码的生成矩阵G 时，作cmG运算即可实现编码。 如输入信息序列为m（101101010

9、0）时，求（3，1，2）卷积码的输出码字序列为0010101110010101110010101110010101110010101101c计算得c（ 111 010 110 101 011 ） 1610.2 卷积码的概率译码卷积码的概率译码 10.2.1 状态图和网格图状态图和网格图 在维特比译码算法中，可以利用状态图来描述卷积码的编、译码过程。 卷积码的译码可分为代数译码和概率译码两大类。卷积码的代数译码方法完全依赖于码的代数结构。而概率译码不仅根据码的代数结构，而且还利用了信道的统计特性，因此能用增加译码约束长度来减少译码的错误概率。 本节介绍一种目前被广泛应用的概率译码算法：维特比（V

10、iterbi）译码算法。17 以（3，1，2）卷积码为例。它有四种可能的状态（D0D1）：00，01，10和11，分别用S0，S1，S2和S3表示。编码器的工作过程可以通过各移存器的状态转移情况来描述，这就是如图10.2所示的状态转移图，简称状态图状态图。图10.2 （3，1，2）卷积码状态转移图 18 状态图只反映了各状态之间的转移关系，却不能表示出状态转移与时间的关系。为了表示状态转移与时间的关系，我们以时间为横坐标轴，以状态为纵坐标轴，将一个平面划分成网格状，得到了网格图网格图表示。在网格图中，以时钟周期作为时间的计量单位，称为节点，用L表示，即在一个节点时间内完成卷积码编码器一个信息组

11、的输入及相应子码的输出。1910.2.2 极大似然译码极大似然译码 设输入至二进制（n，k，m）卷积码编码器的信息序列为M （m0，mi，mL1，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(yLm1|c Lm1)即 (104) 1)(010)|()|()|(mLnjjjmLii

12、icypppcyCY20对式(104)两边取对数得 (105) 式中：当yj cj 时，p(yjcj) 就是BSC信道的误码率pe。1)(010)(log)(log)(logmLnjjjmLiiicypppcyCY当接收端收到Y后，译码器的任务就是按照极大似然译码准则，在2 kL个码序列中找出一个与 Y最相似的，称为发送序列C的估值序列估值序列 。就是要找到使p(YC)最大的 。称log p(YC)为C序列的似然函数似然函数。 C对于二进制对称信道（BSC），码序列C的似然函数可写成： (106) )1log()()(log),()(logeep,dmLnpdpCYCYCY)1log()(1l

13、og),(eeepmLnppdCYC21在维特比译码中，码序列C的似然函数log p(YC)称为C的路径度量，以M(YC)表示。而log p(yici)和log p(yjcj)分别称为分支度量和码元度量，分别以M(yici)和M(yjcj)表示。由此可得 (107)1)(010)()()(mLnjjjmLiiicyMMMcyCY1010)()()(nljjjliiilcyMMMcyCY对于码序列中前l个分支的部分路径，其部分路径度量为 (108) 对于BSC信道，由于极大似然译码就是最小汉明距离译码，因此可用d（Y,C）代替似然函数log p(YC)作为路径度量，即 (109) 1)(010)

14、()()(mLnjjjmLiiicydddcyCY2210.2.3 维特比译码算法维特比译码算法极大似然译码准则译码方法在实际应用中能否实现与每一帧的节点数L有关。随着节点数L的增大，例如L50，k2，则网格图上可能的路径就有2kL21001030条。显然，将接收序列Y与如此多的路径（码序列）进行比较是不现实的。因此必须寻找一种新的极大似然译码算法 维特比（Viterbi）译码算法不是在网格图上一次比较所有可能的2kL条路径，而是采取接收一段，计算比较一段，选择一段最可能的码段，从而达到整条路径是一条有最大度量的路径。维特比译码算法使节点L的多少与译码的复杂性无关，L只与译码时间成线性关系。2

15、3用维特比算法译码的具体步骤如下：（1）从第m节点（设lm）开始，计算并存贮进入网格图中每一状态的部分路径及其度量值；（2）l增加1，计算此时刻进入各状态的部分路径及其度量值，并挑选出一条度量值最大的部分路径，称此路径为选留路径；（3）如果lLm，重复第（2）步；否则停止。24【例例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），包含有三个错误。利用维特比译码算法求译码

16、器输出的估值信息序列 和估值码序列 。CM25首先，图示出了经过前m2个时刻，共产生2km4条路径，分别对应S0、S1、S2和S3等4个状态的情况。图10.4 l2时（3，1，2）卷积码的网格图 26图10.5 l3时（3，1，2）卷积码的网格图 图表示了l3时的网格图。进入每一状态的部份路径各有两条。为每个状态挑选出一条与Y之间的汉明距离较小的部分路径作为选留路径。27用同样的方法可以得到l4和l5时的网格图 :图10.6 l4时（3，1，2）卷积码的网格图 28译码的最后m2个时刻，即第6，7两个节点，是用来使网格图最终返回到S0状态的。图10.7 l5时（3，1，2）卷积码的网格图 29

17、图10.8 l6时（3，1，2）卷积码的网格图 30图10.9 l7时（3，1，2）卷积码的网格图 本例的最后结果是：路径（111 010 110 101 100 011 001）是一条与Y有最小汉明距离的路径，而 （1011100）。这就是说，接收序列Y中的错误得到了纠正。M31关于维特比译码的全过程可以看到： （1）每一状态在每一时刻都有一条自已的选留路径，而且该路径在该时刻是一条度量值最大的部分路径，但最后应选择一条汉明距离最小者作为译码器输出的估值码序列。 （2）卷积码的纠错能力取决于码的距离特性，这一点与线性分组码是相同的。 （3）维特比译码算法的复杂性只与编码器的状态数2km有关，与L无关，L只与译码时间成线性关系。32卷积码是纠错码中又一个大类。由于卷积码利用了各信息