Network information theory

Network information theory studies the fundamental limits of communication systems in which several terminals generate, transmit, receive, or reconstruct information. It extends Shannon theory, whose elementary point-to-point model contains one source, one channel, and one destination. The presence of multiple terminals changes the mathematical structure of the problem because transmissions interact through shared channel resources, correlated observations, or intermediate nodes.

The central objects are achievable rate regions rather than a single channel capacity. Each coordinate of such a region represents the asymptotic communication rate associated with a message, source, or terminal. A rate tuple is achievable when codes of increasing block length make the prescribed error probability tend to zero while respecting the network model. The closure of all achievable tuples forms the capacity region or, in source-coding settings, the admissible rate region.

Unlike point-to-point communication, general networks rarely admit a universal single-letter capacity formula. Inner bounds arise from explicit coding constructions, while outer bounds follow from information inequalities and network constraints. Exact characterizations occur when these bounds coincide.

Historical development

Claude Shannon established the point-to-point coding framework in 1948 by relating reliable communication to entropy and mutual information. His noisy-channel coding theorem separated the operational definition of reliable transmission from the probabilistic quantity that determines channel capacity.

The first systematic multiuser results appeared during the 1960s and 1970s. Rudolf Ahlswede and H. Liao independently characterized the capacity region of the discrete memoryless multiple-access channel. Their results showed that simultaneous communication by independent senders produces individual rate constraints together with a sum-rate constraint.

David Slepian and Jack Wolf established the lossless distributed source-coding theorem in 1973. The theorem demonstrated that separately encoded correlated sources can asymptotically attain the same total compression rate as jointly encoded sources, although the individual encoders do not observe one another's data.

Thomas M. Cover and Abbas El Gamal developed the principal coding and converse techniques for the relay channel. Their analysis introduced rate expressions associated with decoding at the relay and with compressed relay observations, thereby providing methods that remain central to cooperative communication.

During the same period, broadcast channels and interference channels became distinct branches of multiuser theory. Results for degraded broadcast channels yielded exact capacity regions, whereas general interference channels retained a substantial gap between known achievable regions and converses.

The later theory of communication over directed networks connected information-theoretic coding with graph structure. Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, and Raymond Yeung established that intermediate nodes may increase multicast throughput by coding across incoming messages instead of merely forwarding packets. This result formed the basis of network coding.

Mathematical framework

A discrete memoryless network consists of a finite set of terminals and a conditional probability law

[ p(y_1,\ldots,y_m\mid x_1,\ldots,x_m), ]

where (X_i) denotes the channel input of terminal (i) and (Y_i) denotes its channel output. During a block of length (n), each terminal may select its current input from its local message and its previously received outputs. This causal dependence permits feedback, relaying, and interactive communication within one formal model.

A message (M_{ij}) originating at terminal (i) and intended for terminal (j) is usually taken to be uniformly distributed over a set of size approximately (2^{nR_{ij}}). The number (R_{ij}) is its rate in bits per channel use. A coding theorem identifies the rate tuples for which the destination estimates satisfy

[ \Pr!\left[ \bigcup_{i,j}{\widehat{M}{ij}\ne M{ij}} \right]\longrightarrow 0 ]

as (n) tends to infinity.

For memoryless point-to-point channels, the capacity is

[ C=\max_{p(x)} I(X;Y). ]

This expression contains one optimization over an input distribution. Network formulas typically include several auxiliary random variables, multiple mutual-information constraints, or a union over distributions that encode superposition and correlation structures. Convexification through time sharing accounts for codes that alternate between distinct operating points.

The operational definitions are not restricted to vanishing average error. Maximum-error criteria, zero-error requirements, and strong converses lead to related but sometimes different regions. Such distinctions become consequential in multiuser systems because average-error performance can conceal message pairs whose conditional error probabilities remain comparatively large.

Multiple-access communication

A two-sender discrete memoryless multiple-access channel has transition law (p(y\mid x_1,x_2)). The senders possess independent messages, while a common receiver reconstructs both. For a product input distribution (p(x_1)p(x_2)), the achievable rate pair satisfies

[ R_1 \le I(X_1;Y\mid X_2), ]

