1. Introduction

3GPP LTE, which is a set of enhancements to the 3G Universal Mobile Telecommunications System (UMTS)^[1], has received tremendous attention recently and is considered to be a very promising 4G wireless technology. The Turbo decoder is typically one of the major blocks in a LTE wireless receiver. Key requirements of LTE include packet data support with peak data rates up to 150 Mbps on the downlink and 75 Mbps on the uplink, a low latency of 10 ms layer-2 round trip delay, flexible bandwidths (up to 20 MHz), improved system capacity and coverage^[2]. Advanced technologies were selected to meet these requirements including the turbo decoder.

The bottleneck of turbo decoder design is the high latency which is due to the iterative decoding process, the forward-backward recursion in the maximum a posteriori (MAP) decoding algorithm and the interleaving/de-interleaving between iterations. In this brief, the codeword can be processed concurrently by four, eight or sixteen SISO decoders. The design challenge for these parallel modes is how to transmit parallel data simultaneously through the interconnection between SISO decoders and the memory module^[3].

To achieve high throughput decoder, the low-latency of SISO and interleaver/de-interleaver had to be considered. This brief focuses on these issues and proposes an improved architecture. For a novel SISO system, forward state matrix $\alpha$ and backward state matrix $\beta$ are calculated alternately, where the design made both algorithms share the same structure and had less crucial path delay. The improved interleaver/de-interleaver structure realized interleaving and de-interleaving in one cycle.

The rest of the sections in this paper are organized as follows. Section 2 describes the basic structure of QPP and its several algebraic properties. Then this article proposes an interleaver/de-interleaver design based on QPP algebraic properties. Section 3 concentrates on novel SISO architecture, which uses less resources and has low-latency for the Log{\_}map algorithm. Section 4 provides the implementation results followed by a conclusion.

2. Interleaving

The interleaver is essential to the impressive performance of the Turbo code, but its pseudorandom property complicates the parallel processing of a single codeword. A specific mechanism is required to handle parallel data transmission with traditional interleavers^[4].

The QPP interleaver of a size-$N$ block can be expressed as

$f(x)=f_1 x+f_2 x^2\; {\rm mod}\; N,$

(1)

The $x$ stands for the original address and the $f(x)$ is the interleaved address. The determination of $f_1$ and $f_2$ is related to the block size. In LTE standard specification, $f_1$ is always defined as an odd number while $f_2$ is even. Moreover LTE, the block size $N$ is always divisible by 16, 32, and 64 when $N\geqslant$ 512, 1024, and 2048, respectively. This formula requires intensive calculation as it uses a square, a multiply and reminder operation. An approach to reduce operations is to consider the calculations are done in a progressive way. The reminder of the operations are done in every calculation cycle, then it can be reduced simply. The square and multiply would not be needed anymore. The QPP interleaver can transfer as follows.

$f({x+d})=\left[{f(x)+g(x)} \right] \; {\rm mod}\; N,$

(2)

$g(x)=\left( {2df_2 x+d^2f_2 +f_1 d} \right)\; {\rm mod} \;N,$

(3)

$g({x+d})=\left[{g(x)+2d^2f_2 } \right] \; {\rm mod} \;N,$

(4)

where $g(x)$ is middle stage and $d$ is interleaver step. In this article, decode data would divide into several groups, while all groups can be processed at the same time^[5].

As Figure 1 shows, decode data is saved in $m\times n$ matrix, where $m$ indicates the number of groups and $n$ stands for each group length. Two steps are exploited in parallel interleaving design. Step $d$ is equal to 1 for the forward interleaver while for the backward one, $d$ would be $n-1$. Figure 1(a) shows the forward interleaver. Successive two sequences after the interleaver are mapped in different line and row. Figure 1(b) illustrates the backward interleaving process. In backward interleaver sequences, two original adjacent numbers lie with both neighbor in column and line. After backward interleaving, they are separated in a different line and column. The setting means the two interleavers can be uniform disposal.

However, we can deduce some properties from QPP interleaver formula which is very useful for interleaving processing. QPP equator can be rewritten as follows.

$$\begin{split} f(x) {}& =f_1 ({x+w})+f_2 ({x+w})^2\; {\rm mod}\; n \\& =f_1 x+f_2 x^2\; {\rm mod}\; n, \\ \end{split}$$

