🔢Coding Theory Unit 11 – Turbo Codes and Iterative Decoding

Key Concepts and Principles

• Turbo codes are a class of high-performance forward error correction codes that approach the Shannon limit for reliable communication over noisy channels
• Consist of two or more constituent convolutional codes concatenated in parallel, separated by interleavers that randomize the input data
• Employ iterative decoding algorithms, such as the BCJR algorithm or the MAP (Maximum A Posteriori) algorithm, to achieve near-optimal decoding performance
• Utilize soft-input, soft-output (SISO) decoders that exchange extrinsic information between the constituent decoders to improve decoding accuracy
  • Extrinsic information represents the additional knowledge gained by each decoder about the transmitted bits during the decoding process
• Achieve excellent error correction capabilities at low signal-to-noise ratios (SNRs) and high code rates
• Exhibit an error floor phenomenon at high SNRs due to the presence of low-weight codewords in the code structure
• Offer a trade-off between decoding complexity and performance, with more iterations generally leading to better error correction

Historical Context and Development

• Turbo codes were introduced by Claude Berrou, Alain Glavieux, and Punya Thitimajshima in 1993, representing a significant breakthrough in coding theory
• Developed as a practical coding scheme that could approach the theoretical limits of channel capacity, as defined by Claude Shannon in 1948
• Inspired by the concept of iterative decoding, which was previously explored in the context of low-density parity-check (LDPC) codes by Robert Gallager in the 1960s
• Gained widespread attention due to their exceptional performance, outperforming existing coding schemes at the time
• Underwent rapid development and refinement in the years following their introduction, with various improvements and variations proposed by researchers
  • These include multiple turbo codes, non-binary turbo codes, and turbo codes with different constituent encoders and interleaver designs
• Adopted in several communication standards, such as 3G and 4G mobile networks (CDMA2000, UMTS, LTE), satellite communications (DVB-RCS), and deep space communications (CCSDS)

Turbo Code Structure

• Turbo codes are composed of two or more recursive systematic convolutional (RSC) encoders connected in parallel
• The input data sequence is encoded by the first RSC encoder, while an interleaved version of the input data is encoded by the second RSC encoder
• The interleaver permutes the order of the input bits, decorrelating the inputs to the two encoders and improving the code's distance properties
  • Common interleaver designs include block interleavers, random interleavers, and S-random interleavers
• The outputs of the RSC encoders, along with the original input data (systematic bits), form the codeword of the turbo code
• Puncturing can be applied to the parity bits generated by the RSC encoders to achieve higher code rates and reduce the transmission overhead
• The choice of the constituent RSC encoders (generator polynomials, constraint lengths) and the interleaver design significantly impact the performance of the turbo code

Encoding Process

• The encoding process of a turbo code involves the following steps:
  1. The input data sequence is fed into the first RSC encoder, which generates a set of parity bits based on the input bits and its internal state
  2. The input data sequence is interleaved using a predefined interleaver pattern, reordering the bits in a pseudo-random manner
  3. The interleaved data sequence is fed into the second RSC encoder, which generates another set of parity bits
  4. The systematic bits (original input data) and the parity bits from both RSC encoders are multiplexed to form the output codeword
• The systematic bits are typically transmitted along with the parity bits to facilitate the decoding process and improve the code's overall performance
• Puncturing can be applied to the parity bits to achieve higher code rates, selectively removing some of the parity bits according to a predefined puncturing pattern
• The resulting codeword has a length that depends on the input data length, the code rate, and the puncturing scheme used

Iterative Decoding Algorithm

• Turbo codes are decoded using an iterative decoding algorithm that exchanges soft information between the constituent decoders to progressively refine the decoding decisions
• The iterative decoding process typically involves the following steps:
  1. The received codeword is demultiplexed into the systematic bits and the parity bits corresponding to each RSC encoder
  2. The systematic bits and the parity bits of the first RSC encoder are fed into the first SISO decoder, which computes the extrinsic information for each bit based on the received values and the a priori information from the previous iteration
  3. The extrinsic information from the first decoder is interleaved and used as the a priori information for the second SISO decoder
  4. The systematic bits (after interleaving) and the parity bits of the second RSC encoder are fed into the second SISO decoder, which computes its own extrinsic information
  5. The extrinsic information from the second decoder is deinterleaved and used as the a priori information for the first decoder in the next iteration
  6. Steps 2-5 are repeated for a fixed number of iterations or until a certain stopping criterion is met (e.g., convergence of the decoded bits)
