一种低复杂度的Log-MAP译码器结构

孙增友，李欢欢

(东北电力大学信息工程学院，吉林吉林 132012)

从1993年，Turbo码被 C.Berrou等人［1］提出以来，就以其优异的性能和相对简单可行的编译码算法吸引了众多研究者的目光。Turbo码的实质是并行级联的卷积码，它与以往所有码的不同之处在于它通过一个交织器的作用，达到接近随机编码的目的。它所采用的迭代译码策略，使得译码复杂性大大降低。Bahl等人［2］于1974年首次提出可以由最大后验概率(MAP)迭代译码算法进行译码。Turbo码已被应用于各种通信系统，如深空通信、蜂窝移动通信和卫星通信网络，并且作为第三代移动通信标准，如CDMA2000。

MAP译码算法由于存在非线性函数和大量的乘法和加法运算［3］，实际中Turbo码译码器的硬件实施很困难。因此，在次优译码算法——Log-MAP译码解决方案中，通常在对数域运算。次最优译码算法的目的是降低译码复杂度，同时保持编码的误码率(BER)性能在适度的水平，与最优译码(MAP)相比，只有很小分贝的译码性能损失。

近几年，提出的各种算法均旨在简化Turbo译码算法Log-MAP算法中的max*运算，包括:改进的Max-Log-MAP算法、Constant Log-MAP 算法［4］、Linear Log-MAP 算法、Lookup Log-MAP算法等。这些次最优算法采用近似的方法使得译码算法简化，但性能与最优算法相比略有损失，为了减少性能的损失，额外的修正项需要添加到max运算中。本文提出了一种新的max*运算的近似方法，应用于Turbo码的Log-MAP译码算法中。这种近似方法可以很好地降低每个译码步骤运算的复杂度，相对于传统的Log-MAP算法，性能降低很少。

1 Turbo码的编译码

1.1 Turbo码编码方案

基于并行级联卷积码(PCCC)的Turbo码编码器结构图如图1所示，在Turbo码编码过程中，信息序列u={u1，u2，…，uN}经过交织器后，形成一个新的序列u'={u1'，u2'，…，uN'}。然后将这两个序列u和u'分别传送到两个分量编码器(RSC1，)中进行编码，令生成的编码序列分别为Xp1和Xp2，经过删余器，删除一些校验位，形成新的校验序列Xp，这样做的目的是为了提高码率和系统频谱效率。最后将校验序列Xp与未编码的系统信息Xs经过复接器生成Turbo码的编码序列X。

图1 PCCC型Turbo编码结构

1.2 Turbo码译码方案

Turbo码译码是基于两个SISO译码器之间的迭代过程。如图2所示，第一个SISO译码器的输入端是由比特先验信息Lin，2，经信道传输的信息比特rs，以及第一个编码器输出的校验比特rp，1这3部分构成。然后产生一个软输出值Le，1，作为随后SISO译码器2的先验信息Lin，2，称为外部信息。SISO译码器2的输出经过解交织后作为先验信息Le，2又反馈给SISO译码器1作为输入，这样就完成了一次迭代的过程。经过一定的迭代次数后，SISO译码器2的输出L^u，2进行解交织后经硬判决就是Turbo码的译码输出。

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

工程中常用的译码算法有基于最大后验概率的软输出算法和软输出Viterbi算法两大类。由于MAP算法中的Log-MAP和Max-Log-MAP计算复杂度较低而更适合并行计算。假设u是N比特的信息块。经过Turbo编码和BPSK调制，通过AWGN信道，接收的信息序列为y。在Turbo译码之前先进行软解调。设由输入引起的栅格由K-1时刻的状态S'转移为K时刻状态S。前向递归和后向递归可以递归计算为［5］

式中:¯αk和 ¯βk应先进行初始化［2］;¯γk是在迭代过程中与之对应的栅格状态过渡的分支转移概率。传输比特uk的译码软输出，可以用对数似然比(LLR)计算，即

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

