CorollaryStatement: 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.

Compress-forward and noisy-network-coding bounds for a finite relay channel

Statement

For a finite relay channel, choose $P_{X} P_{X_{r}} P_{{\hat{Y}}_{r} ∣ Y_{r}, X_{r}}$ . Every positive noisy-network-coding rate $R < \min {I (X; Y, {\hat{Y}}_{r} ∣ X_{r}), I (X, X_{r}; Y) - I (Y_{r}; {\hat{Y}}_{r} ∣ X, X_{r}, Y)}$ is achievable by the finite multicast NNC theorem in [F1]; rate $R = 0$ is always achievable by a one-message code. In particular, if $I (Y_{r}; {\hat{Y}}_{r} ∣ X_{r}, Y) \leq I (X_{r}; Y),$ then every positive compress-forward rate $R < I (X; Y, {\hat{Y}}_{r} ∣ X_{r})$ is included, along with the zero rate.

Facts & Assumptions

Given: The finite relay model in [F2], the product input and test-channel law above, and the NNC inner-bound statement [F1].

[F1]

Noisy network coding inner bound for finite multicast networks: for the one-source, one-destination three-node network, its cut $A = {s}$ gives the first mutual-information term, and cut $A = {s, r}$ gives the second term.

[F2]

Finite discrete memoryless relay channel and causal code: the one-way relay network has source, relay, destination and causal relay input.

[F3]

Finite conditional mutual information, Finite conditional mutual information identities and equality, and Finite entropy and mutual-information chain rules: the finite conditional-KL definition, nonnegativity identity, and entropy/mutual-information chain rules apply.

Proof

1.1F1F2given

Substitute $A = {s}$ and $A = {s, r}$ into [F1]. The first cut has no source-side reconstruction penalty because the source reconstruction can be constant; the second cut has only the relay penalty $I (Y_{r}; {\hat{Y}}_{r} ∣ X, X_{r}, Y)$ . These substitutions give the displayed NNC minimum.

1.2F3givenalgebra

The test-channel Markov relation ${\hat{Y}}_{r} - Y_{r} - (X, Y)$ conditional on $X_{r}$ gives $I (Y_{r}; {\hat{Y}}_{r} ∣ X_{r}, Y) = I (X; {\hat{Y}}_{r} ∣ X_{r}, Y) + I (Y_{r}; {\hat{Y}}_{r} ∣ X, X_{r}, Y) .$ Indeed, expand $I (X, Y_{r}; {\hat{Y}}_{r} ∣ X_{r}, Y)$ in both orders; the term $I (X; {\hat{Y}}_{r} ∣ Y_{r}, X_{r}, Y)$ is zero by the test-channel factorization.

2.1F1F3step 1.2algebra

Subtract the first NNC term from the second and use [F3]: $I (X, X_{r}; Y) - I (Y_{r}; {\hat{Y}}_{r} ∣ X, X_{r}, Y) - I (X; Y, {\hat{Y}}_{r} ∣ X_{r}) = I (X_{r}; Y) - I (Y_{r}; {\hat{Y}}_{r} ∣ X_{r}, Y) .$ Thus the stated compress-forward condition makes the second term at least the first. Thus [F1] proves the asserted positive-rate achievability.

3.1F2given∎

At $R = 0$ , choose a singleton message set at the source and let the destination return its sole message. This achieves zero error without needing either strict mutual-information inequality.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

16 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)
Sung Hoon Lim, Young-Han Kim, Abbas El Gamal, and Sae-Young Chung, Noisy Network Coding, IEEE Transactions on Information Theory 57(5), 2011 (standard reference, not scraped)