CCapacity Atlas
less-noisy-broadcast-channel

Less-noisy two-receiver broadcast channel

A less-noisy ordering compares every finite stochastic prefix and yields the exact superposition-coding capacity region.

Broadcast Finite alphabet Discrete memoryless Capacity region Exact Single-letter characterization

Channel and question

Input
A finite common channel input \(X\).
Output
Finite receiver outputs \(Y_1\) and \(Y_2\).
Law
Receiver 1 is less noisy than receiver 2 when \(I(U;Y_1)\ge I(U;Y_2)\) for every finite \(U-X-(Y_1,Y_2)\).
Quantity
Private-message capacity region \(\mathcal C_{\mathrm{LN}}\), measured in ordered pairs of bits per channel use.

Criterion. Closure of achievable private-message rate pairs.

  • Independent private messages and vanishing average error.
  • Arbitrary finite superposition auxiliary alphabets are allowed.

Current status

\[\mathcal C_{\mathrm{LN}}=\bigcup_{P_U P_{X|U}}\{R_1\le I(X;Y_1\mid U),\ R_2\le I(U;Y_2)\}\]
ResultRelationMethodYear
Exact\(\mathcal C_{\mathrm{LN}}=\mathcal R_{\mathrm{superposition}}\)Superposition coding and a less-noisy converse.1979

Lean formalization

Canonical statementStatement

Version 1 · Lean. Less noisy is defined by auxiliary-variable dominance, separately from more capable.

Substantial proofs0 linked

No external Lean proof is registered. Proofs longer than roughly 50 lines or requiring problem-specific infrastructure should live in a dedicated repository and link back to this statement version.

References

  1. Abbas El Gamal (1979). The Capacity of a Class of Broadcast Channels. IEEE Transactions on Information Theory. DOI 10.1109/TIT.1979.1056014.

Discussion

Thread key: capacityatlas:less-noisy-broadcast-channel

Find discussionStart discussion

Related problems

Blackwell deterministic broadcast channel

The three-input Blackwell channel is a concrete nondegraded deterministic broadcast channel with an exact entropy capacity region.

Broadcast Finite alphabet Discrete memoryless Asymmetric Capacity region Exact Single-letter characterization
Solved \(R_1\le H(Y_1),\quad R_2\le H(Y_2),\quad R_1+R_2\le H(Y_1,Y_2)\)
More-capable two-receiver broadcast channel

A more-capable ordering compares the receivers for every input distribution and yields an exact superposition-coding capacity region.

Broadcast Finite alphabet Discrete memoryless Capacity region Exact Single-letter characterization
Solved \(\mathcal C_{\mathrm{MC}}=\bigcup_{P_U P_{X|U}}\{R_2\le I(U;Y_2),\ R_1+R_2\le\min[I(X;Y_1),I(X;Y_1\mid U)+I(U;Y_2)]\}\)
Physically degraded two-receiver broadcast channel

One transmitter sends private messages to receivers whose outputs form a degradation chain.

Broadcast Finite alphabet Discrete memoryless Degraded Capacity region Exact Single-letter characterization
Solved \(\mathcal C=\bigcup_{p(u,x)}\{(R_1,R_2):R_1\le I(X;Y_1|U),\ R_2\le I(U;Y_2)\}\)
Binary skew-symmetric broadcast channel BSSC

This minimal binary-input broadcast channel isolates a persistent gap between Marton-type inner bounds and UV-type outer bounds.

Broadcast Finite alphabet Discrete memoryless Binary Asymmetric Capacity region Bounds only
Open \(\mathcal R_{\mathrm{Marton}}\subseteq\mathcal C_{\mathrm{BSSC}}\subseteq\mathcal R_{\mathrm{UV}}\)