Lecture 18: Transmitting Information Reliably over a Noisy Channel & Shannon’s Noisy Coding Theorem

Quick Overview

Shannon's Noisy Coding Theorem asserts that reliable information transmission over a noisy channel, modeled by the Binary Symmetric Channel (BSC), is possible only if the transmission rate R is strictly less than the channel capacity, defined as $1 - H(p)$, where $H(p)$ is the binary entropy function of the flip probability $p$; if $R$ is greater than this capacity, reliable decoding fails, and if $R$ is less, a random encoding scheme combined with a specific decoding strategy achieves an error probability tending to zero as transmission length $n$ increases.

Key Points: The Binary Symmetric Channel (BSC) model introduces errors where an input bit flips with probability $p$ and passes through correctly with probability $1-p$. Repetition codes, where each bit is repeated $T=100 \log k$ times and decoded via majority vote, achieve error probability going to zero but suffer from a vanishing rate of $1/(100 \log k)$ as message length $k \to \infty$. Shannon's Noisy Coding Theorem states that if the rate $R < 1 - H(p)$, the error rate $\lambda^(R, n)$ goes to 0 as $n \to \infty$; conversely, if $R > 1 - H(p)$, the error rate goes to 1. The channel capacity is $C = 1 - H(p)$, where $H(p) = -p \log2 p - (1-p) \log2 (1-p)$, and this capacity is 0 when $p=1/2$ (maximum noise), meaning no communication is possible. The proof for achieving positive rate relies on using a random encoding function (a random codebook $\mathcal{C}$) and a decoder that checks which codeword's 'ring' (defined by Hamming distance bounds around $np$) the received signal $\tilde{C}$ falls into. The size of a ring around a codeword $C$ is bounded by $2^{H(p)n}$ (Fact 1), and the key lemma shows that for a randomly chosen codebook, the received signal $\tilde{C}$ belongs to the correct codeword's ring and no others with high probability, provided the rate $R < 1 - H(p)$.

Context: The lecture transitions from data compression to error correction in communication theory, focusing on transmitting information reliably over a noisy medium, specifically modeled by the Binary Symmetric Channel (BSC). The BSC is characterized by a single parameter $p$, the independent bit flip probability. The discussion contrasts simple, inefficient error correction methods like repetition codes, which sacrifice transmission rate for reliability, with the theoretical limits established by Claude Shannon regarding achievable constant rates.