InformationTheory.Shannon.ShannonHartley.Operational
Continuous-time Shannon-Hartley operational capacity #
Cover-Thomas. This file gives a non-circular, operational definition of the capacity of the continuous-time band-limited AWGN channel and states the Shannon-Hartley identity
`contAwgnOperationalCapacity W N₀ P = W · log(1 + P / (N₀ · W))`
as contAwgn_eq_shannonHartley (proved in ConverseFinal.lean).
The converse half lands via the prolate-count domination bandGramReal_high_count_le — it needs
only prolateCount T W c / T → 2W, not the tight Landau-Pollak-Slepian concentration.
IsBandlimited uses the L²-Fourier spectral support of the complexification (a
band-limit constraint, not junk-0). The Paley-Wiener sup bound bandlimited_sup_bound
(|f(t)| ≤ √(2W)·‖f‖₂) is fully proven (sorryAx-free) over the L²↔L¹ Fourier-agreement
bridges l2Fourier_eq_fourierIntegral / l2FourierInv_eq_fourierIntegralInv; it caps pointwise
values by the full-line L² energy ‖f‖₂.
ContAwgnCode models the receiver as a bank of k matched filters: k orthonormal test
functions supported in [0, T], against which the codeword is correlated
(ContAwgnCode.observation) before independent Gaussian noise is added
(ContAwgnCode.errorProbAt). This is the Karhunen-Loève discretization, and orthonormality is
what makes the independent per-observation noise law exact. Reading the codeword pointwise on a
grid instead would be an isometry only at the Nyquist spacing, hence would assume what the
theorem must prove; see docs/shannon/shannon-hartley-facts.md §OBSERVATION-MAP for the
non-circularity argument.
Main definitions #
IsBandlimited f W— the L²-Fourier transform of the complexification off : ℝ → ℝhas spectral support in[-W, W](vanishes a.e. on{ξ | W < |ξ|}).ContAwgnCode T W P M— a continuous-time AWGN code:Mband-limited signals of whole-line energy≤ T·P, observed through a free numberkof orthonormal test functions supported in[0, T], together with a decoder acting on the observation vector.ContAwgnCode.observation— the noiseless correlation∫ (encoder m)·(testFn i).contAwgnOperationalCapacity W N₀ P— the per-second operational rate⨅ ε, limsup_T (log M(T, ε)) / T.
Main statements #
contAwgn_eq_shannonHartley— the operational capacity equals the Shannon-Hartley closed formbandlimitedAwgnCapacity W N₀ P.
Implementation notes — the three honesty risks and how the definition fares #
The definition aims to make contAwgn_eq_shannonHartley true, non-circular, and
non-degenerate.
- Truth. Observations are the correlations
⟨encoder m, testFn i⟩against an orthonormal family supported in[0, T], each corrupted by independent noise of varianceN₀/2. Against an orthonormal family, white-noise coefficients are exactly i.i.d., so no spacing or rate condition is smuggled into the noise law. For band-limitedf,⟨f, φᵢ⟩ = ⟨f, P_W φᵢ⟩, so the signal energy the receiver can see is controlled by the compression of the time-band-limiting operator ontospan{φᵢ}; Bessel caps it by‖f‖₂² ≤ T·Puniformly ink, and Cauchy interlacing caps the per-dimension gains by the prolate eigenvalues. RateW·log(1 + P/(N₀·W))is reached in theT → ∞limit exactly when≈ 2WTof those eigenvalues are near1. - Non-circularity. A codeword is a band-limited function
ℝ → ℝ, never a length-⌊2WT⌋sample vector;contAwgnMaxMessagescontains no2Wor⌊2WT⌋; the observation countkis a freeℕfield, not pinned to⌊2WT⌋; the factor2Wis not in any definition and must emerge from the degrees-of-freedom proof —testFnis asked only for orthonormality and[0, T]support. ConsequentlycontAwgn_eq_shannonHartleycannot be closed byrfl/unfold. - Non-degeneracy. The noise corrupts the signal (variance
N₀/2 > 0wheneverN₀ > 0). Neither oversampling nor undersampling inflates the signal-to-noise ratio: raisingkadds observations but Bessel holds∑ᵢ ⟨f, φᵢ⟩² ≤ ‖f‖₂²uniformly, so extra observations split the same energy budget rather than duplicating it, and the whole-lineencoder_powerleaves no energy outside the window for the reproducing kernel to reflect back in.
References #
- T. M. Cover and J. A. Thomas, Elements of Information Theory (2nd ed.), Wiley, 2006.
§A — Band-limited signals #
InformationTheory.Shannon.ShannonHartley.IsBandlimited
sourceA real signal f : ℝ → ℝ is band-limited to [-W, W] if the L²-Fourier transform of its
complexification has spectral support in [-W, W], i.e. vanishes almost everywhere on
{ξ | W < |ξ|}. The complexification t ↦ (f t : ℂ) is needed because the L² Fourier transform
𝓕 : Lp ℂ 2 volume → Lp ℂ 2 volume is complex-valued.
This is a band-limit constraint: unlike the L¹ Real.fourierIntegral (which is 0
for every non-L¹ signal, hence vacuous — junk-0 — on the entire target class of essentially
time-limited band-limited L² signals), the L² transform is defined on the whole a.e. class and
its support separates band-limited functions from broadband ones.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Used by
InformationTheory.Shannon.ShannonHartley.l2Fourier_eq_fourierIntegral
sourceThe L²-L¹ Fourier-agreement bridge: for f ∈ L¹ ∩ L², the coeFn of the L²-Fourier
transform of the canonical Lp representative of f agrees almost everywhere with the classical
L¹ Fourier integral 𝓕 f (the pointwise VectorFourier.fourierIntegral).
This is the plumbing that connects the abstract L²-Fourier isometry 𝓕 : Lp ℂ 2 → Lp ℂ 2 to the
concrete pointwise integral, over the tempered-distribution scaffolding. Both objects define the
same tempered distribution: the L²-Fourier side via Lp.fourier_toTemperedDistribution_eq, the
L¹ pointwise side via the Fourier self-adjointness (multiplication formula)
VectorFourier.integral_fourierIntegral_smul_eq_flip; equality of tempered distributions on the
locally integrable class forces almost-everywhere equality
(ae_eq_of_integral_contDiff_smul_eq).
@audit:ok
Used by
InformationTheory.Shannon.ShannonHartley.l2FourierInv_eq_fourierIntegralInv
sourceThe L²-L¹ inverse-Fourier-agreement bridge, the inverse-transform sibling of
l2Fourier_eq_fourierIntegral: for f ∈ L¹ ∩ L², the coeFn of the L²-inverse-Fourier transform
of the canonical Lp representative agrees almost everywhere with the classical L¹ inverse
Fourier integral 𝓕⁻ f. Used by bandlimited_sup_bound to realize a band-limited signal as the
inverse transform of its (compactly supported, hence L¹) spectrum.
@audit:ok
Used by
InformationTheory.Shannon.ShannonHartley.bandlimited_sup_bound
sourcePaley-Wiener sup bound: a continuous band-limited L² signal is bounded pointwise by its
L² energy, |f t| ≤ √(2W)·‖f‖₂. Continuity pins the raw codeword to the canonical
representative, and this bound caps the sample values by the codeword energy — dissolving the
pointwise-vs-a.e. defect that made an encoder-only code unbounded.
The proof realizes the signal as the inverse Fourier transform of its (compactly supported, hence
L¹) spectrum via l2FourierInv_eq_fourierIntegralInv, bounds the pointwise inverse transform by
the L¹ norm of the spectrum, and closes with Hölder on [-W, W] and Plancherel.
@audit:ok
Used by
§B — Continuous-time AWGN code #
InformationTheory.Shannon.ShannonHartley.ContAwgnCode
sourceA continuous-time AWGN code over the window [0, T] with bandwidth W, average power
P, and M messages.
The encoder maps each message to a band-limited function ℝ → ℝ (never a fixed
sample vector — this is what keeps the definition non-circular), whose whole-line energy is at most
T · P. The receiver does not read the codeword pointwise; it correlates it against k
orthonormal test functions supported in [0, T], observing the vector
i ↦ ∫ (encoder m)·(testFn i) corrupted by independent Gaussian noise
(ContAwgnCode.observation, ContAwgnCode.errorProbAt). This is the textbook Karhunen-Loève /
matched-filter discretization of the channel: against an orthonormal family the coefficients of
white noise are exactly i.i.d. N(0, N₀/2), which is what makes the product law Measure.pi
in errorProbAt an exact description of the physical channel rather than a surrogate for one.
A point-sampling observation map would be an isometry only at the Nyquist spacing —
i.e. calibrated at exactly the value the Shannon-Hartley identity has to prove; see
docs/shannon/shannon-hartley-facts.md §OBSERVATION-MAP for the non-circularity argument.
The observation count k is a free ℕ field, and no field mentions 2W or
⌊2WT⌋: testFn is asked only to be orthonormal and supported in [0, T], and
the W in encoder_bandlimited is a physical bandwidth, not a dimension count. The ≈ 2WT
degrees-of-freedom count is therefore not available from this definition. It has to come from the
prolate-spheroidal eigenvalue distribution: a band-limited f satisfies ∫ f·φᵢ = ⟪f, P_W φᵢ⟫,
so the Gram matrix of the test family is a compression of the time-band-limiting operator of
TimeBandLimiting.lean, and how many of its eigenvalues sit near 1 is exactly the
Landau-Pollak-Slepian count.
The
Mband-limited codewords, one per message.Each codeword lies in
L²(regularity: together withtestFn_memLpthis makes every observation integral∫ (encoder m)·(testFn i)well-defined, by Cauchy-Schwarz).Each codeword is band-limited to
[-W, W].Average-power constraint: the whole-line energy of each codeword is at most
T · P. The budget is over all ofℝ, not just the window: a band-limited signal cannot be supported in[0, T], and charging it only for the energy it happens to park inside the window leaves the rest free to be reflected back in by the reproducing kernel.The number of observations, a free
ℕparameter not pinned to⌊2WT⌋.The test functions the receiver correlates the codeword against.
Each test function lies in
L²(regularity, paired withencoder_memLp).Each test function is supported in the window
[0, T]: the receiver may listen only while the codeword is being transmitted.- testFn_orthonormal(i j : Fin self.k) : ∫ (t : ℝ), self.testFn i t * self.testFn j t = if i = j then 1 else 0
The test functions are orthonormal. This is the field that makes the coefficients of white noise against them exactly i.i.d., hence
ContAwgnCode.errorProbAt's product law exact. The decoder maps the observation vector back to a message.
The decoder is measurable (needed on the continuous output alphabet).
Instances For
Used by
InformationTheory.Shannon.ShannonHartley.ContAwgnCode.observation
sourceThe noiseless observation of message m along the i-th test function: the correlation
∫ (encoder m)·(testFn i) of the codeword with the matched filter testFn i.
This is the analysis half of the Karhunen-Loève discretization. It depends on encoder m only
through its a.e. class, and is finite because encoder_memLp and testFn_memLp put both factors
in L². Since testFn i is supported in [0, T], the integral only sees the codeword during the
transmission window; since encoder m is band-limited, ∫ f·φᵢ = ⟪f, P_W φᵢ⟫, which is what
routes the degrees-of-freedom question to the spectrum of the time-band-limiting operator.
Instances For
Used by
InformationTheory.Shannon.ShannonHartley.ContAwgnCode.errorProbAt
sourcePoint-wise error probability for message m: the noisy observation vector
y = ContAwgnCode.observation m + noise (per-observation noise variance N₀/2, independent
across observations) lands in the decoding-error region {y | decoder y ≠ m}.
Modeled directly as Measure.pi (fun i => gaussianReal (observationᵢ) (N₀/2)), i.e. the
memoryless per-observation AWGN law — the same law computed by the discrete
ChannelCoding.Code.errorProbAt for awgnChannel (N₀/2), but inlined so that no
IsAwgnChannelMeasurable kernel-measurability hypothesis is needed inside the definition.
The product law is exact here, not an approximation: the noise coefficients are ⟪ξ, φᵢ⟫ for the
orthonormal family testFn, and the coefficients of white noise along an orthonormal family are
i.i.d. N(0, N₀/2) for that family alone — no spacing, rate or bandwidth condition enters. This
is what ContAwgnCode.testFn_orthonormal buys.
Equations
- c.errorProbAt N₀ m = (MeasureTheory.Measure.pi fun (i : Fin c.k) => ProbabilityTheory.gaussianReal (c.observation m i) (N₀ / 2).toNNReal) {y : Fin c.k → ℝ | c.decoder y ≠ m}
Instances For
Used by
InformationTheory.Shannon.ShannonHartley.ContAwgnCode.averageError
sourceAverage error probability under a uniform message: (1/M) ∑ₘ errorProbAt m
(0 for the empty code M = 0).
Equations
- c.averageError N₀ = if M = 0 then 0 else (↑M)⁻¹ * ∑ m : Fin M, c.errorProbAt N₀ m
Instances For
Used by
§C — Operational capacity #
InformationTheory.Shannon.ShannonHartley.contAwgnMaxMessages
sourceThe largest number of messages distinguishable over the window [0, T] with average
error probability at most ε — an operational primitive that contains no 2W or
⌊2WT⌋.
Equations
- InformationTheory.Shannon.ShannonHartley.contAwgnMaxMessages T W N₀ P ε = sSup {M : ℕ | ∃ (c : InformationTheory.Shannon.ShannonHartley.ContAwgnCode T W P M), (c.averageError N₀).toReal ≤ ε}
Instances For
Used by
InformationTheory.Shannon.ShannonHartley.contAwgnRate
sourceThe per-second rate achievable at error level ε: limsup_T (log M(T, ε)) / T.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Used by
InformationTheory.Shannon.ShannonHartley.contAwgnOperationalCapacity
sourceThe operational capacity of the continuous-time band-limited AWGN channel:
the per-second rate in the vanishing-error limit, ⨅_{ε ∈ (0,1)} contAwgnRate W N₀ P ε.
The infimum over ε extracts the ε → 0 capacity; ε is restricted to (0, 1) because
ε ≥ 1 is satisfied by every code (average error is ≤ 1) and would make the message set
unbounded.
The infimum is taken over the subtype ↥(Set.Ioo 0 1), not via the bounded-binder
⨅ ε ∈ Set.Ioo 0 1. The two are not the same for the conditionally-complete order ℝ: the
bounded-binder form unfolds to ⨅ ε, ⨅ (_ : ε ∈ Set.Ioo 0 1), contAwgnRate …, and for every
ε ∉ (0, 1) the inner ⨅ ranges over an empty index, contributing the junk value
sInf ∅ = 0. Since contAwgnRate ≥ 0, that phantom 0 collapses the whole infimum to 0,
making both contAwgn_ge_shannonHartley and contAwgn_eq_shannonHartley false as framed for
P > 0. The subtype infimum ranges only over (0, 1) and carries no phantom.
Equations
- InformationTheory.Shannon.ShannonHartley.contAwgnOperationalCapacity W N₀ P = ⨅ (ε : ↑(Set.Ioo 0 1)), InformationTheory.Shannon.ShannonHartley.contAwgnRate W N₀ P ↑ε