卷积码的译码方法

1.卷积码的距离特性

同分组码一样,卷积码的纠错能力也由距离特性决定,但卷积码的纠错能力与它采用的译码方式有关,因此不同的译码方法就有不同的距离度量。称长度为N·n的编码序列之间的最小汉明距离为最小距离dmin;称任意长的编码序列之间的最小汉明距离为自由距离dfree。由于卷积码并不划分为码字,因而以自由距离作为纠错能力的度量更为合理。对于卷积码中广泛采用的维特比译码算法,自由距离dfree是个重要参量。一般情况下,在卷积码中dmin≤dfree。

由于卷积码的线性性质,所有码序列之间的最小汉明距离应该等于非全“0”码序列的最小汉明重量,因此不论求dmin还是dfree都只需考虑码树下半部的码序列。例如图10.6.2所示(2,1,3)卷积码的最小码距,由于约束长度N=3,所以只求树状图中下半部所有三条支路路径的汉明重量即可。包含三条支路的路径共4条:abca、abcb、abdc和abdd,汉明重量分别为5、3、4、4,所以dmin=3,表明了卷积码在连续N段以内的距离特性。

求dfree时必须对任意长度的路径加以考察。但由于dfree是有限的,而且由于路径的汉明重量在与全0路径汇聚以后不再增长,所以与dfree对应的路径最后必然汇聚到全0路径上。因此dfree可以从全0序列出发,再回到全0序列的所有非0路径中求得。这可以利用网格图,从图10.6.5容易看出产生dfree的路径为abca,相应的输出码序列为110111,所以有dfree=5。

2.卷积码的译码

卷积码的译码分为代数译码和概率译码两大类。卷积码发展的早期多采用代数译码,现在概率译码已越来越被重视。概率译码算法主要有维特比译码和序列译码。由于维特比译码在通信中用得更为广泛,因此这里仅介绍维特比译码。

维特比译码算法采用的是最大似然算法。它把接收码序列同所有可能的码序列作比较,选择一种码距最小的码序列作为发送数据。

在如图10.6.7所示的卷积码编译码系统中,若输入信息序列M被编码为序列X,此X序列可以用树状图或网格图中某一特定的路径来表示,这里假设X序列经过有噪声的无记忆信道传送到接收端译码器。

图10.6.7　编译码系统模型

离散无记忆信道是一种具有数字输入和数字输出(或称为量化输出)的噪声信道的理想化模型,其输入X是一个二进制符号序列,而输出Y则是具有J种符号的序列。X序列每发一个符号xi(i=1,2),则信道输出端收到一个相应的符号yj(j=1,2,3,…,J)。由于是无记忆,故yj只与xi有关。如果J=2,则离散无记忆信道输出的是二进制序列。

译码器对信道输出序列Y进行考察,以判定长度为L的2L个可能发送的序列中究竟是哪一个进入了编码器。当某一特定的信息M进入编码器时,发送序列为X(M),接收到的序列为Y,若译码器输出为M′≠M,说明译码出现了差错。

假设所有信息序列是等概率出现的,译码器在收到Y序列情况下,若

则判定输出为M′,这样可以使序列差错率最小。如此得到的译码器可以认为是最佳的,称为最大似然序列译码器,条件概率P[Y/X(M)]称为似然函数。所以,最大似然译码器判定的输出信息是使似然函数为最大时的消息。(www.xing528.com)

对于长度为L的二进制序列的最佳译码,需要对可能发送的2L个不同序列的2L条路径似然函数进行比较,选取其中最大的一条。显然,译码过程的计算量随L的增加而指数增长,这样很难实现,实际当中只能采用次最佳的译码方法。这种基于树状图的译码方法,正是序列译码法的基础。

用网格图描述时,由于路径的汇聚消除了树状图中的多余度,译码过程中只需考虑整个路径集合中那些能使似然函数最大的路径。如果在某一节点上发现某条路径已不可能获得最大对数似然函数,那么就放弃这条路径,然后在剩下的路径中重新选择译码路径,这样一直进行到最后第L级。由于这种方法较早地丢弃了那些不可能的路径,从而减轻了译码的工作量,维特比译码正是基于这种想法。

