CCapacity Atlas
general-two-receiver-broadcast-channel

General two-receiver discrete memoryless broadcast channel

The capacity region for two arbitrary broadcast receivers remains unknown outside important ordered subclasses.

Broadcast Finite alphabet Discrete memoryless Capacity region Bounds only

Channel and question

Input
One transmitter chooses \(X\in\mathcal X\).
Output
Receivers observe \(Y_1\) and \(Y_2\).
Law
An arbitrary memoryless law \(p(y_1,y_2|x)\).
Quantity
Capacity region \(\mathcal C_{\mathrm{BC}}\), measured in rate pairs in bits per channel use.

Criterion. Vanishing average error at both receivers.

  • Each receiver requests a private message.
  • No degradedness or receiver ordering is assumed.

Current status

\[\mathcal R_{\mathrm{Marton}}\subseteq\mathcal C_{\mathrm{BC}}\subseteq\mathcal R_{\mathrm{UV}}\]

The two regions coincide for many special classes but not in general.

Known results and bounds for General two-receiver discrete memoryless broadcast channel
ResultRelationMethodYear
Inner Region\(\mathcal R_{\mathrm{Marton}}\subseteq\mathcal C\)Correlated auxiliaries, random binning, and superposition.1979
Outer Region\(\mathcal C\subseteq\mathcal R_{\mathrm{UV}}\)A single-letter outer region using two auxiliary variables.2007

Open question

Determine the private-message capacity region of the general two-receiver DMC broadcast channel.

The transmitter must coordinate incompatible receiver-specific descriptions, and known converses do not capture the full binning structure of the best inner bounds.

Research directions

  • Find a channel separating or matching Marton's inner region and current outer bounds.
  • Discover a tighter computable outer region.

Formal verification

Lean coverageFormally stated

Concrete operational definitions and admitted research statements are present. Existing proofs are preserved. New statements require mathematical review and proof completion.

Claims

  • The fixed two-auxiliary Marton inner bound and UV outer bound, with closures.
    marton-uv-bounds · capacity bounds · solved · Formally stated · v1
  • Independently tracked marton achievability.
    marton-achievability · achievability · solved · Formally stated · v1
  • Independently tracked uv converse.
    uv-converse · converse · solved · Formally stated · v1
Lean declarations (3)

References

  1. Katalin Marton (1979). A Coding Theorem for the Discrete Memoryless Broadcast Channel. IEEE Transactions on Information Theory. DOI 10.1109/TIT.1979.1056046.
  2. Chandra Nair and Abbas El Gamal (2007). An Outer Bound to the Capacity Region of the Broadcast Channel. IEEE Transactions on Information Theory. DOI 10.1109/TIT.2006.887492.
  3. Abbas El Gamal and Young-Han Kim (2011). Network Information Theory. Cambridge University Press. DOI 10.1017/CBO9781139030687.

Discussion

Find discussionStart discussion

Related problems

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}}\)
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)\)
Discrete memoryless multiple-access channel with feedback

Common noiseless output feedback lets distributed encoders cooperate, but the general capacity region is unknown.

Multiple access Finite alphabet Discrete memoryless Feedback Capacity region Bounds only
Open \(\mathcal R_{\mathrm{CL}}\subseteq\mathcal C_{\mathrm{MAC,fb}}\subseteq\mathcal R_{\mathrm{DB}}\)
Discrete memoryless two-way channel

Two terminals exchange messages while adapting each input to their own past observations.

Two-way Finite alphabet Discrete memoryless Feedback Capacity region Bounds only
Open \(\mathcal R_{\mathrm{Shannon,in}}\subseteq\mathcal C_{\mathrm{TWC}}\subseteq\mathcal R_{\mathrm{Shannon,out}}\)