|
Academic Open Internet Journal |
Volume 14, 2005 |
Optimal Design of Forward Error Correcting Codes for Wireless Communication
1Dr. A.Shanmugam, 2A.R.Abdul Rajak
1Professor and HoD, 2Research Scholar
Dept of ECE, PSG College of Technology
Coimbatore, Tamil Nadu -641 004
India
Abstract
Wireless mobile communication systems present several design challenges resulting from the mobility of users throughout the system and the time-varying channel (Multi-path fading). There has been an increasing demand for efficient and reliable digital communication systems. To tackle these problems effectively, an efficient design of forward error coding (FEC) scheme is required for providing high coding gain. The extra coding gain offered by FEC can be used either to save bandwidth or reduce power requirements in the link budget. So the design trade-offs of design engineers is to minimize the received error probability by making efficient use of power and bandwidth resources, while keeping system complexity reasonable in order to reduce cost and processing time. This paper provides solution to the problem by using concatenated coding schemes. To obtain high coding gains with moderate decoding complexity, concatenation of codes has proved to be an attractive scheme. In this paper, a comparison among various concatenated codes is made to select the best code for mobile communication. Results that concatenated irregular turbo code with Reed-Solomon code has better performance among all codes and thus can be suggested for mobile communication.
1. Introduction
The traditional codes cannot be used for mobile communication. The major difficulty of traditional codes is that, in an effort to approach the theoretical limit for Shannon’s channel capacity, there is need to increase the code-word length of a linear block code or a constraint length of a convolutional code, which, in turn, causes the computational complexity of a decoder to increase exponentially. Random codes are known to achieve Shannon limit performance as k gets large, but at the price of a prohibitively complex decoding algorithm. Ultimately, a point is reached where complexity of decoder is so high that it becomes physically unrealizable. Also wireless channels are mostly affected by burst errors. But the existing codes are effectively suited for correcting random errors, but not burst errors. So the goal is to design a channel coding scheme for wireless communication that can operate at low signal to noise ratios and perform reliably. The way to combat the problem is to use concatenated coding, where two (or more) constituent codes are used in serial or in parallel. Concatenated coding schemes are proposed by Forney [1] as a method for achieving large coding gains by combining two or more relatively simple building block or component codes. The optimal FEC scheme for mobile communication is as shown in fig 1.
Turbo codes are selected because they are proved to have performance close to Shannon theoretical limit. Reed-Solomon codes are selected as outer codes as they are one of the best burst error correcting code.
2. Turbo code
A turbo code (TC) is a parallel concatenation of two or more recursive systematic convolutional codes (RSC). The two component encoders are separated by an interleaver. Typically, but not necessarily, the same code is used for both constituent coders (RSC). The interleaver is a device that permutes the ordering of a sequence of bits from a fixed alphabet in a completely deterministic manner. That is it takes the symbols at the input and produces identical symbols at the output but in a temporal order. A generalized turbo encoder is shown in fig 2[2,3].
 |
