HSC welcomes all external visitors to this site, especially students and members of the academic community. Please use the comments box at the bottom of each page to record any comments or suggestions for improvement.

Introduction

Concatenated codes are based on the premise that a large coding gain? can be achieved by combination of relatively simpler code structure. The resulting code has the error correction capability of much longer codes and the decoding is much simpler as compared to decoding of a longer code. A serial concatenated code is most often used for power limited systems (like satellite system). Most widely used structure is the one with Reed-Solomon? as outer code and convolutional-code? as inner code. A turbo code can be thought of as an enhancement to the concatenated encoding with iterative algorithm for decoding. {1,2,3}

History

In 1948, Professor Claude Shannon proved the existence of techniques that could provide a coding gain of 11-12 dB. Forty years later, the error-correction coding schemes were able to achieve coding gain of upto 6 dB. In 1993, a remarkable discovery gave rise to turbo codes that can provide about 10 dB of coding gain (most of what Shannon had predicted). Since then, turbo coding represents the key research topic among all error-correcting research.

Convolutional Vs Turbo code

Convolutional Code

Convolutional Code transforms an m-bit information symbol to be an n-bit symbol , where m/n is the code rate (n >= m) and the transformation is a function of the last k information symbols, where k is the constraint length of the code.

To convolutionally encode data, start with k memory registers, each holding one input bit. All memory registers are reset to zero unless specified otherwise. The encoder has n generator polynomials. At every processing cycle, all the register contents are shifted left and an input bit is fed into the leftmost register. Using the generator polynomial, contents of the registers and the current input, n bits are produced by the encoder. Once the input bits are exhausted, the encoder uses zero as input untill all the registers are reset back to inital state.

The encoder can be systematic (data being encoded is part of the output) or non-systematic(data being encoded is not the part of output). Systematic codes are almost always recursive (output is fed back) while non-systematic codes are non-recursive.

The performance of convolutional code can be increased by increasing the constraint length. However, this results in exponential increase in the decoder complexity.

Turbo Codes

Turbo code caters to the need of achieving higher error correction capability without adding to decoding complexity needed for long codes. Turbo code encodes the same information more then once. The information bits are fed to the encoders in different order. The decoder in the turbo codes are soft input soft decoder output. Soft output decision algorithm provide as an output a real number which is the measure of probability of error in decoding bits. The decoding is based on principle of iterative decoding.

turbo codes achieve near Shannon limit error correction performance with relatively simple component code and large interleavers

Summary

Criteria		Turbo code		Convolution code
Constraint Length		Improves with constraint length		No effect
Coding Rate		Performance improves significantly		Not significant
Recursive encoders and soft output decoders		Must		Not must except in a concatenated configuration
Large Free Distance		Indifferent		Improves performance

How Turbo Code works

Theory used

• Codes perform well at large block size.
• Maximizing the weight of the output codeword gives the best BER performance for a moderate bit SNR as the random interleaver size N gets larger.
• By increasing the memory codeword length in an encoder memory, greater protection or coding gain can be achieved, the trade off being the complexity of the decoding algorithm.
• Simpler decoding strategies which combines simpler codes in such a way that each code can be decoded separately with less complex decoders.

Few key points about Turbo Code

• Turbo codes achieve near Shannon limit error correction performance with relatively simple component codes and large interleavers.
• Turbo code encodes the same information twice but in different order. The more scrambled is the information sequence for the second order the more uncorrelated the information exchange is between decoders. This is one key idea that allows continuous improvement in correction capability when the decoding process is iterated.
• Soft output decoders : This can be interpreted as a measure of reliability of decoders hard decision. This extrinsic information is used for the next stage in iterative decoding process.
• Iterative decoding relies on a link between soft soft output decision algorithm, special encoding and information exchange techniques

Encoder

Figure below shows a generic PCCC turbo encoder. The input sequence to be encoded is organized in block of length N. The first block of data id encoded by ENC1. The same block of information bits is interleaved by the interleaver? INT and is encoded by ENC2. The coded bit produced by the encoder is the output of each encoder block.

The Interleaver block, INT, rearranges the order of information bit for input to second encoder. The main purpose of the interleaver is to increase the minimum distance of turbo code such that after correction in one dimension the remaining errors should be correctable in second dimension. The outcome of the turbo encoders are Xk ,Yk1 ,Yk2 for systematic code Dk = Xkis the input data at time k. Yk1 ,Yk2 are two parity bits at time k. The parity bits can be punctured where puncturing? can be implementers by the switch as shown in the figure above. Puncturing helps in achieving higher coding rate . For instance a rate code can be achieved by alternatively selecting the outputs of the two encoders in order to produce the following output sequence (X1,Y11,X2,Y22,X3,Y13,X4..)

