InformationTheory

InformationTheory.Shannon.ShannonHartley.Operational

source

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 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 of f : ℝ → ℝ has spectral support in [-W, W] (vanishes a.e. on {ξ | W < |ξ|}).
  • ContAwgnCode T W P M — a continuous-time AWGN code: M band-limited signals of whole-line energy ≤ T·P, observed through a free number k of 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 form bandlimitedAwgnCapacity 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 variance N₀/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-limited f, ⟨f, φᵢ⟩ = ⟨f, P_W φᵢ⟩, so the signal energy the receiver can see is controlled by the compression of the time-band-limiting operator onto span{φᵢ}; Bessel caps it by ‖f‖₂² ≤ T·P uniformly in k, and Cauchy interlacing caps the per-dimension gains by the prolate eigenvalues. Rate W·log(1 + P/(N₀·W)) is reached in the T → ∞ limit exactly when ≈ 2WT of those eigenvalues are near 1.
  • Non-circularity. A codeword is a band-limited function ℝ → ℝ, never a length-⌊2WT⌋ sample vector; contAwgnMaxMessages contains no 2W or ⌊2WT⌋; the observation count k is a free field, not pinned to ⌊2WT⌋; the factor 2W is not in any definition and must emerge from the degrees-of-freedom proof — testFn is asked only for orthonormality and [0, T] support. Consequently contAwgn_eq_shannonHartley cannot be closed by rfl/unfold.
  • Non-degeneracy. The noise corrupts the signal (variance N₀/2 > 0 whenever N₀ > 0). Neither oversampling nor undersampling inflates the signal-to-noise ratio: raising k adds observations but Bessel holds ∑ᵢ ⟨f, φᵢ⟩² ≤ ‖f‖₂² uniformly, so extra observations split the same energy budget rather than duplicating it, and the whole-line encoder_power leaves 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 #

def

InformationTheory.Shannon.ShannonHartley.IsBandlimited

source
(f : ) (W : ) :

A 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
      theorem

      InformationTheory.Shannon.ShannonHartley.l2Fourier_eq_fourierIntegral

      source

      The - Fourier-agreement bridge: for f ∈ L¹ ∩ L², the coeFn of the -Fourier transform of the canonical Lp representative of f agrees almost everywhere with the classical Fourier integral 𝓕 f (the pointwise VectorFourier.fourierIntegral).

      This is the plumbing that connects the abstract -Fourier isometry 𝓕 : Lp ℂ 2 → Lp ℂ 2 to the concrete pointwise integral, over the tempered-distribution scaffolding. Both objects define the same tempered distribution: the -Fourier side via Lp.fourier_toTemperedDistribution_eq, the 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
        theorem

        InformationTheory.Shannon.ShannonHartley.l2FourierInv_eq_fourierIntegralInv

        source

        The - inverse-Fourier-agreement bridge, the inverse-transform sibling of l2Fourier_eq_fourierIntegral: for f ∈ L¹ ∩ L², the coeFn of the -inverse-Fourier transform of the canonical Lp representative agrees almost everywhere with the classical inverse Fourier integral 𝓕⁻ f. Used by bandlimited_sup_bound to realize a band-limited signal as the inverse transform of its (compactly supported, hence ) spectrum.

        @audit:ok

        Used by
          theorem

          InformationTheory.Shannon.ShannonHartley.bandlimited_sup_bound

          source
          (f : ) (W : ) (hW : 0 < W) (hf : MeasureTheory.MemLp f 2 MeasureTheory.volume) (hbl : IsBandlimited f W) (hcont : Continuous f) (t : ) :

          Paley-Wiener sup bound: a continuous band-limited signal is bounded pointwise by its 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 ) spectrum via l2FourierInv_eq_fourierIntegralInv, bounds the pointwise inverse transform by the norm of the spectrum, and closes with Hölder on [-W, W] and Plancherel.

          @audit:ok

          Used by

            §B — Continuous-time AWGN code #

            structure

            InformationTheory.Shannon.ShannonHartley.ContAwgnCode

            source
            (T W P : ) (M : ) :

            A 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.

            • encoder : Fin M

              The M band-limited codewords, one per message.

            • encoder_memLp(m : Fin M) : MeasureTheory.MemLp (self.encoder m) 2 MeasureTheory.volume

              Each codeword lies in (regularity: together with testFn_memLp this makes every observation integral ∫ (encoder m)·(testFn i) well-defined, by Cauchy-Schwarz).

            • encoder_bandlimited(m : Fin M) : IsBandlimited (self.encoder m) W

              Each codeword is band-limited to [-W, W].

            • encoder_power(m : Fin M) : (t : ), self.encoder m t ^ 2 T * P

              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.

            • k :

              The number of observations, a free parameter not pinned to ⌊2WT⌋.

            • testFn : Fin self.k

              The test functions the receiver correlates the codeword against.

            • testFn_memLp(i : Fin self.k) : MeasureTheory.MemLp (self.testFn i) 2 MeasureTheory.volume

              Each test function lies in (regularity, paired with encoder_memLp).

            • testFn_support(i : Fin self.k) : Function.support (self.testFn i) Set.Icc 0 T

              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.

            • decoder : (Fin self.k)Fin M

              The decoder maps the observation vector back to a message.

            • decoder_meas : Measurable self.decoder

              The decoder is measurable (needed on the continuous output alphabet).

            Instances For
              Used by
                noncomputable def

                InformationTheory.Shannon.ShannonHartley.ContAwgnCode.observation

                source
                {T W P : } {M : } (c : ContAwgnCode T W P M) (m : Fin M) (i : Fin c.k) :

                The 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 . 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.

                Equations
                Instances For
                  Used by
                    noncomputable def

                    InformationTheory.Shannon.ShannonHartley.ContAwgnCode.errorProbAt

                    source
                    {T W P : } {M : } (c : ContAwgnCode T W P M) (N₀ : ) (m : Fin M) :

                    Point-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
                    Instances For
                      Used by
                        noncomputable def

                        InformationTheory.Shannon.ShannonHartley.ContAwgnCode.averageError

                        source
                        {T W P : } {M : } (c : ContAwgnCode T W P M) (N₀ : ) :

                        Average error probability under a uniform message: (1/M) ∑ₘ errorProbAt m (0 for the empty code M = 0).

                        Equations
                        Instances For
                          Used by

                            §C — Operational capacity #

                            noncomputable def

                            InformationTheory.Shannon.ShannonHartley.contAwgnMaxMessages

                            source
                            (T W N₀ P ε : ) :

                            The 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
                            Instances For
                              Used by
                                noncomputable def

                                InformationTheory.Shannon.ShannonHartley.contAwgnRate

                                source
                                (W N₀ P ε : ) :

                                The 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
                                    noncomputable def

                                    InformationTheory.Shannon.ShannonHartley.contAwgnOperationalCapacity

                                    source
                                    (W N₀ P : ) :

                                    The 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
                                    Instances For
                                      Used by