卷积码网格图中共有2(kN-1)种状态,每个节点(即每个状态)有2k条支路引入,也有2k条支路引出。这里讨论k=1的情形,若起始点为全0状态,由网格图的前N-1条连续支路构成的路径互不相交,即最初的2N-1条路径各不相同,当接收到第N条支路时,每条路径都有2条支路延伸到第N级上,而第N级上的每两条支路又都汇聚在一个节点上。在维特比译码算法中,把汇聚在每个节点上的两条路径的对数似然函数累加值进行比较,然后把具有较大对数似然函数累加值的路径保存下来,而丢弃另一条路径,经挑选后第N级只留下2N-1条路径,选出的路径连同它们的对数似然函数累加值一起被存储起来。由于每个节点引出两条支路,因此以后各级中路径的延伸都增大一倍,但比较它们的似然函数累加值后,丢弃一半,结果留存下来的路径总数保持常数。由此可见,上述译码过程中的基本操作是“加—比—选”,即每级求出对数似然函数累加值,然后两两比较并作出选择。有时会出现两条路径的对数似然函数累加值相等的情形,在这种情况下可以任意选择其中一条作为“幸存”路径。

既然在每一级中都有2N-1条幸存路径,那么当序列发送完毕后,如何判断其最后结果呢?这就要在网格图的终结处加上N-1个已知信息(即N-1条已知支路)作为结束信息。在结束信息到来时,由于每一状态中只有与已知发送信息相符的那条支路被延伸,因而在每级比较后,幸存路径减少一半。因此,在接收到N-1个已知信息后,在整个网格图中就只有唯一的一条幸存路径保留下来,这就是译码所得的路径。也就是说,在已知接收到的序列情况下,这条译码路径和发送序列是最相似的。

维特比译码过程并不复杂,译码器的工作是前向的、无反馈的。由于每级中每个状态上要进行“加—比—选”运算,因此译码器的复杂性与状态数成正比,同时随约束长度N的增加而指数增长。译一个L位码的序列,译码操作的总次数为L2N-1,当L＞N时,L2N-1将比用树状图进行最大似然译码所需的操作次数2L-1小很多。然而,维特比译码的运算量仍然是随N成指数增加的,因此目前只限于应用在约束长度较短(N≤10)的卷积码中。

维特比译码的具体步骤以(2,1,3)卷积码(如图10.6.2所示)的网格图(如图10.6.5所示)为例归纳如下:

(1)该(2,1,3)码的编码约束度为3,所以先用前3组接收子码序列为标准,与到达第3级4个节点的8条路径对照,计算8条路径与送入译码器的序列Y在等长范围内的汉明距离,为每一个节点挑选并存储一条到达本节点码距最小的路径作为幸存路径。

(2)将当前节点移到第4级,此时刻第3级选出的4条幸存路径又延伸为8条,计算这8条路径和接收序列Y在等长范围内的汉明距离,仍为各个节点挑选有最小距离的幸存路径(遇到进入某节点的两条路径距离相同时可以随机留存)。

(3)重复步骤(2),直到第6级,选出到达节点a和c的两条幸存路径(此时到终点a只可能从第6级的a、c点出发),最后剩下一条到达第7级终点a的幸存路径对应的就是译码器输出的码序列M′。

显然,维特比译码并不能纠正所有可能发生的错误,当错误模式超出卷积码的纠错能力时,译码后的输出序列就会带有错误。

一般的维特比译码器方框图如图10.6.8所示。

由于卷积码的优异性能,它在很多方面得到了应用,主要应用于加性白色高斯噪声信道,特别是在卫星通信和空间通信中。一般与PSK或QPSK调制结合起来使用。

为了比较编码后系统与未编码系统的性能,常常用相同误比特率时所需要的Eb/n0作为度量,其中Eb为单位码元能量,n0为噪声功率谱密度。编码增益为未编码系统所需要的Eb/n0与编码后系统的Eb/n0之差。正的编码增益意味着编码后系统为达到相同的误码率可以节省发射功率。如编码增益为3dB时,可以将发射功率降低为1/2。当然,与此同时,如果传输频带不变,则信息传输率势必下降为Rc=k/n倍。或者说,如果要保持信息传输率不变,则必须增加传输频带。在功率受限的卫星信道中,传输频带往往不是主要矛盾,而降低发射功率则是最重要的。

图10.6.8　维特比译码器原理方框图