 Open Access
 Total Downloads : 18
 Authors : A.Sagar, A.Rajagopal, K.Karibasappa
 Paper ID : IJERTCONV2IS14012
 Volume & Issue : CSECONF – 2014 (Volume 2 – Issue 14)
 Published (First Online): 30072018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Low Complexity Modified Turbo Decoders
A.Sagar, A.Rajagopal, K.Karibasappa
Dept of ECE, Dayananda Sagar College of Engineering, Bangalore, Karnataka560078, 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, ZigZag codes.

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 errorcorrection 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 ThirdGeneration (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 rate1/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 rate1/3 ILCHTC achieve Bit Error Rate.(BER) of 105 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

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.

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)

ILCHTC Encoder
Since RSC codes have better errorcorrecting 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, rate1/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)


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 (i1)+ /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.

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 (i1)+ <[ 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:

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

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

Maxlog approximation
j=1
W(Z1, Z2, …, Zn) = [ n sign(Zj)]* min1jnZj .
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 MaxLog MAP decoder and the deinterleaver (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

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))= +

Backward recursion:
B[q](pk(i1))=p k(i1) +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)

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)Dn1 W(m1)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
J1).. …, [] (dk(i, J)), B[q](pk(i)) (13)
serial manner. The multidimensional decoder in [12], whose characteristic function can be described by,
L(m)Dn = D+nn W(m1)Dn (18)
Eqn. (18) can be regarded as a parallel process in which all N decoding modules can be activated concurrently during the mth iteration, since the left hand side of (11) depends only on the results of the (m1)th iteration.
Fig 4. An Ndimensional decoder. (a) The global decoder.
(b) The detailed structure of DECn. (c) The block labeled by Fn in (b) consists of a MAP decoder and an interleavedde interleaver pair.


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 LogMAP 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

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 105 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

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

M. C. Valenti and J. Sun, The UMTS turbo code and an efficient decoder implementation suitable for softwaredefined radios," International J.Wireless Inf. Netw., vol. 8, no. 4, pp. 203214, Oct. 201.

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.

Li Ping, TurboSPC Codes, IEEE Trans. On Communications, Vol. 49, No. 5, May 2001, pp. 754 759.

AlMohandes and M. I. Elmasry, \Design of an energyeffcient turbo decoder for 3rd generation wireless applications," in Proc. ICM 2003, Dec. 2003, Cairo, Egypt, pp. 127

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.

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.16201622.

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

Papaharalabos, S., Sweeney, P., Evans, B.G.: SISO algorithms based on MaxLogMAP and logMAP turbo decoding, IET Commun., 2007, 1, (1), pp. 49 54

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

J.G.: Digital communications (McGrawHill International Edition, 2001, India, 4th edn.

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

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

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