PaperlayerView exact revision on arXiv

Source-linked AI summary

Noisy Network Coding

Sung Hoon Lim, Young-Han Kim, Abbas El Gamal, Sae-Young Chung

arXiv:1002.3188v2cs.IT

TL;DR

The paper addresses how to communicate multiple sources over general noisy networks while extending network coding and compress-forward beyond their established settings. It introduces noisy network coding with message repetition, relay signal compression, and simultaneous decoding, and reports tighter Gaussian multicast approximations and better performance than several specialized schemes.

  • Problem

    The paper asks for a coding scheme and capacity-region results for multiple sources communicating over a general network.

  • Method

    Noisy network coding combines message repetition across independently coded blocks, relay signal compression without Wyner-Ziv binning, and simultaneous message decoding.

  • Results

    The scheme extends network coding and compress-forward to general noisy networks, improves the Gaussian multicast gap to the cutset bound, and outperforms several specialized schemes in reported AWGN examples.

  • Takeaways & Limitations

    Noisy network coding provides a common framework covering network coding variants and compress-forward-based results across discrete memoryless and Gaussian networks.

Abstract

from arXiv · show

A noisy network coding scheme for sending multiple sources over a general noisy network is presented. For multi-source multicast networks, the scheme naturally extends both network coding over noiseless networks by Ahlswede, Cai, Li, and Yeung, and compress-forward coding for the relay channel by Cover and El Gamal to general discrete memoryless and Gaussian networks. The scheme also recovers as special cases the results on coding for wireless relay networks and deterministic networks by Avestimehr, Diggavi, and Tse, and coding for wireless erasure networks by Dana, Gowaikar, Palanki, Hassibi, and Effros. The scheme involves message repetition coding, relay signal compression, and simultaneous decoding. Unlike previous compress--forward schemes, where independent messages are sent over multiple blocks, the same message is sent multiple times using independent codebooks as in the network coding scheme for cyclic networks. Furthermore, the relays do not use Wyner--Ziv binning as in previous compress-forward schemes, and each decoder performs simultaneous joint typicality decoding on the received signals from all the blocks without explicitly decoding the compression indices. A consequence of this new scheme is that achievability is proved simply and more generally without resorting to time expansion to extend results for acyclic networks to networks with cycles. The noisy network coding scheme is then extended to general multi-source networks by combining it with decoding techniques for interference channels. For the Gaussian multicast network, noisy network coding improves the previously established gap to the cutset bound. We also demonstrate through two popular AWGN network examples that noisy network coding can outperform conventional compress-forward, amplify-forward, and hash-forward schemes.

I. INTRODUCTION

The paper introduces noisy network coding as a unified extension of network coding and compress-forward coding to general noisy networks. Its scheme uses message repetition, relay compression, and simultaneous decoding, and improves reported performance over prior schemes in several network settings.

  • The achievability proof avoids a topology-dependent two-step time-expansion approach for networks with cycles.Earlier network-coding proofs used acyclic time-expanded networks to handle cyclic networks.
  • Noisy network coding extends and unifies network coding and compress-forward coding for general noisy networks.The scheme includes prior network-coding results and extends the equivalent compress-forward characterization.
  • The scheme repeats the same message across multiple blocks using independently generated codebooks, rather than sending different messages block by block.This message repetition resembles the scheme used for cyclic noiseless networks.
  • Relays send compression indices without Wyner-Ziv binning, while destinations simultaneously decode messages from all blocks without explicitly decoding compression indices.Decoding uses simultaneous joint typicality over the received signals from all blocks.
  • The scheme extends to general multiple-source networks by combining noisy network coding with interference-channel decoding techniques.The paper considers decoding all messages at one extreme and treating interference as noise at the other.
  • For Gaussian multicast networks, noisy network coding tightens the gap to the cutset bound and can outperform specialized schemes in two AWGN network examples.The comparisons include conventional compress-forward, amplify-forward, and hash-forward schemes, as well as schemes for two-way and interference relay channels.

