采用近似max*运算的Log-MAP译码算法

孙增友　李欢欢　王　蒙　王景芹

1(东北电力大学信息工程学院　吉林 吉林 130012)2(河北工业大学电气工程学院　天津 300130)



采用近似max*运算的Log-MAP译码算法

孙增友1李欢欢1王蒙2王景芹2

1(东北电力大学信息工程学院吉林 吉林 130012)2(河北工业大学电气工程学院天津 300130)

为有效降低Turbo码译码的硬件存储消耗，提出一种基于近似max*运算的改进的Log-MAP算法。并通过设计合适的数字电路来找出一组数据中最大的两个值嵌入到其相关函数项中，有效实现了低复杂度的Turbo译码器的硬件结构。实验结果表明，所提出的结构比ConstantLog-MAP算法结构平均简化了30%，达到了与Log-MAP几乎相同的误码率(BER)性能，降低译码的复杂度，便于实际工程应用。

Turbo码Log-MAP算法ConstantLog-MAP复杂度

0　引　言

Turbo码是在信道编码领域最大的成就之一。Turbo码编码方式以其接近香农极限的优越性能[1]，自1993年提出以来，受到了人们的广泛关注。Turbo码主要应用于无线通信领域。

Turbo编码通常指的是并行级联卷积码的结构，可以通过MAP算法、Log-MAP算法、Max-Log-MAP算法、SOVA算法等进行迭代译码。为降低译码过程中的计算复杂度，人们提出的各种算法均旨在简化Turbo译码算法Log-MAP算法中的max*运算，包括：改进的Max-Log-MAP算法、ConstantLog-MAP算法[5]、LinearLog-MAP算法等。这些次优算法采用近似的方法使得译码算法简化，但性能与最优算法相比略有损失。为了减少性能的损失，本文提出了一种基于近似的max*运算的Log-MAP译码算法。这种近似方法可以很好地降低每个译码步骤运算的复杂度，相对于传统的Log-MAP算法，性能降低很小。

1　Turbo码的译码方案

图1　Turbo码的迭代译码示意图

假设u是N比特的信息块。经过Turbo编码和BPSK调制，通过AWGN信道，接收的信息序列为y。在Turbo译码之前先进行软解调。设由输入引起的栅格由K-1时刻的状态S′转移为K时刻状态S。前向递归和后向递归可以递归计算为：

(1)

(2)

(3)

max*运算，可以利用Jacobian算法定义为：

max*(x1,x2)=ln(expx1+expx2)

=max(x1,x2)+ln{1+exp(-|x2-x1|)}

=max(x1,x2)+fc(|x2-x1|)

(4)

式中：fc(·)为相关函数。如果忽略相关函数的值，采用这种简化方法得到的就是Max-Log-MAP算法[7]。即令fc(|x2-x1|)=0，则：

max*(x1,x2)=max(x1,x2)

(5)

这种近似虽然大大简化了Max-log-MAP算法，也造成了性能上的损失。

SOVA算法是最大似然序列估计算法，最简单，同时性能也最差。而Log-MAP算法的复杂性约是SOVA的两倍左右。

三种不同译码算法BER性能仿真如图2所示。图2是基于MATLAB环境下，使用随机输入数据，编码器的RSC子码采用(13,15)码，码率为1/3，帧长为400，交织方式为随机交织，迭代5次，在高斯信道下采用BPSK调制。可以看出Log-MAP算法性能最好，Max-Log-MAP算法性能介于Log-MAP算法和SOVA算法之间，SOVA算法性能最差，比Log-MAP算法约差了0.8dB。

图2　三种不同译码算法的BER性能比较

2　Log-MAP算法的近似译码算法

2.1近似的max*运算

max*运算是Log-MAP算法的计算核心。当Turbo码编码器中寄存器个数为M时，译码器中存在2M个变量的max*运算，根据式(4)可知，多变量max*需要递归计算，当M≥3时硬件实现复杂，这也是硬件实现时少采用Log-MAP算法的关键原因，而采用Max-Log-MAP性能又有不少下降，因此提出一种改进的Log-MAP算法。

从式(3)中可以看出在Log-MAP算法中计算ln(expx1+…+expxn)表达式很必要。常规的Log-MAP算法采用式(4)中的max*运算。为了得到2个变量以上的max*运算，应用了递归Jacobian算法，如：

