Turbo codes are the channel coding scheme used in wireless cellular networks as they are able to reach nearer to the Shannon limit. The interleaver used in Turbo codes play a major role in the performance of Turbo codes. Hence it is necessary to design Turbo codes with good interleaver structure. In this paper ,we analyse the performance of Turbo codes for varying interleaver structure and sizes in terms of the bit error rate (BER). The size and type of interleaver plays a major role in the performance of turbo codes. We discuss the various types of interleavers used in Turbo codes and find the most optimal interleaver. The turbo codec is simulated for varying interleaver structures. The channel is subjected to Additive White Gaussian Noise in terms of the Signal to noise ratio(Eb/N0) in db.. The performance graph is plotted between the number of decoding iterations and the bit error rate for various interleavers. An analysis is made for the optimal choice in the size and structure of interleaver.

Index Terms- Interleavers ,Encoder, Iterative decoding, Bit error rate

INTRODUCTION

Turbo codes play a major role in the error channel coding scheme used in wireless cellular networks. Turbo codes emerged in 1993 [1] and have since become a popular area of communications research. It is due to their exceptional performance that turbo codes are being accepted as 3GPP standard in personal communications. In next era of wireless communications, mainly the 4 G applications, there is a need to provide the best Qos (Quality of Service) provisioning. The 4G cellular systems are aimed at supporting various applications like voice, data and multimedia over packet switched networks. Different applications have varied Qos requirements in terms of the data rate , bit error rate (BER),frame size and the packet error rate . For certain type of transmission like text transmission , the packet loss is intolerable while delay is acceptable. But for real time video, there can be an acceptable degradation in the video, but delay in the system cannot be accepted.. Turbo codes is the most adaptable error coding scheme used to adapt to the varying Qos requirement .Hence there is a need to analyse the performance of Turbo codes by varying all the parameters which can be made adaptable. Based on the analysis ,the most suitable parameters are chosen . In this paper we analyse the behaviour of Turbo codes for various interleaver size and structure. The simulation is done for the various noise levels and the graph is plotted against the bit error rate and the signal to noise ratio. The paper is organised as follows, the basics of parallel concatenated coding or Turbo coding is done in I, the Iterative decoding is dealt in section II, the interleaver types and features in section III, the effect of interleaver size is given in section IV. The analysis of the results is done in V along with the conclusion.

I .TURBO CODES

The structure of Turbo encoder is shown in Figure.1.A turbo encoder is formed by parallel concatenation of two recursive systematic convolutional (RSC) encoders separated by an interleaver[2]. The encoder structure is called parallel concatenation because the two encoders operate on the same set of input bits

(1)

,rather than one encoding the output of the other. So turbo codes are also called as parallel concatenated convolutional code. The generator matrix of a rate ½ component RSC code can be represented as given in equation 1 where g0(D) and g1(D) are a feedback and feedforward polynomial with degree v ,respectively. In the encoder , the same information sequence is encoded twice but in a different order .The first encoder operates directly on the sequence, denoted by u, of length N. The second encoder operates on the same set of data interleaved in a different fashion.The information is encoded using the Turbo encoder before transmission and, after reception the data is decoded by the Turbo decoder The important characteristics of turbo codes are the small BER achieved even at low Signal to noise ratio (SNR) and the flattening of the error rate curve (i.e.)the error floor at moderate and high values of SNR. The binary input sequence u which has finite duration is fed into the first RSC encoder yielding the redundancy sequence c1 with the same finite duration as u. Sequence u1 which is an interleaved replica of u is put into RSC encoder 2. The output of RSC encoder yields redundancy sequence c2. Both the redundancy sequences c1 and c2 as well as u are punctured and multiplexed to form output sequence b.

The constraint length of the encoder is K and memory is v=K-1

The input to the encoder at time k is a bit u_kand the corresponding binary output

g_1i= 0,1 (2)

g_2i= 0,1 (3)

where g1i and g2i are the two encoder generators .

II.ITERATIVE DECODING

There are two main algorithms to decode the data. One of the algorithm is called Soft Output Viterbi Algorithm(SOVA) and the other one is Maximum A Posteriori Algorithm(MAP). The first algorithm finds the most probable output data sequence. The trellis diagram is drawn and the path with the least Hamming distance is found. The MAP algorithm finds the marginal probability that the received bit was a 1 or a 0. Since the bit could occur in many different codewords, the sum of all the probabilities are considered. The decision is made by using the likelihood ratio of the marginal distributions from 1 and 0.The calculation is structured by using the trellis diagram. The decoder examines the states and computes the a posteriori probabilities associated with the state transitions. The loglikelihood ratio of the estimated bit is the division of the probability that uk=1 to the probability that the bit was uk=0

(4)

The MAP algorithm is preferred as it minimises the bit error probability.

The iterative decoding algorithm is done with the MAP algorithm. The iterative MAP turbo decoder is shown in Figure 2.It consists of two component decoders serially concatenated via an interleaver . The first MAP decoder takes as input the received information sequence r₀ and the received parity sequence generated by the first encoder r₁. The decoder then produces a soft output, which is interleaved and used to produce an improved estimate of the a priori probabilities of the information sequence for the second decoder. The other two inputs to the second MAP decoder are the interleaved received information sequence r₃ and the received parity sequence produced by the second encoder r₂. The second MAP decoder also produces a soft output, which is used to improve the estimate of the apriori probabilities for the information sequence at the input of the first MAP decoder. The feedback loop is a distinguishing feature of this decoder. After a certain number of iterations, the soft outputs of both MAP decoders stop to produce further performance improvements. Then the last stage of decoding makes a hard decision after deinterleaving.

