InformationTheory.Shannon.BroadcastChannel.Achievability.Assembly
Broadcast channel — superposition random-coding assembly and the achievability theorems #
The superposition random-coding assembly (E0 vanishing, per-codebook error decomposition,
two-codebook average bounds, random → deterministic two-tier pigeonhole, rate slack) and the
three achievability forms it carries. bc_achievability_of_rate_lt asks only that the rate pair
lie strictly inside the three superposition constraints, so it holds over any broadcast channel.
bc_achievability_of_infoJoint_ge takes the information-level rate-sum inequality
I(X; Y₁ ∣ U) + I(U; Y₂) ≤ I((U, X); Y₁) as a hypothesis rather than deriving it, so it serves
any comparison class that supplies it, and the headline bc_achievability is the branch where
degradedness discharges that inequality.
Assembly (superposition random-coding, two receivers) #
The receiver-1/receiver-2 swap lemmas of
BroadcastChannel/Achievability/ErrorAnalysis.lean are stitched into the achievability
theorems through the same skeleton as the MAC achievability assembly
(MultipleAccess/Achievability.lean), adapted to the two-tier (cloud / conditional-satellite)
codebook and the two per-receiver error probabilities:
E0vanishing: the correct-cloud ((U, Y₂)) and correct-triple ((U, X, Y₁)) atypical masses tend to0(AEP / LLN).- per-codebook
averageErrorProb.toRealdecomposition into the Bonferroni terms. - two-codebook average bounds (weight-summed swaps).
- pigeonhole to a deterministic codebook pair.
- rate-slack vanishing under the sum constraint
max R₁ 0 + R₂ < I((U, X); Y₁)on the rate pair.
InformationTheory.Shannon.BroadcastChannel.bcAmbient_pairwise_coord
sourcePairwise independence of any BC coordinate selector under the ambient measure.
Used by
Vanishing of the E0 terms #
InformationTheory.Shannon.BroadcastChannel.bc_chan_fold_UXY₁_set
sourceChannel fold on the (U, X, Y₁) axes: the (U, X, Y₁)-block law of a finite set T
equals the cloud/satellite/channel average of the β₁-projected channel mass. Receiver-1
analogue of bc_chan_fold_UY₂_set, obtained from the master fold by projecting the pair
output to β₁.
Used by
InformationTheory.Shannon.BroadcastChannel.bc_random_codebook_E0₁_swap
sourceReceiver-1 correct-triple averaged swap for the E0 event: the two-tier random-codebook
average of the correct-triple atypical event equals the joint (U, X, Y₁)-block law of the
atypical set. Receiver-1 analogue of bc_random_codebook_E0₂_swap.
Used by
InformationTheory.Shannon.BroadcastChannel.bc_E0₂_vanishing
sourceThe receiver-2 E0 error term vanishes: the correct-cloud atypical (U, Y₂)-block mass
tends to 0 by the two-variable joint AEP (jointlyTypicalSet_prob_tendsto_one).
Used by
InformationTheory.Shannon.BroadcastChannel.bc_E0₁_vanishing
sourceThe receiver-1 E0 error term vanishes: the correct-triple atypical (U, X, Y₁)-block
mass tends to 0 by the three-variable joint AEP (macJointlyTypicalSet_prob_tendsto_one).
Used by
Per-codebook averageErrorProb.toReal decomposition #
InformationTheory.Shannon.BroadcastChannel.bc_averageErrorProb₂_toReal_le
sourcePer-codebook averaging bound for receiver 2: the .toReal of the receiver-2 average
error probability of the deterministic code bcCodebookToCode cU cX is at most the uniform
average of the two-event Bonferroni bound (bc_errorProbAt₂_le_bonferroni).
Used by
InformationTheory.Shannon.BroadcastChannel.bc_averageErrorProb₁_toReal_le
sourcePer-codebook averaging bound for receiver 1: the .toReal of the receiver-1 average
error probability of bcCodebookToCode cU cX is at most the uniform average of the
three-event Bonferroni bound (bc_errorProbAt₁_le_bonferroni3).
Used by
Two-codebook average bounds #
The two-tier codebook expectation is the nonnegative-weighted "linear functional"
L f = ∑ cU, wU cU * ∑ cX, wX cU cX * f cU cX. The generic bc_weighted_two_tier_*
lemmas express its monotonicity and linearity; the per-alias swaps evaluate L on each
Bonferroni term, and bc_pair_aggregate₂/₁ fold them into the closed-form bounds.
InformationTheory.Shannon.BroadcastChannel.bc_weighted_two_tier_mono
sourceMonotonicity of the two-tier nonnegative-weighted codebook average.
Used by
InformationTheory.Shannon.BroadcastChannel.bc_weighted_two_tier_add
sourceAdditivity of the two-tier weighted codebook average.
Used by
InformationTheory.Shannon.BroadcastChannel.bc_weighted_two_tier_const_mul
sourcePulling a constant scalar out of the two-tier weighted codebook average.
Used by
InformationTheory.Shannon.BroadcastChannel.bc_weighted_two_tier_sum_index
sourceInterchanging a finite index sum with the two-tier weighted codebook average.
Used by
InformationTheory.Shannon.BroadcastChannel.bc_pair_aggregate₂
sourceReceiver-2 aggregation: folding the per-message two-event Bonferroni bound together with
the two evaluated swaps (E0 mass A, wrong-cloud exponent e2) bounds the two-tier
weighted codebook average by the closed form A + (M₂ − 1) · e2.
Used by
InformationTheory.Shannon.BroadcastChannel.bc_pair_aggregate₁
sourceReceiver-1 aggregation: folding the per-message three-event Bonferroni bound together
with the three evaluated swaps (E0 mass A, wrong-satellite exponent eb, wrong-cloud
exponent ec) bounds the two-tier weighted codebook average by the corresponding closed
form.
Used by
InformationTheory.Shannon.BroadcastChannel.bc_random_codebook_average₂_le
sourceTwo-codebook average bound for receiver 2: the random-codebook expectation of the
receiver-2 average error is at most the (vanishing) E0 mass plus the wrong-cloud exponent.
Used by
InformationTheory.Shannon.BroadcastChannel.bc_random_codebook_average₁_le
sourceTwo-codebook average bound for receiver 1: the random-codebook expectation of the
receiver-1 average error is at most the (vanishing) E0 mass plus the wrong-satellite (E_b)
and wrong-cloud (E_c) exponents.
Used by
Random → deterministic (two-tier pigeonhole) #
InformationTheory.Shannon.BroadcastChannel.bc_two_tier_pigeonhole
sourceAbstract two-tier pigeonhole. Nonnegative outer weights wU summing to 1, and for every
outer index a nonnegative inner-weight family wX cU summing to 1, whose weighted double
average of val is ≤ B, force some index pair with val cU cX ≤ B. (If every pair had
val > B the weighted average would strictly exceed B.)
Used by
InformationTheory.Shannon.BroadcastChannel.bc_exists_codebook_le_avg
sourceTwo-tier pigeonhole for the superposition random code: if the random-codebook expectation
of the summed per-receiver errors is ≤ B, some deterministic cloud/satellite codebook pair
achieves the summed error ≤ B. Bounding the sum lets a single codebook meet both
receivers' targets simultaneously.
Used by
Degradedness and rate slack #
InformationTheory.Shannon.BroadcastChannel.bcMarkovChain_UX_Y₁_Y₂
sourceBase data-processing Markov chain (U, X) → Y₁ → Y₂ for the degraded broadcast joint
law: under physical degradedness the degraded output Y₂ is a stochastic function of Y₁
alone (via the degrading kernel Q), hence conditionally independent of the cloud/input
pair (U, X) given Y₁.
@audit:ok
Used by
InformationTheory.Shannon.BroadcastChannel.bc_degraded_infoJoint_ge
sourceSuperadditivity under degradedness: for a physically degraded channel X → Y₁ → Y₂, the
joint information I((U, X); Y₁) dominates the sum of the two per-receiver informations
I(X; Y₁ ∣ U) + I(U; Y₂). Chain rule I((U, X); Y₁) = I(U; Y₁) + I(X; Y₁ ∣ U) plus data
processing I(U; Y₁) ≥ I(U; Y₂). This makes the receiver-1 joint-decoding rate sum
R₁ + R₂ < I((U, X); Y₁) follow automatically from the two corner constraints.
@audit:ok
Used by
InformationTheory.Shannon.BroadcastChannel.bc_Ec_lt_of_rate
sourceThe receiver-1 wrong-cloud rate slack (E_c) vanishes: with the joint AEP gap
I((U, X); Y₁) − (R₁ + R₂) − 3ε > 0 and non-negative rate 0 ≤ R₁, the wrong-cloud
prefactor (⌈exp(nR₂)⌉−1)·⌈exp(nR₁)⌉ times exp(n(−I((U, X); Y₁) + 3ε)) falls below any
tolerance for large n. The 0 ≤ R₁ hypothesis is essential: for R₁ < 0 the ceil
⌈exp(nR₁)⌉ floors at 1 instead of shrinking like exp(nR₁), so the negative slack the
gap allocates to the R₁ factor is not delivered and the prefactor diverges. The bound is
stated over abstract rates so that a superposition scheme may instantiate it at either the
message rates or the subcodebook rates; every such instantiation runs at a strictly positive
rate, so the precondition is met.
Used by
InformationTheory.Shannon.BroadcastChannel.bc_ceil_exp_max_zero
sourceUsed by
InformationTheory.Shannon.BroadcastChannel.bc_Ec_lt_of_clamped_rate
sourceUsed by
Superposition achievability: the general forms and the degraded headline #
InformationTheory.Shannon.BroadcastChannel.bc_achievability_of_rate_lt
sourceUsed by
InformationTheory.Shannon.BroadcastChannel.bc_achievability_of_infoJoint_ge
sourceUsed by
InformationTheory.Shannon.BroadcastChannel.bc_achievability
sourceAchievability half of the degraded broadcast channel coding theorem, in the superposition
inner-bound form of Cover–Thomas Elements of Information Theory. Over a physically
degraded broadcast channel W with cloud law pU and conditional input kernel K, any
rate pair strictly inside the auxiliary-variable region
R₁ < I(X; Y₁ ∣ U)(= bcInfo₁, the strong receiver), andR₂ < I(U; Y₂)(= bcInfo₂, the degraded receiver)
is achievable: for all large enough block lengths n there is a BroadcastCode whose two
per-receiver average error probabilities are both below any prescribed ε' > 0. The proof
is the two-tier superposition random-coding argument; degradedness X → Y₁ → Y₂ is a
structural precondition ensuring the receiver-1 joint-decoding rate sum is met automatically.
@audit:ok