一种适用于T-TCM系统的简化的Log-Map算法

王建，李建平

(中国传媒大学 信息工程学院，北京100024)

1 引言

Turbo网格编码调制(T-TCM)[1]把网格编码调制[2，3]和Turbo编码[4]结合在一起，它可以同时获得卓越的编码增益和频带效率，与此同时，它却引入了更高的译码复杂度[5]。逐符号的Log-MAP算法把MAP算法引入对数域，它是高斯白噪声环境下的最佳译码算法[6-8]。但是，对于Log-MAP算法来说，从一个巨大的对数表中查找数据是一个相当耗费时间的过程。MAX-Log-MAP(以后简称MLM)算法以其简单的复杂度成了Log-MAP算法的一大候补，但是由于损失了大量性能增益，因此它是一种次优算法[9-11]。Improved MAX-Log-MAP[12]算法实现了在性能和复杂度上的折中，然而它却引入了不能带来性能增益的冗余计算，此外，在很多情形下，它和MAX-Log-MAP是等价算法。显然，提出一种既能实现好的性能又能有效降低复杂度的算法是非常必要的。

在本文中，我们提出了一种简化Log-MAP算法(以后简称SLM)，它可以用非常低的复杂度在硬件轻松实现。我们的算法是在improved MAX-Log-MAP(IMLM)算法基础上对Log-MAP(LM)算法的一种改进，它可以提供和LM几乎等价的性能。

文中其余部分按以下方式组织：在第二部分，我们介绍译码算法，包括传统的译码方法和我们提出的译码方法；在第三部分，我们描述本中提出算法的详细硬件实现过程；在第四部分，我们将描述实验仿真结果，包括性能仿真和复杂度分析两部分；最后，我们在第五部分得出结论。

2 T-TCM译码算法

2.1 传统的译码算法

在这里，我们简单介绍一下现存的几种经典译码算法，详细的算法描述可以参考文献[12]。

Log-MAP算法的关键是计算信息比特xk的对数先验概率(LLR)值，可以用以下公式计算：

(1)

在这里，R表示接收到的信息序列。

根据译码网格图，(1)式可以修改为下式：

(2)

在这里，是发送的信息序列，s和s′分别代表在k时刻和k-1时刻的状态。把 R分成三部分，我们可以得到如下表达式：

