# Performance of Bit-Level Decoding Algorithms for Binary LTE Turbo Codes with Early Stopping.

Abstract: Turbo codes apply an iterative message passing mechanism between two concatenated decoders. Their astounding performance has led to their widespread adoption in several communication standards such as Long Term Evolution, and Code Division for Multiple Access 2000. This paper gives an overview of three bit-level decoding Max-Log-MAP algorithms with Sign Difference Ratio-based early stopping that can be used with Long Term Evolution Turbo Codes. A detailed computational complexity analysis is given for the three methods. It is observed that the complexity of the decoding methods decrease significantly as the [E.sub.b]/[N.sub.0] increases when Sign Difference Ratio is used. Moreover, the Bit Error Rate performance of the methods was also assessed and compared for different modulation schemes. Results show that the different methods perform differently in the waterfall and error-floor regions with different modulation schemes. Moreover, the computational complexity analysis show that Method 2 requires fewer overall number of computations compared to Methods 1 and 3.Keywords: LTE Turbo Codes, Max-Log-MAP Turbo Decoding, Computational Complexity Analysis.

1. Introduction

Turbo codes are a class of error correcting codes in coding theory and consist of two concatenated decoders passing messages iteratively between each other. They are used in several communication standards such as Long Term Evolution (LTE), and Code Division for Multiple Access (CDMA) 2000. The Turbo decoding algorithms are the Maximum A-Posteriori Probability (MAP), Logarithmic MAP (Log-MAP), and the Maximum Log-MAP (Max Log-MAP) algorithms. The MAP algorithm was the initially presented Turbo decoding algorithm in [1]. However, due to its numerical instability and high computational complexity, the Log-MAP algorithm was proposed by researchers. The Max Log-MAP algorithm was brought forward with the aim of having additional reduction in computational complexity. The trade-off accompanied by this reduction is a slight degradation in error performance. There exists this computational complexity issue of Turbo decoding algorithms and several papers have proposed variants to address this problem. In [2], a complexity analysis with three symbol-level decoding algorithms for duo-binary Turbo codes was performed. The work in [3] focussed on the decoder complexity for LTE downlink Turbo code and proposed the application of a decoding framework with adaptive complexity. The author of [4] has proposed a new substitute to the conventional Logarithmic Bahl-Cocke-Jelinek-Raviv (Log-BCJR) algorithm for Turbo decoding. It has been shown that the proposed algorithm which is compatible with all Turbo codes, can provide throughputs and latencies of up to 6.86 times better than the conventional algorithms when employed with Turbo codes of the LTE and WiMAX standards with a trade-off of slightly increased resource requirement and computational complexity. The authors of [5], investigated the computational complexity of Turbo decoding with multiple-input multiple-output (MIMO) detection. Results demonstrated the suitability of the proposed decoder for parallel and pipeline architectures which can meet the requirements for high throughput.

Schemes like iterative detection or early stopping are employed in the decoding process to prevent unnecessary additional iterations with the aim to reduce the decoding complexity of Turbo codes. For example, in [6], the authors proposed early stopping mechanisms using a predicted decoding threshold. These techniques have been categorised into two groups. One is soft-bit decision based, such as absolute LLR measurements [7] and Cross Entropy (CE) [8]. The second class is hard-bit decision based, such as Sign Change Ratio (SCR) [9] and Sign-Difference Ratio (SDR) [10]. These mechanisms help reducing the computational complexity by not performing additional unnecessary iterations. The report of [11] presents a stopping criterion used with the Turbo decoder of the LTE standard with the objective of reducing the power and energy consumption. A configuration of the decoder to use 1, 2, 4, 8, or 16 MAP decoders in parallel can be performed. This has shown to help achieve a throughput of 110Mb/s for 7 iterations when operating at a clock frequency of 200 MHz. The work of [12] proposed two early stopping mechanisms based on the regression angle computed at every half-iteration and the Pearson's correlation coefficient for the low and high [E.sub.b]/[N.sub.0] range respectively.

This paper gives an overview of bit-level decoding Max-Log-MAP algorithms with the different equations used for Binary LTE Turbo codes together with SDR-based early stopping mechanism. The computations involved in the three decoding techniques are explicitly detailed and an analysis of the complexity has been provided. Simulation results with different modulation schemes reveal that the different decoding techniques perform differently in the waterfall and error floor regions with different modulation schemes.

The organisation of the paper is as the following. The different decoding methods and results for LTE Turbo codes with Max Log-MAP decoding algorithm are presented in Section 2. The simulation results are presented in Section 3 and Section 4 concludes the paper.

2. Binary LTE Turbo Codes

Figure 1 depicts the complete encoding structure for Binary LTE Turbo codes [13], [14].

The information bits are sent to an LTE Turbo encoder consisting of a parallel concatenation of two Recursive Systematic Convolutional (RSC) encoders, RSC1 and RSC2, separated by an interleaver ([product]). A Quadratic Polynomial Permutation (QPP) interleaver is employed in the design of the LTE Turbo encoding system. The interleaved permutation with a QPP interleaver is obtained using a quadratic polynomial. The relationship between the output index z and input index [pi](z) is expressed by the following equation [14]:

[mathematical expression not reproducible] (1)

Where,

[f.sub.1] and [f.sub.2] are the permutation coefficients, K is the size of the information block.

After the encoding process, each of the three output streams [S.sub.0], [P.sub.1], and [P.sub.2] is interleaved with its own sub-block interleaver resulting in [d.sub.0], [d.sub.1], and [d.sub.2] respectively. Sub-block interleaving is performed as follows:

