1第十章

第十章卷积码内容提要差错控制系统中使用的纠错码，除前面已学过的分组码之外，还广泛使用着卷积码。本章首先介绍卷积码的基本概念，重点论述卷积码的定义及其矩阵描述。在此基础上，介绍一种目前被广泛应用的概率译码算法：维特比（Viterbi）译码算法。第十章卷积码10.1卷积码的基本概念卷积码是纠错码中的又一大类。由于分组码码字中的n－k个校验元仅与本码字的k个信息元有关，与其它码字无关，因此分组码的编译码是对各个码字孤立地进行的。从信息论的观点看，这种做法必然会损失一部份相关信息，而卷积码的出现使人们有可能利用这部份相关信息。10.1.1卷积码概述卷积码在编码不仅与本子码的k个信息元有关，而且还与此前m个子码中的信息元有关，因此卷积码的编码器需要有存储m组信息元的记忆部件。卷积码是伊利亚斯（Elias）于1955年提出的。图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－2在编码器输出端，由旋转开关实现并／串转换显然，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。综上所述，一个（n，k，m）卷积码具有以下重要参数：(1)码长n，子码的信息元个数k，校验元个数n－k；(4)编码约束度N，表示子码之间的约束程度。(2)码率k／n，表示卷积码传输信息的有效性；(5)编码约束长度NA＝nN，表示相互约束的码元个数。(3)编码存贮m，表示信息组在编码器中的存贮周期；10.1.２卷积码的矩阵描述描述卷积码的方法很多，大致可以分为两大类型：（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……令输出的码序列c＝[m0p0,1p0,2m1p1,1p1,2m2p2,1p2,2m3p3,1p3,2m4p4,1p4,2…]表示成矩阵形式：432104243431323202121101000010100011000010000001010001100001000101110100010011010001001001mmmmmmmmmmmmmmmmmmmmmmmmmmmTC00000011100001011110001011100000000010001011100000000010001011143210mmmmmc即c＝mG111010111001010111000001010111000000001010111GG被称作（3，1，2）卷积码的生成矩阵：仔细观察（3，1，2）卷积码的生成矩阵G可发现：（１）G中的每一行都是前一行右移3位的结果，可以由矩阵的第一行完全确定。将第一行取出并表示为g＝[111010001000000…]g称作基本生成矩阵。（２）基本生成矩阵g只有前3组（等于该卷积码的编码约束度N＝m＋1＝3）数字有意义，以后各组数字全部为零。分别用g0，g1，g2表示各组，即g0＝[111]，g1＝[010]，g2＝[001]，g0，g1，g2称作生成子矩阵。（3）现在，G可表为上式中D是延时算子，表示一个时钟周期的延迟。2102102102ggggggggggggG000000DDmmmDDgggggggggggggggG2102102102000000把以上对（3，1，2）卷积码的矩阵描述推广到一般。对于任意一个（n，k，m）卷积码，其生成矩阵G是一个半无限矩阵：(10－1)式中g＝[g0g1g2…gm0…](10－2)称作基本生成矩阵。下面举一个（3，2，1）卷积码的例子：由n＝3，k＝2，m＝1，可知该码的基本生成矩阵g形式如下g＝[g0g10…]其中生成子矩阵g0,g1都是23阶矩阵，设0101010g1001001g则（3，2，1）卷积码的生成矩阵001010001101000001010000001101000000001010000000001101G当已知卷积码的生成矩阵G时，作c＝mG运算即可实现编码。如输入信息序列为m＝（1011010100…）时，求（3，1，2）卷积码的输出码字序列为0010101110010101110010101110010101110010101101c计算得c＝（111010110101011…）用同样的输入信息序列m用来求（3，2，1）卷积码的输出码序列时有0010100011010010100011010010100011010001011110][c得)001011010110101(c可得以上两个卷积码各码字都具有系统码特征。10.2卷积码的概率译码10.2.1状态图和网格图在维特比译码算法中，可以利用状态图来描述卷积码的编、译码过程。卷积码的译码可分为代数译码和概率译码两大类。卷积码的代数译码方法完全依赖于码的代数结构。而概率译码不仅根据码的代数结构，而且还利用了信道的统计特性，因此能用增加译码约束长度来减少译码的错误概率。本节介绍一种目前被广泛应用的概率译码算法：维特比（Viterbi）译码算法。以（3，1，2）卷积码为例。它有四种可能的状态：00，01，10和11，分别用S0，S1，S2和S3表示。编码器的工作过程可以通过各移存器的状态转移情况来描述，这就是如图10.2所示的状态转移图，简称状态图。图10.2（3，1，2）卷积码状态转移图状态图只反映了各状态之间的转移关系，却不能表示出状态转移与时间的关系。为了表示状态转移与时间的关系，我们以时间为横坐标轴，以状态为纵坐标轴，将一个平面划分成网格状，得到了网格图表示。在网格图中，以时间周期作为时间的计量单位，称为节点，用L表示。L＝5时（3，1，2）卷积码状态图。输入1011100网格图的特点：（1）若编码器从S0状态开始编码工作并最终结束于S0状态，则对该码，需要L+m+1个节点。（2）最初的m=2个节点，相应于编码器油S0出发往各个状态，最后的m=2个节点，相应于编码器由各状态最终返回到S0状态。（3）只有从第m节点开始至第L节点，编码器可处于任意状态，或者说编码器处于正常工作状态。（4）网格图上的第一行各个节点都代表寄存器处于S0状态，第二行处于S1状态，依次类推。正常状态都有两个输入和两个输出。（5）每个分支旁的标注，分别代表该节点输入的信息元和输出的子码。例0/001（6）编码器的工作过程可用网格图上的一条路径表示。所有可能输入信息序列共有2kL种，所以网格图上可能存在的路径也有2kL，它们对应着2kL个长为N=(L+m)n的不同码序列。10.2.2最大似然译码设输入至二进制（n，k，m）卷积码编码器的信息序列为M＝（m0，…，mi，…，mL－1，0，…，0）经编码后，编码器输出的码序列为C＝（c0，…，ci，…，cL+m-1）式中mi代表长度为k的信息组；0代表长度为k的全零信息组。有用的信息长度是前Lk位，后面的m组0，其作用是使编码器在完成对一帧信息序列M的编码后恢复到初始状态，实现信息的分帧传输。若码序列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)即1)(010)/()/()/(mLnjjjmLiiicypppcyCY对式(10－4)两边取对数得(10－5)式中：当yj≠cj时，p(yj︱cj)是二进制对称信道的误码率pe。1)(010)(log)(log)(logmLnjjjmLiiicypppcyCY当接收端收到Y后，译码器的任务就是按照最大似然译码准则，在2kL个码序列中找出一个与Y最相似的，称为发送序列C的估值序列。就是要找到使p(Y︱C)最大的。称logp(Y︱C)为C序列的似然函数。Cˆ对于二进制对称信道（BSC），码序列C的似然函数可写成：(10－6))1log()],()([log),()(logeepdmLnpdpCYCYCY)1log()(1log),(eeepmLnppdCYCˆ在维特比译码中，码序列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)()()(mLnjjjmLiiicydddcyCY10.2.3维特比译码算法最大似然译码准则译码方法在实际应用中能否实现与每一帧的节点数L有关。随着节点数L的增大，例如L＝50，k＝2，则网格图上可能的路径就有2kL＝2100＞1030条。显然，将接收序列Y与如此多的路径（码序列）进行比较是不现实的。因此必须寻找一种新的最大似然译码算法维特比（Viterbi）译码算法不是在网格图上一次比较所有可能的2kL条路径，而是采取接收一段，计算比较一段，选择一段最可能的码段，从而达到整条路径是一条有最大度量的路径。维特比译码算法使节点L的多少与译码的复杂性无关，L只与译码时间成线性关系。用维特比算法译码的具体步骤如下：（1）从第m节点（设l＝m）开始，计算并存贮进入网格图中每一状态的部分路径