InformationTheory

InformationTheory.Shannon.ShannonHartley.Achievability

source

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) W when n ≤ 2WT (synthSignal_bandlimited): each shifted sincN(·/Δ) 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 shape ContAwgnCode.encoder_power asks for: with a = √(n/T)·c it reads ∑ᵢ cᵢ² ≤ T·P.

References #

  • T. M. Cover and J. A. Thomas, Elements of Information Theory (2nd ed.), Wiley, 2006. (achievability).

§A — Sinc synthesis #

noncomputable def

InformationTheory.Shannon.ShannonHartley.synthSignal

source
(T : ) (n : ) (a : Fin n) :

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

      InformationTheory.Shannon.ShannonHartley.sincN_natCast_sub

      source
      (p q : ) :
      NormalizedSinc.sincN (p - q) = if p = q then 1 else 0

      sincN of a difference of natural-number casts is the Kronecker delta.

      Used by

        §B — interpolation exactness #

        theorem

        InformationTheory.Shannon.ShannonHartley.synthSignal_sample

        source
        (T : ) (n : ) (a : Fin n) (hT : 0 < T) (hn : 0 < n) (j : Fin n) :
        synthSignal T n a (j * (T / n)) = a j

        At 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 -Fourier isometry, giving both the membership of the sinc and the explicit -Fourier transform. Everything else (band-limitedness, energy) is finite linearity.

          noncomputable def

          InformationTheory.Shannon.ShannonHartley.specBoxcar

          source
          (c Δ : ) :

          The spectral boxcar Δ · e^{-2πi c ξ} supported on [-1/(2Δ), 1/(2Δ)]. This is the -Fourier transform of the shifted, dilated normalized sinc t ↦ sincN((t - c)/Δ).

          Equations
          Instances For
            Used by
              theorem

              InformationTheory.Shannon.ShannonHartley.exp_dilate_interval_integral

              source
              (Δ u : ) ( : 0 < Δ) :
              (ξ : ) in -(1 / (2 * Δ))..1 / (2 * Δ), Complex.exp (↑(2 * Real.pi * u * ξ) * Complex.I) = (↑Δ)⁻¹ * (NormalizedSinc.sincN (u / Δ))

              Dilated boxcar integral: rescaling the fundamental-interval identity integral_exp_boxcar_eq_sincN to the band [-1/(2Δ), 1/(2Δ)].

              Used by
                theorem

                InformationTheory.Shannon.ShannonHartley.specBoxcar_memLp

                source
                (c Δ : ) ( : 0 < Δ) (p : ENNReal) :

                The spectral boxcar lies in every Lᵖ: it is bounded by Δ on a compact set.

                Used by
                  theorem

                  InformationTheory.Shannon.ShannonHartley.fourierInv_specBoxcar

                  source
                  (c Δ : ) ( : 0 < Δ) (t : ) :

                  Pointwise inverse Fourier transform of the spectral boxcar is the shifted, dilated sinc.

                  Used by
                    theorem

                    InformationTheory.Shannon.ShannonHartley.shiftSinc_memLp

                    source
                    (c Δ : ) ( : 0 < Δ) :

                    The complexified shifted, dilated sinc lies in (it is the inverse transform of an L¹ ∩ L² boxcar).

                    Used by
                      theorem

                      InformationTheory.Shannon.ShannonHartley.fourier_shiftSinc_toLp

                      source
                      (c Δ : ) ( : 0 < Δ) :

                      The abstract -Fourier transform of the sinc's canonical Lp representative is the boxcar's canonical Lp representative.

                      Used by
                        theorem

                        InformationTheory.Shannon.ShannonHartley.inner_specBoxcar_toLp

                        source
                        (c c' Δ : ) ( : 0 < Δ) :

                        Boxcar orthogonality (Plancherel on the band): the inner product of two spectral boxcars collapses to Δ · sincN((c - c')/Δ).

                        Used by
                          theorem

                          InformationTheory.Shannon.ShannonHartley.synthSignal_complex_memLp

                          source
                          (T : ) (n : ) (a : Fin n) (hT : 0 < T) (hn : 0 < n) :

                          The complexified synthesis lies in (a finite sum of shifted sincs).

                          Used by
                            theorem

                            InformationTheory.Shannon.ShannonHartley.synthSignal_toLp_eq_sum

                            source
                            (T : ) (n : ) (a : Fin n) (hT : 0 < T) (hn : 0 < n) ( : 0 < T / n) :
                            MeasureTheory.MemLp.toLp (fun (t : ) => (synthSignal T n a t)) = i : Fin n, (a i) MeasureTheory.MemLp.toLp (fun (t : ) => (NormalizedSinc.sincN ((t - i * (T / n)) / (T / n))))

                            The synthesis's canonical Lp representative decomposes as the finite Lp combination ∑ᵢ aᵢ • (shifted sinc)ᵢ.

                            Used by

                              §C — band-limitedness #

                              theorem

                              InformationTheory.Shannon.ShannonHartley.synthSignal_bandlimited

                              source
                              (T W : ) (n : ) (a : Fin n) (hT : 0 < T) (hn : 0 < n) (hnW : n 2 * W * T) :

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

                                theorem

                                InformationTheory.Shannon.ShannonHartley.synthSignal_sq_integrable

                                source
                                (T : ) (n : ) (a : Fin n) (hT : 0 < T) (hn : 0 < n) :

                                The squared synthesis is integrable on the whole line (it lies in ).

                                @audit:ok

                                Used by
                                  theorem

                                  InformationTheory.Shannon.ShannonHartley.synthSignal_energy

                                  source
                                  (T : ) (n : ) (a : Fin n) (hT : 0 < T) (hn : 0 < n) :
                                  (t : ), synthSignal T n a t ^ 2 = T / n * i : Fin n, a i ^ 2

                                  Parseval / 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 #

                                    theorem

                                    InformationTheory.Shannon.ShannonHartley.contAwgn_log_le_of_pos_k

                                    source
                                    {T W N₀ P ε : } {M : } (hN₀ : 0 < N₀) (hP : 0 P) (hT : 0 < T) (hε0 : 0 < ε) (hε1 : ε < 1) (hM : 2 M) (c : ContAwgnCode T W P M) (hk : 0 < c.k) (hce : (c.averageError N₀).toReal ε) :
                                    Real.log M ((T * P + 1) / N₀ + Real.log 2) / (1 - ε)

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

                                      InformationTheory.Shannon.ShannonHartley.contAwgn_averageError_of_k_eq_zero

                                      source
                                      {T W P : } {M : } (hM : 0 < M) (c : ContAwgnCode T W P M) (hk : c.k = 0) (N₀ : ) :
                                      (c.averageError N₀).toReal = (M - 1) / M

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

                                        InformationTheory.Shannon.ShannonHartley.contAwgnMaxMessages_bddAbove

                                        source
                                        (T W N₀ P ε : ) (hT : 0 < T) (hW : 0 < W) (hN₀ : 0 < N₀) (hP : 0 P) (hε0 : 0 < ε) (hε1 : ε < 1) :
                                        BddAbove {M : | ∃ (c : ContAwgnCode T W P M), (c.averageError N₀).toReal ε}

                                        The 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

                                        Used by