Low Complexity Modified Turbo Decoders

Low Complexity Modified Turbo Decoders

A.Sagar, A.Rajagopal, K.Karibasappa

Dept of ECE, Dayananda Sagar College of Engineering, Bangalore, Karnataka-560078, India

Abstract — In Forward Error Correction (FEC) it is desirable to have low Bit Error Rates (BER) and low decoder complexity for reliable data transmission in Digital Communication System. FEC such as Block codes and Convolutional codes are included in standards for 2G wireless networks. Convolutional codes give greater performance compared to Block codes with increase in implementation complexity. Recently, Turbo Convolutional Codes (TCC) have been introduced in standards for 3G wireless networks. TCC are more powerful FEC codes compared to Block codes and have performance nearer to the Shannon channel capacity. TCC decoders is based on iterative decoding thus it requires more computations inorder to decode information therefore increasing the implementation complexity. These papers present a review on a new form of Low complexity decoders for modified turbo codes. Low complexity Modified turbo decoders reqiures less decoding computation compared to TCC as they use multiple concatenations of simple block codes and convolutional codes inorder to simplify decoder complexity and computation.

Index terms — ILCHTC, Iterative decoding, low complexity decoding, Turbo codes, Zig-Zag codes.

1. INTRODUCTION

   In Digital communication system, Forward Error Correction plays an important role in effective usage of available bandwidth and transmission power. Shannon proved that the improvement of error-correction techniques with increasing coding gain has a limitation on the channel capacity. [1] Since then, FEC code designers are working on constructing new codes that can operate closer to the Shannon limit. However, any improvement in coding gain comes at the expense of decoder complexity and it is neccassary that practical implementation of the designed codes is compactible for existing technologies. A new class of binary parallel concatenated Recursive Systematic Convolutional (RSC) codes called turbo codes as the performance very nearer to theoretical bounds and is capable of achieving power efficiency close to the Shannon limit. Turbo codes have been adopted by the International Telecommunication Union (ITU) to effectively improve system capacity for Third-Generation (3G) wireless highspeed data services high- speed data services (CDMA2000 and W- CDMA)[1]. The error correcting capability of Turbo codes increases with increase in constraint length, however computational complexity of Turbo codes increases exponentially with the increase in constraint length of constituent convolutional codes.

   A In past few years, several Techniques to achieve low complexity Turbo decoders designs have appeared in the literature and it is seen that Modified Turbo Code (MTC) provides a good tradeoff between reduced complexity and error performance. It has been shown that low complexity modified Turbo codes provide error correcting capability which is equivalent to Turbo codes. Recently, a class of modified Turbo codes termed as Low Complexity Hybrid Turbo Codes (LCHTC) has been proposed [5]. In order to improve the speed of error convergence, a new code, called as Improved Low Complexity Hybrid Codes (ILCHTC) is constructed by modifying the structure of LCHTC encoder.

   Generally TCC decoding Algorithm is based on A Posteriori Probability (APP) which is computationally complex [1] as an alternative Maximum A Posteriori (MAP) algorithm in log domain is used then decoder complexity is about 480 Addition Equivalent Operations per Information Bit per Iteration (AEO/IB/I) and ILCHTC is multiple concatenations of simple ZigZag codes and RSC codes However, the decoding complexity of the concatenated zigzag codes is considerably lower. For instance, the MLA algorithm costs only 20 AEO/IB/Iter for rate-1/2 concatenated zigzag codes with four constituent encoders [2]. According to simulation results it is seen that ILCHTC achieve Bit Error Rate (BER) which is comparable to TCC. Simulation results show that rate-1/3 ILCHTC achieve Bit Error Rate.(BER) of 10-5 at Bit Energy to Noise Ratio (Eb/No) of 2.6 dB, which is 0.5 dB higher than Eb/No for TCC Moreover, ILCHTC decoder requires half the number of computations as compared to those required for TCC decoder.

   The rest of the section is organized as follows, section II Describes modified turbo codes. In section III Low Complexity Modified Turbo Decoders will be described. In section IV comparsion of different decoder complexity are discussed. Matlab simulation results in section VI and conclusion in section VII

