El Gamal A., Kim Y.-H. Network Information Theory

Cambridge University Press, 2011. — 714 p.Network information theory aims to establish the fundamental limits on information flow in networks and the optimal coding schemes that achieve these limits. It extends Shannon’s fundamental theorems on point-to-point communication and the Ford–Fulkerson max-flow min-cut theorem for graphical unicast networks to general networks with multiple sources and destinations and shared resources. Although the theory is far from complete, many elegant results and techniques have been developed over the past forty years with potential applications in real-world networks. This book presents these results in a coherent and simplified manner that should make the subject accessible to graduate students and researchers in electrical engineering, computer science, statistics, and related fields, as well as to researchers and practitioners in industry.
The first paper on network information theory was on the two-way channel by Shannon. This was followed a decade later by seminal papers on the broadcast channel by Cover, the multiple access channel by Ahlswede and Liao, and distributed lossless compression by Slepian and Wolf. These results spurred a flurry of research on network information theory from the mid 1970s to the early 1980s with many new results and techniques developed; see the survey papers by van der Meulen and El Gamal and Cover, and the seminal book by Csiszar and Korner. However, many problems, including Shannon’s two-way channel, remained open and there was little interest in these results from communication theorists or practitioners. The period from the mid 1980s to the mid 1990s represents a lost decade for network information theory during which very few papers were published and many researchers shifted their focus to other areas. The advent of the Internet and wireless communication, fueled by advances in semiconductor technology, compression and error correction coding, signal processing, and computer science, revived the interest in this subject and there has been an explosion of activities in the field since the mid 1990s. In addition to progress on old open problems, recent work has dealt with new network models, new approaches to coding for networks, capacity approximations and scaling laws, and topics at the intersection of networking and information theory. Some of the techniques developed in network information theory, such as successive cancellation decoding, multiple description coding, successive refinement of information, and network coding, are being implemented in real-world networks.
The idea of writing this book started a long time ago when Tom Cover and the first author considered writing a monograph based on their aforementioned 1980 survey paper. The first author then put together a set of handwritten lecture notes and used them to teach a course on multiple user information theory at Stanford University from 1982 to 1984. In response to high demand from graduate students in communication and information theory, he resumed teaching the course in 2002 and updated the early lecture notes with recent results. These updated lecture notes were used also in a course at EPFL in the summer of 2003. In 2007 the second author, who was in the 2002 class, started teaching a similar course at UC San Diego and the authors decided to collaborate on expanding the lecture notes into a textbook. Various versions of the lecture notes have been used since then in courses at Stanford University, UC San Diego, the Chinese University of Hong Kong, UC Berkeley, Tsinghua University, Seoul National University, University of Notre Dame, and McGill University among others. The lecture notes were posted on the arXiv in January 2010. This book is based on these notes. Although we have made an effort to provide a broad coverage of the results in the field, we do not claim to be all inclusive. The explosion in the number of papers on the subject in recent years makes it almost impossible to provide a complete coverage in a single textbook.
We considered several high-level organizations of the material in the book, from source coding to channel coding or vise versa, from graphical networks to general networks, or along historical lines. We decided on a pedagogical approach that balances the introduction of new network models and new coding techniques. We first discuss single-hop networks and then multihop networks. Within each type of network, we first study channel coding, followed by their source coding counterparts, and then joint source–channel coding. There were several important topics that did not fit neatly into this organization, which we grouped under Extensions. The book deals mainly with discrete memoryless and Gaussian network models because little is known about the limits on information flow for more complex models. Focusing on these models also helps us present the coding schemes and proof techniques in their simplest possible forms.Preliminaries
Information Measures and Typicality
Point-to-Point Information Theory
Single-Hop Networks
Multiple Access Channel
Degraded Broadcast Channels
Interference Channels
Channels with State
General Broadcast Channels
Gaussian Vector Channels
Distributed Lossless Compression
Lossy Compression with Side Information
Distributed Lossy Compression
Multiple Description Coding
Joint Source–Channel Coding
Multihop Networks
Graphical Networks
Relay Channels
Interactive Channel Coding
Discrete Memoryless Networks
Gaussian Networks
Compression over Graphical Networks
Extensions
Communication for Computing
Information Theoretic Secrecy
Wireless Fading Channels
Networking and Information Theory
Appendices
Convex Sets and Functions
Probability and Estimation
Cardinality Bounding Techniques
Fourier–Motzkin Elimination
Convex Optimization