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.

Noisy-network-coding inner region for the finite two-way relay channel

Statement

For the finite two-way relay channel in Finite two-way relay channel and causal code, choose independent inputs $P_{X_{1}} P_{X_{2}} P_{X_{r}}$ and a relay test channel $P_{{\hat{Y}}_{r} ∣ Y_{r}, X_{r}}$ . The following rates are achievable by the finite multicast NNC theorem [F1]: $R_{1} < \min {I (X_{1}; Y_{2}, {\hat{Y}}_{r} ∣ X_{2}, X_{r}), I (X_{1}, X_{r}; Y_{2} ∣ X_{2}) - I (Y_{r}; {\hat{Y}}_{r} ∣ X_{1}, X_{2}, X_{r}, Y_{2})},$ $R_{2} < \min {I (X_{2}; Y_{1}, {\hat{Y}}_{r} ∣ X_{1}, X_{r}), I (X_{2}, X_{r}; Y_{1} ∣ X_{1}) - I (Y_{r}; {\hat{Y}}_{r} ∣ X_{1}, X_{2}, X_{r}, Y_{1})} .$ The closure of the union over such laws, together with the zero-rate pair, is an inner region, not asserted to be capacity. The zero pair is attained by singleton message sets at both terminals.

Facts & Assumptions

Given: The finite two-way relay model, independent terminal messages, and the input and relay test-channel laws above.

[F1]

Noisy network coding inner bound for finite multicast networks: for each destination, every cut separating that destination from its required message sources gives the corresponding NNC rate inequality.

[F2]

Finite two-way relay channel and causal code: terminal 1 wants terminal 2's message and terminal 2 wants terminal 1's message; all inputs depend only on local messages and past local outputs.

[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

For destination 2 and message source 1, the cut containing only node 1 yields $I (X_{1}; Y_{2}, {\hat{Y}}_{r} ∣ X_{2}, X_{r})$ ; the cut containing nodes 1 and $r$ yields $I (X_{1}, X_{r}; Y_{2} ∣ X_{2}) - I (Y_{r}; {\hat{Y}}_{r} ∣ X_{1}, X_{2}, X_{r}, Y_{2})$ . The other node's observation reconstruction may be constant. These are the two bounds on $R_{1}$ .

2.1F1F2step 1.1

For destination 1 and message source 2, the two cuts are respectively node 2 alone and nodes 2 with the relay. Substitution into [F1] yields the displayed two bounds on $R_{2}$ . Both destinations can use their own message as side information, as in [F2].

3.1F1F3step 1.1step 2.1algebra

Taking the intersection of the two destination constraints and then closure over rates yields the stated inner region; the finite mutual-information quantities use the chain-rule and conditional-law conventions of [F3]. The simultaneous multicast code supplied by [F1] serves both destinations, with each terminal using its own message as side information.

4.1F2given∎

If $R_{1} = R_{2} = 0$ , both terminals use singleton message sets and return their unique required messages, so the error probability is zero. This includes the zero-rate pair even if a displayed right-hand side is negative.

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

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)
Abbas El Gamal and Young-Han Kim, Lecture Notes on Network Information Theory, arXiv:1001.3404v4 (standard reference, not scraped)