Information Theory Tutorial
Learn Information Theory step by step: 37 lessons in 9 chapters with examples, quizzes, diagrams and projects.
Start learning →
of lessons completed
Getting Started
- What Is Information Theory? Meet information theory: how Claude Shannon turned 'information' into a number of bits, why it governs compression and reliable communication, and what this course covers.
- Bits and Surprise Learn self-information, -log2 p: why rare events carry more bits, how bits, nats and hartleys relate, and why information adds up for independent events.
- A Probability Refresher The probability you need for information theory: distributions, expectation, joint and marginal tables, conditional probability, independence and Bayes' rule, with NumPy.
- The Communication System Walk through Shannon's model of communication: source, encoder, noisy channel, decoder. Simulate a binary symmetric channel and see why a repetition code trades rate for reliability.
Entropy and Information
- Entropy Define Shannon entropy as expected surprise, compute it in Python, see why the fair coin and uniform distribution maximize it, and estimate entropy from real text.
- Joint and Conditional Entropy Compute joint entropy H(X,Y) and conditional entropy H(Y|X) from a probability table, prove the chain rule numerically and see why conditioning never increases entropy.
- Mutual Information Mutual information I(X;Y) measures how many bits one variable tells you about another. Compute it from a joint table, estimate it from samples and compare with scikit-learn style checks.
- KL Divergence and Cross-Entropy Understand relative entropy (KL divergence) and cross-entropy: the extra bits you pay for coding with the wrong model, Gibbs' inequality, and the link to log-loss in machine learning.
- Properties and Inequalities The tools that make information theory proofs work: Jensen's inequality, the log-sum inequality, the data processing inequality, Markov chains and Fano's inequality, checked numerically.
Source Coding
- Codes and Prefix Codes What a code is, why fixed-length codes waste bits, and why prefix-free codes can be decoded instantly. Build encoders and decoders, a code tree, and a unique-decodability test in Python.
- The Kraft Inequality The Kraft-McMillan inequality tells you exactly which codeword lengths a prefix code can have. Learn the tree-counting proof idea, then build a code from lengths in Python.
- The Source Coding Theorem Why no lossless code beats entropy and how close you can get: the bound H <= L < H+1, block coding that squeezes the overhead, and the entropy rate of sources with memory.
- Shannon and Shannon-Fano Codes Build Shannon coding (lengths ceil(-log2 p)) and Shannon-Fano coding (recursive splitting) in Python, compare them to entropy, and learn why Fano is not always optimal.
Huffman and Arithmetic Coding
- Huffman Coding Learn Huffman coding: merge the two least likely symbols until one tree remains. Implement it with heapq, encode and decode text, and measure the average length against entropy.
- Huffman: Optimality, Canonical Codes and Limits Why Huffman coding is optimal, how canonical Huffman codes store only code lengths (as in DEFLATE), brute-force verification on small sources, and why a 1-bit minimum motivates arithmetic coding.
- Arithmetic Coding Arithmetic coding represents a whole message as one number inside a shrinking interval. Implement an exact encoder and decoder with Fractions and see why it gets within 2 bits of the entropy.
- Arithmetic Coding with Integers and Adaptive Models Build a real 32-bit integer arithmetic coder with renormalization and carry handling, pair it with an adaptive frequency model, and see how learning probabilities on the fly compares with static ones.
- Comparing Source Coders Benchmark fixed-length, Shannon, Huffman, block Huffman and arithmetic coding against entropy on different sources, and learn how to choose a coder and where context modelling beats them all.
Channel Capacity
- Mutual Information and Discrete Channels Model a noisy channel as a probability matrix, compute joint entropy and mutual information in Python, and see how much a received symbol tells you about the sent one.
- The Binary Symmetric and Erasure Channels Simulate the binary symmetric channel and the binary erasure channel in Python, derive their capacities 1 - H(p) and 1 - e, and compare noisy and erased bits.
- Channel Capacity and Shannon's Noisy-Channel Theorem Define channel capacity as maximum mutual information, compute it with the Blahut-Arimoto algorithm in Python, and understand Shannon's promise of reliable communication.
- The Gaussian Channel and the Shannon-Hartley Limit Learn the AWGN channel capacity C = B log2(1 + SNR), convert decibels, find the minimum Eb/N0 of -1.59 dB, and check the formulas with Python simulations.
Error-correcting Codes
- Error Detection: Parity, Checksums and CRC Add redundancy to detect transmission errors: parity bits, sums and CRC. Implement CRC-8 and CRC-32 from scratch in Python and compare detection rates.
- Repetition Codes and Hamming Codes Correct bit errors, not just detect them: build repetition and Hamming(7,4) codes in Python, decode with syndromes, and simulate them on a binary symmetric channel.
- Linear Block Codes and Syndrome Decoding Understand linear block codes: generator and parity-check matrices, minimum distance, weight enumerators, syndrome tables and the extended Hamming SECDED code in Python.
- Reed-Solomon and Convolutional Codes Build a Reed-Solomon style code over a prime field that survives lost symbols and errors, and a rate-1/2 convolutional code with a Viterbi decoder, all in Python.
Compression in Practice
- Dictionary Compression: LZ77 and LZ78 Learn how Lempel-Ziv dictionary coders replace repeats with references: implement LZ77 sliding-window and LZ78 dictionary compression in Python and test round trips.
- DEFLATE, gzip and zlib in Practice See how DEFLATE combines LZ77 and Huffman coding, how gzip and zlib wrap it, and measure compression levels, block types and the entropy limit with Python's zlib.
- The Burrows-Wheeler Transform and Move-to-Front Understand the Burrows-Wheeler transform, move-to-front coding and run-length encoding that power bzip2, and implement the whole reversible pipeline in Python.
- Lossy Compression and Rate-Distortion Theory Learn what lossy compression trades away: distortion measures, the rate-distortion function, scalar quantization and DCT transform coding, with runnable NumPy and SciPy examples.
Applications
- Cross-Entropy and KL Divergence in Machine Learning See why classifiers minimize cross-entropy: derive KL divergence, softmax loss and its gradient, label smoothing and perplexity, and train a softmax classifier from scratch in NumPy.
- Information Theory in Cryptography Apply entropy to security: Shannon's perfect secrecy and the one-time pad, key reuse failures, password entropy, min-entropy and unicity distance, with Python demos.
- Entropy of Text, DNA and Real Data Estimate entropy rates of English text and DNA with n-gram models, learn why plug-in estimates are biased on small samples, and use compression as an entropy meter.
Projects and Practice
- Project: A Byte-Entropy Analyzer Build a tool that slides a window over a file, computes Shannon entropy per byte, and classifies regions as text, zeros, compressed or random, a trick used in forensics and malware analysis.
- Project: An Error-Correction Simulator Build an end-to-end simulator with a message source, repetition, Hamming and convolutional encoders, a binary symmetric channel and decoders, then compare bit error rates with the Shannon limit.
- Project: A Mini DEFLATE-Style Compressor Build a working lossless compressor in Python from scratch: an LZ77 match finder, a Huffman coder, a bit-level encoder and decoder, a round-trip test and a comparison against zlib.
- Practice Problems with Solutions: Channels, Codes and Compression Ten worked information theory problems on channel capacity, mutual information, Hamming codes, sphere-packing, Shannon-Hartley, KL divergence, LZ77, Reed-Solomon and rate-distortion.