什么是卷积码?

[拼音]：juanjima

[外文]：convolutional code

对信息序列不分组的纠错码，它的校验元不仅与当前的信息元有关，而且与以前有限时间段上的信息元有关。1955年由P.伊莱亚斯提出，虽经多年努力，在编码方法上还没有找到象分组码那样有效的数学工具和系统的理论。不过，卷积码在译码方面，不论在理论上还是在实用上都超过了分组码，因而在差错控制和数据压缩系统中得到广泛应用。

以二元码为例，编码器如图1。输入信息序列为u＝(u0，u1，…)，其多项式表示为u(x)＝u0+u1x＋…＋u


x


＋…。编码器的连接可用多项式表示为


(x)＝1+x+x2和


(x)＝1+x2，称为码的子生成多项式。它们的系数矢量


=(111)和


=(101)称作码的子生成元。以子生成多项式为阵元构成的多项式矩阵G(x)＝[


(x)


(x)]称为码的生成多项式矩阵。由生成元构成的半无限矩阵

称为码的生成矩阵。其中(11，10，11)是由


和


交叉连接构成。编码器输出序列为c＝u·G，称为码序列，其多项式表示为c(x)，它可看作是两个子码序列c


(x)和c


(x)经过合路开关S合成的，其中c


(x)＝u(x)·


(x)和c


(x)＝u(x)g


(x)，它们分别是信息序列和相应子生成元的卷积，卷积码由此得名。

在一般情况下，输入信息序列经过一个时分开关被分成k0个子序列，分别以u


(x)表示，其中i=1，2，…k0，即u(x)＝[u


(x)，…，u


(x)]。编码器的结构由k0×n0阶生成多项式矩阵

给定。输出码序列由n0个子序列组成，即

c(x)＝[c


(x)，c


(x)，…，c


(x)]，且c(x)=u(x)·G(x)。

若m是所有子生成多项式g


(x)中最高次式的次数，称这种码为(n0，k0，m)卷积码。

输出子序列中的每个数字都与存储在移位寄存器中的各输入子序列的(m+1)位数字有关，总共与n


＝(m＋1)k0个信息数字有关，n


称为编码约束长度。

编码器可看作是有限状态线性网络，移位寄存器中的存数可看作是状态。如(2，1，2)码有四个状态：ɑ=00，b=01，c=10和d=11。可用有向图表示输出、输入和状态的关系(图2)。要展示输入和输出的所有可能情况，可将状态图展示成树图(图3)。图中的粗体线表示输入序列 u=(1011100…)时编码器沿树图走过的路径，相应的输出序列c=(111000011001111)。在q无编码时，每个节点的分支数为q


个。卷积码各分支间具有线性关系，它是一般树码的一个子类。

若将树图中同一级节点上所有相同状态的各分支合并，便构成图4中的格图。它能更简洁地描述卷积码，因此卷积码又称格码。

用cL表示码树中L分支长的路径或码段，d(cL，cL)表示同段上两个不同路径cL和cL之间的汉明距离。称

为L长码段上的最小距离；称dmin(nA)为码的最小距离，以dmin表示，它和分组码的最小距离相当。称dmin(∞)为码的自由距离，以df表示。一般df≥dmin，上例的df=5，dmin=3。自由距离在卷积码的研究中有重要作用。但尚无系统的代数方法，在给定n0、k0和m下构造dmin和df尽可能大的码，实用中常用计算机搜索。

类似于分组码，卷积码可分为系统码和非系统码、纠正独立错误和纠突发错误码以及择多逻辑可译卷积码。

若信道干扰序列为


，其中


。接收序列为


，其中


和





。这里“+”为模 2 运算(q=p


元码按模p运算)。译码就是根据编码规则和信道干扰的统计特性，对信息序列u(x)作出估值的方法。常用的有三类译码方法，即代数译码、维特比译码和序贯译码。

代数译码是将卷积码的一个编码约束长度的码段看作是[n0(m+1)，k0(m+1)]线性分组码，每次根据(m+1)分支长接收数字，对相应的最早的那个分支上的信息数字进行估计，然后向前推进一个分支。上例中信息序列


＝(10111)，相应的码序列 c＝(11100001100111)。若接收序列R＝(10100001110111)，先根据R的前三个分支（101000）和码树中前三个分支长的所有可能的 8条路径(000000…)、(000011…)、(001110…)、(001101…)、(111011…)、(111000…)、(110101…)和(110110…)进行比较，可知(111001)与接收序列(101000)的距离最小，于是判定第 0分支的信息数字为 0。然后以R的第 1～3分支数字(100001)按同样方法判决，依此类推下去，最后得到信息序列的估值为


=(10111)，遂实现了纠错。这种译码法，译码时采用的接收数字长度或译码约束长度为(m+1)n0，所以只能纠正不多于(dmin-1)/2个错误(n


长上的)。实用中多采用反馈择多逻辑译码法实现。

维特比译码是根据接收序列在码的格图上找出一条与接收序列距离（或其他量度）为最小的一种算法。它和运筹学中求最短路径的算法相类似。若接收序列为R=(10100101100111)，译码器从某个状态，例如从状态ɑ出发，每次向右延伸一个分支（对于l＜L，从每个节点出发都有2


=2种可能的延伸，其中L是信息序列段数，对l≥L，只有一种可能），并与接收数字相应分支进行比较，计算它们之间的距离，然后将计算所得距离加到被延伸路径的累积距离值中。对到达每个状态的各条路径（有2


=2条）的距离累积值进行比较，保留距离值最小的一条路径，称为幸存路径（当有两条以上取最小值时，可任取其中之一），译码过程如图5。图中标出到达各级节点的幸存路径的距离累积值。对给定 R的估值序列为


=(10111)。这种算法所保留的路径与接收序列之间的似然概率为最大，所以又称为最大似然译码。这种译码的译码约束长度常为编码约束长度的数倍，因而可以纠正不多于(df/2)个错误。

维特比译码器的复杂性随m呈指数增大。实用中m不大于10。它在卫星和深空通信中有广泛的应用。在解决码间串扰和数据压缩中也可应用。

序贯译码是根据接收序列和编码规则，在整个码树中搜索（既可以前进，也可以后退）出一条与接收序列距离（或其他量度）最小的一种算法。由于它的译码器的复杂性随m值增大而线性增长，在实用中可以选用较大的m值（如20～40）以保证更高的可靠性。许多深空和海事通信系统都采用序贯译码。