II. PROBLEM SETUP AND MAIN RESULTS

The paper formulates noisy network coding for discrete memoryless networks and develops achievable rate regions for multicast and general multiple-source communication. It specializes the framework to noiseless, relay, erasure, deterministic, and Gaussian networks, with stated comparisons to cutset bounds and competing schemes.

  • Problem setup: The DMN model comprises N sender–receiver alphabet pairs, independent messages, encoders, decoders, and achievable rates defined by vanishing error probability.The capacity region is the closure of the achievable rate tuples.
  • Multicast networks: Theorem 1 gives a multicast inner bound based on mutual information across network cuts and a penalty for conveying compressed relay outputs.The bound applies when every destination decodes every source message.
  • Special cases: Noiseless and erasure specializations coincide with the cutset bound, characterizing their capacity regions under the stated constructions.The noiseless specialization sets compressed outputs equal to channel outputs; the erasure result assumes destinations know the erasure pattern.
  • Special cases: For relay channels, the inner bound reduces to the alternative characterization of the compress–forward lower bound.This connects the general noisy-network construction to the classical relay-channel result.
  • Special cases: For deterministic networks, the theorem recovers prior single-source and multiple-source results and is tight when the cutset bound is attained by a product input distribution.A semideterministic specialization yields R(S) < I(X(S); Y(Sc)|X(Sc), Q).

III. NOISY NETWORK CODING FOR MULTICAST

The section develops noisy network coding for multicast networks, beginning with the relay channel and extending the construction to general discrete memoryless networks. The proof uses repeated message transmission, relay-output compression, and simultaneous joint typicality decoding across blocks.

  • Relay-channel construction: Noisy network coding transmits the same message across multiple independently generated blocks rather than using independent messages in successive blocks.The relay-channel construction sends x1j(m) in every block, with block-specific codebooks.
  • Relay-channel construction: Each relay compresses its received signal conditioned on its transmitted codeword and forwards the corresponding codeword in the next block.The relay finds a compression index after each block and transmits x2,j+1 based on the compressed output.
  • Relay-channel construction: The decoder jointly tests all received blocks and searches over compression indices without explicitly decoding those indices.Decoding succeeds when a unique message has compatible compression-index sequences across the blocks.
  • Relay-channel construction: For the relay channel, the achievable rate is bounded by the minimum of a compressed-observation term and a destination-information term minus the compression penalty.The stated condition is R < min{I(X1; ˆY2, Y3|X2), I(X1, X2; Y3) − I(ˆY2; Y2|X1, X2, Y3)} − δ(ǫ) − δ(ǫ′).
  • General multicast DMNs: The error probability tends to zero as blocklength grows after eliminating compression rates and letting the number of blocks tend to infinity.The proof first imposes covering conditions such as ˆRk > I(ˆYk; Yk|Xk) + δ(ǫ′), then takes b →∞.
  • General multicast DMNs: For general multicast DMNs, Theorem 1 gives a cut-based achievable region using relay compressions and a minimum over destinations outside each cut.The condition applies to every S whose complement contains at least one destination, with an optional time-sharing variable Q.

A. Proof of Theorem 2 via Multicast Completion with Implicit Decoding

This subsection establishes Theorem 2 by modifying the previous simultaneous decoding rule for multicast completion with implicit decoding. The error analysis is stated to follow the earlier theorem's proof and is supplied in an appendix.

  • Decoding rule: Theorem 2 is proved by modifying the preceding decoding rule while retaining simultaneous typicality conditions across blocks.The decoder searches over message and compression-index tuples satisfying the blockwise typicality tests.
  • Error analysis: The error analysis is similar to the analysis for Theorem 1 and is provided in Appendix A.The subsection explicitly delegates the detailed derivation to the appendix.

B. Proof of Theorem 3 via Treating Interference as Noise

