2 - Fundamentals of information theory

Summary

We begin with a brief overview of some of the fundamental concepts and mathematical tools of information theory. This allows us to establish notation and to set the stage for the results presented in subsequent chapters. For a comprehensive introduction to the fundamental concepts and methods of information theory, we refer the interested reader to the textbooks of Gallager [2], Cover and Thomas [3], Yeung [4], and Csiszár and Körner [5].

The rest of the chapter is organized as follows. Section 2.1 provides an overview of the basic mathematical tools and metrics that are relevant for subsequent chapters. Section 2.2 illustrates the fundamental proof techniques used in information theory by discussing the point-to-point communication problem and Shannon's coding theorems. Section 2.3 is entirely devoted to network information theory, with a special emphasis on distributed source coding and multi-user communications as they relate to information-theoretic security.

Mathematical tools of information theory

The following subsections describe a powerful set of metrics and tools that are useful to characterize the fundamental limits of communication systems. All results are stated without proof through a series of lemmas and theorems, and we refer the reader to standard textbooks [2, 3, 4] for details. Unless specified otherwise, all random variables and random vectors used throughout this book are real-valued random vectors.

Useful bounds

We start by recalling a few inequalities that are useful to bound the probabilities of rare events.