(5)

where $w$ can be divided by $n$. From Equation (5), we can draw a conclusion that parallel data can be read at the same address from different memories.

Figure 2 shows that process. The column interleaving generator combines by two progressive adders. Forward column address generator equations, for computing forward state matrix $\alpha$, shown as follows.

$f( {x+1})=\left[{f(x)+G(x)} \right] \; {\rm mod} \;n,$

(6)

$f({x+1})=\left[{f(x)+G(x)} \right] \; {\rm mod}\; n,$

(7)

$G({x+1})=\left[{G(x)+{\rm delta}} \right] \; {\rm mod} \; n,$

(8)

${\rm delta}=\left( {2f_2 } \right)\; {\rm mod} \; n,$

(9)

$G(0)=\left( {f_1 +f_2 } \right)\; {\rm mod}\; n,$

(10)

$f(0)=0,$

(11)

where $x$ ranged from 0 to $n$ - 1, is the forward sequence. $f(x)$ is the forward interleaved column address. The same as the forward address generator, backward address generator equations can be expressed as follows:

$f({x-1})=\left[{f(x)+G(x)} \right] \; {\rm mod} \; n,$

(12)

$G({x-1})=\left[{G(x)+{\rm delta}} \right] \; {\rm mod}\; n,$

(13)

${\rm delta}=\left( {2f_2 } \right)\; {\rm mod}\; n,$

(14)

$G({n-1})=\left( {3f_2 -f_1 } \right)\; {\rm mod} \; n,$

(15)

$f({n-1})=\left( {f_2 -f_1 } \right)\; {\rm mod}\; n.$

(16)

In these group formulas, $x$ is the backward sequence, covered from $n$ - 1 to 0. $f({x-1})$ is the backward interleaved column address. The signal column{\_}c{\_}in would be used in an intra-row permutation process.

Figure 2 illustrates only half of the interleaver/de-interleaver operation and intra-row permutation is another half. Figure 3 gives more detail.

Intra-row permutation includes 16-groups progressive adders. Figure 3 illustrates one group work. Equations (17)-(19) show intra-row permutation. Where m is the number of groups covered 1, 4, 8 or 16, so we can just keep 2, 3 or 4 bits corresponding to the final result instead of the reminder operation.

$f({x+1})=\left\{ {\left[{f(x)+g(x)} \right] \% n} \right\} \;{\rm mod} \; m,$

(17)

$g({x+1})=\left\{ {\left[{g(x)+{\rm delta}} \right] \% n} \right\} \;{\rm mod}\; m,$

(18)

${\rm delta}=\left[{\left( {2f_2 } \right)\% \;n} \right] \;{\rm mod}\; m.$

(19)

For forward address calculation, the equator can be transformed to

${\rm row}\_f( {w+x+1} )= \left( {\begin{array}{l} {\rm row}\_f( {w+x} )\;+ \\ {\rm row}\_g( x) \\ \end{array}} \right)\;{\rm mod} \; m,$

(20)

${\rm row}\_g( {w+x+1} )= \left( {\begin{array}{l} {\rm row}\_g( {w+x} )\;+ \\ {\rm row}\_{\rm delta} \\ \end{array}} \right)\;{\rm mod}\; m,$

(21)

${\rm row}\_{\rm delta}= \left( {\begin{array}{l} \left( {2f_2 } \right)\% \;n\;+ \\ {\rm column\_c\_in} \\ \end{array}} \right)\;{\rm mod} \; m,$

(22)

${\rm row}\_g(0)=\left[{g( 0)\% n} \right] \;{\rm mod} \; m,$

(23)

${\rm row}\_f( 0)=\left[{f( 0)\% n} \right] \;{\rm mod} \; m.$

(24)

The same as the forward intra-row permutation, backward calculation can use the same architecture with different initial inputs. Two permutations can share the same adders in various time slots. However, backward intra-row permutation should be adjusted, because the next permutation is in the following line. By this way, the Turbo decoder can generate a mapping/demapping address every cycle.

${\rm row}\_f( {w+x-1})=\left( {\begin{array}{l} {\rm row}\_f( {w+x} )+ \\ {\rm row}\_g( {w+x}) \\ \end{array}} \right)\; {\rm mod} \; m,$

