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)\}\]
Known results and bounds for Less-noisy two-receiver broadcast channel
ResultRelationMethodYear
Exact\(\mathcal C_{\mathrm{LN}}=\mathcal R_{\mathrm{superposition}}\)Superposition coding and a less-noisy converse.1979

Formal verification

Lean coverageFormally stated

New statements await mathematical review and proofs.

Claims

  • The private-message capacity region when receiver 1 is less noisy.
    operational-capacity · exact capacity · solved · Formally stated · v1
Lean declarations (2)

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

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

The capacity region of this binary-input broadcast channel remains unknown.

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}}\)