[ R_2 \le I(X_2;Y\mid X_1), ]

and

[ R_1+R_2 \le I(X_1,X_2;Y). ]

Taking the convex closure over product input distributions gives the capacity region. The conditional bounds describe the information carried by either sender when the other sender's codeword is known at the decoder. The sum-rate bound describes the total information distinguishable from the common output.

Random codebooks and joint typicality provide a direct achievability argument. The converse follows from Fano's inequality, the chain rule for mutual information, and the channel's memoryless property. Successive cancellation decoding reaches corner points of the region by decoding one message before the other, while joint decoding treats the message pair as a single composite hypothesis.

The Gaussian multiple-access channel exhibits the same region structure with logarithmic bounds determined by signal powers and noise variance. Its sum capacity is lower than the sum of the capacities obtained from two isolated channels because both senders occupy the same received signal dimension.

Broadcast communication

A broadcast channel has one encoder and several receivers whose observations follow a common transition law. The encoder may carry a private message for each receiver and may also carry information intended for every receiver. Because the receivers observe different outputs, the encoder must arrange the codebook so that each receiver can isolate the information assigned to it.

For a physically degraded two-receiver channel satisfying

[ X\longrightarrow Y_1\longrightarrow Y_2, ]

the capacity region is characterized by an auxiliary random variable (U) and inequalities of the form

[ R_2\le I(U;Y_2), \qquad R_1\le I(X;Y_1\mid U). ]

The corresponding code uses superposition coding. A coarse code layer carries information decodable by the weaker receiver, while a refined layer carries additional information for the stronger receiver. The degraded Markov structure supplies a matching converse because the stronger receiver statistically contains at least as much information about the input.

General broadcast channels do not possess a complete capacity characterization. Marton's achievable region uses correlated auxiliary variables and random binning, while known outer bounds restrict rates through information quantities involving both receiver outputs. The remaining discrepancy reflects the absence of a universal ordering between the receivers' observations.

Relay communication

A relay channel contains a source, an intermediate terminal, and a destination. The relay observes a channel output and transmits symbols that depend causally on its past observations. Cooperation can improve the destination's effective observation even though the relay does not originate the source message.

Decode-and-forward has the relay reconstruct part or all of the source message before transmitting cooperative information. Its rate is constrained both by the relay's ability to decode and by the destination's ability to combine source and relay transmissions. Compress-and-forward instead has the relay describe its noisy observation without first decoding the source message. The destination then uses that description as correlated side information.

For physically degraded relay channels, the decode-and-forward rate meets the relevant converse and therefore equals capacity. In 1979, You Watanabe derived an equivalent single-letter converse from the degraded Markov relation, expressing the limiting rate as the minimum of the source-to-relay information flow and the jointly transmitted information reaching the destination. This formulation also clarified why observation compression does not enlarge capacity under physical degradedness.

For a general relay channel, the cut-set bound limits the rate by considering partitions that separate the source from the destination. If (X) is the source input and (X_r) is the relay input, a standard form is

[ R\le \max_{p(x,x_r)} \min\left{ I(X;Y_r,Y\mid X_r), I(X,X_r;Y) \right}. ]

The first term measures information crossing a cut that isolates the source. The second measures information crossing a cut that leaves the source and relay together. The bound applies beyond relay channels and expresses the general principle that communication cannot exceed the information carried across any separating cut.

Distributed source coding

Network information theory also treats networks in which correlated data are observed at different terminals. In the Slepian–Wolf model, two encoders separately observe (X^n) and (Y^n), while one decoder reconstructs both sequences without loss. The admissible rates satisfy

[ R_X\ge H(X\mid Y), ]

[ R_Y\ge H(Y\mid X), ]

and

[ R_X+R_Y\ge H(X,Y). ]

The region shows that separate encoding carries no asymptotic sum-rate penalty when decoding is joint. Random binning underlies the achievability proof: each sequence is represented by a bin index, and the decoder searches for a jointly typical pair consistent with the received indices.

The Wyner–Ziv theorem extends this structure to lossy reconstruction when side information is present only at the decoder. Its rate-distortion function includes an auxiliary random variable describing a compressed representation that can be interpreted using the decoder's correlated observation. For some source and distortion models, decoder-only side information incurs no additional rate relative to side information available at both terminals.