(25)

${\rm row}\_g( {w+x-1})=\left( {\begin{array}{l} {\rm row}\_g( {w+x} )\;+ \\ {\rm row\_delta} \\ \end{array}} \right)\; {\rm mod}\; m,$

(26)

${\rm row\_delta}=\left( {\begin{array}{l} \left( {2f_2 } \right)\% \;n\;+ \\ {\rm column\_c\_in} \\ \end{array}} \right)\; {\rm mod}\; m,$

(27)

${\rm row}\_g( {n-1})=\left[{g( {n-1})\% n} \right]\; {\rm mod}\; m,$

(28)

${\rm row}\_f( {n-1})=\left[{f( {n-1})\% n} \right] \; {\rm mod}\; m.$

(29)

3. Improved soft in soft out

In order to illustrate the improved MAP shown in Figure 5, we compare it with original sliding window MAP (SW-MAP). Figure 4 shows common SW-MAP decoder architecture which requires one set of $\alpha$ unit, $\beta$ unit, branch unit, and a Log Likelihood Ratio Calculator (LLRC) unit. A SMP buffer is used to save the stakes for use in the next Turbo iteration. In the SW algorithm, the parity $L_{\rm p}$ is loaded from the symbol memory in the sequential order. Priori information $L_{\rm a}$ is loaded from the double port memory in the sequential order for the first half iteration, and in the interleaving order for the second half iteration^[6]. The same as the $L_{\rm a}$ information loading scheme, the systematic $L_{\rm s}$ is the load from the symbol memory. However, the ordinary SW-MAP design has two problems. One is $\alpha$ and $\beta$ calculation which employs fully parallel add-compare-select-add^[7]. This operation needs to be completed in one cycle which means the decoder cannot work in the high speed clock system. Another problem is resource consumption. The new design scopes on these two issues and employs mending structure.

The new add-compare-select-add operator idea is separated into two parts by a register. Two parts can deal different operation, one calculated $\alpha$ while the other calculated $\beta$ or vice versa. Both $\alpha$ unit and $\beta$ unit can be replaced by $\alpha$ or $\beta$ unit. In this way, two $\alpha$ or $\beta$ units can finish all $\alpha$ and $\beta$ computation with one clock more than conversion SISO but shorten the critical path delay. Since the output sequence is different, the construction has to be taken.

Compared with a conventional SW-MAP decoder, the improved decoder does not use a sliding window and has only one $\alpha$ or $\beta$ unit instead of $\alpha$ unit and $\beta$ unit in the old one. Because $\alpha$ and $\beta$ calculator structures are almost the same except branch transition probability mapping which can be control by mode select. What is more, the branch of last in first out memory (LIFO) had been saved because it takes parts in LLRC calculation directly.

In the improved MAP decoder, $\alpha$ and $\beta$ are calculated alternately. Both $\alpha$ unit and $\beta$ unit employ an add-compare-select-add operator, which is decided critical path delay in IC design ascertaining the system clock. To solve this bottleneck, a register is utilized to split the operator into add-compare and select-add. Because state matrix $\alpha$ and backward state $\beta$ are independent of each other, the $\alpha$ or $\beta$ unit calculates $\alpha$ and $\beta$ in turn. The novel scheme not only yields a fast system clock but also reduces resource consumption by reusing the unit. Alternatively calculating $\alpha$ and $\beta$ has another advantage: the transition probability computed by the branch unit need not save at all, which takes part in LLRC decoding directly with a clock delay. The new design finished half an iteration in the double group length clock, while SW-MAP using a group length and the width of the window. In short, two new MAP decoders are equivalent~to one SW-MAP decoder in complex, and spend less time in decoding.

Table 1 summarizes the implementation result of the proposed decoder and the hardware comparison with existing decoders. The new SISO architecture was only a trial by FPGA and would be verified by a trial chip in the future.

4. Conclusions

This paper details the implementation of a parallel Turbo decoder for the LTE standard, analyzing aspects including interleaving and SISO design, and the verification idea in FPGA. The proposed circuit is designed to achieve high throughput. Interleaver and Log-MAP algorithm optimizations in a parallelized architecture make it possible to achieve high throughput rates with low latency, without performance loss.