基于DSP处理器的UMTS Turbo MAP 解码器高效实现

Turbo码自1993年问世以来，以其出色的性能，在工业和科研领域都引起了广泛的关注。Turbo码性能逼近（信噪比差为0.7dB或更小）由Claude E. Shannon确定的信道容限。Berrou、Glavieux和Thitimajshima最先提出了Turbo码，其结构由两个并行级联卷积编码器组成。Turbo码编码方案产生同一信息序列的两个不同交织形式的分量码。解码时，由两个MAP解码器以迭代方式对判决结果进行解码。MAP 解码算法利用接收数据和校验符号（以真实和交织形式的数据计算而来的校验位），以及其他的解码软输出（外部的）信息，得到更加可靠的判决结果。

本文将讨论在ADI Blackfin通用定点DSP处理器上如何高效实现Turbo MAP 解码器的技术。

TURBO解码器

在Turbo解码过程中,MAP算法被用于确定最接近传输数据的信息位。MAP算法先对每个传送的数据位计算一个后验概率值（APPs），然后根据最大的后验概率值为该数据位分配一个判决值，再进行解码。MAP 算法使用后验概率值APP计算每一个传送位Cn的最大似然比LLR，使误码率（BER）最小，其计算公式如下：

(1)
其中，Y1N=[y1,y2,…,yN]。
译出的信息位通过以下硬判决得到：

在UMTS Turbo解码器中，应用一个八状态的RSC编码网格，在n时刻，当输入序列为Y1N时，比特“1”和比特“0”的APP可分别由式（2）和式（3）求得。

(2)

(3)
其中，分别是的对数, 是在n时刻和状态m下的前向状态度量， 是n时刻和状态m下的分支度量，是n+1时刻和状态k下的反向状态度量。每级中，只需要两个（当采用BPSK调制来传输数据比特流时）分支度量，而这些分支度量值可以由解码输入和另一个解码器的中间软输出计算得到。

式（4）中，前向状态度量根据编码器状态（对应于每级或时刻n）的网格表示从n=0时刻进行递归计算（由于在对数域内，采用累加）得到，这里假定的初值为，当1≤k≤2M-1时，。其中，M是编码生成多项式(1+D2+D3)的幂。类似的，式（5）中的反向状态度量从网格级n=N+1开始进行递归计算得到，同样假定的初始状态为和，其中1≤k≤2M-1。状态度量和的递归算法如下。
(4)
(5)
其中，b(i,m)和f(i,m)分别是与第n级的状态m相关的第n-1级和第n+1级状态值。在α，β和LLR的计算中，我们必须解一个形如ez=ex+ey的方程。其和的近似值可由ex=emax(x,y)(1+e-|x-y|)或z=max(x,y)+ln(1+e-|x-y|)= max*(x, y)计算得到。该算子被称为Log-MAP算子。修正项ln(1+e-|x-y|) 是一个非线性函数，它对MAP解码器在低信噪比下的性能增益带来最高0.5dB的提高。如果我们忽略了这个修正项，算子z=max(x,y)则被称为Max-Log-MAP算子。本文只考虑Turbo MAP解码器实现中的Max-Log-MAP算子。

TURBO解码器的实现

Turbo解码器由两个MAP解码器组成，这两个解码器由一个交织器和解交织器分隔开。由于篇幅有限，我们将不讨论Turbo解码器的完全实现而只讨论性能敏感度最高的“度量计算”部分。

1度量计算

式（1）中LLR的值由APP求得，而APP则由式（2）和式（3）计算得到。在计算APP时，我们要用到第n级所有状态下的α (前向状态度量)，β(后向状态度量)和γ(分支度量)。在第n级，γ值根据已接收到的信息和第n级的外部信息计算得到，而α用第n-1级的α和第n级的γ计算得到，β则由第n+1级的β和第n级的γ计算得到。换句话说，为了计算第n级的LLR值，我们要同时利用由前n级计算出的α值和由后N-n级计算出的β值，如图1所示。

图1 第n级LLR的计算图解

2 基于窗口的算法实现