• The SISO decoders commonly employ the BCJR algorithm or the MAP algorithm to compute the extrinsic information, taking into account the trellis structure of the constituent RSC encoders
• The exchange of soft information between the decoders allows them to progressively improve their estimates of the transmitted bits, leading to better decoding performance with each iteration

Performance Analysis

• Turbo codes exhibit excellent error correction performance, particularly at low SNRs and high code rates
• The performance of turbo codes is often evaluated using bit error rate (BER) or frame error rate (FER) curves, which plot the error probability against the SNR or the $E_b/N_0$ (energy per bit to noise power spectral density ratio)
• Turbo codes can achieve BER values close to the Shannon limit for a given channel capacity, outperforming conventional coding schemes like convolutional codes and Reed-Solomon codes
• The performance of turbo codes improves with increasing interleaver sizes, as larger interleavers provide better decorrelation between the inputs to the constituent encoders
  • However, larger interleaver sizes also increase the decoding latency and memory requirements
• The number of decoding iterations also affects the performance, with more iterations generally leading to lower error rates at the cost of increased decoding complexity
• Turbo codes exhibit an error floor phenomenon at high SNRs, where the error rate decays more slowly due to the presence of low-weight codewords in the code structure
  • The error floor can be lowered by careful design of the constituent encoders and the interleaver, as well as by using techniques like doping or concatenation with outer codes
• The performance of turbo codes can be further enhanced by using advanced decoding algorithms, such as the log-MAP algorithm or the max-log-MAP algorithm, which provide a good trade-off between decoding complexity and performance

Applications and Use Cases

• Turbo codes have found widespread application in various communication systems that require reliable data transmission over noisy channels
• Mobile communication networks: Turbo codes are used in 3G and 4G standards, such as CDMA2000, UMTS, and LTE, to ensure reliable voice and data transmission in the presence of multipath fading, interference, and other channel impairments
• Satellite communications: Turbo codes are employed in satellite communication standards, such as DVB-RCS (Digital Video Broadcasting - Return Channel via Satellite), to enable efficient and reliable data transmission over satellite links
• Deep space communications: Turbo codes are used by space agencies, such as NASA and ESA, for deep space missions, where the signal-to-noise ratio is extremely low and the communication delay is significant
  • The Consultative Committee for Space Data Systems (CCSDS) has standardized turbo codes for use in deep space communications
• Wireless local area networks (WLANs): Turbo codes can be used in high-speed WLAN standards, such as IEEE 802.11n and 802.11ac, to improve the data throughput and range of the network
• Storage systems: Turbo codes can be applied to magnetic recording systems and flash memories to enhance the reliability of data storage and reduce the bit error rate

Advanced Topics and Future Directions

• Non-binary turbo codes: Turbo codes can be extended to work with non-binary alphabets, such as $GF(2^m)$, to improve the code's distance properties and reduce the error floor
• Turbo equalization: Turbo codes can be combined with equalization techniques to mitigate the effects of intersymbol interference (ISI) in frequency-selective channels
  • Turbo equalization iteratively exchanges soft information between the equalizer and the turbo decoder to jointly optimize the equalization and decoding processes
• Turbo-like codes: The principles of turbo codes can be applied to other coding schemes, such as low-density parity-check (LDPC) codes and repeat-accumulate (RA) codes, to create powerful hybrid coding schemes
• Spatially coupled turbo codes: Spatially coupled turbo codes, also known as convolutional turbo codes, introduce a spatial coupling between the constituent encoders to improve the code's distance properties and reduce the error floor
• Quantum turbo codes: Turbo codes can be adapted for use in quantum error correction schemes, where they can help protect quantum information from decoherence and other errors
• Machine learning-based decoding: Machine learning techniques, such as deep learning and reinforcement learning, can be applied to the decoding of turbo codes to improve the decoding performance and reduce the computational complexity
• Joint source-channel coding: Turbo codes can be integrated with source coding techniques, such as compression and quantization, to create joint source-channel coding schemes that optimize the end-to-end performance of the communication system