Information Theory: Entropy & Coding

Learning Goal: Quantify data mathematically, understand the conceptual and physical meaning of Shannon entropy, analyze source coding theorems for optimal compression, and construct error-correcting codes to secure data transmission across noisy channels.

• Prerequisites: High-school algebra (basic exponents) and basic arithmetic. No prior programming or advanced probability theory is required.
• Estimated Total Study Time: 15 Hours

---

Module 1: Mathematical Foundations: Probability & Logarithms

To measure information, we must first learn how to mathematically model uncertainty and scaling. This module establishes the bedrock mathematical concepts required for information theory: intuitive probability, expected values, logarithmic scaling (specifically base-2), and Bayesian updating.

Recommended Videos

Why this video

This video provides a masterclass in visualizing Bayes' Theorem geometrically. Instead of forcing you to memorize abstract formulas, it uses interactive area models to show how new evidence alters the space of possibilities. This geometric intuition is essential when dealing with noisy transmission channels later in the course.

Knowledge Checkpoint

• Visualise probability spaces as geometric areas that sum to 1.
• Explain how "prior beliefs" are updated dynamically when new evidence or noise is introduced.
• Write out the formula for Bayes' Theorem and map each term to its geometric equivalent.

---

Why this video

Information is naturally additive, whereas independent probabilities are multiplicative. Logarithms bridge this gap. Khan Academy provides an incredibly clear, intuitive foundation for logarithms, showing how they undo exponentiation and count the number of times we must scale a system.

Knowledge Checkpoint

• Define a logarithm as the inverse of an exponent.
• Calculate basic logarithms by hand (e.g., $\log_2(8)$ and $\log_2(16)$).
• Explain why base-2 logarithms are uniquely suited to binary systems (bits).

---

Why this video

Shannon Entropy is fundamentally an "expected value" of surprise. This video breaks down the concept of expected value using easy-to-follow probability scenarios, demonstrating how to weight different outcomes by their likelihood to find a long-term average.

Knowledge Checkpoint

• State the mathematical formula for the expected value of a discrete random variable.
• Calculate the expected value of an unfair coin or die.
• Understand how expected value acts as a probability-weighted average.

---

Module 2: Quantifying Data: Shannon Entropy

Here, we enter the core of Information Theory. You will learn how Claude Shannon revolutionized science by defining "information" as the resolution of uncertainty. We will define "surprisal", calculate Shannon Entropy mathematically, and explore how it links physical systems to digital ones.

Recommended Videos

Why this video

This is a highly engaging, high-level introduction to why Shannon's work changes how we view the universe. It details the math behind $H = -\sum p(x)\log_2 p(x)$ and builds the intuition that highly unlikely events carry far more "surprise" (and thus more information) than guaranteed events.

Knowledge Checkpoint

• Explain why a certain event (probability $p = 1$) carries zero information.
• Articulate the relationship between the probability of an event and its "surprisal" value ($-\log_2 p$).
• Describe how Claude Shannon's concept of a "bit" differs from a physical transistor switch.

---

Why this video

This video uses concrete, physical analogies to explain how Shannon's formula works. It visually walks through the decision-tree structure of finding a hidden object, showing how the formula calculates the minimum number of yes/no questions needed on average to resolve uncertainty.

Knowledge Checkpoint

• Convert a probability distribution of outcomes into a Shannon Entropy value in bits.
• Draw the connection between the "bounce/decision tree" analogy and logarithmic equations.
• Explain why a uniform distribution (where all outcomes are equally likely) yields the maximum possible entropy for a system.

---

Why this video

Theoretical physicist Sean Carroll connects the dots between Shannon's mathematical entropy and thermodynamic entropy (Boltzmann's constant). It's a profound conceptual bridge showing that "information" isn't just an abstract computer science tool—it is a fundamental physical property of matter.

Knowledge Checkpoint

• Contrast physical entropy (disorder in thermodynamic states) with informational entropy (uncertainty in messages).
• Explain how Ludwig Boltzmann and Claude Shannon independently arrived at the same mathematical core equation.

---

Module 3: Source Coding & Lossless Compression

Now that we can measure information, how do we represent it using the fewest bits possible? This module covers Shannon's Source Coding Theorem, prefix-free codes, and David Huffman’s elegant greedy algorithm for optimal data compression.