p(s′，s，R)=p(Rt>k|s)p(s，Rk|s′)p(s′，Rt

(3)

定义下面三式：

αk(s′)=p(s′，Rt

(4)

βk+1(s)=p(Rt>k|s)

(5)

γk(s′，s)=p(s，Rk|s′)，

(6)

我们可以把(3)式重写为如下表达式：

p(s′，s，R)=αk(s′)γk(s′，s)βk+1(s)

(7)

这里α，β和γ分别表示前向度量、后向度量和分支度量。我们用下式对α，β和γ重新表示：

(8)

(9)

(10)

这里σk和σk+1分别表示在k时刻和k+1时刻的所有状态的集合，Lc是信道置信度。

下式是雅克比变化式，利用它可以避免复杂的指数求和运算：

max*(x，y)=ln(ex+ey)

=max(x，y)+ln(1+e-|x-y|)

(11)

这里ln(1+e-|x-y|)是译码校正项，它的存在使Log-MAP算法有着最佳的性能。利用雅克比变换式，我们可以引入以下对数域度量：

(12)

(13)

γk(s′，s)=lnγk(s′，s)

(14)

随后，我们利用上面三式利用前向递归和后向递归运算去计算α和β，这个过程可以参照图1。

最后，LLR值可以通过下式计算：

(15)

LLR值同样也是用递归运算计算，详情见图2。

图1 式(12)的前向递归和式(13)的后向递归运算

图2 LLR值得递归运算过程

MAX-Log-MAP算法以其简单的复杂度而被广泛使用，它通过修改雅克比变化式(11)得到。在这里，雅克比变化式中的对数项被省略，修改后如下：

max*(x，y)≈max(x，y)

(16)

最后，LLR被重写为下式：

(17)

Improved MAX-Log-MAP算法利用了迈克劳林展开式，它把式(13)修改为下式[13]：

(18)

2.2 本文提出的算法

我们先看Log-MAP 算法，式(11)中的校正项ln(1+e-|x-y|)虽然使其成为最优算法，但是也带来了许多问题。首先，把ln(1+e-|x-y|)的计算结果保存到对数表中会引入由截断引起的量化错误；其次，对数表需要设定大范围的信噪比，这样会大大提高硬件花费；最后，从对数表中读取数据也是一个非常耗时的过程。

显然，如何用函数近似ln(1+e-|x-y|)是解决问题的关键。我们对式(18)进一步推导，过程如下：

令|x-y|=t，式(18)可等价为下式：

(19)

当t<1.3862时，我们可以对x和y进一步讨论。

情况1：当x>y时，有：

(20)

情况2：当x

(21)

显然无论x与y哪个值大，我们都可以得到以下恒等式

(22)

最后，式(19)可以用下式表示：

(23)

用式(23)计算前向度量αk(s)，后向度量βk(s)以及LLR值，我们得到了简化的Log-MAP算法。由于我们是对校正项ln(1+e-|x-y|)进行数学逼近，因此我们的算法可以实现和Log-MAP算法几乎等价的性能。同时，又由于式(23)和式(18)是恒等式，因此我们的算法可以实现与improved MAX-Log-MAP算法完全等价的性能。此外，由于算法中只有简单的加法和乘除2运算，它可以用非常低的复杂度轻松在硬件实现。

3 硬件实现

图3 不同状态的节点计算单元

图4显示了计算αk(s)的详细硬件实现过程，βk(s)和LLR也是用类似的方法实现。从图4可以看出，我们提出的简化算法的实现过程远比Log-MAP算法和improved MAX-Log-MAP算法的实现过程简单。

图4 提出算法的详细硬件实现过程

4 仿真结果

4.1 性能比较

我们分别在生成多项式g1=[7，5]和 g2=[11，13]两种情形下做仿真实验。在实验中，我们把交织长度(记作N)设为1024，编码效率(记作R)设成1/3，最大迭代次数设为6次。我们只考虑高斯白噪声(AWGN)环境和BPSK调制方法。

图5展示了生成多项式g1=[7，5]的仿真结果。四条线显示了我们提出算法和LM，MLM以及IMLM的对比。图6展示和图5类似的仿真结果，但是它的生成多项式改为g2=[11，13]。

图5 四种算法的BER性能比较，生成多项式g1=[7，5]，N=1024，BPSK调制，AWGN信道

图6 四种算法的BER性能比较，生成多项式g2=[11，13]，N=1024，BPSK调制，AWGN信道

从图5和图6我们可以看出，和MLM算法相比，SLM，IMLM和LM算法在性能方面有着明显的优势，我们提出的简化算法SLM比MLM算法额外获得0.3db的性能增益。此外，从仿真结果我们还可以看出SLM和IMLM有着完全等价的性能，且这个性能非常接近LM。

4.2 复杂度分析

要想计算我们提出算法的复杂度，必须先计算αk(s)，βk(s)以及LLR在t位于不同区间时的概率。我们选择5个信噪比做仿真实验得到大量统计数据，然后分别计算在区间(0，1.3862)以及区间(1.3862，∞)的平均值，然后分别记作p1，p2，这两个值如下式所示：

(24)

通过参考文献[13]和文献[14]，我们计算得到表1，表中的M是编码器的约束长度。

从表1我们可以清楚地看出，SLM算法不需要进行复杂的对数运算，并且它的复杂度比IMLM算法降低了大约39%。

表1 四种译码算法的复杂度比较

5 结论

我们在文中提出了一种简化的Log-MAP算法，该算法利用一种非常简单的分段函数代替了对数校正项。从实验仿真结果我们可以看出我们提出的算法实现了和Log-MAP非常接近的性能，并且它不用进行复杂的对数查表运算。和文献[12]提到的improved MAX-Log-MAP算法相比，它再提供与其完全等价的性能的同时，降低了大约39%计算复杂度。文中提出的算法易于在硬件实现，它可以轻松地应用在T-TCM系统中。

[1]S Robertson，Worz T.Bandwidth-efficient turbo trellis-coded modulation using punctured component codes[J].IEEE J Sel Areas Commun，1998，16(2)：206-218.

[2]Ungerboeck G.Channel coding with multilevel/phase signalling[J].IEEE Trans Inf Theory，1982，25(1)：55-67.

[3]Sybis，Michal.Branch canceling technique for turbo TCM decoding[J].IEEE European Wireless Conference，2012，1-5.

[4]Ji Hoon Kim，In CheolPark.Bit-Level extrinsic information exchange method for double-binary turbo codes[J].IEEE Transactions，56(1)：81-85.

[5]Sybis S.Log-MAP equivalent Chebyshev inequalitybased algorithm for turbo TCM decoding，Electron Lett，2011，47(18)：1049-1050.

[6]D Mackay.Good error correcting codes based on very sparse matrices[J].IEEE Trans Inform Theory，vol 45，1999，399-431.

[7]L Bahl，J Cocke，J Jelinek，J Raviv，F Raviv.Optimal decoding of linear codes for minimizing symbol error rate[J]. IEEE Trans Inform.Theory，vol IT- 20，1974，284-287.

[8]Xiaoyi Li，Zhao Fang.Research on improved turbo-codes decoding algorithm [J].Computer 2009(25)：230-232.

[9]C Berrou，A Glavieux，P Thitimajshima.Near Shannon limit error-correcting coding and decoding：Turbo-codes[J].Proc ICC ’93，1993，1064-1070.

[10]Robertson P，Hoeher P，Villebrun E.Optimal and sub-optimalmaximum a posteriori algorithms suitable for turbo decoding[J].Eur Trans Telecommun，1997，8(2)：119-125.

[11]J P Woodard，L Hanzo.Comparative study of turbo decoding techniques：An overview[J].IEEE Trans Veh，Technol，49(6)：2208-2233，2000.

[12]S Talakoub，L Sabeti，B Shahrrava，M Ahmadi.An improved Max-Log-MAP algorithm for turbo decoding and turbo equalization[J].IEEE Trans.on Instrumentation and measurement，56(3)：1058-1063，2007.

[13]Park S J.Combined Max-Log-MAP and Log-MAP of turbo codes[J].Electron Lett，2004，40(4)：251-252.

[14]Robertson P，Villebrun E，Hoeher P.A comparison of optimal and sub-Optimal MAP decoding algorithms operating in the Log domain[J].IEEE International Conference on 1822，1995，1009-1013.

[15]S Lin，Daniel，J Costello.Error Control Coding (Second Edition)[M].Beijing：China Machine Press，2007，372-378，478-484 .