Information theory measures how much information a source produces and how reliably it can cross a noisy channel. It sets hard limits: the least a message can be compressed to, and the most a channel can carry without error. Compression, error-correcting codes, communications and parts of machine learning all rest on it.
Key concepts
- Entropy: the average surprise of a source in bits; it is the lower bound on lossless compression.
- Source coding: Huffman and arithmetic coding approach the entropy limit.
- Channel capacity: the highest rate at which a noisy channel can carry data with arbitrarily small error.
- Error-correcting codes: added redundancy lets the receiver detect and repair errors; parity, Hamming and Reed-Solomon codes are classics.
- Mutual information: how much knowing one variable tells you about another.
Vocabulary
- Bit: the unit of information, one yes-or-no choice between equally likely options.
- Redundancy: the part of a message that is not needed to convey its content.
- Lossy and lossless: whether the original can be recovered exactly.
- Kolmogorov complexity: the length of the shortest program that outputs a given string.
What to study, in order
- Probability basics: distributions, expectation and independence.
- Compute the entropy of a text by letter frequencies and compare it with what a general-purpose compressor achieves.
- Implement Huffman coding and measure its gap from the entropy.
- Build a Hamming code that corrects a single flipped bit.
- Study channel capacity for a binary symmetric channel, then cross-entropy as a loss in learning.
Related tags
#probability #cryptography #signal-processing #machine-learning