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.

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

Lean formalization

Canonical statementStatement

Version 1 · Lean. The concrete maps and entropy region are fixed in the central statement.

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. Sergei I. Gel'fand and Mark S. Pinsker (1980). Capacity of a Broadcast Channel with One Deterministic Component. Problems of Information Transmission.

Discussion

Thread key: capacityatlas:blackwell-broadcast-channel

Find discussionStart discussion

Related problems

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