ℹ️Information Theory Unit 10 – Error–Correcting Codes

Fundamentals of Error-Correcting Codes

• Error-correcting codes enable reliable data transmission over noisy communication channels by detecting and correcting errors
• Redundancy is added to the original message to facilitate error detection and correction
  • Redundant bits are appended to the original message bits
  • Increases the overall message length but improves reliability
• Channel coding theorem establishes the maximum achievable rate for reliable communication over a noisy channel
• Hamming distance measures the number of positions in which two codewords differ and determines the error-correcting capability of a code
  • A code with a minimum Hamming distance of $d$ can correct up to $\lfloor\frac{d-1}{2}\rfloor$ errors
• Generator matrix $G$ is used to encode the original message into a codeword
• Parity-check matrix $H$ is used for error detection and syndrome calculation

Types of Errors in Data Transmission

• Bit errors occur when individual bits in a transmitted message are flipped due to noise or interference
  • Single bit errors affect only one bit in a codeword
  • Burst errors affect multiple consecutive bits in a codeword
• Erasure errors happen when the receiver is aware of the positions of the erroneous or missing bits
  • Easier to handle compared to bit errors since the locations are known
• Additive white Gaussian noise (AWGN) is a common noise model in communication systems
• Interference from other sources can introduce errors in the transmitted data
• Channel fading and multipath propagation can lead to errors in wireless communication systems
• Synchronization errors occur when the receiver's clock is not perfectly aligned with the transmitter's clock

Basic Principles of Error Detection

• Error detection techniques identify the presence of errors in the received data without necessarily correcting them
• Parity bits are added to the original message to detect errors
  • Even parity: The parity bit is set to make the total number of 1s in the codeword even
  • Odd parity: The parity bit is set to make the total number of 1s in the codeword odd
• Checksum is computed by summing up the data bits and appending the result to the message
  • Receiver recomputes the checksum and compares it with the received checksum to detect errors
• Cyclic redundancy check (CRC) is a more advanced error detection technique
  • A polynomial division is performed on the message bits using a generator polynomial
  • The remainder of the division is appended to the message as the CRC bits
• Error detection codes can detect the presence of errors but cannot determine the exact location or correct them

Introduction to Error Correction Techniques

• Error correction techniques not only detect errors but also correct them to recover the original message
• Forward error correction (FEC) adds redundancy to the message before transmission, enabling the receiver to correct errors without retransmission
  • Suitable for one-way communication or when retransmission is costly or impractical
• Automatic repeat request (ARQ) relies on error detection and retransmission of erroneous data
  • Receiver requests retransmission of the corrupted data from the transmitter
  • Suitable for two-way communication systems
• Hamming codes are simple linear block codes used for error correction
  • Can correct single-bit errors and detect double-bit errors
• Reed-Solomon codes are powerful non-binary block codes that can correct both bit errors and erasures
  • Widely used in data storage systems (CDs, DVDs) and digital communication
• Turbo codes and low-density parity-check (LDPC) codes are modern error correction techniques that approach the channel capacity

Linear Block Codes: Structure and Properties

• Linear block codes are a class of error-correcting codes defined by linear algebraic properties
• An $(n,k)$ linear block code encodes a $k$-bit message into an $n$-bit codeword
  • The code rate is defined as $R=\frac{k}{n}$, representing the ratio of message bits to codeword bits
• Generator matrix $G$ is used to encode the message $m$ into a codeword $c$ using the equation $c=mG$
  • $G$ is a $k \times n$ matrix that defines the encoding process
• Parity-check matrix $H$ is used for error detection and syndrome calculation
  • $H$ is an $(n-k) \times n$ matrix that satisfies $GH^T=0$
• Systematic form of a linear block code separates the message bits and parity bits in the codeword
  • Message bits appear unchanged in the codeword, followed by the parity bits
• Minimum distance of a linear block code determines its error-correcting capability
  • A code with a minimum distance of $d$ can correct up to $\lfloor\frac{d-1}{2}\rfloor$ errors
• Dual code of a linear block code is obtained by interchanging the roles of $G$ and $H$

Cyclic Codes and Their Applications

• Cyclic codes are a subclass of linear block codes with additional cyclic structure
• A cyclic shift of a codeword in a cyclic code results in another valid codeword
  • Enables efficient encoding and decoding using shift registers