This subsection proves Theorem 3 by combining noisy network coding with decoding that treats unintended messages as noise. The resulting construction uses auxiliary codewords and modified simultaneous decoding.

  • Codebook and encoding: Theorem 3 introduces auxiliary sequences U_k alongside message codewords and compressed relay-output sequences.The codebook contains u_kj(lk,j−1), x_kj(mk|lk,j−1), and ˆy_kj(lkj|lk,j−1).
  • Codebook and encoding: Each node selects a compression index after receiving its block output and transmits the codeword indexed by its message and previous compression index.The construction uses lk0 = 1 and forwards the selected index through the next block's codeword.
  • Decoding: Decoding treats unintended messages as noise, so codewords associated with those messages are omitted from the decoding test.The rule still uses simultaneous joint typical decoding for the messages intended for each destination.
  • Error analysis: The probability-of-error analysis for this construction is delegated to Appendix B.The subsection does not reproduce the derivation in the main text.

V. GAUSSIAN NETWORKS

The paper applies noisy network coding to AWGN networks modeled by a linear channel with Gaussian noise and per-sender power constraints. The section then develops capacity inner bounds for relay-network examples.

  • AWGN model: The AWGN network has output Y^N = GX^N + Z^N, where G is the channel-gain matrix and Z^N contains independent unit-variance Gaussian noise.The model is specified for an input vector X^N and a real-valued gain matrix G.
  • AWGN model: Each sender is subject to an average power constraint P.The section states this constraint for every sender.
  • Cut representation: For a cut S, the signals observed outside the cut are expressed using the channel submatrices G(S) and G′(S), plus Gaussian noise.The decomposition is Y(Sc) = G(S)X(S) + G′(S)X(Sc) + Z(Sc).
  • Applications: The Gaussian section proves an AWGN-network theorem and develops inner bounds for the AWGN two-way relay and interference relay channels.These bounds are used in the paper's example figures.

A. AWGN Multicast Capacity Gap (Proof of Theorem 4)

The proof compares the noisy network coding inner bound with the AWGN multicast cutset outer bound. Under Gaussian inputs and the stated power constraints, this comparison establishes Theorem 4.

  • Cutset outer bound: The AWGN multicast cutset outer bound is simplified using covariance-matrix positivity and the per-node power constraint.The proof bounds tr(K_X(S)) by |S|P.
  • Noisy network coding inner bound: The noisy network coding inner bound follows by adapting Theorem 1 to AWGN networks with a power constraint and product input distributions.The construction uses independent zero-mean Gaussian inputs and independent unit-variance Gaussian quantization noises.
  • Compression penalty: The proof bounds the compression penalty through a Markov relation between the compressed observations, channel outputs, and decoder observations.This yields the inequality I(Ŷ(S);Y(S)|X^N,Ŷ(S^c),Y_d) ≤ I(Ŷ(S);Y(S)|X^N).
  • Achievability: The resulting achievable rate inequalities hold for every source subset S whose complement contains a destination.The proof identifies these inequalities as the noisy network coding inner bound.
  • Capacity gap: Comparing the cutset outer bound with the noisy network coding inner bound completes the proof of Theorem 4.The comparison is stated explicitly as the final proof step.

B. AWGN Two-Way Relay Channels

For the AWGN two-way relay channel, the paper specializes its noisy network coding inner bound to rate-pair inequalities. It presents this bound alongside prior amplify-forward and compress-forward results.

  • Setup: The two-way relay channel model is used to evaluate noisy network coding for bidirectional communication.The section recalls the AWGN two-way relay channel before stating the achievable region.
  • Prior schemes: Earlier work established AWGN two-way relay inner bounds using amplify-forward and an extension of compress-forward.The cited amplify-forward result is followed by a corresponding compress-forward extension.
  • Comparison: Specializing Theorem 2 gives a noisy network coding inner bound for the two-way relay channel.The paper states this specialization as the comparison point for the AWGN two-way relay results.
  • Noisy network coding: The noisy network coding inner bound constrains each direction’s rate by the minimum of a relay-assisted term and a destination-decoding term.The two inequalities separately bound R1 and R2 using mutual-information expressions involving the compressed relay observation.
  • Gaussian specialization: The bound permits distributions p(q)p(x1|q)p(x2|q)p(x3|q)p(ŷ3|y3,x3,q), including a Gaussian specialization with Q = ∅.The Gaussian relay description is Ŷ3 = Y3 + Ẑ with Ẑ distributed as N(0,σ^2), for some σ^2 > 0.

