深入探究卷积码的描述

描述卷积码的方法有两类:解析表示和图解表示。

1.卷积码的解析表示

一般有两种解析表示法描述卷积码,它们是移位算子(延迟算子)多项式表示法和半无限矩阵表示法。

在移位算子多项式表示中,编码器中移位寄存器与模2和的连接关系以及输入、输出序列都表示为移位算子x的多项式。一般情况下,输入序列的二进制表示为m1,m2,m3,m4,…,则输入序列可表示为

这时移位算子x的幂次等于相对于时间起点的单位延时数目,时间起点通常选在第1个输出比特。

例如,输入序列若为10111001…,可表示为

用x算子多项式表示移位寄存器各级与各模2和连接关系的方法是:若某级寄存器与某模2和相连,则多项式中相应项的系数为1,否则为0(表示无连接线)。以图10.6.2所示的(2,1,3)卷积码为例,上、下两个模2和与寄存器各级的连接关系可表达为

可见,在卷积码中连接关系多项式的个数由n的个数决定;连接关系多项式的系数表示某级是否与模2加法器连接(1表示相连,0表示不相连),最左边的级对应着连接关系多项式的最低幂次。这样,有n个连接关系多项式,且连接关系多项式的最高次数为kN-1。上例中n=2,输出引自2个模2加法器,所以就有2个连接关系多项式与其对应,并且连接关系多项式的最高幂次均为2。

通常把表示移位寄存器与模2和连接关系的多项式称为生成多项式,因为可以用输入序列多项式和生成多项式相乘计算出输出序列。一个生成多项式gi(x)对应于子码的一个输出yi,j(x),写成通式为

即对应一位输出码元,必须由n个生成多项式才可以得到编码器的n位输出序列。

例10.6.1 图10.6.2所示的卷积码编码器,设输入信息序列m=1011,求与其对应的输出码序列。

解 输入序列多项式为m(x)=1+x2+x3,依式(10.6.4)计算

所求输出码序列为

则

这里需要注意的是在计算式(10.6.4)时采用模2加运算。

由以上分析可以看出,在编码效率k/n及约束长度相同时,采用不同的生成多项式所得到的卷积码是不同的。那么如何选择生成多项式,以获得最佳的纠错能力,显然是一个非常重要的问题,对于这个问题这里不作讨论,有兴趣的读者可参阅有关文献。

另一种解析表示方法是采用半无限矩阵和矢量。在这种方法中,输入信息序列和输出序列都用半无限矢量表示。输入信息序列表示为

对于图10.6.2的卷积码,其输出序列可表示为

若移位寄存器起始状态为全0,那么第1位信息码输入时,输出的两位分别为

第2位信息码输入时,m1右移一位,输出为

第3位信息码输入时,m1右移两位,输出为

第j位信息码输入时,输出为

表示成矩阵形式为

式中,

当第1,2位信息码输入时有一个过渡过程,即

式中,

综合以上编码过程,可以得到输出序列矩阵和输入序列矩阵的关系式为(www.xing528.com)

式中,半无限矩阵G称为生成矩阵,即

式中,矩阵的空白区元素均为0。式(10.6.10)与分组码的表示方法相同,不过分组码的生成矩阵是有限矩阵。

生成矩阵与生成多项式之间有着确定的关系。上述卷积码的生成多项式表示成二进制序列为

把生成序列g1、g2按下列顺序排列,就可以得到生成矩阵

代入gij值后所得结果与式(10.6.10)相同。式(10.6.12)还可以表达为

式中,每个子矩阵Gi(i=1,2,3)为

对于一般情况的(n,k,N)码,输入序列矩阵和输出序列矩阵为

码的生成序列一般表示为

式中,i=1,2,…,k;j=1,2,…,n;L=1,2,…kN;gLi,j表示每组k位输入码中第i位码经L-1位延迟后的输出端与每组n位输出码中第j位码模2加法器的输入端的连接关系,gLi,j=1表示有连线,gLi,j=0表示没有连线。这样可以写出(n,k,N)码的生成矩阵的一般形式为

