CCapacity Atlas
general-relay-channel

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

Channel and question

Input
Source input \(X\) and relay input \(X_r\).
Output
Relay observation \(Y_r\) and destination observation \(Y\).
Law
A memoryless law \(p(y,y_r\mid x,x_r)\).
Quantity
Shannon capacity \(C\), measured in bits per channel use.

Criterion. Average-error source-to-destination capacity.

  • The relay acts causally on past observations.
  • Average decoding error vanishes.

Current status

\[R_{\mathrm{DF}}\le C\le R_{\mathrm{cut}}\]

The bounds coincide for important subclasses but not for the unrestricted model.

Known results and bounds for General discrete memoryless relay channel
ResultRelationMethodYear
Lower\(C\ge R_{\mathrm{DF}}\)The relay decodes and cooperatively forwards the message.1979
Upper\(C\le R_{\mathrm{cut}}\)Apply a converse across each source-destination cut.1979
Lower\(C\ge R_{\mathrm{CF}}\)Compress-and-forward with I(Z;Zhat|R,Y) <= I(R;Y), product source/relay input distributions.1979

Open question

Find a computable exact capacity characterization for the unrestricted relay channel.

A relay can mix decoding, compression, and coherent cooperation across blocks, while standard cut arguments discard causal structure.

Research directions

  • Identify a new subclass where inner and outer bounds coincide.
  • Strengthen the converse using relay causality.

Formal verification

Lean coverageFormally stated

Concrete operational definitions and admitted research statements are present. Existing proofs are preserved. New statements require mathematical review and proof completion.

Claims

  • Decode-and-forward and compress-and-forward are lower bounds, cut set is an upper bound.
    df-cf-cut-set · capacity bounds · solved · Formally stated · v1
  • Independently tracked decode forward achievability.
    decode-forward-achievability · achievability · 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. Abbas El Gamal and Young-Han Kim (2011). Network Information Theory. Cambridge University Press. DOI 10.1017/CBO9781139030687.

Discussion

Find discussionStart discussion

Related problems

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
Open \(R_{\mathrm{CF}}\le C(R_0)\le C_{\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)\}\)