Information Theory & Error-Correcting Codes

← Back to Domain-Specific Families

Abstractions about quantifying and transmitting information reliably, covering entropy and typicality (binary entropy function, asymptotic equipartition property, min-entropy), channel models (binary erasure channel, directed information), and error-correcting code constructions and decoding methods (polar codes, Parvaresh-Vardy codes, sequential decoding).

20 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Asymptotic equipartition property — The information-theoretic property that long source sequences concentrate on a typical set whose members have nearly equal exponential probability.
• Binary entropy function — The Shannon entropy of a Bernoulli variable as a concave function of its success probability.
• Binary erasure channel — A memoryless channel model that delivers each input bit correctly or replaces it with an explicit erasure symbol at a fixed probability.
• Directed information — An information-theoretic quantity summing the conditional information that the present and past of one process provide about each current value of another given the latter's past.
• Elias Bassalygo bound — An asymptotic upper bound on error-correcting-code rate derived by restricting codewords to a dense Hamming sphere and applying a Plotkin-type distance bound.
• Incompressibility method — A proof method that selects a Kolmogorov-incompressible object and shows that failure of the desired property would yield an impossibly shorter description.
• Information dimension — The asymptotic growth rate of the Shannon entropy of increasingly fine quantizations of a random variable or distribution.
• Krichevsky–Trofimov estimator — Estimate categorical symbol probabilities by adding one-half to every observed count, the Jeffreys-prior predictive rule that attains asymptotically minimax worst-case coding regret.
• Linear programming decoding — Error-correcting-code decoding by relaxing maximum-likelihood integer constraints to a tractable linear program over a codeword polytope approximation.
• Log area ratio — A logarithmic transform of a speech-filter reflection coefficient used as a quantized transmission parameter in legacy linear-predictive codecs.
• Min-entropy — The negative logarithm of the largest outcome probability, measuring worst-case single-guess unpredictability as the order-infinity Rényi entropy.
• Parvaresh–Vardy code — An algebraic error-correcting code that encodes correlated polynomial evaluations so received words can be efficiently list-decoded beyond the Reed–Solomon radius.
• Polar code (coding theory) — A linear error-correcting code that recursively transforms channels into nearly perfect and nearly useless bit-channels, placing information only on the reliable ones.
• Relay channel — An information-theoretic channel with a source, a causally acting relay, and a destination, whose joint channel law determines what cooperation can achieve.
• Sequential decoding — A variable-effort tree-search method for approximately maximum-likelihood decoding long convolutional or tree codes using far less memory than exhaustive trellis decoding.
• Set redundancy compression — Compression that exploits shared structure across a collection of related data objects rather than encoding each object independently.
• Shannon–Fano–Elias coding — A prefix-coding construction that chooses codewords from binary expansions of cumulative-probability midpoints.
• Small-bias sample space — A compact distribution on binary strings whose parity over every nonempty coordinate subset differs from uniform by at most ε, providing pseudorandomness against linear tests.
• Typical set — The high-probability set of long source sequences whose per-symbol information is close to the source entropy.
• Wozencraft ensemble — An explicit finite ensemble of rate-one-half linear codes over a finite field in which almost every member asymptotically meets the Gilbert–Varshamov distance bound.