Information Theory
Network Information Theory
Цели урока
- Describe the MAC channel and compute its capacity region via subset constraints
- Explain superposition coding for the degraded broadcast channel
- Understand the principle of network coding and the max-flow min-cut theorem
- Know open problems in network information theory: interference channel, general BC
Предварительные знания
- Channel Capacity
- Mutual Information
How can multiple users share the same band without losing capacity? Where does information theory for networks remain open?
- 5G Massive MIMO: 64 antennas, 16 users - joint decoding on the boundary of MAC theory
- LTE NOMA: superposition coding for near and far users in the same band
- BitTorrent and RLNC: random linear network coding speeds P2P by 30-50%
- 5G CoMP: base-station coordination converts an interference channel to a MAC
From One Channel to Networks
Shannon (1948) solved the single-user channel. Network problems turned out to be fundamentally harder. MAC: solved by Ahlswede (1971) and Liao (1972) independently. Broadcast channel: partly solved by Bergmans (1974) for the degraded case. Interference channel: open since Ahlswede (1978). Network coding: revolution by Ahlswede-Cai-Li-Yeung (2000). Today active research: multi-hop networks, D2D, federated learning with limited communications.
Multiple Access Channel (MAC)
Ericsson uses MAC channel theory in Massive MIMO: with 64 base-station antennas and 16 simultaneous users, joint decoding achieves a sum rate of 500 Mbps over 20 MHz - operating on the boundary of Shannon's multiuser theory, which was opened not in 1948 but in 1971 by Ahlswede.
CDMA as a MAC Strategy
IS-95 CDMA (Qualcomm, 1995): each user multiplies the signal by a length-64 pseudorandom code. At the receiver: correlation with the user's code plus SIC. This is a MAC decoding implementation. With 10 users and ideal SIC, 90% of the sum bound C_12 is achieved; practical efficiency is 60-70% due to imperfect channel estimation.
MAC-BC duality: the capacity region of a Gaussian BC equals the dual MAC region at the same total power. This non-trivial result by Vishwanath and Tse (2003) allows BC problems to be solved via the simpler MAC.
How many constraints define the capacity region of a K-user MAC channel?
One constraint per non-empty S ⊆ {1,...,K}. At K=2: 3 constraints - a pentagon. At K=3: 7 constraints. The exponential growth makes the general problem hard.
Broadcast Channel and Superposition Coding
The MAC theorem is completely proved. The broadcast channel is not. After 50 years of research, the general BC capacity region remains open. Only for the degraded Gaussian BC is there a full solution - through superposition coding.
LTE and 5G implement superposition coding in NOMA (Non-Orthogonal Multiple Access): near and far users receive different powers in the same band. The near user (high SNR) performs SIC; the far user does not. This is a direct engineering realization of the BC theorem.
In superposition coding for the degraded BC, who performs SIC?
In the degraded BC, User 1 (strong, low noise N1) sees the signal at high SNR. It can first decode U1 (intended for the weak user), subtract, then decode U2. User 2 (weak) receives U1 directly without SIC - its SNR is insufficient to resolve U2.
Network Coding and the Max-Flow Min-Cut Theorem
Year 2000: Ahlswede, Cai, Li, and Yeung publish 'Network Information Flow'. Result: in networks with crossing flows, simple routing (forwarding) is suboptimal. Linear coding at intermediate nodes is needed - network coding. This opened a new class of information-theoretic problems.
BitTorrent and Random Linear Network Coding
BitTorrent uses a principle close to network coding: each peer transmits random linear combinations of file blocks. The receiver accumulates linearly independent packets and solves the system. This is RLNC (Random Linear Network Coding). Microsoft used RLNC in Avalanche (2005) for P2P distribution. Result: download speed 30-50% higher with the same number of seeders.
Why is simple routing suboptimal in the butterfly network?
In the butterfly network two receivers want (x1, x2) but through the middle edge only one bit can pass. Routing: either x1 or x2. Coding x1 XOR x2: each receiver has one of x1, x2 and recovers the other via XOR.
Interference Channel: an Open Problem
Interference channel: two transmitters to two receivers, each receiver wants only one message but receives both. This is the baseline model for Wi-Fi interference from neighboring access points. The problem has been open since 1978 - the general capacity region is unknown.
Etkin, Tse and Wang (2008) found a within-1-bit-per-second-per-Hz bound for all interference regimes. This is the best known result. In 5G, inter-cell interference is managed via CoMP (Coordinated Multi-Point): multiple base stations coordinate transmissions, turning the interference channel into a MAC. Gain: up to 30% capacity improvement at cell edges.
Why is the interference channel considered one of the major open problems in information theory?
The interference channel is solved only in extreme cases: very weak interference (treat as noise) and very strong interference (decode both). The general case has been open since Ahlswede's 1978 paper. Etkin-Tse-Wang (2008) gave the best known bound, but the exact solution remains elusive.
Connection to Other Topics
Network information theory combines: MAC channel (SIC achieves corner points of the multiuser region), BC duality with MAC, and network coding (generalizes max-flow min-cut from graph theory). In ML: federated learning with limited bandwidth is a MAC problem; multi-agent systems with partial observations use network information-theoretic principles.
- Channel Capacity — Single-user capacity is the special case n=1 of the multiuser MAC region
- Joint and Conditional Entropy — Multiuser bounds use conditional entropy of subsets of source variables
- Slepian-Wolf Theorem — Source-coding dual of network coding for correlated distributed sources
Итоги
- MAC: 2^K-1 constraints, SIC achieves corner points; sum rate = C(sum_P/N)
- Degraded BC: superposition coding + SIC at the strong user
- Network coding: XOR/linear combinations at nodes achieve max-flow min-cut
- Interference channel: open since 1978; solved only in extreme regimes
Вопросы для размышления
- Why is the MAC theorem fully proved while the broadcast and interference channels are not?
- How does network coding change the fundamental routing limitation in a network?
- What is the similarity and difference between the MAC channel and distributed compression of correlated sources?