• Generator polynomial $g(x)$ defines the encoding process of a cyclic code
  • Message polynomial $m(x)$ is multiplied by $g(x)$ to generate the codeword polynomial $c(x)$
• Parity-check polynomial $h(x)$ is used for error detection and syndrome calculation
  • $h(x)$ satisfies $g(x)h(x)=x^n-1$, where $n$ is the codeword length
• Bose-Chaudhuri-Hocquenghem (BCH) codes are a class of powerful cyclic codes
  • Can correct multiple errors and have efficient decoding algorithms
• Reed-Solomon codes are a special case of non-binary BCH codes
  • Widely used in data storage systems and digital communication
• Cyclic redundancy check (CRC) codes are cyclic codes used for error detection
  • Commonly used in data link layer protocols (Ethernet, Wi-Fi)

Convolutional Codes and Viterbi Decoding

• Convolutional codes are a class of error-correcting codes that introduce memory into the encoding process
• Encoder consists of a shift register and modulo-2 adders
  • Input bits are shifted through the register, and output bits are generated based on the current state and input
• Trellis diagram represents the state transitions and output bits of a convolutional code
  • Each path through the trellis corresponds to a possible encoded sequence
• Viterbi algorithm is used for maximum-likelihood decoding of convolutional codes
  • Finds the most likely transmitted sequence based on the received sequence and trellis structure
  • Uses dynamic programming to efficiently compute the path metrics and survivor paths
• Constraint length $K$ determines the memory of the convolutional code
  • A larger constraint length provides better error correction but increases decoding complexity
• Puncturing is a technique used to increase the code rate of a convolutional code
  • Selected output bits are removed from the encoded sequence according to a puncturing pattern
• Turbo codes are a class of high-performance convolutional codes that approach the channel capacity
  • Consist of two or more convolutional encoders connected by interleavers
  • Iterative decoding algorithm exchanges soft information between the component decoders

Modern Error-Correcting Codes in Practice

• Low-density parity-check (LDPC) codes are linear block codes with sparse parity-check matrices
  • Iterative message-passing decoding algorithms (sum-product, min-sum) enable efficient decoding
  • Used in modern communication systems (5G, Wi-Fi, satellite communication)
• Polar codes are a class of capacity-achieving codes based on channel polarization
  • Recursive construction of polar codes leads to polarized channels that are either very reliable or very noisy
  • Successive cancellation decoding exploits the polarized structure to achieve capacity
• Spatially coupled LDPC codes are a variant of LDPC codes with improved performance
  • Coupling of the parity-check matrix across spatial dimensions leads to threshold saturation
• Raptor codes are a class of fountain codes that enable efficient encoding and decoding for large-scale data dissemination
  • Rateless property allows generation of unlimited number of encoded symbols
  • Used in multimedia streaming and distributed storage systems
• Quantum error-correcting codes are designed to protect quantum information from errors
  • Stabilizer codes (CSS codes) are a class of quantum codes based on classical error-correcting codes
  • Surface codes are a promising approach for fault-tolerant quantum computation

Limitations and Future Directions

• Fundamental trade-off between code rate, error-correcting capability, and decoding complexity
  • Increasing the code rate reduces the redundancy and error-correcting capability
  • Improving error correction often comes at the cost of increased decoding complexity
• Channel capacity sets the theoretical limit for reliable communication over a noisy channel
  • Achieving capacity requires codes with long block lengths and complex decoding algorithms
• Finite block length analysis provides insights into the performance of short codes
  • Finite-length scaling laws characterize the gap to capacity as a function of block length
• Joint source-channel coding aims to optimize the end-to-end performance by considering source and channel coding together
  • Exploits the source statistics and channel properties to achieve better performance
• Machine learning and deep learning techniques are being explored for error correction
  • Neural network-based decoders can learn to exploit complex channel characteristics
  • Autoencoder-based approaches learn the encoding and decoding functions jointly
• Quantum error correction is crucial for realizing fault-tolerant quantum computation and communication
  • Requires codes with high error thresholds and efficient decoding algorithms
  • Topological codes (surface codes, color codes) are promising candidates for practical quantum error correction