C. AWGN Interference Relay Channels

The paper applies noisy network coding to AWGN interference relay channels and compares its resulting inner bounds with generalized hash-forward and related schemes. The bounds are expressed as rate-pair inequalities involving channel gains, power, and compression noise.

  • Channel model: The section studies the AWGN interference relay channel with orthogonal receiver components.The model is introduced as the setting for the rate-region comparison.
  • Hash-forward: Generalized hash-forward sends a bin index of the relay’s noisy observation and uses list decoding at destination nodes.The cited scheme provides an inner bound on the capacity region.
  • Rate regions: The compared achievable regions consist of rate pairs constrained by individual and sum-rate inequalities.The supplied expressions include bounds on R1 + R2 and gain-dependent terms involving P and compression parameters.
  • Noisy network coding: The noisy network coding specialization uses Ŷ3 = Y3 + Ẑ with Ẑ ∼ N(0,σ^2) to obtain an inner bound.The construction requires some σ^2 > 0.
  • Gaussian expressions: The resulting expressions include channel-gain combinations such as (g13g24 − g23g14)^2P^2 and (g23g15 − g13g25)^2P^2.These terms appear in the stated sum-rate bounds for the interference relay channel.

VI. CONCLUDING REMARKS

The paper concludes that noisy network coding unifies prior network-coding and compress-forward results while providing robust relay operations and improved performance in several settings. It also identifies networks and operating regimes where other strategies can be better.

  • Contributions: Noisy network coding establishes inner bounds on the capacity region of general noisy networks.The concluding remarks present this as the paper’s main result.
  • Unification: The scheme unifies and extends prior network coding, its extensions, and compress-forward for the relay channel.The paper also states that it can outperform previous network compress-forward schemes.
  • Mechanisms: Its stated mechanisms include no Wyner–Ziv binning, no required correct decoding of compression indices, and simultaneous decoding over all blocks.These features are given as reasons for outperforming previous network compress-forward schemes.
  • Scope of performance: Noisy network coding is optimal in some special cases and generally performs well under high-SNR conditions.The conclusion states these properties without claiming universal optimality.
  • Robustness: Relay operations do not depend on the specific source and destination codebooks or even the network topology.The paper characterizes this as making the scheme robust and scalable.
  • Limitations and extensions: For low-SNR AWGN cascade networks, decode-forward can be optimal, while multiple paths, coherent cooperation, or partial decoding can further improve performance.The paper explicitly says noisy network coding is not always the best strategy in this setting.

APPENDIX A

The appendix analyzes decoding-error probabilities for multicast and multi-source networks, deriving rate conditions under which error probability tends to zero. It also compares noisy network coding with hybrid and compress-forward bounds, showing a strict advantage in a noiseless example.

  • Multi-source error analysis: For the multi-source setting, eliminating compression rates and letting the block count grow yields the achievable rate condition in (28).The resulting condition includes a mutual-information benefit from received compressed signals and a penalty for compression uncertainty.
  • Proof completion: Coded time sharing completes the proofs for general Q after establishing the results for Q = ∅.This step is stated for both theorem analyses.
  • Comparison with hybrid coding: In a four-node binary noiseless network, noisy network coding achieves capacity C = 1, whereas the hybrid scheme's achievable rate is zero.The example has one destination and three relays, demonstrating a strict separation between the two bounds.
  • Comparison with hybrid coding: The appendix states that noisy network coding outperforms the hybrid scheme for noiseless networks with more than two relays, although relay decoding can sometimes favor the hybrid scheme.The comparison is therefore not uniformly one-sided in general networks without similar augmentation.
Loading 1002.3188v2…