CCapacity Atlas
binary-skew-symmetric-broadcast-channel

Binary skew-symmetric broadcast channel

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

Broadcast Finite alphabet Discrete memoryless Binary Asymmetric Capacity region Bounds only

Channel and question

Input
A binary symbol \(X\).
Output
Binary outputs \(Y_1,Y_2\).
Law
For \(X=0\), \(Y_1=0\) and \(Y_2\) is fair; for \(X=1\), \(Y_1\) is fair and \(Y_2=1\).
Quantity
Private-message capacity region \(\mathcal C_{\mathrm{BSSC}}\), measured in ordered pairs of bits per channel use.

Criterion. Closure of achievable private-message rate pairs.

  • Independent private messages are sent to the receivers.
  • Average probability that either receiver errs vanishes.

Current status

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

Equality of the named inner and outer descriptions is the canonical formal target.

Known results and bounds for Binary skew-symmetric broadcast channel
ResultRelationMethodYear
Inner Region\(\mathcal R_{\mathrm{Marton}}\subseteq\mathcal C_{\mathrm{BSSC}}\)Marton coding specialized to binary input and symmetric outputs.1979
Outer Region\(\mathcal C_{\mathrm{BSSC}}\subseteq\mathcal R_{\mathrm{UV}}\)Auxiliary-variable broadcast outer bound.2007

Open question

Close the gap between the best Marton-type inner region and UV-type outer region for the fixed BSSC law.

Known auxiliary-variable optimizations do not coincide on all supporting hyperplanes.

Certify a strict separating rate pair or prove the two optimized descriptions equal.

Formal verification

Lean coverageFormally stated

New statements await mathematical review and proofs.

Claims

  • Marton/UV bounds specialized to the concrete binary skew-symmetric channel.
    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 (4)

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. Yanlin Geng, Chandra Nair, Shlomo Shamai, and Zizhou Vincent Wang (2010). On Broadcast Channels with Binary Inputs and Symmetric Outputs. arXiv preprint.

Discussion

Find discussionStart discussion

Related problems

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
Open \(\mathcal R_{\mathrm{Marton}}\subseteq\mathcal C_{\mathrm{BC}}\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}}\)