InformationTheory.Shannon.ShannonHartley.Main
Continuous-time Shannon-Hartley: headline theorems #
This file holds the achievability half contAwgn_ge_shannonHartley (≥) of the continuous-time
band-limited AWGN channel — at a position downstream of the achievability assets it must consume.
It rests on the prolate-eigenvalue count (le_prolateCount / prolateCount_le) of
TimeBandLimiting.lean, whose assets are visible only below the achievability and operational
modules, so the theorem lives here rather than at its original upstream site.
The achievability half (contAwgn_ge_shannonHartley) needs only the lower count
le_prolateCount (via prolateCount_div_tendsto) fed through the block
awgn_channel_coding_theorem, not the tight Landau-Pollak-Slepian concentration. The converse
(≤) half and the identity contAwgn_eq_shannonHartley (=) live downstream in
ConverseFinal.lean, which bundles the water-filling (Waterfill.lean)
and Gaussian rotation / band-Gram ellipsoid (Rotation.lean) layers.
Both halves are stated over the phantom-free contAwgnOperationalCapacity (the subtype infimum
⨅ ε : ↥(Set.Ioo 0 1)); the earlier bounded-binder ⨅ ε ∈ Set.Ioo 0 1 collapsed to 0 on the
conditionally-complete ℝ and made both false as framed (see contAwgnOperationalCapacity).
References #
- T. M. Cover and J. A. Thomas, Elements of Information Theory (2nd ed.), Wiley, 2006.
Foundational lemmas for continuous-time achievability #
The achievability argument builds continuous-time codewords as band-limited signals and reads
them off through [0, T]-supported orthonormal test functions. This section supplies the two
supporting lemmas feeding the pre-equalizer (ShannonHartleyPreequalizer.exists_preequalizer):
exists_testFn_family— a receiver test-function familyφsupported in[0, T], paired with the band-limited encoder familyh(real representatives of aℂ-orthonormal basisuofV = prolateEigenspaceSup T W c). The two families are tied by the cross-map energy identity: the receiver's recovered energy∑ᵢ ⟨∑ⱼ vⱼ hⱼ, φᵢ⟩²equals the time-limited energy‖Q_T (∑ⱼ vⱼ uⱼ)‖². That identity is the shapeexists_crossMap_lower_boundconsumes.exists_crossMap_lower_bound— the cross-mapA(with(A v)ᵢ = ∫ (∑ⱼ vⱼ hⱼ)·φᵢ) is bounded below by√c:c ∑ᵢ vᵢ² ≤ ∑ᵢ (A v)ᵢ². This is exactly thehbddhypothesis ofexists_preequalizeronceAis packaged as an endomorphism ofEuclideanSpace ℝ (Fin k)(‖v‖² = ∑ᵢ vᵢ²,‖A v‖² = ∑ᵢ (A v)ᵢ²). The bound comes from the energy identity plus the time-window energy concentrationle_norm_timeLimitProj_sq_of_mem.
InformationTheory.Shannon.ShannonHartley.exists_testFn_family
sourceFor V = prolateEigenspaceSup T W c (0 < c), there is a ℂ-orthonormal basis u of V
together with a band-limited real encoder family h (real representatives of u) and a receiver
test-function family φ, [0, T]-supported and pointwise-orthonormal, such that for every
coefficient vector v : Fin (prolateCount T W c) → ℝ the receiver's recovered energy equals the
time-limited energy of the corresponding V-combination:
∑ᵢ (∫ (∑ⱼ vⱼ hⱼ)·φᵢ)² = ‖Q_T (∑ⱼ vⱼ uⱼ)‖², with Q_T = (timeLimitSubspace T).starProjection.
The φ family is the [0, T]-supported real orthonormal basis of S = span_ℝ {Q_T uⱼ}; the
energy identity holds because the time-limited encoders Q_T uⱼ span S, so the receiver recovers
the full time-limited energy of any V-combination.
@audit:ok
Used by
InformationTheory.Shannon.ShannonHartley.exists_crossMap_lower_bound
sourceThe cross-map A v = (∫ (∑ⱼ vⱼ hⱼ)·φᵢ)ᵢ sending encoder coefficients to receiver observations
is bounded below by √c: c ∑ᵢ vᵢ² ≤ ∑ᵢ (A v)ᵢ². This is the hbdd input to
ShannonHartleyPreequalizer.exists_preequalizer (once A is read as an endomorphism of
EuclideanSpace ℝ (Fin (prolateCount T W c)), where ‖v‖² = ∑ᵢ vᵢ² and ‖A v‖² = ∑ᵢ (A v)ᵢ²),
which then yields the norm-controlled pre-equalizer ‖a‖² ≤ (1/c) ‖x‖².
The bound is the energy identity of exists_testFn_family composed with the time-window energy
concentration le_norm_timeLimitProj_sq_of_mem (c ‖w‖² ≤ ‖Q_T w‖² on V) and
‖∑ⱼ vⱼ uⱼ‖² = ∑ⱼ vⱼ² (u is ℂ-orthonormal, v real).
@audit:ok
Used by
Assembly: lifting a discrete AWGN code to a continuous-time code #
Given a discrete AwgnCode on k = prolateCount T W c observations at per-observation power
c·T·P/k, we synthesize a ContAwgnCode whose observations reproduce the discrete codewords
exactly, transport the error probability, and read off a lower bound on contAwgnMaxMessages
via le_csSup. The three foundational leaves feeding it are: memLp_sum_smul (L²-membership of a
finite real combination of the band-limited encoders), isBandlimited_sum_smul (band-limitedness
of that combination), and integral_sum_smul_sq_eq (its whole-line energy is the coefficient
ℓ²-norm).
InformationTheory.Shannon.ShannonHartley.contAwgnMaxMessages_ge_of_awgnCode
sourceA discrete AWGN code on prolateCount T W c observations lifts to a continuous-time
code, giving a lower bound on contAwgnMaxMessages.
Given a discrete AwgnCode on k = prolateCount T W c observations at per-observation power
c·T·P/k whose every message decodes with error < ε, the receiver cross-map A of
exists_crossMap_lower_bound (bounded below by √c) is invertible with norm control
(exists_preequalizer), so each discrete codeword xₘ has a band-limited pre-image bₘ. The
signals ∑ⱼ (bₘ)ⱼ hⱼ are then band-limited codewords of a ContAwgnCode whose observations equal
xₘ exactly; the error probability transports unchanged, and le_csSup (via the wall-free
contAwgnMaxMessages_bddAbove) turns the discrete message count into the lower bound.
@audit:ok
Used by
Assembly: the achievability half contAwgn_ge_shannonHartley #
The lower bound bandlimitedAwgnCapacity ≤ contAwgnOperationalCapacity reduces, over the
phantom-free ⨅ ε : ↥(Set.Ioo 0 1) (le_ciInf), to a per-ε statement
bandlimitedAwgnCapacity ≤ contAwgnRate ε. For P > 0 that is proved by a
le_of_forall_lt argument: for y below the closed form pick a threshold c ∈ (0,1), a
per-observation power Q, and a block rate R with y < 2WR and R < ½ log(1 + 2Q/N₀)
(exists_params_of_lt), feed Q, R to the discrete awgn_channel_coding_theorem, and lift the
resulting codes to continuous-time codes on prolateCount T W c observations
(contAwgnMaxMessages_ge_of_awgnCode). Since prolateCount T W c / T → 2W
(prolateCount_div_tendsto, from the le_prolateCount / prolateCount_le sandwich), the
per-window rate ⌈exp(kR)⌉-count gives 2WR ≤ limsup_T log(M(T))/T = contAwgnRate ε.
InformationTheory.Shannon.ShannonHartley.deficit_div_tendsto_zero
sourceUsed by
InformationTheory.Shannon.ShannonHartley.prolateCount_div_tendsto
sourceUsed by
InformationTheory.Shannon.ShannonHartley.contAwgnRate_isBoundedUnder
sourceThe per-window rate log(contAwgnMaxMessages T)/T is bounded above (the operational
capacity is finite): from the Bessel converse the message count grows no faster than
exp(T·P/(N₀(1-ε))), so the rate is capped near P/(N₀(1-ε)).
Used by
InformationTheory.Shannon.ShannonHartley.contAwgnRate_nonneg
sourceThe per-ε rate is nonnegative: contAwgnMaxMessages is a ℕ, so its log is ≥ 0.
Used by
InformationTheory.Shannon.ShannonHartley.exists_params_of_lt
sourceUsed by
InformationTheory.Shannon.ShannonHartley.sh_le_contAwgnRate
sourceThe core per-ε achievability step: the closed form is below the operational rate at level
ε.
@audit:ok
Used by
InformationTheory.Shannon.ShannonHartley.contAwgn_ge_shannonHartley
sourceThe operational capacity is at least the Shannon-Hartley closed form (achievability, ≥).
The infimum over ε reduces (via le_ciInf over the phantom-free subtype ↥(Set.Ioo 0 1)) to
the per-ε bound sh_le_contAwgnRate, which builds continuous-time band-limited codewords out of
a discrete AwgnCode on prolateCount T W c observations (contAwgnMaxMessages_ge_of_awgnCode)
fed by the block awgn_channel_coding_theorem, and reads off the ≈ 2WT degrees-of-freedom count
prolateCount_div_tendsto (from le_prolateCount / prolateCount_le) through a limsup
comparison.
The achievability half needs only that prolateCount T W c / T converges to 2W (the crude
two-sided count), not the tight Landau-Pollak-Slepian concentration. The infimum is taken over the
phantom-free subtype ↥(Set.Ioo 0 1): the bounded binder ⨅ ε ∈ Set.Ioo 0 1 would instead pick
up the phantom sInf ∅ = 0 from every ε ∉ (0,1) on the conditionally-complete ℝ, collapsing
the capacity to 0.
Hypotheses hW/hN₀/hP are regularity-only (not load-bearing).
@audit:ok (sorryAx-free; signature scan regularity-only, no load-bearing hyp. The block
awgn_channel_coding_theorem's only non-rate hypothesis h_meas is discharged by the theorem
AWGN.isAwgnChannelMeasurable N, not leaked into this signature; the load-bearing
awgn_capacity_closed_form (h_bridge_gauss/h_bdd/h_max_ent) is off-path — 0 transitive
references from this headline.)