max*(x1,x2,x3)=max*{max*(x1,x2),x3}

(6)

为了降低对n个输入变量参数的max*运算近似算法的复杂度，针对这个问题，采用Chebyshev不等式，所提出的改进的Log-MAP算法的n输入max*运算为：

max*(x1+x2+…+xn)

(7)

由此所提出的改进的Log-MAP算法的n输入max*运算为：

max*(x1,x2,…,xn)≈y1+ln[(1+K1exp{-δ})]+K2

(8)

式中：y1=max{x1,x2,…,xn}n个输入值中第一个最大值，y2=max{x1,x2,…,xn/y1}是第二个最大值，δ=y1-y2，K1=(n-1)/n，K2=ln[2n/(n+1)]。近似的max*运算的第一项是一个简单的max运算，第二项可以认为是另一个校正功能的函数fc(·)。

式(8)中，K2是一个正常数，在迭代译码过程中可以忽略，当n的值很大时，K1≈1，所以式(8)可以简化为：

max*(x1,x2,…,xn)≈y1+ln(1+exp{-δ})=y1+fc(δ)

(9)

2.2max*运算中相关函数的实现

式(9)的实现需要设计合适的数字电路[8]找出y1和y2，计算出δ，然后应用于相关函数fc(·)。本文应用了ConstantLog-MAP算法的相关函数项，并在硬件实现的过程中做进一步改进，有效地将译码复杂度进一步降低，其相关函数曲线如图3所示。Log-MAP算法中的max*运算中相关函数fc(x)=ln{1+exp(-x)}，其中，x=|x1-x2|，函数曲线如图3所示。

图3　Log-MAP相关函数fc(x)和Constant Log-MAP算法的fc(x)

(10)

ConstantLog-MAP中的fc(x)是对Log-MAP中fc(x)的近似，在硬件实现Turbo码译码器时，可以通过ConstantLog-MAP算法的相关函数fc(x)进一步降低其复杂度。

因为式(9)中δ≥0，fc(δ)的实现可以更简化。设c是给定δ=δp-1…δ0时fc(δ)的取值，且c=cp-1…c0。可以看出：

1) 如果c=3/8，那么cp-1…c0=″0…0.011″，或cp-1…c0=″0…0.000″，(即，c0=c1且ci=″0″，2≤i≤p-1)。

2) 如果δ<2，那么δp-2…δ0=″0000x.xxx″(因为δ≥0，所以δp-1=″0″)，其中x任意表示为1或0， (即δj=′0′，2≤j≤p-2)。因此c0和c1仅当δj=0,4≤j≤p-2时等于1，即：

(11)

图4　改进的结构图(灰色框为改进部分)

(a) 2输入的MVG结构;(b)n输入的近似max*运算结构

3　仿真结果与比较

将所提出的近似max*运算方法，应用于Turbo译码中，对应信噪比下(Eb/N0)的BER(误码率)性能仿真如图5所示。其中，对4种译码算法进行仿真分析：①ConstantLog-MAP算法[5]，② 所提出的改进的Log-MAP算法，用Log-MAP-max*表示，③Log-MAP算法，④Max-Log-MAP算法。

仿真的Turbo码参数为移位寄存器具有16个状态，码率为R=1/2，生成多项式为(1,33/23)o分别代表前馈多项式和反馈多项式。信息序列N=103的比特，传输帧总数为106。为了保证仿真结果性能的准确性，每个性能仿真实验中至少引入了100个位错误。使用了伪随机Turbo交织器，在接收端最多进行10次迭代，采用BPSK调制，应用于CCSDS标准[3]中。

图5　不同译码算法的性能仿真比较

由图5可知，所提出的改进的Log-MAP算法，总是能达到接近最优的译码算法的BER性能，其译码复杂度接近Max-Log-MAP算法，而纠错性能显著优于Max-Log-MAP算法。因为改进的Log-MAP算法是对ConstantLog-MAP算法的简化，所以性能略差于ConstantLog-MAP算法，如在BER等于10-5时，相差不到0.1dB。在低误码率时，如10-6时，所提出的改进的译码算法可以实现与ConstantLog-MAP算法和Log-MAP算法基本上相同的BER性能。

4　译码复杂度分析