One of the popular variant of the turbo encoder is the SCCC. This encoder has two constituent convolution encoder separated by a random interleaver. This structure is called parallel concatenated convolution encoder(SCCC). This is called so because same information stream is encoded twice, in parallel using the straight and interleaved sequence of the information bits. An alternative is to interleave the output of one encoder and re-encode its again. This is called as serial concatenated convolution encoder(SCCC).

PCCC Vs SCCC

• At low SNR PCCC performs better. At high SNR SCCC performs better. The crossover point depends on interleaver size and interleaver design
• Interleaver gain for SCCC is given by N-1 Interleaver gain for PCCC is given by N-(d+1)/2
• SCCC is preferred over PCCC for a very low BER

Decoder

The optimal turbo decoder is the Maximum Likelihood? decoder. The limitation with the approach is the complexity associated with the turbo decoder due to the interleaver used in the encoder. The complexity arises due to large number of states in trellis of the turbo decoder for a large interleaver size. Iterative decoding with ML decoding applied to elementary convolution/block codes of the turbo code is a more practical solution considering the trade off between performance and complexity of decoding procedure. Experiments have shown that with iterative decoding Turbo decoder achieves near Shannon limit error correction performance with relatively simple component codes and large interleavers. Simpler(then Maximum Likelihood Decoding Algorithm) decoding strategies which combines simpler codes in such a way that each code can be decoded separately with less complex decoders.

In Iterative process information needs to be passed from one component decoder to another component decoder. A soft output decoder is used for this.

In the traditional approach the demodulator block makes a hard decision(0 or 1) of the received symbols and passes it to the error control decoder block . No information about the reliability of the hard decision is passed. Better results are obtained when quantized received signal is passed directly to the decoder. A soft decision decoder outputs a real number which is a measure of the probability of a correct decision. This real number is called as a posteriori probability(APP). Widely used Soft decision decoding algorithm SOVA : Less complex less accurate{4} MAP :More Complex more accurate{5,6}(at low SNR) SISO : Similar to MAP but easier to use in the case where there are two parallel path in Trellis diagram{7} LOVA:To Reduce the error floor of turbo codes. Combines conventional turbo decoder with a list decoder. After each iteration the the turbo decoder output is checked for errors using CRC. If the test is passed in less then a pre-defined number of itrations, the block is accepted else list decoder is invoked and list of L probable path is invoked{8}(similar to SLVA in {9}). The performance of turbo coding scheme improves as the number of decoder iteration is increased. But, the coding gain from one iteration to another decreases with the number of iterations.

Figure aove depicts the structure of a Turbo decoder. In the figure two soft decision decoders are employed. Decoders DEC1 provides soft output which is a measure of the reliability of each decoded bit from the reliability. From the reliability information the extrinsic information is extracted. The extrinsic information is independent of the current decoder input. The extrinsic information after interleaving is passed to the DEC2 which uses this information to decode te interleaved bit sequences. From the soft outputs of DEC2 the new extrinsic information is fed back to the input of DEC1 and so on. If the error occurs due to noisy input of the first decoder, it may be corrected by the second decoder.

Glossary

BTC		Block Turbo Coding
CTC		Convolutional Turbo Code
ML		Maximum Likelihood
PCCC		Parallel Concatenated Convolutional Code
SCCC		Serial Concatenated Convolutional Code
SOVA		Soft Output Viterbi Algorithm
MAP		Maximum A Posteriori
SISO		Soft Input Soft Output
LOVA		List Output Viterbi Algorithm
SLVA		Soft List Viterbi Algorithm

See Also

Convolutional Code? FEC? Reed-Solomon Code?

References

{1}Near Optimum. Error. Correcting. Coding And Decoding: Turbo-Codes. Claude. Berrou,. Member, IEEE,. and Alain Glavieux {2}Concatenated codes by G. D. Forney Jr {3}C. Berroux and A. Glavieux, "Near optimum error correction coding and decoding: Turbo codes," IEEE Transactions on Communications {4}J. Hagenauer and P. Hoeher,A Viterbi Algorithm with SoftDecision Outputs and its Applications {5}L. Bahl, J. Jelinek, J. Raviv, and F. Raviv, Optimal Decoding of Linear Codes for minimising symbol error rate, {6}S. Pietrobon and S. A. Barbulescu, A simplification of the modified Bahl decoding Algorithm for systematic convolutional codes, {7}S. Benedetto, G. Montorsi, D. Divsalar and F. Pollara, Serial Concatenation of Interleaved Codes: Performance Analysis, Design, and Iterative Decoding, {8}N. Seshadri and CE. W. Sundberg, List Viterbi Decoding Algorithms with Applications, {9}K. R. Narayanan and G. L. Stueber, List decoding of Turbo codes

page views:### Maintained by: rajenish.jain@hsc.com

Categories: Wireless

Comments