Channel capacity #
A channel from inputs C to outputs W is a Markov kernel κ : Kernel C W. An input
distribution μ induces the joint law μ ⊗ₘ κ and the output marginal κ ∘ₘ μ, and the
capacity of the channel is the supremum over input distributions of the mutual information
Im[μ ⊗ₘ κ].
Over finite alphabets the mutual information is the input average of the divergence of each row
κ c from the output marginal, and averaging the divergence from any other reference measure
overshoots it by the divergence of the output marginal from that reference (the compensation
identity). An input distribution achieves capacity when no row lies farther from its output
marginal than the information it conveys.
Each row's divergence is also the row's expected log posterior of its input less the input's log
prior, and the Bayesian decoder maximizes that expected log posterior. Hence, taking a fixed input
distribution's expected log posteriors as the exponent, the free energy relative to the uniform
distribution of every input distribution is at most its mutual information less log |C|, with
equality at the fixed distribution. By the Gibbs variational principle the capacity-achieving
input distributions of positive mass everywhere are exactly the fixed points of the
Blahut–Arimoto update, which tilts the uniform distribution by that exponent, and at such a
fixed point every row lies at divergence exactly the capacity from the output marginal.
Main definitions #
InformationTheory.channelCapacity:⨆ μ, Im[μ ⊗ₘ κ]over probability measuresμ.InformationTheory.blahutArimoto: the uniform distribution tilted by each input's expected log posterior.
Main results #
InformationTheory.measureMutualInfo_compProd,InformationTheory.sum_mul_toReal_klDiv:Im[μ ⊗ₘ κ]is theμ-average of the divergencesklDiv (κ c) (κ ∘ₘ μ), and the compensation identity.InformationTheory.sum_mul_integral_log_le: the Bayesian decoder maximizes the expected log posterior of the input.InformationTheory.eq_blahutArimoto_iff: the capacity-achieving input distributions of positive mass everywhere are the Blahut–Arimoto fixed points.
References #
- C. E. Shannon, A Mathematical Theory of Communication (1948)
- R. E. Blahut, Computation of channel capacity and rate-distortion functions (1972)
- S. Arimoto, An algorithm for computing the capacity of arbitrary discrete memoryless channels (1972)
- T. M. Cover and J. A. Thomas, Elements of Information Theory (2006)
The capacity of a channel is the supremum over input distributions of the mutual information between its input and output.
Equations
- InformationTheory.channelCapacity κ = ⨆ (μ : MeasureTheory.ProbabilityMeasure C), InformationTheory.measureMutualInfo ((↑μ).compProd κ)
Instances For
The Blahut–Arimoto update of an input distribution is the uniform distribution tilted by each input's expected log posterior ([Bla72], [Ari72]).
Equations
- InformationTheory.blahutArimoto κ μ = (ProbabilityTheory.uniformOn Set.univ).tilted fun (c : C) => ∫ (w : W), Real.log (((ProbabilityTheory.posterior κ μ) w).real {c}) ∂κ c
Instances For
The conditional entropy of a channel's output given its input is the input average of the entropies of the rows.
The compensation identity. Averaging the divergence of the rows of a channel from a reference measure overshoots the mutual information by the divergence of the output marginal from that reference.
Mutual information across a channel is the input average of the divergence of each row from the output marginal.
Mutual information across a channel is at most the log of the number of outputs.
The capacity of a channel is at most the log of the number of outputs.
Sufficiency of the divergence condition. An input distribution achieves capacity when no row of the channel lies farther from the output marginal than the information conveyed.
The divergence of a row from the output marginal is the row's expected log posterior of its input, less the input's log prior.
The Bayesian decoder maximizes the expected log score of the input. No decoder that charges every input the posterior charges does better, even one that gives no guess at some outputs.
The Blahut–Arimoto fixed point #
The capacity-achieving priors are the Blahut–Arimoto fixed points. An input distribution achieves capacity with positive mass everywhere exactly when it is the uniform distribution tilted by each input's expected log posterior ([Bla72], [Ari72]).
Necessity of the divergence condition. An input distribution of positive mass everywhere that achieves capacity puts every row of the channel at divergence exactly the capacity from the output marginal.