Information Theory
Network Information Theory
When 50 phones connect to one 5G base station, how much can each receive? Network information theory answers exactly. The answer is not 'share equally' but something far richer and more interesting.
- **NOMA in 5G** (Non-Orthogonal Multiple Access) implements superposition coding, the information-theoretic optimum for broadcast. Users close to the base station help the far ones.
- **Wi-Fi 6 OFDMA** allocates the frequency budget close to the MAC capacity region.
- **Interference alignment** (Motahari, 2008) showed that with N user pairs each can transmit at (1/2) log P regardless of N. A surprising statement about cooperative use of interference.
Предварительные знания
Multi-user channels
Classical Shannon theory has one sender and one receiver. Real networks are messier: many users share one medium (Wi-Fi), a single transmitter serves many listeners (TV), signals collide with each other (cellular cells). Network information theory studies these cases. The central object is the 'capacity region': the set of rate tuples (R_1, R_2, ...) that all users can sustain simultaneously.
**Multiple Access Channel (MAC):** K users transmit to one receiver. The capacity region is defined by conditions of the form: for every subset S of users, sum_{i in S} R_i <= I(X_S; Y | X_{S^c}). The region is a convex polytope. Each vertex is reached by successive interference cancellation (SIC).
| Topology | Example | Capacity | Difficulty |
|---|---|---|---|
| MAC (many -> one) | Wi-Fi uplink | Known exactly | Low |
| Broadcast (one -> many) | Wi-Fi downlink, TV | Known exactly (Gaussian) | Medium |
| Relay | Mesh networks | Partially known | High |
| Interference | 4G/5G cells | Mostly open! | Very high |
Historical note
Network information theory started with Ahlswede (1971) and Cover (1972). After 50 years of research the capacity of the general interference channel is still unknown. It is one of the great open problems of information theory.
In a multi-user channel each user has its own independent capacity C.
Users share a single capacity. The capacity region is the set of admissible combinations (R_1, R_2, ...), not a vector of independent ceilings.
There is one physical channel and signals overlap on it. The total information carried is bounded by the joint capacity, and must be partitioned.
For a two-user MAC the constraint sum R_i <= I(X_1, X_2; Y) means:
Broadcast channels
Broadcast channel: one transmitter, several receivers with different channel qualities, each wanting its own message. The optimal strategy is superposition coding: the 'weak' receiver decodes only the lower layer, the 'strong' one decodes both layers. That is exactly what LTE does when serving users close to and far from the base station.
**Gaussian broadcast:** one transmitter at power P, receiver 1 with SNR_1 > SNR_2 (receiver 2). Optimal scheme: X = sqrt(alpha) X_1 + sqrt(1 - alpha) X_2 (superposition). Receiver 1 (strong) decodes X_2, subtracts it (SIC), then decodes X_1. The Gaussian broadcast capacity is known exactly; the general discrete case is not.
| Scheme | Description | Where used | Optimality |
|---|---|---|---|
| TDMA | Take turns in time | Legacy 2G | Suboptimal |
| FDMA | Split in frequency | 3G, DSL | Suboptimal |
| Superposition coding | Layered superposition | LTE NOMA, DVB | Optimal |
| NOMA | Non-Orthogonal MA | 5G research | Near optimal |
Historical note
Thomas Cover determined the capacity of the Gaussian broadcast channel in 1972. Superposition coding now appears in DVB-T2 (digital TV) and is being studied for 5G NOMA. The capacity of the general discrete broadcast channel is still open.
A broadcast channel is just several independent point-to-point channels.
A broadcast channel has one transmitter and shared power. Physically every signal reaches every receiver.
You cannot beam different signals to different users 'separately' in a wireless medium. Superposition is a fact of physics.
Why is superposition coding more efficient than TDMA on a broadcast channel?
Relay channels
Relay channel (van der Meulen, 1971): a relay node sits between source and destination. It can 'overhear' part of the source signal and forward information. Three main strategies: decode-and-forward (DF), compress-and-forward (CF), amplify-and-forward (AF). None is optimal in general. The capacity of the relay channel is still unknown.
**Decode-and-Forward:** the relay decodes the source message, re-encodes, and retransmits. Rate R <= min(I(X; Y_relay), I(X, X_relay; Y)). **Compress-and-Forward:** the relay compresses its observation and forwards it. **Cut-set bound:** R <= max over p(x, x_relay) of min(I(X, X_relay; Y), I(X; Y, Y_relay | X_relay)) - an upper bound on capacity.
| Strategy | Advantage | Drawback | Where used |
|---|---|---|---|
| Decode-and-Forward | Optimal when SR is strong | Requires full decoding at relay | Cooperative comm. |
| Compress-and-Forward | Flexible, works at weak SR | More complex | Sensor networks |
| Amplify-and-Forward | Simple, zero delay | Amplifies noise | LTE heterogeneous nets |
| Cut-set bound | Upper bound | Often not tight | Theoretical limit |
Historical note
Relay channel capacity is an open problem from 1971. The 'degraded relay' special case was solved by Cover and El Gamal in 1979. Wi-Fi mesh and cooperative communication in LTE are practical applications of relay-channel ideas.
A relay always improves channel capacity.
A relay can fail to improve, or even hurt, capacity if it adds interference or delay.
The relay signal can interfere with the source signal at the destination. Proper coordination requires care.
Why is decode-and-forward not always better than amplify-and-forward at a relay?
Interference channel
Interference channel: two transmitters send to two receivers, but their signals collide. This models cellular networks: one subscriber's phone interferes with the neighboring cell. The general capacity is one of the greatest open problems of information theory. Partial results exist: capacity is known exactly under strong interference; under weak interference it remains open.
**Interference channel:** under 'strong interference' (a >= 1 + P_1) both receivers decode both messages (TIN, treating interference as noise, is suboptimal). Under 'weak interference' TIN is optimal: just treat interference as noise. Han-Kobayashi (1981) is the best known inner bound. Capacity gap <= 1 bit/s/Hz (El Gamal, Costa, 1982).
| Interference regime | Optimal scheme | Capacity known? |
|---|---|---|
| None (a = 0) | Independent coding | Yes (immediate) |
| Weak (a < 1) | TIN (treat as noise) | No (open problem) |
| Strong (a >= 1 + P) | Joint decoding | Yes |
| Mixed (0.5 <= a <= 1) | Han-Kobayashi | No |
Historical note
The interference channel is the oldest open problem in information theory. Early work: Shannon (1961), Ahlswede (1981). In 2008 Motahari and Khandani showed that interference alignment achieves sum capacity (1/2) log P at high SNR. A breakthrough, but not a full solution.
The interference channel capacity has been known for a long time. It is an easy problem.
The general interference channel capacity is one of the greatest open problems of information theory, despite 60 years of work.
Inner bounds (Han-Kobayashi) keep improving, but proving tightness across all parameter regimes has been out of reach.
TIN (treat interference as noise) on an interference channel is:
Takeaways
- **MAC (Multiple Access Channel):** K users -> one receiver. Capacity region is a convex polytope, reached by successive cancellation.
- **Broadcast:** one -> many. Superposition coding is optimal in the Gaussian case.
- **Relay:** a relay assists the transmission. The general relay capacity is unknown. DF, CF, AF are different strategies.
- **Interference:** mutual interference between pairs. The oldest open problem of information theory. 60 years in, no full solution.
Related topics
Network IT unifies channels, coding, and joint typicality.
- Channel and capacity — The base case: one sender, one receiver.
- Typical sequences and AEP — Joint typicality is the proof tool of network IT.
- Information theory at interviews — MAC and broadcast are advanced system-design questions.
Вопросы для размышления
- The interference channel capacity is open after 60 years. What does that say about multi-user systems compared to single-channel ones?
- How does Wi-Fi 6 borrow from network information theory? What is 'optimal' in it from an information-theoretic point of view?
- Interference alignment shows that with N user pairs each can sustain (1/2) log P. Why is that 'surprising', and what does it mean in practice?