a. The input block is written row-wise in a rectangular matrix to form a [R.sub.s] by [C.sub.s] matrix.

b. A permutation is performed on the columns of this matrix.

c. A column-wise read is performed on the permuted matrix to obtain the output.

The number of columns, [C.sub.s], is fixed to 32 and the number of rows, [R.sub.s], is (K / 32). The inter-column permutation is achieved using the Bit-Reversal-Order (BRO) pattern given below:

Q(j)= [0, 16, 8, 24, 4, 20, 12, 28, 2, 18, 10, 26, 6, 22, 14, 30, 1, 17, 9, 25, 5, 21, 13, 29, 3, 19, 11, 27, 7, 23, 15, 31] Q(j) is the original column position of the jth permuted column.

LTE Turbo coded standard performs multiplexing such that the rearranged systematic bits, [d.sub.0], are placed in the beginning followed by bit-by-bit interlacing of the two rearranged parity streams, [d.sub.1] and [d.sub.2], in order to form a single output buffer [14]. The resulting bit-stream is then sent to the modulation block to be mapped to the corresponding constellation.

The modulated signal is then transmitted over an AWGN channel. The received noisy symbols are demodulated, sub-block de-interleaved and de-interlaced.

Figure 2 shows a typical Turbo decoding framework with an early stopping mechanism. The Turbo decoder is made up of two decoders concatenated with an interleaver similar to the one in the encoder. Decoder 1 accepts r0 and r1 which are noisy versions of [S.sub.0] and [P.sub.1], obtained after modulation and transmission over the channel. Decoder 2 accepts [bar.r0] which is the interleaved version of r0 and r2 which is the noisy version of [P.sub.2]. [[conjunction].sub.1e](t)and [[conjunction].sub.2e](t) are the extrinsic information generated by the decoders. [[conjunction].sub.1](t) and [[conjunction].sub.2](t) are the Log Likelihood Ratio (LLR) output from Decoders 1 and 2 respectively.

The extrinsic and a-posteriori LLRs from each of Decoders 1 and 2 are fed to the SDR stopping mechanism block. A signal T1 is generated to stop the decoding at Decoder 1 and a signal T2 is generated to stop the decoding at Decoder 2. The scale factor for each decoder d at iteration n is computed as follows:

[mathematical expression not reproducible] (2)

Where,

[mathematical expression not reproducible], and [mathematical expression not reproducible] have the same sign, otherwise [mathematical expression not reproducible] = 0,

N is the frame size in bits.

The complexity breakdown for the SDR based scale factor at each half-iteration is shown in Table 2

Where,

Comp() refers to the Comparison operations, Add() refers to the Addition operations, and Div() refers to the Division operations.

Depending on which signal has been generated, the hard decision is performed on the correponding a-posteriori LLR to estimate the transmitted information. The decoding equations for the max Log-MAP algorithm are presented in the sub-sections 2.1, 2.2 and 2.3.

2.1. Max Log-MAP Turbo Decoding: Method 1

The decoding equations based on the Max-Log MAP algorithm used for the first decoder are [14], [13], [15]:

[mathematical expression not reproducible] (3)

Where,

