Efficient UMTS Turbo MAP decoding on a DSP

I. INTRODUCTION
Turbo Codes have attracted great attention in the industry and research communities since their introduction in 1993 because of their remarkable performance. The Turbo Codes operate near (with SNR gap of 0.7dB or less) the ultimate limits of capacity of a communication channel set by Claude E. Shannon [1]. Turbo Codes were first proposed in [2] by Berrou, Glavieux and Thitimajshima. Turbo codes are constructed using two concatenated constituent convolutional coders. In the Turbo Coding scheme, two component codes on different interleaved versions of the same information sequence are generated. On the decoder side, two MAP decoders are used to decode the decisions in an iterative manner. The MAP decoding algorithm uses the received data and parity symbols (which correspond to parity bits computed from actual and interleaved versions of data bits) and other decoder soft output (extrinsic) information to produce more reliable decisions.

In this paper, we discuss efficient implementation techniques to implement a Turbo MAP decoder on ADI Blackfin general purpose fixed point DSP processors. The paper is organized as follows. Section II briefly discusses the computations involved in the Turbo decoder and provides mathematical expressions for computing the three major metrics. Section III discusses practical implementation details of the Turbo decoder. Section IV introduces efficient implementation techniques for the computationally heavy metrics of MAP decoder on Blackfin processor, and provides assembly code. Section V summarizes the major findings and concludes the discussion of this paper.

II. TURBO DECODER
In Turbo decoding, the MAP algorithm is used to determine the most likely information bit that has been transmitted. The MAP algorithm calculates an a posteriori probabilities (APPs) value for each transmitted data bit and then the data bit is decoded by assigning a decision value that corresponds to the maximum a posteriori probability. The MAP algorithm using APPs minimizes the bit error probability (BER) by calculating the LLR for every transmitted bit c_n as below.

where Y₁^N = [y₁, y₂,…, y_N].

The decoded bit is obtained by hard decision as below

In a UMTS turbo decoder, using an eight state RSC encoder trellis, APPs for bit "1" and bit "0" at time n with a received sequence Y₁^N is obtained by Equation (2) and Equation (3) respectively.

(Click to enlarge)

where α_n^m, β_n+1^k, γ_nⁱ are logarithms of α_n^m, β_n+1^k, γ_nⁱ respectively, α_n^m ≈Pr(Y₁^n-1 | S_n = m) a forward state metric at time n and state m, γ_n^i,m ≈Pr(c_n = i, S_n = m, Y_n), a branch metric at time n and state m and β_n+1^k = Pr(Y_n+1^N | S_n+1 = k), a reverse state metric at time n+1 and state k. For each stage, only two branch metrics are needed (as we are using BPSK modulation to transmit bits) and these are computed using the received inputs and intermediate soft outputs of the other decoder. The forward state metrics α_n^m in Equation (4) are recursively computed (by accumulation as we are in the log domain) with the trellis representation of encoder states (for each stage or time instance n) from time n=0 assuming initial values for α₀^m as α₀⁰ = 0 and α₀^k = –∞, where 1 ≤ k ≤ 2^M - 1 and M is the power of the encoder generating polynomial (1+D²+D³). Similarly, the reverse state metrics β_n^m in Equation (5) are recursively computed from trellis stage n = N + 1 assuming initial values for β_N+1^m as β_N+1⁰ = 0 and β_N+1^k = –∞, where 1 ≤ k ≤ 2^M - 1. The state metrics α_n^m and β_n^m are computed recursively as below.

where b(i,m) is the allowed stage n-1 state value which is connected to state m at stage n and f(i,m) is the allowed stage n+1 state value which is connected to state m at stage n. In computing Alphas, Betas and LLR, we have to compute an equation of the form e^z = e^x + e^y. The approximation for this summation is given by e^z = e^max(x,y)(1 + e^{–| x – y|} or z = max(x, y) + ln(1 + e^{–| x – y|}. This operator is called the Log-MAP operator. The correction term ln(1 + e^{–| x – y|} is a non-linear function and this contributes up to 0.5 dB gain to MAP decoder performance at low SNR. If we ignore this correction term, the resulting operator z = max(x, y) is called the Max-Log-MAP operator. In this paper, we are considering only the Max-Log-MAP operator in the implementation of the Turbo MAP decoder.

Page 2: TURBO DECODER IMPLEMENTATION
Page 1 | 2 | 3