式中,GL(L=1,2,…,kN)是k行n例子矩阵,即

可见,构造生成矩阵的关键是寻找第一行(称为基本生成矩阵),以后的每一行都是对上一行向右延迟n位得到。

2.卷积码的图解表示

卷积码编码过程有三种图解表示方法,即树状图、网格图和状态图。

(1)树状图

对不同的输入信息可以利用上述解析方法求出输出码序列。若将这些序列画成树枝形状就得到树状图,或叫做码树图,并且码树可一直向右延伸,所以又称为半无限码树图。它描述了输入任何信息序列时,所有可能的输出码字。与图10.6.2中(2,1,3)编码电路对应的码树示于图10.6.4中。图中每个分支表示一个输入符号。通常输入码元为0对应上分支,输入码元为1对应下分支。每个分支上面标示着对应的输出,从第三级支路开始码树呈现出重复性(自上而下重复出现a、b、c、d四个节点),表示从第4位数据开始,输出码字已与第1位数据无关,它解释了编码约束长度N的含义。

图10.6.4　(2,1,3)卷积码的码树表示

树状图从节点a开始画,此时移位寄存器状态(即存储内容)为00。当第一位输入码元m1=0时,输出码元y1,1y2,1=00;若m1=1,则y1,1y2,1=11。因此从a点出发有两条支路(树叉)可供选择,m1=0时取上面一条支路,m1=1时则取下面一条支路。输入第二位码元时,移位寄存器右移一位后,上支路情况下移位寄存器的状态仍为00,下支路的状态则为01,01状态记作b。新的一位输入码元到来时,随着移位寄存器状态和输入码元的不同,树状图继续分叉成4条支路,2条向上,2条向下。上支路对应于输入码元为0,下支路对应于输入码元为1。如此继续下去,即可得到图10.6.4所示的二叉树图形。树状图中,每条树叉上所标注的码元为输出码元,每个节点上标注的a、b、c、d为移位寄存器的状态,a表示mj-2mj-1=00,b表示mj-2mj-1=01,c表示mj-2mj-1=10,d表示mj-2mj-1=11。显然,对于第j位输入信息码元,有2j条支路,但在j=N≥3时,树状图的节点自上而下开始重复出现4种状态。

以图10.6.2为例,当输入序列为1011时,对应的输出码序列为11010010。画出的编码路径如图10.6.4中黑粗线所示。

(2)网格图

如果把码树中具有相同状态的节点合并,就可以得到网格图。与码树中的规定相同,输入码元为0对应上分支(用实线表示);输入码元为1对应下分支(用虚线表示)。网格图中支路上标注的是输出码元。图10.6.5表示的是上述(2,1,3)卷积码的网格图。

图10.6.5　(2,1,3)卷积码的网格图表示

当输入序列为1011时,图10.6.4中黑粗线所对应的输出码序列路径在网格图中如图10.6.5中黑粗线所示。

(3)状态图

图10.6.6　(2,1,3)卷积码的状态图

状态图表示的是编码器中移位寄存器存数状态转移的关系。上述(2,1,3)卷积码k=1,寄存器级数为2,所以有4级状态00、01、10、11分别记为a、b、c、d,与其对应的状态图示于图10.6.6中。状态转移路线上端的数字表示输入信息码元,状态转移路线下端的数字表示与其对应的输出。

以输入1011为例,移位寄存器的状态由初始状态a依次变化为b、c、b、d,相应的输出码元序列仍然是11010010。

上述三种图解表示方法,都是以图10.6.2所示(2,1,3)编码电路的卷积码为例给出的。对于一般的(n,k,N)卷积码,可以由此推广出来以下结论:

①对应于每组k个输入比特,编码后产生n个输出比特。

②树状图中每个节点引出2k条支路。

③网格图和状态图都有2(kN-1)种可能的状态。每个状态引出2k条支路,同时也有2k条支路从其他状态或本状态引入。