The Turbo Code and an Efficient Decoder Implementation using MAP Algorithm for Software Defined Radios

The Turbo Code and an Efficient Decoder Implementation using MAP Algorithm for Software Defined Radios

Mr Rupesh Singh (Principal), Dr. Nidhi Singh (Associate Professor) SriGanganagar Engineering College,SriGanganagar.

Abstract: After the initial interest caused by the appearance of turbo codes in 1993. special attention on the implementation has led to their adoption in some of the most important 3G standards. However. future broadband systems (with data rates up to 155 Mbps) still require a better speed/ latency/ power performance than those found in current implementations. Several steps towards an efficient implementation have resulted in turbo decoding architectures that reach 10 Mb/s with reasonable power and latency. The possibility of using turbo codes in real systems has triggered the interest of standardization bodies. A major landmark was the adoption of turbo codes as one of the IMT-2000 channel coding standards for third generation (3G) mobile communications systems known as UMTS. It was followed by the approval of turbo codes as the major coding scheme in the interactive channel for digital video broadcasting (DVB-RCS) and in the CCSDS standard for telemetry in space research missions. We aimed at optimizing turbo coding implementations as defined in 3G standards towards specifications that met broadband wireless communications. the original MAP algorithm is of great complexity, so it is impractical to implement it in hardware. So the Log-MAP and Max- Log-MAP algorithms were proposed later to reduce the arithmetic complexity while still maintaining good decoding performance. Due to its excellent error correction performance, many communication standards have chosen Turbo codes as the Forward Error Correction (FEC) codes, such as CDMA-2000, W-CDMA, DVB-RCS, HSDPA, UMTS, IEEE 802.16e

WiMax, and 3GPP LTE. The CDMA2000 standard provides mixed voice and data services. A parent rate-1/5 turbo code consisting of two identical, eight state, parallel, rate-1/3 constituent recursive systematic convolutional (RSC) encoders is employed. This paper provides a description of the turbo code used by the UMTS third-generation cellular standard, as standardized by the Third-Generation Partnership Project (3GPP), and proposes an efficient decoder suitable for insertion into software-defined radio or for use in computer simulations. Because the decoder is implemented in software, rather than hardware, singleprecision floating-point arithmetic is assumed and a variable number of decoder iterations is not only possible but desirable. The well-known log-MAP decoding algorithm with detailed analysis is proposed and the simulation results are shown.

1. Introduction: Due to their near Shannon-capacity [1] performance, turbo codes have received a considerable amount of attention since their introduction [2]. They are particularly attractive for cellular communication systems and have been included in the specifications for both the WCDMA (UMTS) and CDMA2000 third-generation cellular standards. At this time, the reasons for the superior performance of turbo codes [3,4] and the associated decoding algorithm [5,6] are, for the most part, understood.

   The purpose of this paper is to explain the phenomenal performance of turbo codes and to derive the decoding algorithm. Also the purpose is to clearly explain an efficient decoding algorithm suitable for immediate implementation in a software radio receiver. In order to provide a concrete example, the discussion is limited to the turbo code used by the Universal Mobile Telecommunications System (UMTS) specification, as standardized by the Third-

   Generation Partnership Project (3GPP) [7]. The decoding algorithm is based on the log-MAP algorithm [8], although many parts of the algorithm have been simplified without any loss in performance.

   Some critical implementation issues are discussed, in particular the decoding iterations. Simple, but effective, solutions for MAP Algorithm are proposed and illustrated through computer simulations. In the description of the algorithm, we have assumed that the reader has a working knowledge of the Viterbi algorithm [9]. Information on the Viterbi algorithm can be found in a tutorial paper by Forney [10].

