Turbo译码器基于组合逻辑电路的低复杂度Log-MAP算法

王　东，李秀朋

(中国电子科技集团公司第五十四研究所，河北 石家庄 050081)

0　引言

Turbo编码作为第一种接近香农极限的信道编码方式，已经在包括LTE(Long Term Evolution)、CCSDS(Consultative Committee for Space Data System)、DVB-RCS(Digital Video Broadcasting - Return Channel via Satellite)等在内的大量无线通信标准中得到应用。Log-MAP算法是一种简化版的最大后验概率(MAP)算法，广泛应用于Turbo译码器中。尽管通过将对数域引入MAP算法已经去除了大部分的指数和乘法运算，但剩余的指数和对数运算在实现上仍然比较困难。

1　Log-MAP算法

在文献[1]中，Log-MAP算法的核心max*运算定义如下：

max*(x1,x2)=max(x1,x2)+ln(1+e-|x2-x1|)=

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

(1)

式中，fc=ln(1+e-|x2-x1|)通常被称为修正因子。Log-MAP是SISO(Soft Input Soft Output)迭代译码的最优算法，然而fc较高的复杂度使得该算法实现起来十分困难[2-4]。为了解决这一问题，在文献[5-11]中已经出现了一系列简化的Log-MAP算法。

Max-Log-MAP算法[5]直接忽略了修正因子fc，在这种情况下，max*运算可以仅用一个比较器实现。然而，伴随着复杂度的降低，性能也有相对较大的下降。通过舍弃fc，Max-Log-MAP算法在所有简化的Log-MAP算法中取得了最低的复杂度和最差的BER性能。SF-Log-MAP算法[6]通过将外部信息乘以一个缩放系数(Scaling Factor，SF)，在小幅增加复杂度的情况下改善了Max-Log-MAP算法的BER性能。然而该算法性能的提升十分有限，依然不能满足实际应用的需求。

Linear-Log-MAP[7]和Constant-Log-MAP[8]等一系列算法采用了线性函数完成对fc的近似。这些算法将fc分为若干部分，每一部分都使用特定的线性函数对fc进行近似。特别的，在Constant-Log-MAP算法中使用的线性函数是一个常量。这些线性近似算法取得了更好的BER性能，也引入了更高的复杂度[9]。一些算法使用了非线性函数[10]来计算fc，也可以在理论上获得更好的BER性能。然而在实际应用中，为了方便硬件实现，通常将非线性函数修正为分段的线性函数。从这一点来看，这些方法也可以归为线性近似。

就目前来看，大多数研究人员都遵从了下面这些步骤来实践Log-MAP算法的简化。首先，确定一个简单的函数来近似fc。之后，使用比较器、加法器和移位器等实现比较及其他算术运算。

这些方法的局限性也是显而易见的。一方面，随着复杂度的提升，函数分段的数量不可能无限制地增加。这样对fc的粗略估计直接导致了BER性能的下降。另一方面，作为最基本的运算，比较器、加法器和移位器在实现上引入的复杂度无法进一步降低。

文献[11]提出了一种Constant-Log-MAP算法的新的实现方法很值得关注。这个方法使用适当的数字电路替换掉了fc，然而简化效果需通过观察发现，且该方法无法应用在其他算法中。受文献[11]的启发，本文提出了一种完整的简化Log-MAP算法实现方案。该方案适用于包括最前沿算法在内的所有Log-MAP相关算法。第二部分将阐明Constant-Log-MAP算法是本文提出方案的一个特例，且可以通过特定的步骤推导得出，而无需依赖观察。

2　基于CLC的简化实现

Log-MAP算法的流程如图1所示，其中虚线标识的模块完成修正因子fc的计算。表1展示了几种典型的简化算法。考虑到硬件实现，|x2-x1|和fc均为有确定位宽的定点数据。这样，用来计算fc的模块可以看作是一个系统或者一个组合逻辑电路，其输入为|x2-x1|，输出为fc。fc中的每一位可由|x2-x1|经逻辑运算得出。之后，将该模块的系统函数由一个算术表达式变换为N个逻辑表达式，其中N为fc的位宽。最终，加法器、比较器和移位全部被逻辑电路替换。本文提出的实现方法的各个步骤将在下面进一步描述。

图1　简化Log-MAP算法流程

表1适合定点和浮点算法的fc近似

