FOLLOW AN IDEA
Information and Coding Theory
Explore information measures; compression and channels; error correction. Concepts and connections are available independently of video coverage.
Prerequisites and connections
Probability
A probability measure assigns nonnegative weights to events, with total weight one and countable additivity on disjoint events.
3 reviewed resources
Information measures
Shannon entropy
Entropy is expected negative log probability for a discrete distribution.
Video explanations to be addedConditional entropy
Conditional entropy averages remaining uncertainty after another variable is observed.
Video explanations to be addedMutual information
Mutual information measures statistical dependence as the reduction in uncertainty from observing another variable.
Video explanations to be addedRelative entropy
KL divergence compares distributions and is generally asymmetric, with support conditions affecting finiteness.
Video explanations to be added
Compression and channels
Source coding
Source coding represents messages efficiently, with entropy constraining lossless average code length.
Video explanations to be addedPrefix codes
No codeword is a prefix of another, enabling unambiguous immediate decoding.
Video explanations to be addedHuffman coding
A greedy merging procedure builds an optimal binary prefix code for given symbol probabilities.
Video explanations to be addedChannel capacity
Capacity bounds achievable reliable information rates for a specified channel model.
Video explanations to be added
Error correction
Hamming distance
Hamming distance counts differing positions between equal-length strings.
Video explanations to be addedLinear codes
Codewords forming a finite-field vector subspace enable algebraic encoding and decoding.
Video explanations to be addedParity checks
A parity-check matrix produces a syndrome that diagnoses violations of code constraints.
Video explanations to be addedError correction bounds
Minimum distance d permits correcting up to floor((d-1)/2) arbitrary symbol errors.
Video explanations to be added