Recommended Videos

Why this video

Reducible offers a stunning visual transition from Shannon-Fano coding to Huffman coding. It demonstrates why Huffman codes are mathematically guaranteed to achieve optimal average codeword lengths by building prefix-free trees from the bottom up.

Knowledge Checkpoint

• Explain what makes a code "prefix-free" and why this property is essential for real-time decoding.
• Demonstrate how a bottom-up binary tree is built using a list of symbol frequencies.
• Calculate the average codeword length of a Huffman-coded alphabet and compare it to the source's Shannon Entropy.

---

Why this video

Computerphile walks through the practical mechanics of Huffman coding. This video is highly applied, showing step-by-step how text files are analyzed, translated into binary trees, and then decompressed back into original characters without losing a single bit.

Knowledge Checkpoint

• Construct a Huffman Tree manually given a custom set of characters and frequencies.
• Encode and decode messages using your constructed Huffman tree.
• Understand why lossless compression cannot compress every possible file (the pigeonhole limitation).

---

Why this video

For students looking to master the rigorous mathematics, this academic lecture formally proves Shannon's Source Coding Theorem. It establishes that the entropy $H(X)$ is the absolute, unbreakable limit for the average number of bits per symbol required to represent a source.

Knowledge Checkpoint

• State Shannon's Source Coding Theorem formally.
• Describe the mathematical bounds on expected code length: $H(X) \le L < H(X) + 1$.
• Define the concept of "redundancy" in coding systems.

---

Module 4: Noisy Channels & Mutual Information

What happens when we transmit data through a channel that suffers from electrical noise or interference? This module defines Mutual Information (how much one variable tells us about another) and explores Shannon's Noisy-Channel Coding Theorem, which proves we can achieve error-free communication up to a speed limit called "Channel Capacity."

⚠️ Curriculum Note on Topic Gaps: The available video pool lacks highly visual, beginner-friendly explanations of Mutual Information and Channel Capacity. To complement the lectures below, we highly recommend searching YouTube for these exact queries:

• Search Query 1: "Mutual information intuitive explanation visual"
• Search Query 2: "Shannon channel capacity limit explained"

Recommended Videos

Why this video

StatQuest does a phenomenal job of demystifying Mutual Information. Rather than starting with intimidating probability notation, it uses highly intuitive, color-coded examples to show how we calculate the reduction in uncertainty of one variable given knowledge of another.

Knowledge Checkpoint

• Write out the formula for Mutual Information $I(X; Y) = H(X) - H(X|Y)$ and explain its terms.
• Interpret what a Mutual Information of 0 bits means (complete independence of variables).
• Distinguish between Entropy (uncertainty in one variable) and Mutual Information (shared information between two variables).

---

Why this video

This video details Shannon's mind-bending Noisy-Channel Coding Theorem. Historically, engineers thought that to get a lower error rate, you had to slow down your transmission rate to a crawl. Shannon proved you can transmit at maximum efficiency with zero errors, as long as your transmission rate is below the channel's capacity.

Knowledge Checkpoint

• Define Channel Capacity ($C$).
• State the Noisy-Channel Coding Theorem and its implications for modern communications.
• Explain how modern systems use redundant coding to correct errors on-the-fly rather than resending messages.

---

Why this video

This academic video introduces the physics of channel capacity via the famous Shannon-Hartley Theorem: $C = B \log_2(1 + \text{SNR})$. It explains how bandwidth ($B$) and Signal-to-Noise Ratio ($\text{SNR}$) limit the physical capacity of any communication channel (like Wi-Fi, 5G, or fiber optic cables).

Knowledge Checkpoint

• Calculate the capacity of a channel using the Shannon-Hartley equation given bandwidth and SNR.
• Convert Signal-to-Noise Ratio from decibels (dB) to a linear scale for calculation.
• Explain how increasing bandwidth affects channel capacity versus increasing signal power.

---

Module 5: Error-Correcting Codes

To actually achieve reliable communication over noisy channels, we must construct Error-Correcting Codes (ECC). This module covers simple parity bits, explores the elegant geometry of Richard Hamming’s "Perfect" Hamming (7,4) Code, and briefly examines block codes like Reed-Solomon codes that protect QR codes and CDs.