算法Max⁃Log⁃MAPConstant⁃Log⁃MAPLinear⁃Log⁃MAP参考文献[9]fc00．375x2-x1<20x2-x1≥2{-0．25×(x2-x1-2．5)x2-x1<2．50x2-x1≥2．5{max(0，ln2-0．5×x1-x2)

表23位有效位定点算法的fc近似

x2-x100．1250．250．3750．50．6250．750．87511．1251．251．3751．51．6251．751．875fc0．6250．6250．50．50．3750．3750．250．250．250．250．250．250．1250．1250．1250．125定点101101100100011011010010010010010010001001001001

2.1　选择fc的近似方案

如前文所述，|x2-x1|和fc均为有确定位宽的定点数据，也可以说是有确定步长的离散值。在这一部分，应对每一个|x2-x1|对应的fc的值进行清晰的定义，既可以通过现有的简化算法计算得出，也可以由研究人员直接确定。本文中|x2-x1|和fc分别采用[8.3]和[0.3]定点结构，其中[m.n]表示该定点数据有m位整数位和n位小数位。几种简化Log-MAP算法对fc的近似如图2所示。在本文对fc进行近似的Example(2)中，令δ=|x2-x1|，

(2)

式中，T(·)表示表2定义的查找表，⎣x⎤为不大于x的最大整数。显然式(2)无法通过一个简单的函数进行描述，进而在传统观点上被认为难以进行实现。在下一部分，本文将介绍如何通过CLC架构完成对这种fc近似的实现。

图2　几种简化Log-MAP算法对fc的近似

2.2　确定最大项/最小项方程

当输入和输出的映射关系确定之后，它们之间的逻辑关系可以通过数字电路得到。最大项或最小项[12-13]能够首先确定。令c和u分别表示|x2-x1|和fc，又令c=cm-1…c0，u=un-1…u0分别表示他们的定点形式。这样，式(2)的最小项可以确定为：

u0=∑c(0,1,4,5,12,13,14,15)，

u1=∑c(4,5,6,7,8,9,10,11)，

u2=∑c(0,1,2,3)。

(3)

方程(3)准确地给出了fc和|x2-x1|间的逻辑关系。然而，从实现的角度来看，该表达式并非最简的。为了进一步降低硬件复杂度，必须对其进行简化[12]。

2.3　确定最简表达式

代数方法和卡诺图[13-14]是简化数字电路逻辑表达式的两条主要途径。根据最小项(3)，卡诺图很容易设计，如图3所示。其中，“1”表示最小项方程中包括该项。

图3　与公式(3)对应的卡诺图

通过卡诺图，可以进一步简化(3)，

(4)

显然，本文提出的架构适用于任意一种fc的近似，只需知晓fc与|x2-x1|之间的映射表即可。特殊地，文献[11]中的简化方案作为本架构的一个特例，可以通过上面的步骤得到。Example(2)中基于CLC的fc计算模块的组成如图4所示。

3　仿真与硬件实现

本文针对CCSDS和LTE标准对AWGN信道[15]下Turbo译码器的BER性能进行了仿真，仿真参数如表3所示[15-16]。fc与|x2-x1|在仿真中分别以[8.3]和[0.3]的定点数据呈现。图5和图6分别给出了CCSDS和LTE两种标准下的BER性能与Eb/N0的关系。为了保证结果的准确性，针对每一个Eb/N0至少要仿真5×104个帧[17-19]。

表3图5和图6所使用的仿真参数

标准码长码率迭代调制方式CCSDS17841/610BPSKLTE35201/310QPSK

图5　CCSDS标准下几种简化算法的BER性能

图6　LTE标准下几种简化算法的BER性能

从仿真中可以得出，Max-Log-MAP和SF-Log-MAP会造成0.15～0.5 dB的BER性能恶化。其他3种算法性能十分接近，其中Linear-Log-MAP和Example(2)性能略高于Constant-Log-MAP。表4和表5分别给出了CCSDS和LTE两种标准下LINEAR-LOG-MAP、使用CLC的LINEAR-LOG-MAP和使用CLC的(2)的几种算法占用硬件资源情况。实现平台为Xilinx ML605评估板和ISE Design Suit 13.4开发环境。

表4CCSDS标准下几种算法复杂度对比

算法寄存器查找表触发器对RAM18Linear⁃Log⁃MAP2396(100%)7462(100%)7694(100%)180(100%)使用CLC的Linear⁃Log⁃MAP2629(110%)5578(74．8%)5789(75．2%)180(100%)使用CLC的(2)2622(109．4%)5495(73．6%)5678(73．8%)180(100%)

表5LTE标准下几种算法复杂度对比

算法寄存器查找表触发器对RAM18Linear⁃Log⁃MAP1654(100%)4452(100%)4659(100%)75(100%)使用CLC的Linear⁃Log⁃MAP1597(96．6%)3137(70．5%)3328(71．4%)75(100%)使用CLC的(2)1639(99．1%)3084(69．3%)3292(70．7%)75(100%)

对比传统的Linear Log-MAP架构，基于CLC的架构能够减少约30%的查找表和触发器对，与此同时寄存器的数量基本持平或仅需小幅增加。正如我们所看到的，尽管式(2)无法使用一个简单的函数描述，但使用基于CLC的架构对其进行实现的复杂度仍然低于Linear Log-MAP。从这一点来看，研究人员可以跳过目前广泛采用的函数近似或曲线拟合，而直接设计fc与|x2-x1|之间的映射。文献[11]中也给出了一些关于基于CLC的实现和传统的Constant Log-MAP之间的对比，可以看作是本文提出的架构的一个特例。

4　结束语

本文提出了一种基于CLC的简化Log-MAP算法，并给出了其有效的硬件实现。相对于传统的简化Log-MAP算法，本文提出的架构可以降低高达30%的复杂度并保持相同的BER性能。特别地，基于CLC的架构无需关注fc是否能用一个简单的函数描述即可硬件实现Log-MAP算法。本文提供了一个新的途径来帮助研究人员设计更具灵活性、更高BER性能和更低复杂度的Log-MAP简化算法。

[1]Robertson P,Villebrun E,Hoeher P.A Comparison of Optimal and Sub-optimal MAP Decoding Algorithms Operating in the Log Domain[C] ∥in proc.IEEE Int.Conf.Commun.,1995,2:1009-1013.

[2]Classon B,Blankenship K,Desai V.Channel Coding for 4G Systems with Adaptive Modulation and Coding[J].IEEE Wireless Commun.,2002,9( 2): 8-13.

[3]Consultative Committee for Space Data Systems (CCSDS):Telemetry Channel Coding[DB/OL].Avaliable: (2002).http://public.ccsds.org/publications/archive/101x0b6s.pdf.

[4]Digital Video Broadcasting (DVB): InteractionChannel for Satellite Distribution Systems [DB/OL].Avaliable: (2009).http://www.etsi.org/deliver/etsi_en/301700_301799/301790/01.05.01-60/en_301790v010501p.pdf.

[5]Erfanian J,Pasupathy S,Gulak G.Reduced Complexity Symbol Detectors with Parallel Structure for ISI Channels[J].IEEE Trans.Commun.,1994,42(234):1661-1671.

[6]Vogt J,Finger A.Improving the Max-Log-MAP Turbo Decoder[J].IEE Electron.Lett.,2000,36(23):1.

[7]Cheng J F,Ottosson T.Linearly Approximated Log-MAP Algorithms for Turbo Decoding[C]∥in proc.IEEE.Veh.Technol.Conf.,2000,3:2252-2256.

[8]GrossW J,Gulak P G.Simplified MAP Algorithm Suitable for Implementation of Turbo Decoders[J].IET Electron.Lett.,1998,34(16):1577-1578.

[9]Talakoub S,Sabeti L,Shahrrava B,et al.An Improved Max-Log-MAP Algorithm for Turbo Decoding and Turbo Equalization[J].IEEE Trans.Instrum.Meas.2007,56(3):1058-1063.

[10] Wang H,Yang H,Yang D.Improved Log-MAP Decoding Algorithm for Turbo-like Codes[J].IEEE Commun.Lett.,2006,10(3):186-188.

[11] Martina M,Papaharalabos S,Mathiopoulos P T,et al.Simplified Log-MAP Algorithm for Very Low-complexity Turbo Decoder Hardware Architectures[J].IEEE Trans.Instrum.Meas.2014,63(3):531-537.

[12] Das S R,Choudhury A K.Maxterm Type Expressions of Switching Functions and Their Prime Implicants[J].IEEE Trans.Electron. Comput., 1965,EC-14(6):920-923.

[13] Wakerly J F.Digital Design Principles and Practices[M].3rd ed.Englewood Cliffs,NJ,USA:Prentice Hall,2000.

[14] Karnaugh M.The Map Method for Synthesis of Combinational Logic Circuits[J].AIEE,Trans.Commun.Electron.,1953,72(5):593-599.

[15] 许文龙,文运丰,邓晓平,等.无人飞行器通信中联合信道估计和Turbo均衡[J].无线电工程,2016,46(1):46-49.

[16] 郭晓东,陈卫东.高误码率下双二进制Turbo码交织器的识别算法[J].无线电工程,2017,47(2):69-73.

[17] 郝亚男,杜克明,冯昊轩.一种用于LTE的提前终止Turbo码算法仿真[J].无线电工程,2017,47(4):24-27.

[18] 高红山,高凡琪.瑞利信道下基于Turbo-BICM-ID的DFT-S-OFDM性能研究[J].无线电工程,2017,47(9):38-43.

[19] 张亚林,树玉泉,张金涛,等.一种多进制LDPC编译码器硬件的实现方法[J].无线电工程,2018,48(1):72-79.