ExampleConstruction: AI-adaptedVerification: AI-generatedPipeline-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.

A two-hop Gaussian relay with a half-bit quantization penalty

Example

Consider a real three-node relay with unit power and unit noise variance at every node, source-to-relay gain $\sqrt{10}$ , relay-to-destination gain $\sqrt{10}$ , and zero direct gain. Use independent $X, X_{r} \sim N (0, 1)$ , a constant reconstruction at the source, the unquantized destination output, and the fixed relay quantizer ${\hat{Y}}_{r} = Y_{r} + {\hat{Z}}_{r}$ with independent ${\hat{Z}}_{r} \sim N (0, 1)$ . The noisy-network-coding rate for this fixed test channel is $R_{N N C} = \min {\frac{1}{2} \log_{2} 6, \frac{1}{2} \log_{2} 11 - \frac{1}{2}} = \frac{1}{2} \log_{2} 11 - \frac{1}{2} \approx 1.2297$ bits per use. The cut-set value is $\frac{1}{2} \log_{2} 11 \approx 1.7297$ , so this fixed quantizer's NNC rate is half a bit below that outer bound.

Facts & Assumptions

Given: The three-node Gaussian relay with the stated gains, power constraints, independent inputs, and fixed quantizer.

[A1]

Assume AC (The Axiom of Choice), as required by the Gaussian coding and entropy suppliers [F2] and [F3].

[F1]

Real scalar Gaussian multicast relay network and power constraints: the channel is memoryless additive Gaussian with per-node unit power and unit noise variance.

[F2]

Noise-level noisy-network-coding inner bound for real Gaussian multicast networks: for a cut $A$ and destination $d$ , NNC subtracts $I (Y_{A}; {\hat{Y}}_{A} ∣ X_{[N]}, Y_{d}, {\hat{Y}}_{A^{c}})$ from $I (X_{A}; Y_{d}, {\hat{Y}}_{A^{c}} ∣ X_{A^{c}})$ ; constant reconstructions are allowed.

[F3]

Gaussian maximizes differential entropy at fixed positive-definite covariance: Gaussian laws maximize differential entropy at fixed covariance, so the cut mutual informations are bounded by the corresponding Gaussian log expressions.

Proof

1.1A1F1givenalgebra

Assume [A1] and use the independent unit-variance Gaussian inputs and quantizer noise stated in the example. For the cut separating the source alone, the relay sees $\sqrt{10} X + Z_{r}$ , and adding independent unit-variance quantization noise makes total noise variance $2$ . Thus the NNC first-cut mutual information is $\frac{1}{2} \log_{2} (1 + 10 / 2) = \frac{1}{2} \log_{2} 6$ . The destination has no direct source term, so its observation adds zero information across this cut.

1.2F1F2givenalgebra

For the cut containing source and relay, the destination observes $\sqrt{10} X_{r} + Z_{d}$ , so $I (X, X_{r}; Y_{d}) = \frac{1}{2} \log_{2} (1 + 10) = \frac{1}{2} \log_{2} 11$ . Given all inputs and $Y_{d}$ , the relay observation noise and independent quantization noise have variances $1$ and $1$ , hence $I (Y_{r}; {\hat{Y}}_{r} ∣ X, X_{r}, Y_{d}) = \frac{1}{2} \log_{2} (2) = \frac{1}{2}$ . The two NNC cut rates are therefore the values in the minimum in the statement.

2.1F1F2F3step 1.1step 1.2algebra∎

The first cut is larger because $6 > 11 / 2$ (equivalently $12 > 11$ ), so the minimum is $\frac{1}{2} \log_{2} 11 - \frac{1}{2}$ . In the cut-set expression, the source cut is $I (X; Y_{r}, Y_{d} ∣ X_{r}) = I (X; Y_{r} ∣ X_{r}) \leq \frac{1}{2} \log_{2} 11$ and the relay-to-destination cut is $I (X, X_{r}; Y_{d}) = I (X_{r}; Y_{d}) \leq \frac{1}{2} \log_{2} 11$ , since the direct gain is zero; [F3] gives each Gaussian upper bound. Independent unit-power Gaussian inputs attain both terms, so the cut-set value is $\frac{1}{2} \log_{2} 11$ . Subtracting gives a gap of exactly $1 / 2$ bit.

Scope note

This is the rate of the stated fixed quantizer, not the optimized NNC rate. The general reconstruction-set coding statement [F2], with only the relay quantized, proves achievability of every strict rate below the displayed value and its closure.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

9 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)
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)