[mathematical expression not reproducible] (l', l) is the branch transition probability for decoder 1 from state l' to state l of bit i (i = 0 or 1) at time instant t.

[mathematical expression not reproducible] (i) is the a-priori probability of bit i resulting from the channel extrinsic information and input to the first decoder.

r[0.sub.t] and r[1.sub.t] are the soft bits which have been de-mapped and correspond to the bipolar equivalent of the transmitted systematic bits, [mathematical expression not reproducible] and first parity bits, [mathematical expression not reproducible] respectively.

[[sigma].sup.2] is the noise variance.

The complexity breakdown for the branch transition probability is shown in Table 2. The number of computations is for one branch transition.

Where,

Log() refers to the Logarithmic operations,

Sub() refers to the Subtraction operations, and

Mult() refers to the Multiplication operations.

The forward recursive variable, [mathematical expression not reproducible](l), for a decoder with [M.sub.s] states at state l and time t is computed as follows [16] [17]:

[mathematical expression not reproducible] (4)

The max() operator outputs the maximum of the two forward metrics pertaining to each bit i for each of the state l. The complexity breakdown for the forward recursive variable at each state l is shown in Table 3.

The backward recursive variable, [mathematical expression not reproducible] (l), is computed as follows [16] [17]:

[mathematical expression not reproducible] (5)

The complexity breakdown for the backward recursive variable for each state l' is shown in Table 4.

The Log-Likelihood Ratio (LLR), [mathematical expression not reproducible](t) for the first decoder at time t and iteration r is computed as [16] [17]:

[mathematical expression not reproducible] (6)

The complexity breakdown for the LLR variable is shown in Table 5.

The extrinsic information [mathematical expression not reproducible](t) for the first decoder at time t and iteration r is computed as [16] [17]:

[mathematical expression not reproducible] (7)

Where,

[mathematical expression not reproducible] (t) is the de-interleaved version of the extrinsic information for the second decoder at time / and iteration (r-1). For the first iteration, [mathematical expression not reproducible](t), is initialized to zero. The complexity breakdown for an extrinsic LLR variable is shown in Table 6.

The a-priori probability for the second decoder, [mathematical expression not reproducible] (i) is computed as follows:

[mathematical expression not reproducible] (8)

Where, [mathematical expression not reproducible](t) is the interleaved version of [mathematical expression not reproducible](t).

The complexity breakdown required for the a-priori probability is shown in Table 7.

Where,

Exp() refers to the exponential operations, and Div() refers to the division operations.

The computations for the second decoder can now be started. The decoding equations based on the Max-Log MAP algorithm used for the second decoder are as presented in [16] [17]. The branch metric [15] is given as:

[mathematical expression not reproducible] (9)

Where,

[mathematical expression not reproducible] (l',l) is the branch transition probability for decoder 2 from state l' to state l of bit i (i = 0 or 1) at time instant t. [mathematical expression not reproducible] (i) is the a-priori probability of bit i derived from the channel extrinsic information and input to the second decoder.

[mathematical expression not reproducible] and r[2.sub.t] are the de-mapped soft bits corresponding to the bipolar equivalent of the interleaved systematic bits, [mathematical expression not reproducible] and second parity bits, [P.sub.2t] respectively.

[[sigma].sup.2] is the noise variance.

The complexity breakdown for the branch transition probability is similar to that for the first decoder as shown in Table 2. The forward recursive variable, [mathematical expression not reproducible] (l), for a decoder with [M.sub.s] states at state l and time t is computed as the following [16] [17]:

[mathematical expression not reproducible] (10)

The complexity breakdown for the forward recursive variable is similar to that for the first decoder as shown in Table 3. The backward recursive variable, [mathematical expression not reproducible](l), is computed as follows [16] [17]:

[mathematical expression not reproducible] (11)

The complexity breakdown for the backward recursive variable is similar to that for the first decoder as shown in Table 4. The Log-Likelihood Ratio (LLR), [mathematical expression not reproducible](t) for the second decoder at time t and iteration r is computed as [16] [17]:

[mathematical expression not reproducible] (12)

The complexity breakdown for a LLR variable is similar to that for the first decoder as shown in Table 4. The extrinsic information, [mathematical expression not reproducible](t), for the second decoder at time t and iteration r is computed as [16] [17]:

[mathematical expression not reproducible] (13)

Where, [mathematical expression not reproducible] (t) is the interleaved extrinsic information for the first decoder at time t and iteration r.

The complexity breakdown for an extrinsic LLR variable is similar to that for the first decoder as shown in Table 6. The a-priori probability for the first decoder, [mathematical expression not reproducible](i) is computed as follows:

[mathematical expression not reproducible] (14)

Where,

[mathematical expression not reproducible] (t) is the de-interleaved version of [mathematical expression not reproducible] (t).

The number of computations required for the a-priori probability is similar to that for the first decoder as shown in Table 7. For the second iteration, the same computations are repeated by the first and second decoders with the updated values of the a-priori probabilities.

2.2. Max Log-MAP Turbo Decoding: Method 2

In [18], an approximate Log BCJR algorithm has been presented. The decoding equations are presented next.

Where,

[mathematical expression not reproducible] is the soft decisions of the received bit r[0.sub.t].

[mathematical expression not reproducible] (t) is the de-interleaved extrinsic LLR from decoder 2 in the previous iteration.

The transition state branch metrics are computed as below:

[mathematical expression not reproducible] (16)

[mathematical expression not reproducible] (17)

Where,

[mathematical expression not reproducible] (l',l) is the branch transition metric for the systematic information,

[mathematical expression not reproducible] (l',l) is the branch transition metric for the parity information, and

r[1.sub.t] is the received noisy parity information from the first encoder.

The complexity breakdown for one branch transition metric is shown in Table 8.

The forward recursive variable, [mathematical expression not reproducible](l), for a decoder with [M.sub.s] states at state l and time t is computed as follows [18]:

[mathematical expression not reproducible] (18)

The number of computations required for one forward recursive variable is shown in Table 9.

The backward recursive variable, [mathematical expression not reproducible] (l), is computed as follows [18]:

[mathematical expression not reproducible] (19)

The complexity breakdown required for one backward recursive variable is shown in Table 10.

The un-coded extrinsic log confidences are computed as the following:

[mathematical expression not reproducible] (20)

The complexity breakdown for the un-coded extrinsic log confidences is shown in Table 11.

The un-coded Extrinsic Log-Likelihood Ratio (LLR), [mathematical expression not reproducible](t) for the first decoder at time t and iteration r is computed as [18]:

[mathematical expression not reproducible] (21)

The complexity breakdown for the un-coded extrinsic LLRs is shown in Table 12.

The systematic and extrinsic information are interleaved to be fed to the second decoder:

[mathematical expression not reproducible] (22)

[mathematical expression not reproducible] (23)

The un-coded a-priori input information for the second decoder is computed as the following:

[mathematical expression not reproducible] (24)

The second decoder can now be started. The transition state branch metric is computed as below:

[mathematical expression not reproducible] (25)

[mathematical expression not reproducible] (26)

[mathematical expression not reproducible] (l',l) is the branch transition metric for the systematic information and second decoder

[mathematical expression not reproducible](l',l) is the branch transition metric for the parity information and second decoder

The complexity breakdown for the branch transition probability is similar to that for the first decoder as shown in Table 7. The forward recursive variable, [mathematical expression not reproducible], for a decoder with [M.sub.s] states at state l and time t is computed as follows [18]:

[mathematical expression not reproducible] (27)

The complexity breakdown for the forward recursive variable is similar to that for the first decoder as shown in Table 8. The backward recursive variable, [mathematical expression not reproducible] (l), is computed as follows [18]:

[mathematical expression not reproducible] (28)

The complexity breakdown for the backward recursive variable is similar to that for the first decoder as shown in Table 10 The un-coded extrinsic log confidences are computed as the following:

[mathematical expression not reproducible] (29)

The complexity breakdown for the un-coded extrinsic log confidences is similar to that for the first decoder as shown in Table 11. The un-coded Extrinsic Log-Likelihood Ratio (LLR), [mathematical expression not reproducible] (t) for the second decoder at time t and iteration r is computed as [18]:

[mathematical expression not reproducible] (30)

The complexity breakdown for the un-coded extrinsic LLRs is similar to that for the first decoder as shown in Table 12. The extrinsic information is de-interleaved to be fed to the first decoder:

[mathematical expression not reproducible] (31)

The a-priori LLR to be fed to the first decoder is computed as:

[mathematical expression not reproducible] (32)

The a-posteriori LLR computation to be used in the hard-decision process is as the following:

[mathematical expression not reproducible] (33)

For the second iteration, the same computations are repeated by both decoders with the updated values of the a-priori LLRs.

2.3. Max Log-MAP Turbo Decoding: Method 3

This decoding method is depicted in [19] and [20].

[mathematical expression not reproducible] (34)

Where,

[mathematical expression not reproducible] (l',l) is the branch transition probability for decoder 1 from state l' to state l of bit t (t = 0 or 1) at time instant t.

[S.sub.0t] is the systematic information bit at time instant t.

r[0.sub.t] and r[1.sub.t] are the soft bits which have been de-mapped and correspond to the bipolar equivalent of the transmitted systematic bits, [S.sub.0t] and first parity bits, [P.sub.1t] respectively.

[mathematical expression not reproducible] is the channel reliability estimate and [[sigma].sup.2] is the noise variance.

The complexity breakdown for one branch transition probability is shown in Table 13.

The forward recursive variable, [mathematical expression not reproducible](l), for a decoder with [M.sub.s] states at state l and time t is computed as follows [16] [17]:

[mathematical expression not reproducible] (35)

The complexity breakdown for the forward recursive variable is similar to that for the first decoder with Method 1 as shown in Table 3. The backward recursive variable, [mathematical expression not reproducible] (l), is computed as follows [16] [17]:

[mathematical expression not reproducible] (36)

The complexity breakdown for one backward recursive variable is similar to that for the first decoder of Method 1 as shown in Table 4. The Log-Likelihood Ratio (LLR), [mathematical expression not reproducible] (t) for the first decoder at time t and iteration r is computed as [16] [17]:

[mathematical expression not reproducible] (37)

The complexity breakdown for the LLRs is similar to that for the first decoder of Method 1 as shown in Table 5. The extrinsic information [mathematical expression not reproducible](t) for the first decoder at time t and iteration r is computed as [16] [17]:

[mathematical expression not reproducible] (38)

Where,

[mathematical expression not reproducible] (t) is the de-interleaved version of the extrinsic information for the second decoder at time t and iteration (r-1).

The complexity breakdown for the extrinsic LLRs is similar to that for the first decoder of Method 1 as shown in Table 6. The a-priori probability for the second decoder, [mathematical expression not reproducible](i) is computed as follows:

[mathematical expression not reproducible] (39)

Where,

[mathematical expression not reproducible](t) is the interleaved version of [mathematical expression not reproducible](t).

The complexity breakdown for the a-priori probability is similar to that for the first decoder of Method 1 as shown in Table 7. The decoding operation for the second decoder can now be started. The decoding equations based on the Max-Log MAP algorithm used for the second decoder are [19], [20]:

[mathematical expression not reproducible] (40)

Where,

[mathematical expression not reproducible] (l',l) is the branch transition probability for decoder 2 from state l' to state l of bit t (t = 0 or 1) at time instant t.

[mathematical expression not reproducible] is the interleaved systematic information bit at time instant t.

[mathematical expression not reproducible] and r[2.sub.t] are the de-mapped soft bits corresponding to the bipolar equivalent of the interleaved systematic bits, [mathematical expression not reproducible] and second parity bits, [mathematical expression not reproducible] respectively.

[mathematical expression not reproducible] is the channel reliability estimate and [[sigma].sup.2] is the noise variance.

The complexity breakdown for the branch transition probability is similar to that for the first decoder as shown in Table 13. The forward recursive variable, [mathematical expression not reproducible](l), for a decoder with [M.sub.s] states at state l and time t is computed as the following [16] [17]:

[mathematical expression not reproducible] (41)

The complexity breakdown for the forward recursive variable is shown in Table 3. The backward recursive variable, [mathematical expression not reproducible] (l), is computed as follows [16] [17]:

[mathematical expression not reproducible] (42)

The complexity breakdown for the backward recursive variable is shown in Table 4. The Log-Likelihood Ratio (LLR), [mathematical expression not reproducible] (t) for the second decoder at time t and iteration r is computed as [16] [17]:

[mathematical expression not reproducible] (43)

The complexity breakdown for the LLRs is shown in Table 5. The extrinsic information, [mathematical expression not reproducible](t), for the second decoder at time t and iteration r is computed as [19], [20]:

[mathematical expression not reproducible] (44)

Where,

[mathematical expression not reproducible] (t) is the interleaved extrinsic information for the first decoder at time t and iteration r-1.

The complexity breakdown for the extrinsic LLRs is shown in Table 6. The a-priori probability for the first decoder, [mathematical expression not reproducible](i) is computed as follows:

[mathematical expression not reproducible] (45)

The complexity breakdown for the a-priori probability is shown in Table 7. For the second iteration, the same computations are repeated by the first and second decoders with the updated values of the a-priori probabilities.

2.4. Analysis of Computational Complexity

In this section, a comparison of the computational complexities for the three decoding methods of binary LTE Turbo codes has been performed. The complexity breakdowns at each half-iteration for Methods 1, 2 and 3 with respect to the number of computations are shown in Table 14,

Table 15 and

Table 16 respectively. An explanation on the values obtained for the metrics of Method 1 computed over one half-iteration is given next. Table 2 shows the number of computations for a single branch transition metric of equation (3). There are N transitions in all in the trellis and each transition in the trellis consists of 16 branch transition metrics. Hence, the branch transition metrics are scaled by a factor of 16 and N. The number of computations for the forward recursive variable of equation (4) and backward recursive variable of equation (5) as shown in Table 3 and Table 4 respectively are multiplied by 8 and N since there are 8 states for each transition over a total packet length of N. Table 5 shows the computations for the a-posteriori LLRs of equation (6) which have to be multiplied by N for the whole packet length. The computations of the extrinsic LLRs of equation (7) as shown in Table 6 are also multiplied by N. Similarly, the computations of the a-posteriori probabilities of equations (8) as shown in Table 7 are multiplied by the packet length, N.

The values obtained for the metrics computed over one half-iteration for Method 2 are explained next. The number of computations for the branch transition metric of equations (16-17) shown in Table 8 are multiplied by 8 and N to compute the transitions pertaining to the systematic information bits equal to 1. The number of mathematical computations for the forward recursive variable, backward recursive variable and un-coded extrinsic log confidences are multiplied by the number of states, 8, and the packet length, N. The computations of the extrinsic LLRs of equation (21) as shown in Table 11 are multiplied by the packet length, N.

The values obtained for the metrics computed for Method 3 over one half-iteration are explained next. The number of mathematical computations for the branch transition metric of equation (34) shown in Table 13 are multiplied by 16 and N as explained for Method 1. The computations for the forward recursive variable, backward recursive variable, a-posteriori LLRs, extrinsic LLRs and a-posteriori probabilities are exactly as explained for Method 1.

The total number of different computations required for each of the decoding method can be compared to analyse the number of computations as shown in Table 17.

Table 16 shows that the number of mathematical operations required by Methods 1, 2 and 3 are 7, 3, and 5 respectively. Clearly, Method 2 requires fewer mathematical operations compared to Methods 1 and 3. Method 1 requires 16N Logarithm operations while Methods 2 and 3 require none. 3N exponential operations are required by bot h Methods 1 and 3 while Method 2 requires none. All the 3 methods require the same number of Max operations, i.e 18N. Method 3 requires the maximum number of addition operations which is 103 N followed by Method 2 which requires 88N and finally Method 1 which needs 82N. The number of subtraction operations is highest for Method 1, i.e 51 N followed by Methods 3 and 2 which require 3 N and 1 N subtraction operations respectively. Only Methods 1 and 3 require multiplication operations of 32 N and 48 N respectively. 2 N division operations are required by Method 1 only.

3. Simulation Results

In this section, the performances of the different decoding methods are compared. Three modulation schemes have been used, namely: Binary Phase Shift Keying (BPSK), Quadrature Phase Shift Keying (QPSK), and 16-Quadrature Amplitude Modulation (QAM). An interleaver size of 6144 bits has been used in all the simulations. The parameters for the LTE Turbo code used are as follows [14]:

Generator: G = [1, g1/g2], where g1 = 15 and g2 = 13 in Octal.

Code-rate = 1/3 and channel model: Complex AWGN. QPP Interleaver parameters: [f.sub.1]= 283 and [f.sub.2] = 480 Interleaver size, N= 6144 bits.

Maximum number of iterations, T = 12.

The BER performance of binary LTE Turbo codes with BPSK modulation with early stopping is shown in Figure 3. The overall number of computations at each [E.sub.b]/[N.sub.0] for each decoding method is shown in Figure 5. A more detailed breakdown of the total number of computations per mathematical operation is shown in Figure 6.

It can be observed from Figure 3 that all 3 decoding methods have similar error performances for almost the whole [E.sub.b]/[N.sub.0] range despite the differences in total number of different mathematical operations required. The performance of binary LTE Turbo codes with SDR based early stopping in terms of the average number of iterations required is shown in Figure 4.

It can be observed from Figure 4 that all 3 decoding methods require almost the same number of average decoding iterations for the range [E.sub.b]/[N.sub.0] [less than or equal to] 0.7 dB despite the differences in total number of different mathematical operations required. For the range [E.sub.b]/[N.sub.0] > 0.7 dB Methods 1 and 3 require fewer average decoding iterations as compared to Method 2. The overall number of computations for binary LTE Turbo codes with B-PSK modulation and SDR stopping is shown in Figure 5.

It can be observed from Figure 5 that all 3 decoding methods have different overall number of computations. Method 2 has the least number of overall computations throughout the whole [E.sub.b]/[N.sub.0] range. Method 3 gives an average gain of 3.3812x[10.sup.6] computations over Method 1. Method 2 gives an average gain of 1.1189x[10.sup.7] computations over Method 1. Method 2 gives an average gain of 7.8075x[10.sup.6] computations over Method 3. The breakdown of the overall number of computations per mathematical operation is shown in Figure 6.

It can be observed from Figure 6 that all 3 decoding methods use approximately the same number of maximum operations throughout the whole [E.sub.b]/[N.sub.0] range. Another observation is that eventhough Method 1 uses fewer addition operations than Methods 2 and 3 over the whole [E.sub.b]/[N.sub.0] range, there are the large numbers of logarithm and division operations which are also used.

The BER performance of binary LTE Turbo codes with Q-PSK modulation with SDR stopping is shown in Figure 7.

It can be observed from Figure 7 that all 3 decoding methods with SDR stopping have almost similar error performances for the whole [E.sub.b]/[N.sub.0] range despite the differences in total number of different mathematical operations required. The average number of iterations for binary LTE Turbo codes with QPSK modulation and SDR stopping is shown in Figure 8.

It can be observed from Figure 8 that all 3 decoding methods have almost similar average number of decoding iterations throught the whole [E.sub.b]/[N.sub.0] range. The overall number of computations for binary LTE Turbo codes with QPSK modulation and SDR stopping is shown in Figure 9.

It can be observed from Figure 9 that all 3 decoding methods have different overall number of computations. Method 2 has the least number of overall computations throughout the whole [E.sub.b]/[N.sub.0] range. Method 3 gives an average gain of 3.3510x[10.sup.6] computations over Method 1. Method 2 gives an average gain of 1.1417x[10.sup.7] computations over Method 1. Method 2 gives an average gain of 8.0665x[10.sup.6] computations over Method 3. The breakdown of the overall number of computations per mathematical operation is shown in Figure 10.

It can be observed from Figure 10 that all 3 decoding methods use approximately the same number of maximum operations throughout the whole [E.sub.b]/[N.sub.0] range. Another observation is that eventhough Method 1 uses fewer addition operations than Methods 2 and 3 over the whole [E.sub.b]/[N.sub.0] range, there are the large numbers of logarithm and division operations which are also used.

The BER performance of binary LTE Turbo codes with 16-QAM and SDR stopping is shown in Figure 11.

It can be observed from Figure 11 that all 3 decoding methods with SDR stopping have almost similar error performances for the range [E.sub.b]/[N.sub.0] [less than or equal to] 2.4 dB despite the differences in total number of different mathematical operations required. For the range [E.sub.b]/[N.sub.0] > 2.4 dB, Methods 2 and 3 outperform Method 1 with a gain of 0.1dB on average. The average number of iterations for binary LTE Turbo codes with 16-QAM and SDR stopping is shown in Figure 12.

It can be observed from Figure 12 that all 3 decoding methods have almost similar average number of decoding iterations throught the whole [E.sub.b]/[N.sub.0] range. The overall number of computations for binary LTE Turbo codes with 16-QAM and SDR stopping is shown in Figure 13.

It can be observed from Figure 13 that all 3 decoding methods have different overall number of computations. Method 2 has the least number of overall computations throughout the whole [E.sub.b]/[N.sub.0] range. Method 3 gives an average gain of 2.8108x[10.sup.6] computations over Method 1. Method 2 gives an average gain of 9.9390x[10.sup.6] computations over Method 1. Method 2 gives an average gain of 7.1282x[10.sup.6] computations over Method 3. The breakdown of the overall number of computations per mathematical operation is shown in Figure 14.

It can be observed from Figure 14 that all 3 decoding methods use approximately the same number of maximum operations throughout the whole [E.sub.b]/[N.sub.0] range. Another observation is that eventhough Method 1 uses fewer addition operations than Methods 2 and 3 over the whole [E.sub.b]/[N.sub.0] range, there are the large numbers of logarithm and division operations which are also used.

4. Conclusion

In this paper, a performance analysis of three different iterative decoding techniques for the Max-Log MAP algorithm with SDR-based early stopping has been presented for binary LTE Turbo codes. Three different decoding methods have been shown for Binary LTE Turbo codes with BPSK, Q-PSK and 16-QAM. It can be observed in Figure 3, that with BPSK modulation, the three decoding methods have almost similar performance over the whole [E.sub.b]/[N.sub.0] range. From Figure 7, it can be observed that with QPSK modulation, the three decoding methods have almost similar performance over the whole [E.sub.b]/[N.sub.0] range. Finally, in Figure 11, it can be observed that with 16-QAM, Methods 2 and 3 outperform Method 1 with a gain of 0.1 dB on average for the range [E.sub.b]/[N.sub.0] > 2.4 dB. The different schemes perform differently in the waterfall and error floor regions for different modulation schemes. From the breackdown of the overall computations, it is observed that eventhough Method 1 uses fewer addition operations than Methods 2 and 3 over the whole [E.sub.b]/[N.sub.0] range, there are the large numbers of logarithm and division operations which it uses. A possible future work which can be envisaged from this work would be to perform more in-depth analysis of the decoding mechanisms for even higher order modulation schemes and different code-rates. Another interesting future work would be to provide an analytical proof of the BER performances of these three Turbo decoding techniques using EXtrinsic Information Transfer (EXIT) charts.

5. Acknowledgements

The technical support of the University of Mauritius and the financial support of the Tertiary Education Commission is duly acknowledged.

6. References

[1] C. Berrou, A. Glavieux and P. Thitimajshima, "Near Shannon limit error-correcting coding and decoding: Turbo codes," in IEEE Trans., May 1993.

[2] Y. Beeharry, T. P. Fowdur and K. M. S. Soyjaudah, "Symbol Level Decoding Algorithms for Duo-Binary Turbo codes," HUM Journal (Article in Press), 2017.

[3] J. Geldmacher, K. Hueske, M. Kosakowski and J. Gotze, "Application of syndrome based Turbo decoding with adaptive computational complexity in LTE downlink," Advances in Radio Science, vol. 2012, no. 10, pp. 159-165, 2012.

[4] R. G. Maunder, "A Fully-Parallel Turbo Decoding Algorithm," IEEE transactions on Communications, vol. 63, no. 8, pp. 2762-2775, 2015.

[5] R. El Chall, F. Nouvel, M. Helard and M. Liu, "Iterative receivers combining MIMO detection with turbo decoding: performance-complexity trade-offs," EURASIP Journal on Wireless Communications and Networking, vol. 2015, no. 69, pp. 1-19, 2015.

[6] F. Li and A. Wu, "On the New Stopping Criteria of Iterative Turbo Decoding by Using Decoding Threshold," IEEE Trans, on Signal Processing, vol. 55, no. 11, pp. 5506-5516, 2007.

[7] Z. Wang, H. Suzuki and K. K. Parhi, "VLSI implementation issues of turbo decoder design for wireless applications," Proc. of IEEE Workshop Signal Process. Syst., pp. 503-512, 1999.

[8] J. Hagenauer, E. Offer and L. Papke, "Iterative decoding of binary block and convolutional codes," IEEE Trans. Inf. Theory, vol. 42, no. 2, pp. 429-445, 1996.

[9] R. Y. Shao, S. Lin and M. P. C. Fossorier, "Two Simple Stopping Criteria for Turbo Decoding," IEEE Trans. Commun., vol. 47, no. 8, pp. 1117-1120, 1999.

[10] Y. Wu, B. Woerner and J. Ebel, "A Simple Stopping Criterion for Turbo Decoding," IEEE Commun. Lett., vol. 4, no. 8, pp. 258-260, 2000.

[11] L. Henrik, "Turbo Decoder with early stopping criteria," Lund University Libraries, 2016.

[12] T. P. Fowdur, Y. Beeharry and K. M. S. Soyjaudah, "A novel scaling and early stopping mechanism for LTE turbo code based on regression analysis," Annals of Telecommunications, pp. 1-20,2016.

[13] "3GPP: Technical Specifications Rel. 8," 3GPP, 2009.

[14] F. Khan, LTE for 4G Mobile Broadband Air Interface Technologies and Performance, Cambridge University Press, 2009.

[15] B. Vucetic and J. S. Yuan, Turbo Codes: Principles and Applications, Kluwer Academic Publications, 2000, pp. 58-75.

[16] T. P. Fowdur, Y. Beeharry and K. M. S. Soyjaudah, "Performance of Turbo coded 64-QAM with Joint Source Channel Decoding, Adaptive Scaling and Prioritised Constellation Mapping," in CTRQ, 6th International Conference on Communication Theory, Reliability and Quality of Service, Venice, Italy, 2013.

[17] T. P. Fowdur, Y. Beeharry and K. M. S. Soyjaudah, "Performance of LTE Turbo Codes with Joint Source Channel Decoding, Adaptive Scalig and Prioritised QAM Constellation Mapping," International Journal on Advances in Telecommunications, vol. 6, no. 3 & 4, pp. 143-152, 2013.

[18] L. Li, "University of Southampton," 2015. [Online]. Available:http://users.ecs.soton.ac.uk/rm/wp-content/liang_li_nine_month_report.pdf [Accessed 18 April 2015].

[19] V. Tursenia, "Performance Comparison of Turbo Code in WiMAX Sysetem with Various Detection techniques," International Journal of Engineering Research, vol. 2, no. 3, pp. 232-236, 2013.

[20] S. A. Abrates, April 2004. [Online]. Available: http://paginas.fe.up.pt/~sam/textos/From%20BCJR%20to%20turbo.pdf [Accessed 01 May 2015].

Yogesh BEEHARRY (1), Tulsi Pawan FOWDUR (1), Krishnaraj M. S. SOYJAUDAH (1)

(1) Department of Electrical and Electronic Engineering, University of Mauritius, Reduit, Mauritius y.beeharry@uom.ac.mu, p.fowdur@uom.ac.mu, ssoyjaudah@uom.ac.mu

Received on: 16.01.2017

Accepted on: 23.06.2017

Yogesh Beeharry is currently a PhD student in the field of error control coding at the University of Mauritius. He holds a BEng (Hons) Electronics and Communications engineering with First class honours from the University of Mauritius. He was also the recipient of the Mrs. L. F. Lim Fat Engineering Gold medal. His main research interests are: error control coding, Turbo codes and source and channel coding.

Dr. T. P. Fowdur received his BEng (Hons) degree in Electronic and Communication Engineering with first class honours from the University of Mauritius in 2004. He was also the recipient of a Gold medal for having produced the best degree project at the Faculty of Engineering in 2004. In 2005 he obtained a full-time PhD scholarship from the Tertiary Education Commission of Mauritius and was awarded his PhD degree in Electrical and Electronic Engineering in 2010 by the University of Mauritius. He is presently a Senior Lecturer at the Department of Electrical and Electronic Engineering at the University of Mauritius. His research interests include Coding Theory, Multimedia and Wireless Communications, Networking and Security.

Professor K. M. S. Soyjaudah is a Professor of Communications Engineering at the University of Mauritius. Professor Soyjaudah has a number of publications in the fields of Communications engineering, error control coding, information theory among others.

Table 1. Complexity breakdown for one SDR-based scale factor Comp() Add() Div() Total SDR Scale N N-1 1 2N Factor Table 2. Complexity breakdown for one branch transition metric of Decoder 1 with Method 1 Log() Add() Sub() Mult() Total Branch 1 1 3 2 6 Transition Metric Table 3. Complexity breakdown for one Forward recursive variable of Decoder 1 with Method 1 Max() Add() Total Forward 1 2 3 Recursive Variable Table 4. Complexity breakdown for one Backward recursive vatiable of Decoder 1 with Method 1 Max() Add() Total Backward 1 2 3 Recursive Variable Table 5. Complexity breakdown for the Log-Likelihood Ratio of Decoder 1 with Method 1 Max() Add() Sub() Total Log 2 32 1 35 Likelihood Ratio Table 6. Complexity breakdown for an extrinsic LLR of Decoder 1 with Method 1 Sub() Total Extrinsic Log 2 2 Likelihood Ratio Table 7. Complexity breakdown for the a-priori probability of Decoder 1 with Method 1 Exp() Add() Div() Total Log 3 2 2 7 Likelihood Ratio Table 8. Complexity breakdown for a branch transition metric of Decoder 1 with Method 2 Add() Total Branch 1 1 Transition Metric Table 9. Complexity breakdown for a forward recursive variable of Decoder 1 with Method 2 Max() Add() Total Forward 1 4 5 Recursive Variable Table 10. Complexity breakdown for a backward recursive variable of Decoder 1 with Method 2 Max() Add() Total Backward 1 4 5 Recursive Variable Table 11. Complexity breakdown for the un-coded extrinsic log confidences of Decoder 1 with Method 2 AddO Total Un-coded extrinsic 2 2 Log confidences Table 12. Complexity breakdown for the un-coded extrinsic LLRs of Decoder 1 with Method 2 Max() Sub() Total Un-coded 2 1 3 extrinsic LLRs Table 13. Complexity breakdown for a branch transition metric of Decoder 1 with Method 3 Add() Mult() Div() Total Branch 2 3 1 6 Transition Metric Table 14. Computational complexity breakdown for Method 1 at one half-iteration Comp() Log() Exp() Max() Add() Branch Transition Metric 0 1x16xN 0 0 1 x 16 x N Forward Metric 0 0 0 1 x 8 x N 2 x 8 x N Backward Metric 0 0 0 1 x 8 x N 2 x 8 x N A-Posteriori LLR 0 0 0 2 x N 32 x N Extrinsic LLR 0 0 0 0 0 A-Posteriori Probabilities 0 0 3 x N 0 2 x N SDR Scale Factor N 0 0 0 N-1 TOTAL N 16 N 3 N 18N 83 N-1 Sub() Mult() Div() Total Branch Transition Metric 3 x l6 x N 2 x 16 x N 0 112 N Forward Metric 0 0 0 24 N Backward Metric 0 0 0 24 N A-Posteriori LLR 1 x N 0 0 35 N Extrinsic LLR 2 x N 0 0 2 N A-Posteriori Probabilities 0 0 2 x N 7 N SDR Scale Factor 0 0 1 2N TOTAL 51N 32N 2 N+1 206N Table 15. Computational complexity breakdown for Method 2 at one half-iteration Comp() Max() Add() Sub() Div() Total Branch Transition Metric 0 0 1 x 8 x N 0 0 8N Forward Metric 0 1 x 8 x N 4 x 8 x N 0 0 40 N Backward Metric 0 1 x 8 x N 4 x 8 x N 0 0 40 N Un-coded Extrinsic 0 0 2 x 8 x N 0 0 16 N Log Confidences Extrinsic LLR 0 2 x N 0 1 x N 0 3 N SDR Scale Factor N 0 N-1 0 1 2N TOTAL N 18N 89 N-1 1N 1 109 N Table 16. Computational complexity breakdown for Method 3 at one half-iteration Comp() Exp() Max() Add() Branch Transition Metric 0 0 0 2 x 16 x N Forward Metric 0 0 1 x 8 x N 2 x 8 x N Backward Metric 0 0 1 x 8 x N 2 x 8 x N A-Posteriori LLR 0 0 2 x N 32 x N Extrinsic LLR 0 0 0 0 A-Posteriori Probabilities 0 3 x N 0 7 x N SDR Scale Factor N 0 0 N-1 TOTAL N 3 N 18N 104N-1 Sub() Mult() Total Branch Transition Metric 0 3 x 16 x N 80 N Forward Metric 0 0 24N Backward Metric 0 0 24N A-Posteriori LLR 1 x N 0 35N Extrinsic LLR 2 x N 0 2N A-Posteriori Probabilities 0 0 10N SDR Scale Factor 0 1 2N TOTAL 37N 48N+1 177N Table 17. Total of the number of computations for the different operation at one half-iteration for the 3 Methods Comp() Log() ExpO Max() Add() Sub() Mult() Div() Method 1 N 16N 3N 18N 83N-1 51N 32N 2 N+1 Method 2 N 0 0 18N 89N-1 1N 0 1 Method 3 N 0 3N 18N 104N-1 3N 48N 1 TOTAL Method 1 206N Method 2 109N Method 3 177N

Printer friendly Cite/link Email Feedback | |

Author: | Beeharry, Yogesh; Fowdur, Tulsi Pawan; Soyjaudah, Krishnaraj M.S. |
---|---|

Publication: | Istanbul University - Journal of Electrical & Electronics Engineering |

Article Type: | Report |

Date: | Jul 1, 2017 |

Words: | 7502 |

Previous Article: | Effects of Co-Channel Interference on Sum-Rate Based Relay Selection Method for A Dual-Hop Multiple Full-Duplex Two-Way Wireless Relaying Networks. |

Next Article: | THE MODELLING RECORDED FAULTS IN RAILWAYS AND PREDICTION. |

Topics: |