如图1所示，Turbo解码器工作于符号长度为N的序列或结构上。因此，Turbo解码器的实现就需要一个超大容量的存储器（用来存储所有N级的α、β、γ、LLR、外部信息、接收序列、缓存等等），但是可以通过加窗的方法降低对存储容量的要求。基于加窗口的方法就是将整个数据结构分成一些小的数据块或数据窗（有6K级窗口的重叠，K=M+1，是编码器的约束长度），每次只在一个窗口上执行解码操作。在 MAP 解码中，三个主要的算子是α估计，β估计和LLR估计。在计算当前窗的β和LLR的同时，计算下一个窗中的α，这样就可以平衡ALU和DAG（加载/存储）单元对带宽的需求，如图2所示。

图 2 基于窗口的Turbo解码器的高效实现

BLACKFIN处理器上MAP解码器度量计算实现

在这一部分，将讨论Turbo MAP解码器中复杂的度量计算如何在ADI Blackfin处理器上实现，并充分利用Blackfin处理器提供的专用特性高效实现Turbo解码器。

1 状态度量计算实现

图3 第n+1级和第n级计算的蝶形算法

状态度量α和β可由式（4）和式（5）求得，该状态度量的计算可用图3所示的方法得以实现。α由正向（从左到右）计算得到，而β则由反向（从右到左）计算得到。图中，实线和虚线分别对应于输入“1”和“0”的编码。虽然通过分支度量（γ），可以由两个输入状态度量计算出两个输出状态度量（α和β），但这两个度量的输出状态却根据它们各自的输入状态而有所不同。在执行过程中，这一输入和输出状态度量的位置改变，在将数据从ALU寄存器存入存储器和将数据从存储器载入ALU寄存器时，可以通过加载/存储（DAG）模块解决。

图4 UMTS Turbo解码器状态度量估计的高效实现

UMTS Turbo解码过程中，α和β计算在Blackfin处理器上的高效实现如图4。由于Blackfin处理器能以向量模式运行，在单个指令周期执行四个16位加/减操作或两个16位求最大值操作，每一级α的计算需要8个循环周期来完成，而每一级β的计算则需要另外8个周期来完成。

2 LLR的实现

对于UMTS Turbo解码器，MAP算法的LLR可由式（1），式（2）和式（3）计算得到。式（2）和式（3）分别说明了通过α、γ和β来计算位“1”和位“0”的APP值的关系。这些MAP LLR的关系如图5(a)和图5(b)所示。

图5(a) 位“1”的 MAP关系，(b)位“0”的MAP关系

对于两个相同的输入和输出，位“1”和位“0”的MAP关系并不相似（极少情况下状态被交换），而这类不对称流程使我们无法利用Blackfin中计算单元和加载/存储单元的最大带宽。例如，图5（a）和图5（b）中标示的部分，我们考虑与式（2）和式（3）的前两项相对应的顶端蝶形运算。

图6 在Blackfin ALU上的LLR计算

由于Blackfin只需要三个周期就能完成四个16位加法和两个16位求最大值操作，要平衡加载/存储（DAG）单元的带宽和计算单元，只能用三个周期来加载数据。假设三个寄存器在三个周期中分别加载了α0|α0, α1|α1和 β4|β0，如图6所示。那么通过16位加法操作，我们可以在两个周期中计算出α0+β4|α0+β0和α1+β4|α1+β0。但是，MAX 操作要求仿照式（3）从反方向由α1+β0|α1+β4求得输出的第二项。Blackfin的16位加法指令所支持的交叉选项（CO）选项可用来换回加法的中间输出，如图6所示。如果没有交叉选项（CO），我们将耗费四个周期来计算四次加法，而不是两个。采用（CO）选项换回之后，执行最大向量操作（一个周期）即可得到两个Log-Max 输出。这一部分程序代码如图7所示。有了（CO）选项，就可以在18个Blackfin指令周期内计算某一级上的LLR值。

图7 利用BF5xx处理器交叉选项（CO）的LLR高效实现

总结

本文介绍了在ADI BF5xx处理器上Turbo MAP解码器的高效实现，详细说明了基于窗口的存储空间降低方法，并利用16位加/减和16位求最大值向量指令以及交叉选项（CO），高效地在Blackfin嵌入式处理器上实现了Turbo MAP解码。该方法耗费大约36个BF5xx周期，即可计算得到一个LLR输出。同时，利用约50kB的BF5xx存储空间，完成了UMTS Turbo MAP解码算法的数据和程序存储。