From fig 2, the input data stream is applied directly to the encoder 1 and reordered version of same data stream is applied to the encoder 2. The systematic bits (original message bits) and two sets of parity-check bits generated by two encoders constitute the output of turbo encoder. In fig 2, the encoder is recursive systematic (RSC) type means that present output is feed back along with next input to the next state. The main aim of RSC is to produce more high weight codes even though input contains more number of zeros.
An iterative scheme is used for decoding the turbo codes as given by [2, 3, 4]. The decoding algorithm used is Log-Map. The decoding structure is shown in fig 3.
The interleaver used in both transmitter and receiver is same. The advantage of turbo decoding is that even though the encoding is parallel, decoding is done by two small decoders. The two decoders are serial and share the information between them. This sharing of information is responsible for performance of turbo code.
3. Reed-Solomon code
RS codes are subset of BCH codes and are systematic linear block codes [5]. An RS code is specified as an RS (n, k) with m-bit symbols. Here n refers to the number of encoded symbols in a block, while k refers to the number of original message symbols. The difference n-k (called 2t) is the number of parity bits that have been appended to make encoded block and t indicates the error correcting capability in symbols.
The block diagram for RS coder is as shown in fig 4 [5,17,18].
After entire block of input is given
to the above circuit, the shift registers contain the parity symbols. These
are multiplexed to the input data to form the coded sequence. RS codes are based on finite fields often called Galois fields
(GF).There are many GF fields GF (p) (called as prime Galois field), GF (pm)
(called as extended prime Galois field), GF (2m). Symbols from
extension field of GF (2m) are used in construction of RS codes.
Some fields like set of integers are infinite. This can cause problems when
they are implemented on a computer with fixed word length. This can be avoided
by GF. GF have useful property that operation on an element of the field will
result in another element of the field. GF arithmetic is ideally suited for
hardware implementation. Addition and subtraction are same in GF. Addition
consists of simply XOR’ing two symbols together. Multiplication is slightly
complex, but can be performed by combinational logic. All the elements in GF (2m)
are formed by the elements
, where 
is the primitive element. The generator
polynomial is as in equ(1)
The decoding of RS codes involves three steps. They are syndrome computation, calculation of error locator polynomial and error values. The algorithms used for error locator polynomial are Berlekemp’s iterative algorithm and Forney algorithm as described by [5,6,7,8].
4. Irregular turbo code
Normally in any encoding operation, the input bits are directly fed to the encoder. These are called as regular codes, since each input bit is mapped as a unique input bit of encoder. Block codes, cyclic codes, RS codes, Turbo codes are examples of regular codes. The process of repeating some of systematic bits before encoding is called as called as irregularity. If the irregularity can be introduced in the turbo code, it is called as irregular turbo code. In classical turbo the degree of all information bits is 2. So in regular turbo codes each systematic bit participates exactly in 2 trellis sections.
A more general form of irregular turbo code can be obtained by cascade of array of repetition codes, an interleaver and a turbo code. This is illustrated as[18,19,20] in fig 5
The decoding algorithm for irregular turbo codes is slightly different from original turbo code. The decoding algorithm is implemented as in [20].
5. Simulation Results
The performance turbo codes are analyzed using data frame sizes of 460 which is close to the GSM standard (456 bits) for both AWGN and RAYLEIGH channels. All the simulations are performed in MATLAB 6.1.
5.1 Comparison of turbo code with concatenated turbo-RS code
In first case, original data is given to turbo code and concatenated turbo-RS code in AWGN and Rayleigh channel.
Input parameters
Frame size 460 bits
Number of frame repetitions 100
Generator polynomial [1 1 1; 1 0 1]
Puncturing unpunctured
Interleaver size Golden(size 460 bits)
Decoding algorithm Log MAP
Decoding iterations 3
Field used GF (25)
Message length (k) 23
Encoded length (n) 31
Error correcting capability (t) 4 symbols
Channels AWGN and Rayleigh
Concatenating turbo with RS attains improvements of 0.75 dB at BER of 10-4(fig 6). This concatenation gives improvements of approximately 1.2 dB at BER close to 10-4, 10-2 in Rayleigh channel (fig 6).
5.2 Comparison of turbo code and irregular turbo code
Input parameters
Frame size 460 bits
Number of frame repetitions 100
Generator polynomial [1 1 1; 1 0 1]
Puncturing unpunctured
Interleaver size Golden(size 460 bits)
Decoding algorithm Log MAP
Decoding iterations 3
Irregularity type pseudo-random
Irregularity percentage 5%, 10% and 15 %
The comparison of turbo and irregular turbo code is shown in Fig 7. Comparison is made between turbo code and 5 %, 10%, and 15% irregular turbo code. Plots clearly show that irregularity (5 %, 10%, and 15%) gives improvements of approximately 0.8 dB at BER of 10-4 in AWGN channel. Irregularity also gives better performance in Rayleigh channel. Irregularity achieves gain of approximately 0.8 dB at BER of 10-4 in Rayleigh channel (fig 7). There is very slight improvement in performance from 5 % irregularity to 10 % irregularity and from 10 % irregularity to 15 % irregularity.
5.3 Comparison of turbo code, turbo-RS, irregular turbo, irregular turbo-RS
In this case all 4 possible concatenated codes like turbo code, concatenated turbo-RS code, irregular turbo code, Concatenated irregular-RS code are compared to select the best code.
Input parameters
Frame size 460 bits
Number of frame repetitions 100
Generator polynomial [1 1 1; 1 0 1]
Puncturing unpunctured
Interleaver size Golden(size 460 bits)
Decoding algorithm Log MAP
Decoding iterations 3
Field used GF (25)
Message length (k) 23
Encoded length (n) 31
Error correcting capability (t) 4 symbols
Channels AWGN and Rayleigh
Irregularity type pseudo-random
Irregularity percentage 5%, 10% and 15 %
Interleaver in Irregular turbo code Golden
Decoding algorithm in Irregular turbo code Log-Map.
The comparison of turbo code, concatenated turbo with RS code, irregular turbo code, and concatenated irregular turbo code with RS code is shown in Fig 8. Plots show that concatenated irregular turbo code gives approximately 0.7 dB improvements over turbo code and 0.2 dB improvements over irregular turbo code and concatenated turbo with RS code in AWGN. The BER of irregular –RS code over turbo code is approximately 0.9 dB and 0.2 dB better than turbo, irregular turbo code respectively (fig 8) in Rayleigh channel.
6. Conclusions
From above plots it is clear that concatenated turbo-RS code has performance better than that of original turbo code. Irregular turbo code is better than turbo code. Finally concatenated irregular turbo and RS code has better performance of all codes and thus it can be suggested for wireless communication.
7. References
[1] T. S. Rappaport “ Wireless Communications Principles & Practice”, Prentice Hall, 1996.
[2] C. Berrou, and A. Glavieux “Near Optimum Error Correcting Coding and Decoding: Turbo-Codes”, IEEE Transactions on Communications, Vol. 44, No.10, pp. 1261- 1271, October 1996
[3] C. Berrou, R. Glavieux, and P. Thitimajshima, “Near Shannon limit error- correcting coding and decoding”, in Proc. ICC 1993, pp. 1064-1070.
[4] “Iterative decoding of binary block and convolutional codes”, IEEE transactions on information theory, vol.42, March 1996
[5] Bernard Sklar “ Digital communication-Fundamentals and Applications”, Pearson Education Asia , 2001
[6] S. Crozier, J. Lodge, P.Gunand and A. Hunt “Performance of Turbo-Codes with Relative Prime and Golden Interleaving Strategies”, Sixth International Mobile Satellite Conference (IMSC’99), Ottawa, Canada, pp. 268-275, June, 1999.
[7] J. Hagenauer and P. Robertson “Iterative Turbo Decoding of Systematic convolutional Codes with MAP and SOVA algorithms” in Proc. ITG Conference on Source and Channel Coding, Munich, October 1994.
[8] Lance C.Perez “ A distance spectrum interpretation of turbo code”, IEEE transactions on information theory, Vol.42, No.6, November 1996
[9] Sergio Benedetto “ unveiling turbo codes :some results on parallel concatenated code” IEEE transactions on information theory, Vol.42, No.2, March 1996
[10] Joachim Hagenauer “The turbo code principle: Tutorial introduction and state of Art”, International symposium on turbo codes, France 1997.
[11] “The performance of parallel concatenated code convolutional codes and serial concatenated codes in AWGN channel” by Le Nhat, R.M.A.P Rajatheva, Institute of technology, Bangkok.
[12] “A low complex parallel decoding scheme for turbo codes” by Zhang Zhongpei and Zhou Liang Dept of UESTC, Chedgdu ,China
[13] “Performance of low complexity turbo decoder and its implementation on a low-cost, 16-bit fixed point DSP” by Ken Gracie, Stewart Crozier, Andrew Hunt and John Lodge , at Communication research centre, Ottawa.
[14] “Efficient software implementation of Max-Log-Map turbo decoder on Star
core SC140 DSP” by Amir Chass, Arik GUbeskys and Gideon Kutz C.Meth,
[15] “Reed-Solomon cells now Licensable” , Elctronic design p. 171 , Sept. 5,1995
[16] “Self correcting codes conquer noise part2: Reed-Solomon codecs” by Syed
Shahzad, Saqib yaqub, and Faisal Suleman
[17] “Reed Solomon codes” by Joel Sylvester ,Jan 2001
[18] “Irregulr turbo codes”, by B.J Frey and D.J.C Mackay in Proceedings of the 37th Allerton conference on Communication , Control and computing 1999, Allerton House ,ILLinois
[19] “Asymptotic behavior study of irregular turbo codes” by Joseph J. Bosutrous , Aug 2001, China
[20] “Irregular turbo codes and unequal error protection” by Alex Hubner, Dept. of telecommunications, University of Ulm, Washington, June 2001
[21] J. Hagenauer, E. Offer and L. Papke “Iterative Decoding of Binary Block and
Convolutional Codes”, IEEE Transactions on Information Theory, Vol. 42, No.2,
March 1996.
[22] Simon Haykin “Communication Systems”, John Willey & sons, 4th edition
Technical College - Bourgas,
All rights reserved,
© March, 2000