CCapacity Atlas
blackwell-broadcast-channel

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

Channel and question

Input
One of three symbols \(x\in\{0,1,2\}\).
Output
Two binary outputs with pairs \((Y_1,Y_2)=(0,0),(0,1),(1,1)\), respectively.
Law
Both receiver outputs are deterministic functions of the input.
Quantity
Private-message capacity region \(\mathcal C_{\mathrm B}\), measured in ordered pairs of bits per channel use.

Criterion. Closure of achievable nonnegative private-message rate pairs.

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

Current status

\[R_1\le H(Y_1),\quad R_2\le H(Y_2),\quad R_1+R_2\le H(Y_1,Y_2)\]

Conditions. Union over all input distributions on the three symbols.

Known results and bounds for Blackwell deterministic broadcast channel
ResultRelationMethodYear
Exact\(\mathcal C_{\mathrm B}=\bigcup_{P_X}\{R_1\le H(Y_1),R_2\le H(Y_2),R_1+R_2\le H(Y_1,Y_2)\}\)Deterministic broadcast coding theorem.1980

Formal verification

Lean coverageFormally stated

New statements await mathematical review and proofs.

Claims

  • The operational private-message region of the registered Blackwell channel.
    operational-capacity · exact capacity · solved · Formally stated · v1
Lean declarations (3)

References

  1. Sergei I. Gel'fand and Mark S. Pinsker (1980). Capacity of a Broadcast Channel with One Deterministic Component. Problems of Information Transmission.

Discussion

Find discussionStart discussion

Related problems

Broadcast channel with common and confidential messages

Both receivers decode a common message; receiver 1 also decodes an independent confidential message kept secret from receiver 2.

Broadcast Wiretap Finite alphabet Discrete memoryless Secrecy Capacity region Exact Single-letter characterization
Solved \(\mathcal C_{\mathrm{BCC}}=\overline{\bigcup_{U-V-X-(Y,Z)}\{(R_0,R_1)\ge0:\ R_0\le\min\{I(U;Y),I(U;Z)\},\ R_1\le I(V;Y\mid U)-I(V;Z\mid U)\}}\)
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
Solved \(\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)\}\)
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)]\}\)
Noiseless multisource multicast network

Every sink recovers independent messages generated at several nodes. Linear network coding achieves exactly the cut constraints.

Multiple access Broadcast Finite alphabet Capacity region Exact Single-letter characterization
Solved \(\mathcal C=\{R\ge0:\ \sum_{i:s_i\in U}R_i\le\sum_{e\in\delta^+(U)}c_e\quad\forall t\in T,\ U\subseteq V\setminus\{t\}\}\)