2. DESCRIPTION OF MODIFIED TURBO CODES

   Modified turbo codes (MTC) are a concatenation of both convolutional and block codes. ILCHTC is multiple concatenations of simple ZigZag codes and RSC codes and code rate is 1/3 as parity is generated by 2 different encoders both zigzag and Recursive Systematic Convolutional (RSC) encodes information bits.

   1. Concatenated Zigzag Codes

      In zigzag encoder, a sequence of N data bits is arranged in a J × K array and information bit d (j, k) is denoted as (k + ((j – 1) × K))th bit. Also, d ={d( j, k)}, where, 1 j J and 1 k K. Concatenated zigzag codes are parallel concatenations of M constituent zigzag codes [2]. Let zigzag parity vector of an mth constituent encoder be represented by Z (m) = {Z (m) (k)}, where, 1 k

      K and 1 m M. Then, zigzag parity bit is calculated progressively as follows

      Z (m) (0) = 0. (1)

      For ILCHTC, code rate RIL is given by

      RIL =J/(J + L + M) (6)

      Code rate of ILCHTC is adjusted by changing J, L and M.

      Fig 1. General block diagram of ILCHTC encoder

      =1

      Z (m) (k) = [ d(j, k) + Z (m) (k 1)]. (2)

      Where summation symbol indicates XOR operation on Data bits. Code word, CZ and code rate, RZ for a concatenated zigzag code is given by

      CZ = {d, z(1), z(1), . . . , z(M)}.

      RZ =J/ (J + M). (3)

   2. ILCHTC Encoder

   Since RSC codes have better error-correcting capability, the Data bits are encoded by RSC code in first constituent encoder of ILCHTC [6]. To limit computational complexity only zigzag codes are used in remaining constituent encoders and ILCHTC encodes data bits array of size J × K, where N= J × K. In the first constituent encoder of ILCHTC, rate-1/2 RSC code encodes L rows of the information bit array. Let RSC parity vector for the jth row in first constituent encoder be represented by

   (1) = { (1) (k)}, 1 j L and 1 k K; L J. (4)

   Then, zigzag parity bits are computed for each row of Data bit array. Fig. 1 shows General block diagram of ILCHTC encoder. Parallel concatenation of M constituent encoders forms the overall encoder. Fig. 2 shows the overall ILCHTC encoder then, transmitted code word for ILCHTC, CIL is given by

   CIL = {d, (1), , (1) , . , , (1) , , (1), ,(2), , . , ()}.

   Fig 2. the overall ILCHTC encoder

   Fig 3. Low Complexity Modified Turbo Decoder

   1 2

   (5)