表1给出了所提出的n输入近似max*算法结构(用C表示)在空间(用A表示)和延迟(用D表示)两个方面与两种基于树结构的算法进行比较：① 基于3比特LUT的2输入的Log-MAP算法结构(用A表示)；② 2输入的ConstantLog-MAP算法结构[5](用B表示)。

表1　不同算法的硬件结构空间及延迟比较

实验均表明，所提出的算法结构C不但比算法结构A和算法结构B的空间大大减小，而且具有较低的延迟。如表1中，假设n=16，p=16时，所提出的算法结构C需要5768个等同的门，最小延迟为2 ns，而算法结构B需要7312个等同的门，最小延迟为2.8ns。因此所提出的算法结构空间减少了21%，延迟降为算法结构C的28.5%。在具有与ConstantLog-MAP算法(B)相同的延迟时(DB)作更近一步比较，对应的比较结果如表1中最后一列所示。可以看出，此时与算法B硬件复杂度相比，所提出的结构平均节省了大概30%的空间。

5　结　语

在Log-MAP译码算法中，对其译码过程中的max*运算进行新的近似。max*运算是广义上的对n个输入值计算的简化，将max*运算近似为简单的max运算和相关函数的计算。仿真结果表明，这种方法相对于Log-MAP译码算法，性能有很小的损失，从实践的角度来看，新的改进算法的优势是显著降低了每个译码步骤的译码复杂度，有利于译码器的硬件实现。

[1] Berrou C,Glavieux A,Thitimajhima P.Near Shannon limit error-correcting coding and decoding:Turbo codes[C]//Proc.ICC’93,1993:1064-1070.

[2] Bahl L R,Cocke J,Jelinec F,et al.Optimal decoding of linear codes for minimizing symbol error rate[J].IEEE Trans.Inform.Theory,1974,20(2):284-287.

[3] 张凯.CCSDS标准Turbo码译码器设计及实现[D].北京邮电大学,2013.

[4] 孙增友,张利杰,田勇.SF-MAX-Log-MAP并行译码算法及其在LTE中的应用研究[J].东北电力大学学报,2012,32(4):35-39.

[5] Gross W J,Gulak P G.Simplified MAP algorithm suitable for implementation of turbo decoders[J].IET Electron.Lett.,1998,34(16):1577-1578.

[6] Papaharalabos S,Sweeney P,Evans B G.SISO algorithms based on Log-MAP and Max-Log-MAP turbo decoding[J].IET Proc.Commun,2007,1(1):49-57.

[7] 刘东华.Turbo码原理与应用技术[M].北京:电子工业出版社,2004.

[8] Amarù L G,Martina M,Masera G.High speed architectures for finding the first two maximum/minimum values[J].IEEE Trans.Very Large Scale Integr.(VLSI) Syst.,2012,20(12):2342-2346.

LOG-MAPDECODINGALGORITHMUSINGAPPROXIMATEMAX*OPERATION

SunZengyou1LiHuanhuan1WangMeng2WangJingqin2

1(School of Information Engineering,Northeast Dianli University,Jilin 130012,Jilin,China)2(School of Electrical Engineering,Hebei University of Technology,Tianjin 300130,China)

InordertoeffectivelyreducetheconsumptionofTurbodecodinghardwarestorage,inthispaperweproposeanimprovedLog-MAPalgorithmwhichisbasedonapproximatemax*operation,andfindouttwomaximumvaluesinasetofdatathroughdesigninganappropriatedigitalcircuitandembedthemintotheircorrelatedfunctionterms,thuseffectivelyimplementthehardwarearchitectureofTurbodecoderwithlowcomplexity.Experimentalresultsshowthattheproposedarchitectureissimplerby30%onaveragethanthearchitectureofConstantLog-MAP,itreachestheBERperformancealmostthesameasLog-MAP’s,reducesthedecodingcomplexity,andisconvenientforpracticalengineeringapplication.

TurbocodesLog-MAPalgorithmConstantLog-MAPComplexity

2014-05-13。国家自然科学基金项目(51077039)。孙增友，高工，主研领域：无线电通信。李欢欢，硕士生。王蒙，硕士生。王景芹，教授。

TP3TN911.22

ADOI:10.3969/j.issn.1000-386x.2016.03.060