Computation Theory · Cluster
Information Theory
Entropy, coding, and channel capacity.
- 01 Shannon Entropy as the Expected Cost of an Outcome Why information is measured as the logarithm of reciprocal probability, how entropy averages that quantity over a source, and where the number stops describing anything real.
- 02 Mutual Information and the Capacity of a Noisy Channel How the largest reliable transmission rate is defined as a maximum of mutual information, why the binary symmetric channel peaks at an interior input distribution, and what the capacity formula does not promise.
- 03 Prefix Codes, the Kraft Inequality, and Why Huffman Is Optimal How decodability without separators constrains code lengths, what the Kraft sum measures, and the exchange argument that makes Huffman coding the best prefix code for a known distribution.
- 04 Arithmetic Coding by Interval Subdivision How a message becomes a single rational interval, why the decoder needs no codeword boundaries, and what finite-precision renormalization must do to keep the arithmetic exact.
- 05 LZ77, LZ78, and the Shift from Symbols to Substrings How dictionary coders replace repeated substrings with back-references, why their output is not bounded by the source entropy, and how the parser design determines the compression actually obtained.
- 06 Entropy Rate of a Markov Source and the Value of Context Why the per-symbol cost of a source with memory is not its order-0 entropy, how the entropy rate is computed from a transition matrix, and what context models capture that frequency tables cannot.
- 07 Range Coding and rANS as Practical Entropy Coders How byte-oriented range coders and asymmetric numeral systems implement the arithmetic-coding ideal with integer state, and why interleaving makes the rANS variant parallelizable.
- 08 Rate-Distortion Theory and the Shape of Lossy Compression Why lossy coding is governed by a curve rather than a single number, how the Gaussian bound is derived, and why vector quantization beats scalar quantization at the same rate.
- 09 Sparse Parity-Check Codes and Iterative Decoding How a low-density parity-check matrix defines a code, why belief propagation on its Tanner graph approaches capacity, and where trapping sets produce an error floor.
- 10 Kolmogorov Complexity and the Two-Part MDL Code Why the shortest program describing an object is uncomputable yet still useful, how the two-part minimum description length principle turns that idea into a model selection criterion, and where the criterion misleads.