ℹ️Information Theory Unit 9 – Noisy Channel Coding Theorem

Key Concepts and Definitions

• Noisy channel coding theorem establishes the maximum rate at which information can be transmitted over a noisy channel with a specified probability of error
• Channel capacity ($C$) represents the maximum rate at which information can be reliably transmitted over a noisy channel
• Mutual information ($I(X;Y)$) measures the amount of information that can be obtained about one random variable by observing another
• Entropy ($H(X)$) quantifies the average amount of information contained in a random variable
  • Conditional entropy ($H(X|Y)$) measures the remaining uncertainty in $X$ given knowledge of $Y$
• Encoding involves converting the source message into a suitable form for transmission over the noisy channel
• Decoding aims to reconstruct the original message from the received signal, taking into account the channel's noise characteristics

Shannon's Noisy Channel Model

• Shannon's noisy channel model consists of an information source, encoder, noisy channel, decoder, and destination
• The information source generates the message to be transmitted over the noisy channel
• The encoder converts the message into a form suitable for transmission, adding redundancy for error correction
• The noisy channel introduces errors or distortions to the transmitted signal (additive white Gaussian noise)
• The decoder receives the corrupted signal and attempts to reconstruct the original message by exploiting the added redundancy
  • Maximum likelihood decoding and maximum a posteriori decoding are common decoding strategies
• The destination receives the decoded message, which should closely resemble the original message if the communication system is properly designed

Mutual Information and Channel Capacity

• Mutual information quantifies the reduction in uncertainty about one random variable by observing another
• For a noisy channel, mutual information measures the amount of information that can be reliably transmitted
• Channel capacity is the maximum mutual information over all possible input distributions
  • $C = \max_{p(x)} I(X;Y)$, where $p(x)$ is the input probability distribution
• The noisy channel coding theorem states that for any transmission rate $R < C$, there exists an encoding and decoding scheme that achieves arbitrarily small error probability
• Achieving channel capacity requires optimal encoding and decoding strategies, which may be computationally complex in practice

Encoding and Decoding Strategies

• Encoding adds redundancy to the source message to enable error correction at the receiver
• Linear block codes (Hamming codes) and convolutional codes are widely used encoding schemes
  • Linear block codes add parity bits to fixed-size message blocks
  • Convolutional codes generate encoded bits based on the current and previous input bits
• Decoding aims to reconstruct the original message from the received signal
• Maximum likelihood decoding chooses the codeword that is most likely to have been transmitted given the received signal
  • Viterbi algorithm is an efficient implementation of maximum likelihood decoding for convolutional codes
• Maximum a posteriori decoding incorporates prior knowledge about the message probabilities to improve decoding performance
• Turbo codes and low-density parity-check (LDPC) codes are powerful encoding and decoding schemes that approach the channel capacity

Error Probability and Reliability

• Error probability quantifies the likelihood of incorrectly decoding a received message
• The noisy channel coding theorem guarantees the existence of encoding and decoding schemes that achieve arbitrarily small error probability for rates below the channel capacity
• Bit error rate (BER) and block error rate (BLER) are common metrics for assessing the reliability of a communication system
  • BER measures the average number of bit errors per transmitted bit
  • BLER measures the fraction of decoded blocks that contain at least one error
• Forward error correction (FEC) techniques, such as encoding and decoding, help improve reliability by detecting and correcting errors at the receiver
• Automatic repeat request (ARQ) protocols retransmit erroneously received data to ensure reliable communication

Practical Applications and Examples

• Noisy channel coding theorem has significant implications for the design of reliable communication systems
• Error-correcting codes are widely used in digital communication systems (mobile networks, satellite communications)
  • Convolutional codes and turbo codes are employed in cellular networks (3G, 4G, 5G)
  • Reed-Solomon codes are used in compact discs (CDs) and digital video broadcasting (DVB)
• Deep space communications rely on powerful error-correcting codes to overcome the challenges of long distances and low signal-to-noise ratios
• Data storage systems (hard drives, solid-state drives) employ error-correcting codes to ensure data integrity
• Quantum error correction aims to protect quantum information from errors in quantum computing and communication systems

Limitations and Considerations

• Achieving channel capacity in practice may require complex encoding and decoding schemes, which can be computationally expensive
• The noisy channel coding theorem assumes memoryless channels, where the noise affects each transmitted symbol independently
  • Channels with memory (burst errors) may require different coding techniques
• The theorem assumes a fixed and known channel model, but in practice, the channel characteristics may vary over time (fading channels)
  • Adaptive coding and modulation techniques can help mitigate the effects of time-varying channels
• Feedback from the receiver to the transmitter can improve the performance of error-correcting codes (ARQ protocols)
• The theorem does not account for the delay introduced by encoding and decoding, which may be a concern in real-time applications

Related Theorems and Extensions

• Shannon's source coding theorem establishes the minimum average number of bits required to represent a source message without loss of information
• Joint source-channel coding theorem considers the optimal encoding and decoding strategies when the source and channel coding are combined
• Network information theory extends the noisy channel coding theorem to multi-user scenarios (multiple access, broadcast, relay channels)
  • Capacity regions characterize the achievable rates for multiple users sharing a common channel
• Quantum information theory adapts the noisy channel coding theorem to quantum channels and quantum error correction
• Secure communication over noisy channels can be achieved using techniques from information-theoretic security (one-time pad, wiretap channels)