# Lecture 18: Transmitting Information Reliably over a Noisy Channel & Shannon’s Noisy Coding Theorem Source: https://www.youtube.com/watch?v=kWsJ_JDuFaI Recap page: https://rapidrecap.app/video/kWsJ_JDuFaI Generated: 2025-12-17T16:37:16.441+00:00 --- ## 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 \log_2 p - (1-p) \log_2 (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. ## Detailed Analysis The lecture details the problem of reliable communication over a Binary Symmetric Channel (BSC) with flip probability $p$. Simple repetition codes increase transmission length by $T=100 \log k$ times the original message length $k$, leading to a rate approaching zero as $k \to \infty$. The core result presented is Shannon's Noisy Coding Theorem, which establishes the channel capacity $C = 1 - H(p)$. If the target rate $R$ is less than $C$, there exists an encoding-decoding scheme where the probability of error goes to zero as the transmission length $n$ goes to infinity, allowing for constant, non-zero rate communication. If $R > C$, reliable decoding is impossible. The proof sketch for the positive capacity case relies on the probabilistic method: choosing the encoding function (the codebook $\mathcal{C}$) randomly. A key lemma shows that for a randomly chosen codebook, the received signal $\tilde{C}$ will fall into the ring corresponding to the transmitted codeword $C_i$ and no other codeword's ring with high probability, provided $R < 1 - H(p)$. The size of these rings is combinatorially related to the entropy $H(p)$ via the asymptotic analysis of binomial coefficients $\binom{n}{np}$. The final step uses the probabilistic method and Markov's inequality to select a fixed codebook $C'$ from the randomly generated set that guarantees the desired error bound for all messages, not just a random subset. ### Channel Model and Simple Solution - The Binary Symmetric Channel (BSC) is defined by flip probability $p$ - Repetition codes combat errors by repeating bits $T$ times, allowing majority vote decoding, but result in a rate of $1/T$, which approaches zero as $k \to \infty$. ### Shannon's Noisy Coding Theorem - The theorem asserts two bounds based on capacity $C = 1 - H(p)$ - If $R < C$, error probability $\to 0$ as $n \to \infty$ - If $R > C$, error probability $\to 1$ as $n \to \infty$. ### Intuition on Capacity Extremes - When $p=1/2$, $H(p)=1$, so $C=0$, meaning no positive rate communication is possible because the channel output is purely random - When $p$ is small (or large, due to symmetry), $C$ is positive, allowing reliable communication at a constant rate. ### Proof Strategy for Positive Rate - The successful scheme uses a random encoding function (random codebook $\mathcal{C}$) and decoding based on proximity to codewords in terms of Hamming distance, specifically checking which 'ring' the received signal belongs to. ### Key Combinatorial Result - The asymptotic behavior of $\frac{1}{n} \log \binom{n}{pn}$ results in the binary entropy $H(p)$, which governs the size of the relevant sets (rings) in the decoding space. ### The Key Lemma - For a random codebook, the probability that the received $\tilde{C}$ belongs to the ring of the transmitted $C_i$ and no other $C_j$ ring is high (at least $1-\epsilon$), provided the rate $R$ is strictly less than $1 - H(p)$, utilizing a union bound over alternative codewords.