⚠️ Curriculum Note on Topic Gaps: The video pool has great resources for Hamming Codes, but lacks a detailed step-by-step math tutorial on Reed-Solomon codes. To gain a deep mathematical understanding of Reed-Solomon codes, we highly recommend searching YouTube for:

• Search Query: "How Reed-Solomon codes work step by step"

Recommended Videos

Why this video

Neso Academy provides a mathematically meticulous, step-by-step introduction to Hamming Codes. You will learn the exact placement of parity bits at power-of-two index positions ($1, 2, 4...$) and how they mathematically map to data bits.

Knowledge Checkpoint

• Calculate the number of redundant parity bits needed for any block of data using the equation $2^P \ge M + P + 1$.
• Construct a Hamming (7,4) code matrix manually from a 4-bit message.
• Explain how overlapping parity sets allow a receiver to isolate the exact index of an error.

---

Why this video

This video introduces the beautiful hypercube geometry of Hamming Codes. It explains "Hamming Distance"—the minimum number of single-bit changes needed to transform one valid codeword into another—and shows why Hamming codes are called "Perfect" because they pack the space of possible codes with absolutely zero waste.

Knowledge Checkpoint

• Define "Hamming Distance" and explain how it determines error detection vs. error correction limits.
• Visualize error correction geometrically as finding the nearest valid codeword sphere on a multidimensional hypercube.
• Explain why the Hamming (7,4) code can correct exactly 1 bit error but cannot safely correct 2 bit errors.

---

Why this video

Veritasium's highly interactive project shows how Reed-Solomon codes operate in the real world on a physical QR code. By painting pixels by hand, Derek Muller illustrates how treating messages as polynomials allows QR codes to remain perfectly readable even if up to 30% of the code is smudged, torn, or destroyed.

Knowledge Checkpoint

• Explain the fundamental difference between single-bit Hamming codes and "burst error" correcting block codes like Reed-Solomon.
• Understand how treating message bits as mathematical polynomial coefficients allows systems to recover missing chunks of data.

---

Course Map

---

Key People Index

Claude Shannon (1916–2001)

The Father of Information Theory. In his groundbreaking 1948 paper, "A Mathematical Theory of Communication", Shannon mathematically defined entropy, proved that data can be compressed up to a theoretical limit (Source Coding Theorem), and proved that error-free communication is possible over noisy mediums (Noisy-Channel Coding Theorem).

Richard Hamming (1915–1998)

Pioneer of Error-Correction. Frustrated by unreliable punch-card readers that crashed on single-bit errors, Hamming developed the concept of "Hamming Distance" and constructed the first "Perfect" self-correcting binary linear block codes (Hamming Codes), which are still used in ECC computer memory today.

David Huffman (1925–1999)

Inventor of Huffman Coding. While a PhD student at MIT, Huffman was given a choice by his professor: solve an efficiency problem for message codes or take the final exam. He bypassed the exam by discovering an elegant, tree-based greedy algorithm that produces optimal prefix-free codes, which are still used in JPEG and MP3 formats today.

---

Final Self-Assessment

Test your mastery of Information Theory by confirming you can confidently complete each of the following tasks:

• Calculate the base-2 logarithm of any power of 2 (e.g., $\log_2 128$) and explain its relation to bits of information.
• Manually compute the Shannon Entropy ($H$) of a biased coin that lands on Heads 75% of the time.
• Explain the difference between "Information/Surprisal" of a single event versus the "Entropy" of a whole system.
• Construct an optimal prefix-free binary tree using Huffman's algorithm for a given set of five characters and their frequency of occurrence.
• Verify if a given set of variable-length binary codes is "prefix-free" and describe how to decode it instantly without lookahead.
• Explain the physical meaning of "Mutual Information" and calculate it given the joint distribution of an input signal and a noisy output signal.
• State why the Shannon-Hartley limit means you cannot transmit infinite data down a standard copper phone line, regardless of how clean your transmitter is.
• Generate the required parity bit pattern for a 4-bit message block using the Hamming (7,4) design.
• Detect and correct a single-bit error in a received 7-bit Hamming codeword using parity checks.
• Describe how a QR code can still be successfully scanned even if a piece of it has been completely ripped off (referencing polynomial-based Reed-Solomon codes).