InformationTheory

InformationTheory.Shannon.ShannonHartley.Main

source

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 family h (real representatives of a -orthonormal basis u of V = 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 shape exists_crossMap_lower_bound consumes.

  • exists_crossMap_lower_bound — the cross-map A (with (A v)ᵢ = ∫ (∑ⱼ vⱼ hⱼ)·φᵢ) is bounded below by √c: c ∑ᵢ vᵢ² ≤ ∑ᵢ (A v)ᵢ². This is exactly the hbdd hypothesis of exists_preequalizer once A is packaged as an endomorphism of EuclideanSpace ℝ (Fin k) (‖v‖² = ∑ᵢ vᵢ², ‖A v‖² = ∑ᵢ (A v)ᵢ²). The bound comes from the energy identity plus the time-window energy concentration le_norm_timeLimitProj_sq_of_mem.

theorem

InformationTheory.Shannon.ShannonHartley.exists_testFn_family

source
(T W : ) {c : } (hc : 0 < c) :
∃ (u : Fin (TimeBandLimiting.prolateCount T W c)TimeBandLimiting.E) (h : Fin (TimeBandLimiting.prolateCount T W c)) (φ : Fin (TimeBandLimiting.prolateCount T W c)), Orthonormal u (∀ (i : Fin (TimeBandLimiting.prolateCount T W c)), u i TimeBandLimiting.prolateEigenspaceSup T W c) (∀ (i : Fin (TimeBandLimiting.prolateCount T W c)), MeasureTheory.MemLp (h i) 2 MeasureTheory.volume) (∀ (i : Fin (TimeBandLimiting.prolateCount T W c)), (fun (t : ) => (h i t)) =ᵐ[MeasureTheory.volume] (u i)) (∀ (i : Fin (TimeBandLimiting.prolateCount T W c)), IsBandlimited (h i) W) (∀ (i j : Fin (TimeBandLimiting.prolateCount T W c)), (t : ), h i t * h j t = if i = j then 1 else 0) (∀ (i : Fin (TimeBandLimiting.prolateCount T W c)), Function.support (φ i) Set.Icc 0 T) (∀ (i : Fin (TimeBandLimiting.prolateCount T W c)), MeasureTheory.MemLp (φ i) 2 MeasureTheory.volume) (∀ (i j : Fin (TimeBandLimiting.prolateCount T W c)), (t : ), φ i t * φ j t = if i = j then 1 else 0) ∀ (v : Fin (TimeBandLimiting.prolateCount T W c)), i : Fin (TimeBandLimiting.prolateCount T W c), ( (t : ), (∑ j : Fin (TimeBandLimiting.prolateCount T W c), v j * h j t) * φ i t) ^ 2 = (TimeBandLimiting.timeLimitSubspace T).starProjection (∑ j : Fin (TimeBandLimiting.prolateCount T W c), (v j) u j) ^ 2

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

    InformationTheory.Shannon.ShannonHartley.exists_crossMap_lower_bound

    source
    (T W : ) {c : } (hc : 0 < c) :
    ∃ (h : Fin (TimeBandLimiting.prolateCount T W c)) (φ : Fin (TimeBandLimiting.prolateCount T W c)), (∀ (i : Fin (TimeBandLimiting.prolateCount T W c)), MeasureTheory.MemLp (h i) 2 MeasureTheory.volume) (∀ (i : Fin (TimeBandLimiting.prolateCount T W c)), IsBandlimited (h i) W) (∀ (i j : Fin (TimeBandLimiting.prolateCount T W c)), (t : ), h i t * h j t = if i = j then 1 else 0) (∀ (i : Fin (TimeBandLimiting.prolateCount T W c)), Function.support (φ i) Set.Icc 0 T) (∀ (i : Fin (TimeBandLimiting.prolateCount T W c)), MeasureTheory.MemLp (φ i) 2 MeasureTheory.volume) (∀ (i j : Fin (TimeBandLimiting.prolateCount T W c)), (t : ), φ i t * φ j t = if i = j then 1 else 0) ∀ (v : Fin (TimeBandLimiting.prolateCount T W c)), c * i : Fin (TimeBandLimiting.prolateCount T W c), v i ^ 2 i : Fin (TimeBandLimiting.prolateCount T W c), ( (t : ), (∑ j : Fin (TimeBandLimiting.prolateCount T W c), v j * h j t) * φ i t) ^ 2

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

      theorem

      InformationTheory.Shannon.ShannonHartley.contAwgnMaxMessages_ge_of_awgnCode

      source
      (T W N₀ P : ) (hT : 0 < T) (hW : 0 < W) (hN₀ : 0 < N₀) (hP : 0 P) {c : } (hc0 : 0 < c) (hc1 : c < 1) {ε : } (hε0 : 0 < ε) (hε1 : ε < 1) (hkpos : 0 < TimeBandLimiting.prolateCount T W c) {M : } (d : AWGN.AwgnCode M (TimeBandLimiting.prolateCount T W c) (c * T * P / (TimeBandLimiting.prolateCount T W c))) (hd : ∀ (m : Fin M), (d.toCode.errorProbAt (AWGN.awgnChannel (N₀ / 2).toNNReal ) m).toReal < ε) :
      M contAwgnMaxMessages T W N₀ P ε

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

        theorem

        InformationTheory.Shannon.ShannonHartley.deficit_div_tendsto_zero

        source
        (W : ) (hW : 0 < W) :
        Filter.Tendsto (fun (T : ) => (2 + Real.log (1 + 2 * W * T)) / T) Filter.atTop (nhds 0)
        Used by
          theorem

          InformationTheory.Shannon.ShannonHartley.prolateCount_div_tendsto

          source
          (W : ) (hW : 0 < W) {c : } (hc0 : 0 < c) (hc1 : c < 1) :
          Used by
            theorem

            InformationTheory.Shannon.ShannonHartley.contAwgnRate_isBoundedUnder

            source
            (W N₀ P ε : ) (hW : 0 < W) (hN₀ : 0 < N₀) (hP : 0 P) (hε0 : 0 < ε) (hε1 : ε < 1) :
            Filter.IsBoundedUnder (fun (x1 x2 : ) => x1 x2) Filter.atTop fun (T : ) => Real.log (contAwgnMaxMessages T W N₀ P ε) / T

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

              InformationTheory.Shannon.ShannonHartley.contAwgnRate_nonneg

              source
              (W N₀ P ε : ) (hW : 0 < W) (hN₀ : 0 < N₀) (hP : 0 P) (hε0 : 0 < ε) (hε1 : ε < 1) :
              0 contAwgnRate W N₀ P ε

              The per-ε rate is nonnegative: contAwgnMaxMessages is a , so its log is ≥ 0.

              Used by
                theorem

                InformationTheory.Shannon.ShannonHartley.exists_params_of_lt

                source
                (W N₀ P y : ) (hW : 0 < W) (hN₀ : 0 < N₀) (hP0 : 0 < P) (hy : y < W * Real.log (1 + P / (N₀ * W))) :
                ∃ (c : ) (Q : ) (R : ), 0 < c c < 1 0 < Q Q < c * P / (2 * W) 0 < R R < 1 / 2 * Real.log (1 + 2 * Q / N₀) y < 2 * W * R
                Used by
                  theorem

                  InformationTheory.Shannon.ShannonHartley.sh_le_contAwgnRate

                  source
                  (W N₀ P ε : ) (hW : 0 < W) (hN₀ : 0 < N₀) (hP : 0 P) (hε0 : 0 < ε) (hε1 : ε < 1) :

                  The core per-ε achievability step: the closed form is below the operational rate at level ε. @audit:ok

                  Used by
                    theorem

                    InformationTheory.Shannon.ShannonHartley.contAwgn_ge_shannonHartley

                    source
                    (W N₀ P : ) (hW : 0 < W) (hN₀ : 0 < N₀) (hP : 0 P) :

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

                    Used by