式中:fc(·)为相关函数。为了使得Log-MAP算法复杂度最低，相关函数fc(·)可由查找表来实现。如果忽略相关函数的值，采用这种简化方法得到的就是Max-Log-MAP算法［6］。

2 Log-MAP近似译码算法

2.1 简化的max*运算

max*运算是Log-MAP算法的计算核心。当编码器中寄存器个数为M时，译码器中就有2M个max*运算，且max*运算需要递归运算，当M≥3时，这种算法硬件实现复杂，而采用Max-Log-MAP算法译码后性能损失很大，因此提出一种简化的Log-MAP算法。

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

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

在计算信息比特的L(uk)时，式(3)中的max*运算用式(7)中的max运算。而对式(1)和式(2)中2个变量的max*运算均如式(4)作精确计算。

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

3.2 max*运算中相关函数的实现及硬件结构简化

式(8)的实现需要设计合适的数字电路找出y1和y2，计算出δ，然后应用于相关函数fc(·)。在文献［7］中提出的一种有效的基于树结构的最大值产生器(MVGs)，用于从n个元素中找出y1和y2。这种结构由2个(n/2)-MVG结构和3个最大值单元(MVUs)组成，如图3所示。则式(8)可以通过一个n-MVG结构结合减法器计算δ，利用查找表(LUT)计算fc(δ)的值，再通过加法器实现。其中，s表示A-B。

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

Log-MAP算法中简化的max*运算中的相关函数曲线fc(x)=lg(1+e-x)和Constant Log-MAP算法的近似的相关函数fc(x)如图4所示。Log-MAP算法的近似算法中，Constant Log-MAP算法具有最低的复杂度，并且接近最优的Turbo码BER性能。

图4 Log-MAP相关函数fc(x)和近似的fc(x)

Constant Log-MAP相关函数算法［4］为一个8位二进制的补码整数运算，数值表示为5个整数位和3个小数位，因此，fc(x)的最小值为1/8，对应x的最大值为2.0。如果x≥2，那么fc(x)≈0。另外，根据文献［4］，当x ＜2，fc(x)可以近似为［0，2)的平均值，即，最佳取值为fc(x)≈3/8(即0.375)，因此Constant Log-MAP算法的近似相关函数fc(x)为

Constant Log-MAP算法可以通过其相关函数fc(x)的实现进一步降低其硬件结构复杂度。

因为δ≥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”。

2)如果 δ＜2，那么 δp-2…δ0=“0…0x．xxx”，其中 x 任意表示为1或0。因此c0和c1仅当δj=0，4≤j≤p-2时等于1，即

式中:(·)表示非逻辑运算，∨表示或逻辑运算。所以在硬件实现式(8)时，在计算得出δ后，进行c0的计算时，只需在原有的Constant Log-MAP译码算法硬件结构中引入几个额外的门结构(非门和或门)。改进的结构图如图3中的灰色框部分。这样，所提出的算法利用了δ≥0的优势，使得相关函数的硬件实现的复杂度大约降为Constant Log-MAP译码算法的一半。

3 MATLAB仿真分析

3.1 Turbo码在CCSDS标准中的应用仿真

将所提出的max*近似方法应用于Turbo译码中，对应信噪比下(Eb/N0)的BER性能仿真如图5所示。4条BER曲线分别代表Constant Log-MAP算法［4］、本文提出的改进算法(用Log-MAP max*表示)、Log-MAP和Max-Log-MAP算法的BER性能。

图5 不同译码算法的在CCSDS标准中的性能仿真比较

仿真的Turbo码参数为移位寄存器具有16个状态，码率为R=1/2，生成多项式为(1，33/23)o，33和23为8进制数，分别代表前馈多项式和反馈多项式。信息序列N=103bit，传输帧总数为106。

为了保证仿真结果性能的准确性，每个性能仿真实验中至少引入了100个位错误。使用了伪随机Turbo交织器，在接收端最多进行10次迭代，采用BPSK调制，应用于CCSDS标准［8］中。由图5可知，所提出的改进的Log-MAP算法(用虚线表示)总能达到接近最优的译码算法的BER性能，其译码复杂度接近Max-Log-MAP算法，而纠错能力明显强于Max-Log-MAP算法;在低误码率时，如10-6时，改进的译码算法可以实现与另外两种算法大致相同的BER性能。