2. The UMTS Turbo Encoder and Decoder:

   As shown in Fig. 1, the UMTS turbo encoder is composed of two constraint length 4 recursive systematic convolutional (RSC) encoders concatenated in parallel [12]. The feedforward generator is 15 and the feedback generator is 13, both in octal. The number of data bits at the input of the turbo encoder is K. Data is encoded by the first (i.e., upper) encoder in its natural order and by the second (i.e., lower) encoder after being interleaved. At first, the two switches are in the up position. The interleaver is a matrix with 5, 10, or 20 rows and between 8 and 256 columns (inclusive), depending on the size of the input word. Data is read into the interleaver in a rowwise fashion (with the first data bit placed in the upper-left position of the matrix). Intrarow permutations are performed on each row of the matrix in accordance with a rather complicated algorithm, which is fully described in the specification [11].

   Fig.1

   The data bits are transmitted together with the parity bits generated by the two encoders (the systematic output of the lower encoder is not used and thus not shown in the diagram). Thus, the overall code rate of the encoder is rate 1/3, not including the tail bits. Zk is the parity output from the upper (uninterleaved) encoder, and Zk is the parity output from the lower (interleaved) encoder. After the K data bits have been encoded, the trellises of both encoders are forced back to the all-zeros state by the proper selection of tail bits. Unlike conventional convolutional codes, which can always be terminated with a tail of zeros, the tail bits of an RSC will de- pend on the state of the encoder. Because the states of the two RSC encoders will usually be different after the data has been encoded, the tails for each encoder

   must be separately calculated and transmitted. The tail bits are generated for each encoder by throwing the two switches into the down position, thus causing the inputs to the two encoders to be indicated by the dotted lines.

   Decoder: For each time tick k, decoding is done by calculating the L-values of a +1 bit. If it is positive, the decision is in favor of a +1. Calculation of the L-values or L(uk) is quite a complex process. The main equation used to calculate the L-value is this.

   (s' ).

   k (s).

   e (s' , s)

   k

   L(u ) Lc (u ) L .y Ls

   log u k 1

   (1)

   k k c k

   k 1 (s' (s). e (s' , s)

   k

   u k

   From this computation if L(uk) is positive, then uk is equal to +1. The first term, is the a- priori value from Decoder 2. This is the L-value of the a-priori probability of the bit in question. At first, the decoder has no idea what it is. A good guess is to assume it is 0.5. The second term, is computed by multiplying the systematic information with Lc. This value is the channel L-value and gives an indication of channel SNR. The third big term with all kinds of squiggly items is the a-posteriori probability.

   This number is calculated for each trellis segment. Remember that we can only have one result for a trellis section, a +1 or -1. The L(uk) calculation tells us what that number is, The big equation can be written simply as sum of three pieces of information. L-apriori This is our initial guess about a +1 bit in first iteration L-Channel – This is related to channel SNR and systematic bit nd is equal to Le the computed information in each iteration is called the a- posteriori L-value. The L-channel value does not change from iteration to iteration since is it given by . Neither the Lc nor the systematic bit changes from iteration to iteration, So lets called it K. The only two items that change are the a-priori and a-posteriori L-values. A-priori value goes in, it is used to compute the new a-posteriori probability and then it can be used to compute L(uk) or is passed to the next decoder. Although in the example we compute L(uk) each time, during actual decoding this is not done. Only a-posteriori metric is computed and decoders and keep doing this either a fixed number of times or until it converges. L-posteriori is also called Extrinsic information.

   A branch metric is the correlation of the received signal with its trellis values. In a nutshell, if the received values are the same sign as the coded bits, then the correlation will be high. For each decoder, there are full transition branch metrics which incorporate, the systematic and the parity bits and partial branch metrics which incorporate only the parity bits.

   Fif.2 Iteration cycle of MAP Turbo Decoding

   1. Computing full branch metrics:

      The full branch metric is given by the equation

      ' 1 e 1 1

      1 1,s 1

      q

      1

      1, p 1

      (s , s)

      exp

   2. .L (ck ).ck

   Lc . 2 .yk

   .ck

   exp

   i 2

   Lc . 2 .yk

   .ck

   (2)

   The data required is Lc, the systematic value, parity value and trellis coded values. We compute this for each branch of the trellis for all seven time ticks.

   1. Compute partial branch metrics:

      These values are based only on parity bits. We will use these to compute the total extrinsic L- values. The equation for calculating the partial metrics is given by:

      0 ' q 1

      i, p i

      (s , s) exp

      i 2

      Lc . 2 .yk

      .ck

      (3)

   2. Calculation of forward metrics Encoding always starts in state 1. So we assume that signal can only be in state 1 at time k =0. The initial value of the forward metric is set at 1.0. The other three states are given value of 0.0. Meaning, these are not possible states. Thereafter the forward metrics are computed recursively for each state (not branches). The equation is:

      (s)

      k 1 (s ' )

      s'

      (s ' , s)

      k

      (4)

      k

      k

      s s'

      k 1 (s ' )

      (s ' , s)

   3. Computing backward state metrics:

      '

      k

      k (s) (s , s)

      (s' ) s (5)

      k 1

      k 1

      s s'

      k 2 (s' )

      (s ' , s)

      We assume that the signal will end in state 1. (Tail bits are added to force it end in state 1.) The ending state is always s1, so it gets a value of 1.0 just as the forward state metric. The rest of the three states at k = 7 are given a backward state value of zero.

      k

   4. Computing Extrinsic L-values: Now we will compute the Extrinsic L-value. Which are given by the product of the all three metrics.

   k (s)

   k 1 (s ' ).

   e (s ' , s).

   k (s)

   (6)

   To compute the L-value we need the ratio of these numbers for the +1 and -1 branches. For that we add the top four branch metrics and divide by the sum of the bottom four branch metrics to satisfy the following equation:

   (s' ).

   k (s).

   e (s' , s)

   k

   log u k 1

   k

   k 1 (s' ). (s). e (s' , s)

   u k

   Take the natural log of the ratio. This is the extrinsic value output for this iteration. These values after interleaving go to Decoder 2 and become its a-priori probabilities. Normally the decoder at this point would stop because it has done its job of computing the extrinsic value. But we will compute the L-value of the bit to show you how the bit decisions can be made at any iteration.

3. SIMULATION SET UP: The software packages and MATLAB are used to accomplish complicated calculations. The simulation models are implemented using the software package MATLAB. The results of the mathematical analysis and computer simulation are displayed

   using graphs in which the bit error rate is plotted versus signal-to-noise ratio (Eb/N0) in decibels. Tables are also used to display results.

   The BER performance of the Simplified-Log-MAP algorithm is compared to that of the MAP, Log-MAP, and Max- Log-MAP algorithms. The simulation results are for a Turbo code with 1/2 code rate, N = 1024, m = 3, and the feedback and feedforward generator polynomials equal to 15oct and 17oct respectively. Three iterations were used for the simulations and the results in fig. 2 are for QPSK.

4. SIMULATION RESULTS & DISCUSSION

   The BER performance of the Simplified-Log-MAP algorithm is compared to that of the MAP, Log-MAP, and Max- Log-MAP algorithms. The simulation results are for a Turbo code with 1/2 code rate, N = 1024, m = 3, and the feedback and feedforward generator polynomials equal to I 5oct and I 7oct respectively. Three iterations were used for the simulations. As we can see from the results, the Log-MAP decoding algorithm has similar performance to the MAP algorithm. The performance loss for the MAX-Log-MAP compared to the MAP algorithm is from 0.2 dB. The SNR requirement for a given BER is higher at larger constellation sizes, therefore, the approximation of the logarithm has more significant effect on the BER performance of the MAX-Log-MAP algorithm.

   Table:1 Complexity Comparison obetween different MAP Algorithms

5. CONCLUSIONS:

   The Simplified Log-MAP has a negligible performance degradation compared to the MAP algorithm for QPSK constellation, while the performance loss is approximately 0.1 dB. It can be concluded from the above results that Simplified Log-MAP algorithm together with the new hardware implementation are an appropriate choices for implementing Turbo decoders in practice without any significant loss in performance.

   Fig. 2 BER performance of MAP-based decoding algorithms

   This paper introduces the next generation 3G technology and many communication standards have chosen Turbo codes as the Forward Error Correction (FEC) codes, such as CDMA-2000, W-CDMA, DVB-RCS, HSDPA, UMTS, IEEE 802.16e WiMax, and 3GPP LTE.

   The paper have assessed the performance of 3G TCs. The performance of 3G TCs by varying different components of encoder and decoder in the form of BER vs. Eb/No curve is shown.

6. FUTURE WORK:

   Diversity techniques can be applied to further improve the performance of the codes even when there is severe ISI present. The use of space-time coding scheme, which is based on the idea of the using of multiple transmitting and receiving antennas can be studied, while using turbo code as the channel coding scheme.

   Channel equalization techniques can also aid to improve the performance of the system and its inclusion in the system will be a good idea.

   Finally, crowded constellation scheme such as the trellis coded modulation is also an interesting area to be explored using turbo code.

7. REFERENCES:

1. SHANNON, C. E.: A mathematical theory of communication, Bell Syst. Tech. J., July and October 1948, 27, pp.379423 and 623656.

2. C. Berrou, A. Glavieux, and P. Thitimasjshima, Near Shannon limit error-correcting coding and decoding: Turbo-codes(1), Proc.IEEE Int. Conf. on Commun. (Geneva, Switzerland), pp. 10641070, May 1993.

3. S. Benedetto and G. Montorsi, Unveiling turbo codes: Some results on parallel concatenated coding schemes, IEEE Trans. Inform.Theory, Vol. 42, pp. 409428, Mar. 1996.

4. L. C. Perez, J. Seghers, and D. J. Costello, A distance spectrum interpretation of turbo codes, IEEE Trans. Inform. Theory, Vol. 42, pp. 16981708, Nov. 1996.

5. D. Divsalar, S. Dolinar, and F. Pollara, Iterative turbo decoder analysis base on density evolution, IEEE J. Select. Areas Commun., Vol. 19, pp. 891907, May 2001.

6. S. ten Brink, Convergence behavior of iteratively decoded parallel concatenated codes, IEEE Trans. Commun., Vol. 49, pp. 1727 1737, Oct. 2001.

7. European Telecommunications Standards Institute, Universal mobile telecommunications system (UMTS): Multiplexing and channel coding (FDD), 3GPP TS 125.212 version 3.4.0, pp. 1420, Sept. 23, 2000.

8. P. Robertson, P. Hoeher, and E. Villebrun, Optimal and sub-optimal maximum a posteriori algorithms suitable for turbo decoding, European Trans. on Telecommun., Vol. 8, pp. 119125, Mar./Apr. 1997.

9. A. J. Viterbi, Error bounds for convolutional codes and an asymptotically optimum decoding Algorithm, IEEE Trans. Inform. Theory, Vol. 13, pp. 260269, Apr. 1967.

10. G. D. Forney, The Viterbi algorithm, Proc. IEEE, Vol. 61, pp.268278, Mar. 1973.

11. Third Generation Partnership Project 2 (3Gpp2), Physical Layer Standard for cdma2000 Spread Spectrum Systems, Release C, 3GPP2 C.S0002-C, version 1.0, 2002, pp. 115-122.

12. A. G. Amat, G. Montorsi, S. Benedetto, D. Vogrig, A. Neviani, A. Gerosa, An analog turbo decoder for the UMTS standard, International Symposium on Information Theory, ISIT, 2004, pp. 296.

13. F. Marx, J. Farah, Improved turbo-coded UMTS systems with Unequal Error Protection of compressed video sequences transmitted over frequency-selective channels, International Conference on Communications, vol. 5, June 2004, pp. 3091 – 3095.