InformationTheory.Shannon.BroadcastChannel.Achievability.Setup
Broadcast channel — superposition achievability setup and infrastructure #
Cover–Thomas superposition coding. The structural setup: the per-coordinate joint
distribution and its i.i.d. ambient measure, the auxiliary-variable informations, the two-tier
(cloud / satellite) random codebook, the i.i.d. coordinate facts and positivity of the BC
ambient law, the (U, X) marginal factorization, typical-set relabeling invariance, the two
exponential ingredients of the covering bound, the conditional-slice satellite typicality
bound, and the two-tier decoders assembling the broadcast code.
Per-coordinate joint distribution #
InformationTheory.Shannon.BroadcastChannel.bcJointDistribution
sourceThe per-coordinate broadcast joint law on U × α × β₁ × β₂: the compProd chain
pU → K → W (U ∼ pU, X ∣ U ∼ K, (Y₁, Y₂) ∣ X ∼ W), reshaped from the left-nested
(U × α) × (β₁ × β₂) to the right-nested quadruple.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Used by
InformationTheory.Shannon.BroadcastChannel.bcJointDistribution.instIsProbabilityMeasure
sourceUsed by
I.i.d. ambient measure on ℕ → U × α × β₁ × β₂ #
InformationTheory.Shannon.BroadcastChannel.bcAmbientMeasure
sourceThe i.i.d. broadcast ambient measure:
Measure.infinitePi (fun _ ↦ bcJointDistribution pU K W).
Equations
Instances For
Used by
InformationTheory.Shannon.BroadcastChannel.bcAmbientMeasure.instIsProbabilityMeasure
sourceUsed by
InformationTheory.Shannon.BroadcastChannel.bcUs
sourceThe cloud coordinate ω ↦ (ω i).1.
Equations
- InformationTheory.Shannon.BroadcastChannel.bcUs i ω = (ω i).1
Instances For
Used by
InformationTheory.Shannon.BroadcastChannel.bcXs
sourceThe satellite input coordinate ω ↦ (ω i).2.1.
Equations
- InformationTheory.Shannon.BroadcastChannel.bcXs i ω = (ω i).2.1
Instances For
Used by
InformationTheory.Shannon.BroadcastChannel.bcY₁s
sourceThe first-receiver output coordinate ω ↦ (ω i).2.2.1.
Equations
- InformationTheory.Shannon.BroadcastChannel.bcY₁s i ω = (ω i).2.2.1
Instances For
Used by
InformationTheory.Shannon.BroadcastChannel.bcY₂s
sourceThe second-receiver output coordinate ω ↦ (ω i).2.2.2.
Equations
- InformationTheory.Shannon.BroadcastChannel.bcY₂s i ω = (ω i).2.2.2
Instances For
Used by
Auxiliary-variable informations #
InformationTheory.Shannon.BroadcastChannel.bcInfo₂
sourceThe cloud information I(U; Y₂) = H(U) + H(Y₂) − H(U, Y₂) of the per-coordinate joint
law. This is the achievable rate of receiver 2, which decodes the cloud tier alone.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Used by
InformationTheory.Shannon.BroadcastChannel.bcInfo₁
sourceThe satellite conditional information
I(X; Y₁ ∣ U) = H(U, X) + H(U, Y₁) − H(U, X, Y₁) − H(U) of the per-coordinate joint law.
This is the achievable rate of receiver 1, which decodes the satellite tier on top of the
cloud U. Unlike the MAC macInfo, this is a genuine four-entropy conditional mutual
information, not a plain three-term unconditional one.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Used by
Two-tier (cloud / satellite) random codebook #
InformationTheory.Shannon.BroadcastChannel.BCCloudCodebook
sourceA length-n cloud codebook: for each cloud message w₂ a cloud codeword Uⁿ(w₂).
Equations
- InformationTheory.Shannon.BroadcastChannel.BCCloudCodebook M₂ n U = (Fin M₂ → Fin n → U)
Instances For
Used by
InformationTheory.Shannon.BroadcastChannel.BCSatelliteCodebook
sourceA length-n satellite codebook: for each message pair (w₁, w₂) a satellite codeword
Xⁿ(w₁, w₂). Definitionally the BroadcastCode joint encoder.
Equations
Instances For
Used by
InformationTheory.Shannon.BroadcastChannel.bcCloudCodebookMeasure
sourceThe cloud codebook law: pU-i.i.d. over all M₂ · n cloud letters.
Equations
- InformationTheory.Shannon.BroadcastChannel.bcCloudCodebookMeasure pU M₂ n = MeasureTheory.Measure.pi fun (x : Fin M₂) => MeasureTheory.Measure.pi fun (x : Fin n) => pU
Instances For
Used by
InformationTheory.Shannon.BroadcastChannel.bcSatelliteCodebookMeasure
sourceThe satellite codebook law conditional on the cloud codebook u: each satellite
letter Xₗ(w₁, w₂) is drawn from K (u w₂ l), independently across pairs and letters. This
is the conditional product Πᵢ K(Uᵢ) at the heart of superposition coding — the single point
of departure from the MAC flat-product ensemble.
Equations
- InformationTheory.Shannon.BroadcastChannel.bcSatelliteCodebookMeasure K M₁ M₂ n u = MeasureTheory.Measure.pi fun (p : Fin M₁ × Fin M₂) => MeasureTheory.Measure.pi fun (l : Fin n) => K (u p.2 l)
Instances For
Used by
InformationTheory.Shannon.BroadcastChannel.bcCodebookMeasure
sourceThe joint two-tier codebook law on (cloud, satellite) pairs: draw the cloud codebook
from bcCloudCodebookMeasure, then the satellite codebook conditionally from
bcSatelliteCodebookMeasure.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Used by
I.i.d. coordinate facts for the BC ambient measure #
Every random variable consumed by the covering bound has the form fun ω ↦ g (ω i) for a
measurable coordinate selector g : U × α × β₁ × β₂ → γ. These are the BC analogues of the
InformationTheory.Shannon.MAC macAmbient_* lemmas (IIDAmbient.lean), proven the same way
via Measure.infinitePi_map_eval / iIndepFun_infinitePi.
InformationTheory.Shannon.BroadcastChannel.bcAmbient_map_coord
sourceThe map of a coordinate selector under the BC ambient measure equals the map of the selector under the per-coordinate joint law.
Used by
InformationTheory.Shannon.BroadcastChannel.bcAmbient_iIndepFun_coord
sourceMutual independence of any coordinate selector under the BC ambient measure.
Used by
InformationTheory.Shannon.BroadcastChannel.bcAmbient_identDistrib_coord
sourceIdentical distribution of a coordinate selector across indices.
Used by
InformationTheory.Shannon.BroadcastChannel.bcAmbient_entropy_coord
sourceEntropy of a coordinate selector under the BC ambient measure equals its entropy under the per-coordinate joint law.
Used by
Positivity of the BC per-coordinate joint law and coordinate marginals #
InformationTheory.Shannon.BroadcastChannel.bcJointDistribution_singleton_pos
sourceThe per-coordinate BC joint law has positive singleton mass.
Used by
InformationTheory.Shannon.BroadcastChannel.bcAmbient_coord_marginal_pos
sourcePositivity of any coordinate-selector marginal singleton, reduced to the per-coordinate joint positivity via a chosen fiber witness.
Used by
(U, X) marginal factorization #
InformationTheory.Shannon.BroadcastChannel.bcJointDistribution_map_fst
sourceThe U-marginal of the BC joint law is pU.
Used by
InformationTheory.Shannon.BroadcastChannel.bcJointDistribution_map_UX_singleton
sourceThe (U, X)-marginal singleton mass of the BC joint law factorizes as
pU {u} · K u {x}.
Used by
Relabeling invariance of the typical set (BC-local copy of the MAC helper) #
The two exponential ingredients of the covering bound #
InformationTheory.Shannon.BroadcastChannel.bc_perseq_mass_le
sourcePer-sequence conditional mass bound: for a typical cloud u and a satellite x whose
(U, X)-pair sequence is typical, the conditional-product mass of x is at most
exp(−n (H(U, X) − H(U) − 2ε)).
Used by
InformationTheory.Shannon.BroadcastChannel.bc_slice_card_le
sourceSlice-cardinality bound: the number of satellites x making (u, x, y₁) jointly typical
is at most exp(n (H(X, (U, Y₁)) − H(U, Y₁) + 2ε)).
Used by
Conditional-slice satellite typicality bound #
InformationTheory.Shannon.BroadcastChannel.bc_conditional_slice_prob_le
sourceConditional-slice satellite typicality probability bound for the superposition covering
argument. For a fixed typical cloud codeword u and a fixed typical received word y₁,
the probability under the conditional product law Πᵢ K(uᵢ) that an independently drawn
satellite x is jointly typical with (u, y₁) is at most exp(−n (I(X; Y₁ ∣ U) − 4ε)).
This is the receiver-1 "wrong satellite, correct cloud" sub-event of the superposition
random-coding argument (Cover–Thomas); the exponent matches bcInfo₁, with the
4ε slack the sum of the four entropy-typicality windows (matching the 3ε slack of the
MAC lemmas macJTS_indep_prob_le_*). Full support (hpU/hK/hW) is a regularity
precondition of the AEP mass bounds, not load-bearing.
@audit:ok
Used by
Two-tier decoders and the assembled broadcast code #
InformationTheory.Shannon.BroadcastChannel.bcCloudTypicalDecoder
sourceReceiver-2 (cloud tier) joint-typical decoder. Given a received word
y₂, returns the unique cloud message w₂ whose codeword Uⁿ(w₂) is jointly typical with
y₂, falling back to ⟨0, hM₂⟩ if no such w₂ exists or it is not unique. This is a
single-user joint-typical decoder over the cloud codebook — receiver 2 never needs the
satellite tier.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Used by
InformationTheory.Shannon.BroadcastChannel.bcJointTypicalDecoder
sourceReceiver-1 superposition joint-typical decoder. Given a received word
y₁, returns the unique message pair (w₁, w₂) such that the cloud/satellite/output triple
(Uⁿ(w₂), Xⁿ(w₁, w₂), y₁) is jointly typical, falling back to (⟨0, hM₁⟩, ⟨0, hM₂⟩)
otherwise. The typical-set argument order bcUs, bcXs, bcY₁s matches the covering bound
bc_conditional_slice_prob_le.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Used by
InformationTheory.Shannon.BroadcastChannel.bcCodebookToCode
sourceBundle a cloud codebook cU and satellite codebook cX into a BroadcastCode: cX is
the joint encoder, receiver 1 uses the superposition joint decoder, receiver 2 the cloud
decoder.
Equations
- One or more equations did not get rendered due to their size.