3.2 Turbo码在WiMAX标准中的应用仿真

将双二进制的Turbo码，考虑其含有8种状态的分量卷积码的情况，应用于WiMAX标准［9］中，码率为 R=1/3，2/3和4/5，信息序列长度为N=752 bit，调制方式为QPSK。在接收器端，至少进行10次译码迭代。仿真结果如图6所示。

图6 不同译码算法在WiMAX标准中的性能仿真比较

在图6中，与使用二进制Turbo码的性能仿真相比，所提出的算法与Constant Log-MAP算法的BER性能之间的差异减小，Log-MAP算法与Max-Log-MAP算法的BER性能差异也减小。尤其，当R＞1/2时，可以看出所提出的算法达到了与Constant Log-MAP算法几乎相同的性能，BER=10-6时，甚至更低。

4 硬件复杂度分析

表1给出了所提出的n输入近似max*算法结构(用C表示)在空间(用A表示)和延迟(用D表示)两个方面与两种基于树结构的算法进行比较:1)基于3 bit LUT的2输入的Log-MAP算法结构(用A表示);2)2输入的Constant Log-MAP算法结构［4］(用 B 表示)。

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

实验均表明，所提出算法的结构不但比基于LUT的Log-MAP算法的递归结构和近似的Constant Log-MAP算法的结构空间大大减小，而且在更高的时钟频率运行时具有较低的延迟。如表1中，假设n=16，p=16时，所提出的n输入的max*结构需要5 768个等同的门，具有2 ns的最小延迟，而2输入的Constant Log-MAP结构需要7 312个等同的门，具有2.8 ns的最小延迟。因此所提出的n输入的max*结构空间减少了21%，延迟降为2输入Constant Log-MAP结构的28.5%。在具有与Constant Log-MAP算法(B)相同的延迟时(DB)作更近一步比较，对应的比较结果如表1中最后一列所示。可以看出，此时与Constant Log-MAP硬件复杂度相比，所提出的结构平均节省了大概30%的空间。

5 小结

本文给出了Turbo码译码的简化的Log-MAP译码算法，对其译码过程中的max*运算进行新的近似，并对其硬件实现结构进行了简化。max*运算是广义上的对n个输入值计算的简化，将max*运算近似为简单的max运算和相关函数的计算。仿真结果表明，这种方法相对于Log-MAP译码算法，性能有很小的损失，可以忽略不计。从实践的角度来看，新的改进算法的优势是显著降低了每个译码步骤的译码复杂度，简化了硬件结构，降低了延迟，具有广阔的工程应用前景。

［1］ BERROU C，GLAVIEUX A，THITIMAJSHIMA P.Near Shannon limit error-correcting coding and decoding:Turbo codes［C］//Proc.the IEEE International Conference on Communications.Geneva:IEEE Press，1993:1064-1070.

［2］ BAHL L R，COCKE J，JELINEK F，et al.Optimal decoding of linear codes for minimizing symbol error rate［J］.IEEE Trans.Information Theory，1974，3(20):284-287.

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

［4］ GROSSW J，GULAK P G.Simplified MAP algorithm suitable for implementation of turbo SISOalgorithms based on Log-MAPand Max-Log-MAP turbo decoding［J］.IET Proc.Commun.，2007，1(1):49-57.

［5］ PAPAHARALABOSS，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.

［6］刘东华.Turbo码原理与应用技术［M］.北京:电子工业出版社，2004.

［7］ WEY CL，SHIEH M D，LIN SY.Algorithms of finding the first two minimum values and their hardware implementation ［J］.IEEE Trans.Circuits Syst.I，2008，55(11):3430-3437.

［8］张凯.CCSDS标准Turbo码译码器设计及实现［D］.北京:北京邮电大学，2013.

［9］ IEEE802.16e-2005，Standard for local and metropolitan area networks.Part16:air interface for fixed and mobile broadband wireless access systems［S］.2006.