第十章_卷积码

1第十章卷积码2内容提要:差错控制系统中使用的纠错码，除前面已学过的分组码之外，还广泛使用着卷积码。本章首先介绍卷积码的基本概念，重点论述卷积码的定义及其矩阵描述。在此基础上，介绍一种目前被广泛应用的概率译码算法：维特比（Viterbi）译码算法。第十章卷积码3本章重点：1.卷积码的基本概念；2.维特比译码算法。410.1卷积码的基本概念卷积码是纠错码中的又一大类。由于分组码码字中的n－k个校验元仅与本码字的k个信息元有关，与其它码字无关，因此分组码的编译码是对各个码字孤立地进行的。从信息论的观点看，这种做法必然会损失一部份相关信息，而卷积码的出现使人们有可能利用这部份相关信息。510.1.1卷积码概述卷积码在编码不仅与本子码的k个信息元有关，而且还与此前m个子码中的信息元有关，因此卷积码的编码器需要有存储m组信息元的记忆部件。6图10.1给出了一个二进制卷积码的编码器例子。图10.1（3，1，2）卷积码编码器当输入信息元为mj时，D0、D1中分别存放着此前输入的mj－1和mj－2，经运算可得到两个校验元pj，1和pj，2，即pj，1＝mj＋mj－1pj，2＝mj＋mj－27在编码器输出端，由旋转开关实现并／串转换显然，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。8综上所述，一个（n，k，m）卷积码具有以下重要参数：码长n，子码的信息元个数k，校验元个数n－k；编码约束度N，表示子码之间的约束程度。码率k／n，表示卷积码传输信息的有效性；编码约束长度NA＝nN，表示相互约束的码元个数。编码存贮m，表示信息组在编码器中的存贮周期；910.1.2卷积码的矩阵描述描述卷积码的方法很多，如矩阵方法、多项式方法、状态图和网格图方法等。本节仅介绍矩阵方法。以图10.1给出的（3，1，2）卷积码编码器为例进行分析。设输入的信息序列（m0，m1，m2，…，mi，…）是一个有头无尾的序列，当编码器清零后开始工作时，输出得到的子码如下：c0＝（m0，p0，1，p0，2）其中p0，1＝m0，p0，2＝m0c1＝（m1，p1，1，p1，2）其中p1，1＝m1＋m0，p1，2＝m1c2＝（m2，p2，1，p2，2）其中p2，1＝m2＋m1，p2，2＝m2＋m0c3＝（m3，p3，1，p3，2）其中p3，1＝m3＋m2，p3，2＝m3＋m1c4＝（m4，p4，1，p4，2）其中p4，1＝m4＋m3，p4，2＝m4＋m2……10令输出的码序列c＝[m0p0,1p0,2m1p1,1p1,2m2p2,1p2,2m3p3,1p3,2m4p4,1p4,2…]表示成矩阵形式：432104243431323202121101000010100011000010000001010001100001000101110100010011010001001001mmmmmmmmmmmmmmmmmmmmmmmmmmmcT1100000011100001011110001011100000000010001011100000000010001011143210mmmmmc即c＝mG111010111001010111000001010111000000001010111GG被称作（3，1，2）卷积码的生成矩阵：12（3）现在，G可表为上式中D是延时算子，表示一个时钟周期的延迟。2102102102ggggggggggggG000000DD仔细观察（3，1，2）卷积码的生成矩阵G可发现：（１）G中的每一行都是前一行右移右移3位的结果，可以由矩阵的第一行完全确定。将第一行取出并表为g＝[111010001000000…]g称作基本生成矩阵。（２）基本生成矩阵g只有前（等于该卷积码的编码约束度N＝m＋1＝3）数字有意义，以后各组数字全部为零。分别用g0，g1，g2表示各组，即g0＝[111]，g1＝[010]，g2＝[001]，g0，g1，g2称作生成子矩阵。13mmmDDggggggggggG2102102102000000ggggg把以上对（3，1，2）卷积码的矩阵描述推广到一般。对于任意一个（n，k，m）卷积码，其生成矩阵G是一个半无限矩阵：(10－1)式中g＝[g0g1g2…gm0…](10－2)称作基本生成矩阵。14下面举一个（3，2，1）卷积码的例子：由n＝3，k＝2，m＝1，可知该码的基本生成矩阵g形式如下g＝[g0g10…]其中生成子矩阵g0,g1都是23阶矩阵，设0101010g1001001g则（3，2，1）卷积码的生成矩阵001010001101000001010000001101000000001010000000001101G15当已知卷积码的生成矩阵G时，作c＝mG运算即可实现编码。如输入信息序列为m＝（1011010100…）时，求（3，1，2）卷积码的输出码字序列为0010101110010101110010101110010101110010101101c计算得c＝（111010110101011…）1610.2卷积码的概率译码10.2.1状态图和网格图在维特比译码算法中，可以利用状态图来描述卷积码的编、译码过程。卷积码的译码可分为代数译码和概率译码两大类。卷积码的代数译码方法完全依赖于码的代数结构。而概率译码不仅根据码的代数结构，而且还利用了信道的统计特性，因此能用增加译码约束长度来减少译码的错误概率。本节介绍一种目前被广泛应用的概率译码算法：维特比（Viterbi）译码算法。17以（3，1，2）卷积码为例。它有四种可能的状态（D0D1）：00，01，10和11，分别用S0，S1，S2和S3表示。编码器的工作过程可以通过各移存器的状态转移情况来描述，这就是如图10.2所示的状态转移图，简称状态图。图10.2（3，1，2）卷积码状态转移图18状态图只反映了各状态之间的转移关系，却不能表示出状态转移与时间的关系。为了表示状态转移与时间的关系，我们以时间为横坐标轴，以状态为纵坐标轴，将一个平面划分成网格状，得到了网格图表示。在网格图中，以时钟周期作为时间的计量单位，称为节点，用L表示，即在一个节点时间内完成卷积码编码器一个信息组的输入及相应子码的输出。1910.2.2极大似然译码设输入至二进制（n，k，m）卷积码编码器的信息序列为M＝（m0，…，mi，…，mL－1，0，…，0）经编码后，编码器输出的码序列为C＝（c0，…，ci，…，cL+m-1）若码序列C通过无记忆的BSC信道传输，设译码器收到的接收序列为Y＝（y0，…，yi，…，yL+m-1）＝（c0，…，ci，…，cL+m-1）＋（e0，…，ei，…，eL+m-1）对于BSC信道，输入的码序列C经传输变成接收序列Y的条件概率是p(Y|C)＝p(y0|c0)p(y1|c1)…p(yL＋m－1|cL＋m－1)即(10－4)1)(010)|()|()|(mLnjjjmLiiicypppcyCY20对式(10－4)两边取对数得(10－5)式中：当yj≠cj时，p(yj︱cj)就是BSC信道的误码率pe。1)(010)(log)(log)(logmLnjjjmLiiicypppcyCY当接收端收到Y后，译码器的任务就是按照极大似然译码准则，在2kL个码序列中找出一个与Y最相似的，称为发送序列C的估值序列。就是要找到使p(Y︱C)最大的。称logp(Y︱C)为C序列的似然函数。Cˆ对于二进制对称信道（BSC），码序列C的似然函数可写成：(10－6))1log()]()([log),()(logeep,dmLnpdpCYCYCY)1log()(1log),(eeepmLnppdCYCˆ21在维特比译码中，码序列C的似然函数logp(Y︱C)称为C的路径度量，以M(Y︱C)表示。而logp(yi︱ci)和logp(yj︱cj)分别称为分支度量和码元度量，分别以M(yi︱ci)和M(yj︱cj)表示。由此可得(10－7)1)(010)()()(mLnjjjmLiiicyMMMcyCY1010)()()(nljjjliiilcyMMMcyCY对于码序列中前l个分支的部分路径，其部分路径度量为(10－8)对于BSC信道，由于极大似然译码就是最小汉明距离译码，因此可用d（Y,C）代替似然函数logp(Y︱C)作为路径度量，即(10－9)1)(010)()()(mLnjjjmLiiicydddcyCY2210.2.3维特比译码算法极大似然译码准则译码方法在实际应用中能否实现与每一帧的节点数L有关。随着节点数L的增大，例如L＝50，k＝2，则网格图上可能的路径就有2kL＝2100＞1030条。显然，将接收序列Y与如此多的路径（码序列）进行比较是不现实的。因此必须寻找一种新的极大似然译码算法维特比（Viterbi）译码算法不是在网格图上一次比较所有可能的2kL条路径，而是采取接收一段，计算比较一段，选择一段最可能的码段，从而达到整条路径是一条有最大度量的路径。维特比译码算法使节点L的多少与译码的复杂性无关，L只与译码时间成线性关系。23用维特比算法译码的具体步骤如下：（1）从第m节点（设l＝m）开始，计算并存贮进入网格图中每一状态的部分路径及其度量值；（2）l增加1，计算此时刻进入各状态的部分路径及其度量值，并挑选出一条度量值最大的部分路径，称此路径为选留路径；（3）如果l＜L＋m，重复第（2）步；否则停止。24【例10.1】若输入至图10.1所示（3，1，2）卷积码编码器的信息序列M＝（1011100），编码器输出的码序列C＝（111010110101100011001），通过BSC信道传输后，送入译码器的接收序列Y＝（101010110101111011001），包含有三个错误。利用维特比译码算法求译码器输出的估值信息序列和估值码序列。CˆMˆ25首先，图示出了经过前m＝2个时刻，共产生2km＝4条路径，分别对应S0、S1、S2和S3等4个状态的情况。图10.4l＝2时（3，1，2）卷积码的网格图26图10.5l＝3时（3，1，2）卷积码的网格图图表示了l＝3时的网格图。进入每一状态的部份路径各有两条。为每个状态挑选出一条与Y之间的汉明距离较小的部分路径作为选留路径。27用同样的方法可以得到l＝4和l＝5时的网格图:图10.6l＝4时（3，1，2）卷积码的网格图28译码的最后m＝2个时刻，即第6，7两个节点，是用来使网格图最终返回到S0状态的。图10.7l＝5时（3，1，2）卷积码的网格图29图10.8l＝6时（3，1，2）卷积码的网格图30图10.9l＝7时（3，1，2）卷积码的网格图