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.

Known results and bounds for Primitive relay channel
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
Upper\(C(R_0)\le \max_{P_X}\min\{I(X;Y,Z),I(X;Y)+R_0\}\)Cooperation across the two source-destination cuts. Distinct from the stronger auxiliary converse.1979

Open question

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

Relay compression and destination side information interact beyond the standard cut-set constraints.

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

Formal verification

Lean coverageFormally stated

New statements await mathematical review and proofs.

Claims

  • Primitive-relay compress-and-forward and cut-set bounds with a causal rate-limited link.
    cf-cut-set · capacity bounds · solved · Formally stated · v1
  • Independently tracked compress forward achievability.
    compress-forward-achievability · achievability · solved · Formally stated · v1
  • Independently tracked cut set converse.
    cut-set-converse · converse · solved · Formally stated · v1
Lean declarations (4)

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

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