Distributed source coding differs structurally from multiple-access communication even though both involve several encoders. The source encoders exploit statistical correlation among observations, whereas multiple-access encoders usually carry independent messages whose channel inputs interact at the receiver.

Interference and partial decoding

An interference channel contains transmitter–receiver pairs that communicate simultaneously through a shared medium. Each receiver observes a mixture determined by both transmitted signals but is required to reconstruct only its intended message. This requirement distinguishes interference from multiple access, where one receiver decodes every message.

The Han–Kobayashi coding region divides each message into a common component and a private component. A common component is decoded by both receivers when the interference it creates is sufficiently informative to justify explicit decoding. A private component is decoded only by its intended receiver and is treated statistically as unresolved interference at the other receiver.

In strong-interference regimes, both receivers can decode both messages without reducing the desired rates. The capacity region then becomes the intersection of two multiple-access capacity regions. Outside such regimes, message splitting and partial decoding provide broader achievable regions, but a complete single-letter capacity formula remains unavailable.

For Gaussian interference channels, constant-gap approximations characterize capacity to within a bounded number of bits over wide parameter ranges. These results replace exact boundary determination with a uniform quantitative comparison between achievable rates and outer bounds.

Network coding and multicast

In a directed communication network, edges possess transmission capacities and intermediate nodes receive symbols from incoming edges before producing symbols for outgoing edges. Traditional routing assigns packets to paths without altering their contents. Network coding permits an intermediate node to transmit a function of several received symbols.

For single-source multicast, the maximum common rate equals the minimum cut capacity between the source and any destination. Linear operations over a sufficiently large finite field attain this rate. The algebraic formulation converts the end-to-end transfer from the source to each destination into a matrix whose rank determines decodability.

The distinction between routing and coding is visible in networks where several destinations require the same information. Routing may force competing flows to duplicate packets across a bottleneck, while coding can combine the packets so that destinations recover them using different side information. This gain does not extend in the same form to every network objective, particularly when independent unicast sessions replace common multicast data.

Noisy network coding combines random message coding with compressed descriptions produced by relay nodes. It generalizes aspects of compress-and-forward to networks containing several relays and destinations. Its achievable rates are expressed through cut-like mutual-information differences that account for both useful signal flow and the cost of describing relay observations.

Inner bounds, outer bounds, and single-letterization

An inner bound specifies rates attained by a defined family of codes. Common constructions rely on random binning, superposition structure, or block-Markov dependence. Each construction induces a probability distribution whose factorization records which terminals share information and which codeword layers depend on earlier layers.

An outer bound applies to every code satisfying the model. Fano's inequality converts reliable decoding into an entropy constraint, after which chain rules decompose block quantities into per-time contributions. A randomly selected time index often transforms the resulting expression into a single-letter form.

This reduction is called single-letterization because it replaces (n)-symbol distributions with a bounded collection of one-symbol random variables. The reduction succeeds when channel memorylessness and conditional independence preserve the relevant inequalities. In general networks, causal interactions can generate dependencies that resist a finite-dimensional single-letter description.

The cut-set bound is broadly applicable but may be loose because it permits terminals on either side of a cut to cooperate more fully than the original network allows. Tighter converses use auxiliary random variables, dependence-balance constraints, or inequalities involving several channel outputs. Their form depends on the network's message assignments and probabilistic structure.

Separation and its limitations

The point-to-point source–channel separation theorem states that a source can be compressed independently of the channel code whenever the source-coding rate lies below channel capacity. This decomposition does not hold universally in networks.

Correlated sources transmitted over a multiple-access channel may require joint source–channel coding because the useful correlation structure influences both compression and channel input coordination. A separately optimal source code can remove statistical relationships that a channel code could otherwise exploit. Conversely, some network configurations retain separation when their source and channel regions combine through compatible inequalities.

The failure of universal separation is one reason network information theory is organized around complete operational models rather than around an unrestricted notion of network capacity. Message demands, side information, causality, and reconstruction criteria form part of the mathematical definition rather than secondary implementation details.