TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pending

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Decode-forward inner bound for a finite relay channel

Statement

For a finite relay channel with relay-only causality, fix a finite law $P_{X_{r}} P_{X ∣ X_{r}}$ . Every positive rate $0 < R < \min {I (X; Y_{r} ∣ X_{r}), I (X, X_{r}; Y)}$ is achievable, and rate $R = 0$ is always achievable with a one-message code. Taking the closure of the union over such laws gives the decode-forward inner bound. Mutual informations use the relay channel law and nats per use.

Facts & Assumptions

Given: A finite relay channel, a law $P_{X_{r}} P_{X ∣ X_{r}}$ , and either a positive rate strictly below both displayed mutual informations or the zero-rate case.

[F1]

Finite discrete memoryless relay channel and causal code: the relay observes $Y_{r}$ and its input at time $i$ may depend on $Y_{r}^{i - 1}$ .

[F2]

Joint strong typicality for a finite IID source: IID blocks are strongly typical with probability tending to one.

[F3]

Conditional joint-typicality packing bound for finite alphabets: a wrong independent codeword passes the relevant conditional joint-typicality test with exponent given by the corresponding mutual information.

Proof

1.1givenF1choose

Choose $ϵ > 0$ so that $R + ϵ$ is below both mutual informations. For every block $b \in {1, \dots, B + 1}$ , independently generate a relay codebook $x_{r, b}^{n} (w)$ with $w \in [⌈ e^{n R} ⌉]$ , each word IID from $P_{X_{r}}$ . Given each relay word, generate source words $x_{b}^{n} (m, w)$ independently according to $\prod_{i} P_{X ∣ X_{r}} (x_{i} ∣ x_{r, b, i})$ . Set $w_{0} = w_{B + 1} = 1$ as fixed dummy indices and use $w_{1}, \dots, w_{B}$ for the $B$ messages. In block $b$ , the source sends $x_{b}^{n} (w_{b}, w_{b - 1})$ and the relay sends $x_{r, b}^{n} (w_{b - 1})$ . This is causal under [F1].

2.1F1F2F3step 1.1algebra

At the end of block $b$ , the relay tests candidate $w_{b}$ using $(x_{r, b}^{n} (w_{b - 1}), x_{b}^{n} (w_{b}, w_{b - 1}), y_{r}^{n} (b))$ and accepts the unique jointly typical candidate. The true triple has the IID law $P_{X_{r}} P_{X ∣ X_{r}} W_{Y_{r} ∣ X, X_{r}}$ , so [F2] makes its test pass with probability tending to one. For a wrong candidate, its source word is conditionally independent of the relay observation given the known relay word; [F3] bounds a false test by $e^{- n (I (X; Y_{r} ∣ X_{r}) - ϵ)}$ . There are at most $e^{n R}$ false indices, so the union bound tends to zero because $R + ϵ < I (X; Y_{r} ∣ X_{r})$ .

2.2F1F2F3step 1.1algebra

The destination decodes backward over blocks $b = B + 1, B, \dots, 2$ . It knows $w_{b}$ from the next block (or as the fixed dummy $w_{B + 1}$ ), and tests each candidate $w_{b - 1}$ against the block- $b$ source and relay codewords and $y^{n} (b)$ . The true tuple is IID with law $P_{X_{r}} P_{X ∣ X_{r}} W_{Y}$ and passes by [F2]. For a wrong candidate, the pair of candidate codewords is independent of the output generated by the true pair; [F3] bounds a false test by $e^{- n (I (X, X_{r}; Y) - ϵ)}$ . The union bound over at most $e^{n R}$ wrong indices tends to zero because $R + ϵ < I (X, X_{r}; Y)$ .

3.1step 2.1step 2.2algebra

For positive $R$ there are $B$ message blocks and $B + 1$ channel blocks, so the rate tends to $B R / (B + 1)$ as $n \to \infty$ . For fixed $B$ , the ensemble-average error tends to zero by steps 2.1, 2.2; then letting $B \to \infty$ approaches $R$ . The strict slack permits the typicality tolerances to shrink with $n$ , and closure gives the positive-rate part.

4.1givenalgebra∎

At $R = 0$ , use a singleton message set and let the destination always return its sole element; the error probability is zero for every blocklength. Thus the zero-rate case is included even if one of the mutual informations vanishes.

Depends on

Used by

Capacity of a finite relay channel with output feedback to source and relay Theorem

Dependency tree · two levels

6 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Thomas M. Cover and Abbas A. El Gamal, Capacity Theorems for the Relay Channel, IEEE Transactions on Information Theory 25(5), 1979 (standard reference, not scraped)
Abbas El Gamal and Young-Han Kim, Lecture Notes on Network Information Theory, arXiv:1001.3404v4 (standard reference, not scraped)