Shannon information + entropy; channel + source coding; rate-distortion; Kolmogorov complexity; algorithmic randomness; quantum information primitives; statistical-physics connection.
information-theory
Shannon source coding theorem
Shannon 1948: i.i.d. source with entropy H per symbol can be losslessly compressed to rate R iff R ≥ H. Foundation of data compression.…
Shannon channel coding theorem
Shannon 1948: noisy-channel admits reliable communication at rate R iff R < C = max_p I(X;Y). Channel-capacity. Foundational; achieved by…
Rate-distortion theory
Shannon 1959: lossy-compression of source X to fidelity D bounded by R(D) = min_{p(y|x): E[d(X,Y)]≤D} I(X;Y). Foundation of lossy…
Kolmogorov complexity + MDL
Kolmogorov 1965 / Solomonoff / Chaitin: K(x) = length of shortest program outputting x on universal machine. Algorithmic randomness. MDL…
Typical set + AEP
Asymptotic Equipartition Property: -1/n log p(X^n) → H(X) a.s. for ergodic stationary source. Typical set has ~2^{nH} sequences ≈…
Kullback-Leibler divergence + relative entropy
KL(P||Q) = E_P[log P/Q]. Non-negative; zero iff P=Q. Foundation of statistical-inference + variational-methods + ML. Pinsker inequality TV…
Mutual information
I(X;Y) = H(X) + H(Y) - H(X,Y) = E[log p(X,Y)/p(X)p(Y)]. Symmetric. Channel-capacity = max I. Bridges info-theory + statistics + ML…
Fisher information + Cramer-Rao bound
Fisher I(θ) = E[(∂log p/∂θ)²]. Cramér-Rao: var(θ̂) ≥ 1/(n I(θ)) for unbiased estimators. Foundation of MLE + statistical-physics.…
Compressed sensing (Candès-Tao-Donoho)
Candès-Tao 2005 / Donoho 2006: K-sparse signal recoverable from M ~ K log(N/K) random linear measurements via L^1-minimisation. RIP…
LDPC + Turbo codes
Gallager 1963 LDPC + Berrou-Glavieux 1993 Turbo. Approach Shannon-capacity within fraction-of-dB via belief-propagation decoding on…
Polar codes (Arıkan)
Arıkan 2009 first explicit capacity-achieving codes via channel-polarisation. 5G control-channels. Foundation of next-generation…
Information bottleneck (Tishby)
Tishby-Pereira-Bialek 1999 / Tishby 2017: minimal-sufficient-statistics via min I(X;Z) - β I(Z;Y). Lossy compression preserving relevant…
Shannon channel capacity (1948)
Shannon 1948: noisy-channel coding theorem establishes capacity C = max_p(x) I(X;Y) as fundamental limit; rate < C achievable, rate > C…
Kullback-Leibler divergence
Kullback-Leibler 1951: D_KL(P||Q) = sum p log(p/q); non-negative, asymmetric, zero iff P=Q; foundation of variational inference + Bayesian…
Rate-distortion theorem
Shannon 1959 lossy-source-coding: minimum bits-per-symbol R(D) to reconstruct source with average distortion <= D; convex non-increasing…
Typical set + AEP (Shannon-McMillan)
Asymptotic-equipartition-property: for iid sequence x^n, P(x^n) approx 2^(-nH(X)) for typical x^n; foundation of source-coding +…
Polar codes (Arikan 2008 IT)
Arikan 2008: first explicit construction achieving Shannon-capacity at low complexity; basis of 5G control-channel coding standard.
LDPC codes (Gallager 1962)
Gallager 1962 low-density parity-check codes: rediscovered MacKay 1996; near-Shannon-limit performance via belief-propagation decoding;…
Shannon entropy (1948)
C Shannon 1948 H = -Σ p log p; modern modern foundational text + Kolmogorov-complexity + 2024 ML-information-bottleneck Tishby.
Channel capacity (Shannon 1948)
C Shannon 1948 C = max I(X;Y); modern modern foundational text + LDPC / Polar / Turbo + 2024 6G capacity-theory.
Kraft-McMillan (1949)
L Kraft 1949 + B McMillan 1956 Σ D^-l ≤ 1 prefix-codes; modern modern foundational text + Huffman 1952 + 2024 modern arithmetic-coding…
Hamming codes (1950)
R Hamming 1950 single-error-correcting-codes; modern modern foundational text + extended-Hamming + 2024 LDPC + Polar-codes 5G replaced.
Kolmogorov complexity (1965)
A Kolmogorov 1965 + Solomonoff 1964 + Chaitin 1969 K-complexity; modern modern foundational + algorithmic-info + 2024…
Rate-distortion (Shannon 1959)
C Shannon 1959 R(D)-rate-distortion; modern modern foundational text + 2024 deep-learning rate-distortion-VAE neural-compression Ballé.