InformationTheory.Shannon.ShannonHartley.Achievability
Continuous-time Shannon-Hartley: achievability (Cover-Thomas) #
The ≥ half of the operational Shannon-Hartley sandwich,
`bandlimitedAwgnCapacity W N₀ P ≤ contAwgnOperationalCapacity W N₀ P`
(contAwgn_ge_shannonHartley), together with the boundedness obligation
contAwgnMaxMessages_bddAbove that the operational sSup needs in order not to collapse to
junk-0.
The two have different characters, and the split is the point. Boundedness holds
unconditionally: Bessel's inequality against the orthonormal ContAwgnCode.testFn caps the
observed energy by T·P uniformly in the observation count, which is enough for BddAbove but
only enough for the crude rate P/N₀. Achievability at the exact constant needs more: the
≈ 2WT degrees-of-freedom count — the time–band-limiting operator's eigenvalue concentration
(Landau–Pollak–Slepian) — because the test family must recover near-unit gain on ≈ 2WT
dimensions. See the two declarations for detail.
The synthesis bridge #
synthSignal T n a reconstructs a band-limited signal interpolating the sample values
a : Fin n → ℝ at the grid t_i = i·(T/n); it is how the band-limited codewords of a
ContAwgnCode get built from a discrete awgn_achievability codebook. Its three properties power
the reduction:
- interpolation exactness —
synthSignal T n a (j·(T/n)) = a j(synthSignal_sample). - band-limitedness —
IsBandlimited (synthSignal T n a) Wwhenn ≤ 2WT(synthSignal_bandlimited): each shiftedsincN(·/Δ)has spectrum supported in[-1/(2Δ), 1/(2Δ)] = [-n/(2T), n/(2T)] ⊆ [-W, W]. - Parseval energy —
∫ t, (synthSignal T n a t)² = (T/n)·∑ᵢ (a i)²(synthSignal_energy), an equality on the whole line, which is exactly the shapeContAwgnCode.encoder_powerasks for: witha = √(n/T)·cit reads∑ᵢ cᵢ² ≤ T·P.
References #
- T. M. Cover and J. A. Thomas, Elements of Information Theory (2nd ed.), Wiley, 2006. (achievability).
§A — Sinc synthesis #
InformationTheory.Shannon.ShannonHartley.synthSignal
sourceSinc synthesis at grid spacing Δ = T/n: the band-limited signal interpolating the
sample values a : Fin n → ℝ at the nodes t_i = i·(T/n). This is the synthesis
direction (build a band-limited function from finitely many samples), dual to the
analysis direction of whittaker_shannon_bandlimited.
Equations
- InformationTheory.Shannon.ShannonHartley.synthSignal T n a t = ∑ i : Fin n, a i * InformationTheory.Shannon.NormalizedSinc.sincN ((t - ↑↑i * (T / ↑n)) / (T / ↑n))
Instances For
Used by
InformationTheory.Shannon.ShannonHartley.sincN_natCast_sub
sourcesincN of a difference of natural-number casts is the Kronecker delta.
Used by
§B — interpolation exactness #
InformationTheory.Shannon.ShannonHartley.synthSignal_sample
sourceAt a sample node t = j·(T/n), the sinc synthesis recovers the sample value exactly:
all sinc cross-terms vanish (sincN at nonzero integers is 0).
Used by
§B2 — Sinc/boxcar L²-Fourier atom #
The workhorse of the whole reduction. A single shifted, dilated normalized sinc
t ↦ sincN((t - c)/Δ) is the inverse Fourier transform of the spectral boxcar
Δ · e^{-2πi c ξ} · 𝟙_{[-1/(2Δ), 1/(2Δ)]}. Because the boxcar is compactly supported
(hence L¹ ∩ L²), the inverse Fourier-agreement bridge
l2FourierInv_eq_fourierIntegralInv transfers this pointwise identity to the abstract
L²-Fourier isometry, giving both the L² membership of the sinc and the explicit
L²-Fourier transform. Everything else (band-limitedness, energy) is finite linearity.
InformationTheory.Shannon.ShannonHartley.specBoxcar
sourceThe spectral boxcar Δ · e^{-2πi c ξ} supported on [-1/(2Δ), 1/(2Δ)]. This is the
L²-Fourier transform of the shifted, dilated normalized sinc t ↦ sincN((t - c)/Δ).
Equations
Instances For
Used by
InformationTheory.Shannon.ShannonHartley.exp_dilate_interval_integral
sourceDilated boxcar integral: rescaling the fundamental-interval identity
integral_exp_boxcar_eq_sincN to the band [-1/(2Δ), 1/(2Δ)].
Used by
InformationTheory.Shannon.ShannonHartley.specBoxcar_memLp
sourceThe spectral boxcar lies in every Lᵖ: it is bounded by Δ on a compact set.
Used by
InformationTheory.Shannon.ShannonHartley.fourierInv_specBoxcar
sourcePointwise inverse Fourier transform of the spectral boxcar is the shifted, dilated sinc.
Used by
InformationTheory.Shannon.ShannonHartley.shiftSinc_memLp
sourceThe complexified shifted, dilated sinc lies in L² (it is the inverse transform of an
L¹ ∩ L² boxcar).
Used by
InformationTheory.Shannon.ShannonHartley.fourier_shiftSinc_toLp
sourceThe abstract L²-Fourier transform of the sinc's canonical Lp representative is the
boxcar's canonical Lp representative.
Used by
InformationTheory.Shannon.ShannonHartley.inner_specBoxcar_toLp
sourceBoxcar orthogonality (Plancherel on the band): the L² inner product of two spectral
boxcars collapses to Δ · sincN((c - c')/Δ).
Used by
InformationTheory.Shannon.ShannonHartley.synthSignal_complex_memLp
sourceThe complexified synthesis lies in L² (a finite sum of L² shifted sincs).
Used by
InformationTheory.Shannon.ShannonHartley.synthSignal_toLp_eq_sum
sourceThe synthesis's canonical Lp representative decomposes as the finite Lp combination
∑ᵢ aᵢ • (shifted sinc)ᵢ.
Used by
§C — band-limitedness #
InformationTheory.Shannon.ShannonHartley.synthSignal_bandlimited
sourceThe sinc synthesis is band-limited to [-W, W] provided the sample count satisfies the
Nyquist bound n ≤ 2WT: each shifted sincN(·/Δ) (spacing Δ = T/n) has spectrum supported
in [-1/(2Δ), 1/(2Δ)] = [-n/(2T), n/(2T)], and n/(2T) ≤ W.
@audit:ok
Used by
§D — (iii) Parseval energy #
InformationTheory.Shannon.ShannonHartley.synthSignal_sq_integrable
sourceThe squared synthesis is integrable on the whole line (it lies in L²).
@audit:ok
Used by
InformationTheory.Shannon.ShannonHartley.synthSignal_energy
sourceParseval / sinc self-reproducing energy identity: the whole-line energy of the sinc
synthesis equals Δ · ∑ᵢ (a i)² with Δ = T/n. Follows from the sinc orthogonality
∫ sincN((t-iΔ)/Δ)·sincN((t-jΔ)/Δ) dt = Δ·δᵢⱼ.
@audit:ok
Used by
§E — boundedness of the message set #
InformationTheory.Shannon.ShannonHartley.contAwgn_log_le_of_pos_k
sourceThe crude rate bound via Bessel's inequality alone, for codes with at least one observation:
log M is capped by (T·P + 1)/N₀ plus the Fano terms, uniformly in the observation count
k. This is where Bessel meets awgn_converse, and where ln(1+x) ≤ x discards the
k-dependence.
Used by
InformationTheory.Shannon.ShannonHartley.contAwgn_averageError_of_k_eq_zero
sourceWith no observations at all the receiver learns nothing: every message is decoded to the same
one, so the average error is exactly (M-1)/M.
Used by
InformationTheory.Shannon.ShannonHartley.contAwgnMaxMessages_bddAbove
sourceThe message-count set is bounded above — the BddAbove obligation needed to lower-bound
contAwgnMaxMessages via le_csSup.
It closes by Bessel's inequality alone, without the ≈ 2WT degrees-of-freedom count. The test
family testFn is orthonormal, so for every codeword
`∑ᵢ (observation m i)² = ∑ᵢ ⟨encoder m, testFn i⟩² ≤ ‖encoder m‖₂² ≤ T·P`,
uniformly in the observation count k — no spacing, rate or bandwidth hypothesis enters, and the
whole-line encoder_power supplies the right-hand side directly. That energy bound feeds
awgn_converse on the induced discrete code contAwgnToAwgnCode (per-observation power
P' = (T·P + 1)/k, whose power_constraint holds by construction; the +1 keeps it strictly
positive when P = 0), and log(1+x) ≤ x collapses the k-dependence:
`(k/2)·log(1 + 2(T·P+1)/(k·N₀)) ≤ (T·P+1)/N₀`.
Rearranging the Fano terms against ε < 1 gives log M ≤ ((T·P+1)/N₀ + log 2)/(1-ε), a bound
free of k, so the message set is capped. Two degenerate branches sit outside that argument and
are handled separately: M < 2 (below the converse's range) and k = 0, where the receiver
observes nothing, every message decodes to the same one, the average error is exactly (M-1)/M,
and ε < 1 alone caps M ≤ 1/(1-ε).
That the bandwidth constraint is unused here is the point rather than an oversight: hW is the
only hypothesis the proof never touches, and it is retained solely to keep the signature uniform
with the rest of the sandwich (W itself still appears, via ContAwgnCode T W P M). The proof in
fact reads neither encoder_bandlimited nor testFn_support: orthonormality of testFn plus the
whole-line encoder_power are the only structure fields the bound needs.
This bound is deliberately crude, and its crudeness is load-bearing evidence rather than a
shortcoming: it caps the rate at P/N₀, which ln(1+x) ≤ x makes strictly larger than
bandlimitedAwgnCapacity W N₀ P. Boundedness is free; the exact constant is not, and it is the
part that still needs the prolate eigenvalue count (see contAwgn_eq_shannonHartley).
Hypotheses are regularity-only (not load-bearing).
@audit:ok