CCapacity Atlas
primitive-relay-channel

Primitive relay channel

A relay observes a noisy channel output and sends information over a separate noiseless finite-capacity link, but capacity is unknown in general.

Relay Finite alphabet Discrete memoryless Capacity Bounds only

Channel and question

Input
A finite source input \(X\).
Output
Destination observation \(Y\), relay observation \(Z\), and a relay-to-destination bit-pipe of capacity \(R_0\).
Law
A finite memoryless broadcast law \(P_{Y,Z|X}\) followed by an orthogonal noiseless relay link.
Quantity
Primitive-relay capacity \(C(R_0)\), measured in bits per channel use.

Criterion. Arbitrary blocklength causal relay codes with vanishing average error.

  • The relay encoder is causal in its observations.
  • Average destination decoding error vanishes.

Current status

\[R_{\mathrm{CF}}\le C(R_0)\le C_{\mathrm{cut}}\]

The cut-set bound is not tight for every known subclass.

ResultRelationMethodYear
Lower\(R_{\mathrm{CF}}\le C(R_0)\)Compress-and-forward relay coding.1979
Upper\(C(R_0)\le C_{\mathrm{TU}}\le C_{\mathrm{cut}}\)Primitive-relay auxiliary-variable converse.2008

Research frontier

Determine capacity for the general primitive relay channel and characterize when the cut-set bound is tight.

Why it remains open. Relay compression and destination side information interact beyond the standard cut-set constraints.

What would count as progress

  • Close the inner-outer gap for a concrete finite subclass.

Lean formalization

Canonical statementStatement

Version 1 · Lean. The physical broadcast observation and orthogonal bit-pipe are separate fields; no cut-set-tightness conjecture is assumed.

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. Thomas M. Cover and Abbas El Gamal (1979). Capacity Theorems for the Relay Channel. IEEE Transactions on Information Theory. DOI 10.1109/TIT.1979.1056084.
  2. Ravi Tandon and Sennur Ulukus (2008). A New Upper Bound on the Capacity of a Class of Primitive Relay Channels. Allerton Conference on Communication, Control, and Computing.

Discussion

Thread key: capacityatlas:primitive-relay-channel

Find discussionStart discussion

Related problems

General discrete memoryless relay channel

A causal relay assists a source, but decode-forward and the cut-set bound do not coincide in general.

Relay Finite alphabet Discrete memoryless Capacity Bounds only
Open \(R_{\mathrm{DF}}\le C\le R_{\mathrm{cut}}\)
Binary deletion channel BDC

Each input bit is independently deleted without an erasure marker; the exact capacity is unknown for every nontrivial deletion probability.

Point-to-point Binary Finite alphabet Memory Deletion Capacity Bounds only
Open \(0.1221(1-d)<C_{\mathrm{del}}(d)\le0.3578(1-d)\)
Binary random-insertion channel

In the fixed iid random-insertion model, each transmitted bit may be followed by one independent fair inserted bit and exact capacity is unknown.

Point-to-point Finite alphabet Binary Memory Capacity Bounds only
Open \(0\le C_{\mathrm{ins}}(p)\le1\)
Physically degraded relay channel

When the destination is a degraded version of the relay observation, decode-forward meets the cut-set bound.

Relay Finite alphabet Discrete memoryless Degraded Capacity Exact Single-letter characterization
Solved \(C=\max_{p(x,x_r)}\min\{I(X;Y_r|X_r),\ I(X,X_r;Y)\}\)