Figure .2.Iterative MAP decoder

III .INTERLEAVERS

Interleaving is a process of rearranging the ordering of a data sequence in a one to one deterministic format. The inverse of this process is called deinterleaving which restores the received sequence to its original order. Interleaving is a practical technique to enhance the error correcting capability of coding. In turbo coding, interleaving is used before the information data is encoded by the second component encoder. The basic role of an interleaver is to construct a long block code from small memory convolutional codes, as long codes can approach the Shannon capacity limit. Secondly, it spreads out burst errors[3],[4]. The interleaver provides scrambled information data to the second component encoder and decorrelates inputs to the two component decoders so that an iterative suboptimum-decoding algorithm based on uncorrelated information exchange between the two component decoders can be applied. The final role of the interleaver is to break low weight input sequences, and hence increase the code free Hamming distance or reduce the number of codewords with small distances in the code distance spectrum.The size and structure of interleavers play a major role in the performance of turbo codes. There are a number of interleavers, which can be implemented.

Random interleaver:

The random interleaver [5] uses a fixed random permutation and maps the input sequence according to the permutation order.

Block interleaver

The block interleaver [5] is the most commonly used interleaver in communication system. It writes in column wise from top to bottom and left to right and reads out row wise from left to right and top to bottom.

Diagonal interleaver

Diagonal interleaver writes in column wise from top to bottom and left to right and reads out diagonally from left to right and top to bottom.

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Interleaver(i)	0	6	12	1	7	13	2	8	14	3	9	10	4	5	11

Table 1. Equivalent index position for original matrix index in diagonal interleaver

Table 1. shows a 3 x 5 matrix positions after the matrix is interleaved

Circular-Shifting interleaver

The permutation P of the circular-shifting interleaver is defined by

P (i) = (ai+s) mod L (5)

satisfying a<L, a is relatively prime to L, and s<l where i is the index, a is the step size, and s is the offset. The following table shows a circular-shifting interleaver with L=8, a=3, and s=0.

Index

Circular-

shift permutation

Table 2. Equivalent index position for original matrix index in Circular-shifting interleaver

IV.EFFECT OF INTERLEAVER SIZE

The choice of interleaver size for varying SNRs also play a major role in theperformance of Turbo codes.To reduce the error floor that occurs in Turbo codes,the interleaver size is increased..The bit error probability of a Turbo code over an Additive White Gaussian Noise channel is upper bounded by equation 6 where B_dis the error coefficient, d_min is

(6)

the free distance ,R is the code rate and E_b/N₀ is the signal to noise ratio. The interleaver can reduce the error coefficients of low weight codewords through a process called Spectral Thinning[6].This distance spectrum results in a reduced bit error probability by a factor 1/N which is the interleaving gain.N is the size of interleaver . At low SNR’s , the interleaver size is the only important factor ,as the code performance is dominated by the interleaver gain.The effects induced by changing the interleaver structure at low SNR region are not significant. At high SNRs , the interleaver structure determines the code performance The interleaver structure affects the mapping of low weight input sequences to the interleaver output,and hence the first several distance spectral lines of the turbo code distance spectrum.This plays an important role in determining the code performance at high SNRs.

V.RESULT & CONCLUSION

The simulation of various interleavers for an image data is given in fig3. From the simulation we find that the random interleavers give the best performance

Figure .3

The size and the type of interleaver structure affects the code performance. In this paper,we have found the interleaver structure which gives the best performance.Random interleavers are found to be the best. The effect of the size of interleaver is analysed mathematically. We find that at low SNRs, the interleaver size can be increased to get a better performance. Depending on the Qos parameters, the interleaver size can be chosen.

In future, more efficient interleaver structures can be designed considering the code structure .We can achieve better results with a code matched interleaver.

REFERENCES:

[1] C. Berrou, A. Glavieux, and P. Thitimajshaima, “Near Shannon limit error-correcting coding and decoding: turbo-codes,” in Proc. IEEE Int. Conf. Commun., May 1993, pp. 1064–1070.

[2] C. Berrou, A. Glavieux ,”Near optimum error correcting coding and decoding: Turbo codes,” IEEE Trans. Communications, vol. 44,No 10 pp. 1261–1271,Oct. 1996.

[3] Robert Garello,Paola Pierleoni and Sergio Benedetto,” Computing the free distance of turbo codes and serially concatenated codes with interleavers : Algorithms and Applications,” IEEE Journal on selected areas in communications,Vol.19 No.5,May 2001

[4]S. Dolinar and D.Divsalar,” Weight distribution of Turbo codes using Random and Non random permutations,”JPL TDA progress report 42-122 August 1995.

[5] Branka Vucetic and Jinhong yuan, “Turbo Codes Principles and Applications,”

Buton: Kluwer Academic Publishers, 2000.

[6] Lance C. Perez, Jan Seghers and Daniel.J.Costello,” A distance spectrum interpretation of Turbo codes,” IEEE Trans. Inform. Theory, Special issue on Coding and Complexity April. 1996.

Technical College - Bourgas,

ABSTRACT

INTRODUCTION

I .TURBO CODES

V.RESULT & CONCLUSION