3. LOW COMPLEXITY MODIFIED TURBO DECODERS

   Let the codeword CIL be transmitted into channel using the bipolar format representing bit 0 as 1 and bit 1 as -1. Let IL Denote noisy received code vector by receiver

   for the transmitted code word CIL as IL = { , , }. Here, received vectors for data bits, convolutional parity bits and zigzag parity bits are , , and , respectively. Likelihood ratio (LR) of a received bit is given by

   R( |b) =P( |b = +1)/(P( |b = 1)). (7)

   L[q](dk(i, j))= [d (i-1)+ /p>

   [ 1

   ' [L[q](dk(i, j))]]

   e

   o < e

   Where P( |b = +1) is the probability of receiving if

   + <[ 1

   ' [L[q1](dk(i, j))]] (14)

   transmitted bit b is +1 [1]. Then, logarithm of likelihood ratio (LLR) of each received bit is represented by

   b= log(R( |b)). (8)

   where Lo is initialized as an I × J matrix of zeros.

   1. Final Log Likelihood Ratio Computation

      Initially, a priori value of LLR of each received bit [8] is given by

      L[q]( (d(i, j))= d (i-1)+ <[ 1

      ' [L[q1](dk(i, j))]]

      e

      (15)

      b=(2g/2) ~d. (9)

      For ILCHTC decoding, a priori values of LLR of received data bits of a codeword IL are arranged in a J

      × K array.

      ILCHTC decoding algorithm is as follows:

      1. Decode each of L rows of the array using a priori LLRs as input to SISO convolutional decoder (Log-MAP algorithm). Output produced is a posteriori LLR of that row.

      2. Taking the result of step (1) as a priori, LLRs decode each row of the array using zigzag decoder [9].

         1. Max-log approximation

            j=1

            W(Z1, Z2, …, Zn) = [ n sign(Zj)]* min1jn|Zj |.

            For all other constituent ILCHTC decoders, only Zigzag decoder decodes the information bits. For overall ILCHTC decoders, SISO turbotype decoder structure is implemented. Iterative decoder for ILCHTC is illustrated in Fig. 3.

            An iterative decoding strategy for the multidimensional concatenated ZigZag code is illustrated in Fig.4. Fig.4 (a) represents The global decoder, Fig.4

            (b) consists of N decoding blocks, The block labeled by Fn consists of the interleaver n, the MAP or Max-Log- MAP decoder and the de-interleaver (n) a Its input vector of a priori probability ratios in the mth iteration can be decomposed into two parts, denoted by Pn and

            (m)Dn respectively. Pn is for the parity check bits in the nth dimension and it remains unchanged throughout the

            decoding process. (m)Dn is for the data bits which are

         2. Forward recursion

            (10)

            updated for each iteration. The aposteriori ratio vector

            (m)Dn is generated by Fn, for the information bits and is delivered to the next decoding module as its input. Following the turbo decoding technique [12], the

            F[q](pk(i)) = p k(i) +W(F[q](pk(i 1)),[] (dk(i, 1)), …, []

            extrinsic information vector is defined by

            (dk(i, J))). (11)

            where i = 1, 2, . . . , I and F[q]( pk(0))= +

         3. Backward recursion:

            B[q](pk(i-1))=p k(i-1) +W(B[q](pk(i)),[] (dk(i, 1)), …, []

            W(m)Dn= L(m)Dn ( (m)Dn (16)

            As suggested in [l2], the extrinsic information should be prevented from circulating back to its generator. In the decoder in Fig.4(b), this is realized by subtracting the delayed values of W(m)Dn front of the MAP decoding

            (dk(i, J))). (12)

            where i = I1, …, 2, 1 and B[q] p k(I) = p (i)

         4. Extrinsic Information

   L[q](dk(i, j))=w(F[q](pk(i 1)),[] (dk(i, 1)), …, [] (dk(i,

   block Fn, as,

   ( (m)Dn=L(m)Dn-1 -W(m-1)Dn (17)

   Fig.4 represents a serial updating process, i.e., the N decoding modules {Fn| n=1, 2 … N} are activated in a

   e

   J-1).. …, [] (dk(i, J)), B[q](pk(i)) (13)

   serial manner. The multi-dimensional decoder in [12], whose characteristic function can be described by,

   L(m)Dn = D+nn W(m-1)Dn (18)

   Eqn. (18) can be regarded as a parallel process in which all N decoding modules can be activated concurrently during the m-th iteration, since the left hand side of (11) depends only on the results of the (m-1)th iteration.

   Fig 4. An N-dimensional decoder. (a) The global decoder.

   (b) The detailed structure of DEC-n. (c) The block labeled by Fn in (b) consists of a MAP decoder and an interleavedde- interleaver pair.

4. COMPARSION OF DIFFERENT DECODER COMPLEXITY

   Decoding complexity of a decoder depends upon the number of computation required to decode information bit, generally it depends on number of multiplications and additions required to decode. However Trellis length plays an important role in determine the complexity of decoders [1]. Irrespective of the code rate, the total trellis length of TCC is 2N and convolutional codes present in

   the ILCHTC as a Trellis length T,it is given by T = L ×

   Thus, trellis length increases with the increase in L.Moreover, it is maximum when L =J. ILCHTC and maximum trellis length is N. Let Cm be the number of multiplications/information bit/ iteration (M/IB/I) and Ca be the number of additions/ information bit/iteration (A/IB/I) required by a decoder. Let St be the number of states used in convolutional encoder. If Log-MAP algorithm is used to decode information bits then Cm and Ca for various codes can be found as follows:

   For TCC decoder

   Cm = 8 × St × M (19)

   Ca = (M (16St + 2)) 2 (20)

   For ILCHTC decoder

   Cm = (L(8St 4)/J ) (21)

   Ca = ((16St 1)L/J ) + M(5 + 4/J ) 1 (22)

   For zigzag decoder

   Cm = 0 (23)

   Ca = M(5 + (4/J )) 1 (24)

   The number of computations for each decoder is found using (1924). Comparison of the number of computations per IB per I for each type of decoder with the number of states, St= 8 is shown in Table 1. It can be seen from Table 1 that ILCHTC and LCHTC decoders require about 50% fewer computations than that of TCC

   at the code rate of 1/3. Zigzag decoder requires minimum number of computations [6].

   Table 1 Multiplication and Addition Complexity Of Decoders

   Decoder	R	Parameters	Cm	Ca
   TCC	1/2	M = 2 (punctured)	120	256
   	1/3	M =2	120	256
   ILCHTC	1/2	M =3, J =6, L =3	30	79
   	1/3	M = 4, J =4, L =4	60	150
   Zigzag	1/2	M =4, J =4	00	23
   	1/3	M= 8, J =4	00	47

   1. SIMULATION RESULTS

      The Low Complexity Modified Turbo Decoder was simulated for a length of N=64 at Eb/no =2dB on MATLAB platform. The obtained result is shown below.

      Fig 5 performance of Low Complexity Modified Turbo Decoder for N=64 at Eb/no =2dB

      Fig 6 shows the MATLAB results for BER performance of TCC and ILCHTC for generator polynomial (23, 33)8 with Random interleaving for length N=1024. The comparsion between the TCC and ILCHTC show that at BER of 10-5 is observed at 2.1dB and 2.6dB for TCC and ILCHTC respectively, where ILCHTC 0.5dB more than that of TCC.

      Fig 6 BER performance of Low Complexity Modified Turbo Decoder in AWGN channel

   2. CONCLUSION

In this paper a new class of modified turbo codes termed as ILCHTC and low complexity modified turbo decoders is reviewed. The ILCHTC use multiple concatenations of ZigZag codes and a convolutional code. In low complexity modified turbo decoders information bits are decoded using iterative decoding technique consisting of logmap and zigzagdecoder for better performance. The no. of computations required by ILCHTC decoder is almost 50% of the computations required by TCC decoder therefore the overall decoding complexity of low complexity modified turbo decoders is less than that of TCC.

REFERENCES

1. M. C. Valenti and J. Sun, The UMTS turbo code and an efficient decoder implementation suitable for software-defined radios," International J.Wireless Inf. Netw., vol. 8, no. 4, pp. 203-214, Oct. 201.

2. Li Ping, Xiaoling Huang, and Nam Phamdo, Zigzag Codes and Concatenated Zigzag Codes, IEEE Trans.on Information Theory, Vol. 47, No. 2, Feb. 2001, pp. 800- 807.

3. Li Ping, Turbo-SPC Codes, IEEE Trans. On Communications, Vol. 49, No. 5, May 2001, pp. 754- 759.

4. Al-Mohandes and M. I. Elmasry, \Design of an energy-effcient turbo decoder for 3rd generation wireless applications," in Proc. ICM 2003, Dec. 2003, Cairo, Egypt, pp. 127

5. A. Bhise and P. D. Vyavahare, Low complexity hybrid turbo codes," in Proc. IEEE Wireless Commun. Netw. Conf., Las Vegas, pp. 1525- 1535,Mar. 2008.

6. Archana Bhise and Prakash D. Vyavahare,Improved Low Complexity Hybrid Turbo Codes and their Performance Analysis, IEEE Transaction on Communications, Vol. 58, No. 6, June, 2010, pp.1620-1622.

7. Wade, G.: Coding techniques (Palgrave Publication, India, 2004)

8. Papaharalabos, S., Sweeney, P., Evans, B.G.: SISO algorithms based on Max-Log-MAP and log-MAP turbo decoding, IET Commun., 2007, 1, (1), pp. 49 54

9. Robertson, P., Villebrun, E., Hoeher, P.: A comparison of optimal and sub-optimal MAP decoding algorithms operating in the log domain.Proc. IEEE ICC95, 1995, pp. 10091013

10. J.G.: Digital communications (McGraw-Hill International Edition, 2001, India, 4th edn.

11. Bhatt, Tejas; Stolpman, Victor. Structured Interleavers and Decoder Architectures for Zigzag Codes, IEEE Conference Proceedings on Signals, Systems and Computers, Oct.-Nov. 2006, pp.99-104.

12. Ping, L., Chan, S., Yeung, K.L.: Iterative decoding of multidimensional

13. Concatenated single parity check codes. Proc. IEEE ICC,1998, pp. 131135