| |
| |
Preface to the Second Edition | |
| |
| |
Preface to the First Edition | |
| |
| |
Acknowledgments for the Second Edition | |
| |
| |
Acknowledgments for the First Edition | |
| |
| |
| |
Introduction and Preview | |
| |
| |
| |
Preview of the Book | |
| |
| |
| |
Entropy, Relative Entropy, and Mutual Information | |
| |
| |
| |
Entropy | |
| |
| |
| |
Joint Entropy and Conditional Entropy | |
| |
| |
| |
Relative Entropy and Mutual Information | |
| |
| |
| |
Relationship Between Entropy and Mutual Information | |
| |
| |
| |
Chain Rules for Entropy, Relative Entropy, and Mutual Information | |
| |
| |
| |
Jensen's Inequality and Its Consequences | |
| |
| |
| |
Log Sum Inequality and Its Applications | |
| |
| |
| |
Data-Processing Inequality | |
| |
| |
| |
Sufficient Statistics | |
| |
| |
| |
Fano's Inequality | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Historical Notes | |
| |
| |
| |
Asymptotic Equipartition Property | |
| |
| |
| |
Asymptotic Equipartition Property Theorem | |
| |
| |
| |
Consequences of the AEP: Data Compression | |
| |
| |
| |
High-Probability Sets and the Typical Set | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Historical Notes | |
| |
| |
| |
Entropy Rates of a Stochastic Process | |
| |
| |
| |
Markov Chains | |
| |
| |
| |
Entropy Rate | |
| |
| |
| |
Example: Entropy Rate of a Random Walk on a Weighted Graph | |
| |
| |
| |
Second Law of Thermodynamics | |
| |
| |
| |
Functions of Markov Chains | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Historical Notes | |
| |
| |
| |
Data Compression | |
| |
| |
| |
Examples of Codes | |
| |
| |
| |
Kraft Inequality | |
| |
| |
| |
Optimal Codes | |
| |
| |
| |
Bounds on the Optimal Code Length | |
| |
| |
| |
Kraft Inequality for Uniquely Decodable Codes | |
| |
| |
| |
Huffman Codes | |
| |
| |
| |
Some Comments on Huffman Codes | |
| |
| |
| |
Optimality of Huffman Codes | |
| |
| |
| |
Shannon-Fano-Elias Coding | |
| |
| |
| |
Competitive Optimality of the Shannon Code | |
| |
| |
| |
Generation of Discrete Distributions from Fair Coins | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Historical Notes | |
| |
| |
| |
Gambling and Data Compression | |
| |
| |
| |
The Horse Race | |
| |
| |
| |
Gambling and Side Information | |
| |
| |
| |
Dependent Horse Races and Entropy Rate | |
| |
| |
| |
The Entropy of English | |
| |
| |
| |
Data Compression and Gambling | |
| |
| |
| |
Gambling Estimate of the Entropy of English | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Historical Notes | |
| |
| |
| |
Channel Capacity | |
| |
| |
| |
Examples of Channel Capacity | |
| |
| |
| |
Symmetric Channels | |
| |
| |
| |
Properties of Channel Capacity | |
| |
| |
| |
Preview of the Channel Coding Theorem | |
| |
| |
| |
Definitions | |
| |
| |
| |
Jointly Typical Sequences | |
| |
| |
| |
Channel Coding Theorem | |
| |
| |
| |
Zero-Error Codes | |
| |
| |
| |
Fano's Inequality and the Converse to the Coding Theorem | |
| |
| |
| |
Equality in the Converse to the Channel Coding Theorem | |
| |
| |
| |
Hamming Codes | |
| |
| |
| |
Feedback Capacity | |
| |
| |
| |
Source-Channel Separation Theorem | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Historical Notes | |
| |
| |
| |
Differential Entropy | |
| |
| |
| |
Definitions | |
| |
| |
| |
AEP for Continuous Random Variables | |
| |
| |
| |
Relation of Differential Entropy to Discrete Entropy | |
| |
| |
| |
Joint and Conditional Differential Entropy | |
| |
| |
| |
Relative Entropy and Mutual Information | |
| |
| |
| |
Properties of Differential Entropy, Relative Entropy, and Mutual Information | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Historical Notes | |
| |
| |
| |
Gaussian Channel | |
| |
| |
| |
Gaussian Channel: Definitions | |
| |
| |
| |
Converse to the Coding Theorem for Gaussian Channels | |
| |
| |
| |
Bandlimited Channels | |
| |
| |
| |
Parallel Gaussian Channels | |
| |
| |
| |
Channels with Colored Gaussian Noise | |
| |
| |
| |
Gaussian Channels with Feedback | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Historical Notes | |
| |
| |
| |
Rate Distortion Theory | |
| |
| |
| |
Quantization | |
| |
| |
| |
Definitions | |
| |
| |
| |
Calculation of the Rate Distortion Function | |
| |
| |
| |
Converse to the Rate Distortion Theorem | |
| |
| |
| |
Achievability of the Rate Distortion Function | |
| |
| |
| |
Strongly Typical Sequences and Rate Distortion | |
| |
| |
| |
Characterization of the Rate Distortion Function | |
| |
| |
| |
Computation of Channel Capacity and the Rate Distortion Function | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Historical Notes | |
| |
| |
| |
Information Theory and Statistics | |
| |
| |
| |
Method of Types | |
| |
| |
| |
Law of Large Numbers | |
| |
| |
| |
Universal Source Coding | |
| |
| |
| |
Large Deviation Theory | |
| |
| |
| |
Examples of Sanov's Theorem | |
| |
| |
| |
Conditional Limit Theorem | |
| |
| |
| |
Hypothesis Testing | |
| |
| |
| |
Chernoff-Stein Lemma | |
| |
| |
| |
Chernoff Information | |
| |
| |
| |
Fisher Information and the Cram�er-Rao Inequality | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Historical Notes | |
| |
| |
| |
Maximum Entropy | |
| |
| |
| |
Maximum Entropy Distributions | |
| |
| |
| |
Examples | |
| |
| |
| |
Anomalous Maximum Entropy Problem | |
| |
| |
| |
Spectrum Estimation | |
| |
| |
| |
Entropy Rates of a Gaussian Process | |
| |
| |
| |
Burg's Maximum Entropy Theorem | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Historical Notes | |
| |
| |
| |
Universal Source Coding | |
| |
| |
| |
Universal Codes and Channel Capacity | |
| |
| |
| |
Universal Coding for Binary Sequences | |
| |
| |
| |
Arithmetic Coding | |
| |
| |
| |
Lempel-Ziv Coding | |
| |
| |
| |
Optimality of Lempel-Ziv Algorithms | |
| |
| |
Compression | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Historical Notes | |
| |
| |
| |
Kolmogorov Complexity | |
| |
| |
| |
Models of Computation | |
| |
| |
| |
Kolmogorov Complexity: Definitions and Examples | |
| |
| |
| |
Kolmogorov Complexity and Entropy | |
| |
| |
| |
Kolmogorov Complexity of Integers | |
| |
| |
| |
Algorithmically Random and Incompressible Sequences | |
| |
| |
| |
Universal Probability | |
| |
| |
| |
Kolmogorov complexity | |
| |
| |
| |
Universal Gambling | |
| |
| |
| |
Occam's Razor | |
| |
| |
| |
Kolmogorov Complexity and Universal Probability | |
| |
| |
| |
Kolmogorov Sufficient Statistic | |
| |
| |
| |
Minimum Description Length Principle | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Historical Notes | |
| |
| |
| |
Network Information Theory | |
| |
| |
| |
Gaussian Multiple-User Channels | |
| |
| |
| |
Jointly Typical Sequences | |
| |
| |
| |
Multiple-Access Channel | |
| |
| |
| |
Encoding of Correlated Sources | |
| |
| |
| |
Duality Between Slepian-Wolf Encoding and Multiple-Access Channels | |
| |
| |
| |
Broadcast Channel | |
| |
| |
| |
Relay Channel | |
| |
| |
| |
Source Coding with Side Information | |
| |
| |
| |
Rate Distortion with Side Information | |
| |
| |
| |
General Multiterminal Networks | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Historical Notes | |
| |
| |
| |
Information Theory and Portfolio Theory | |
| |
| |
| |
The Stock Market: Some Definitions | |
| |
| |
| |
Kuhn-Tucker Characterization of the Log-Optimal Portfolio | |
| |
| |
| |
Asymptotic Optimality of the Log-Optimal Portfolio | |
| |
| |
| |
Side Information and the Growth Rate | |
| |
| |
| |
Investment in Stationary Markets | |
| |
| |
| |
Competitive Optimality of the Log-Optimal Portfolio | |
| |
| |
| |
Universal Portfolios | |
| |
| |
| |
Shannon-McMillan-Breiman Theorem | |
| |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Historical Notes | |
| |
| |
| |
Inequalities in Information Theory | |
| |
| |
| |
Basic Inequalities of Information Theory | |
| |
| |
| |
Differential Entropy | |
| |
| |
| |
Bounds on Entropy and Relative Entropy | |
| |
| |
| |
Inequalities for Types | |
| |
| |
| |
Combinatorial Bounds on Entropy | |
| |
| |
| |
Entropy Rates of Subsets | |
| |
| |
| |
Entropy and Fisher Information | |
| |
| |
| |
Entropy Power Inequality and Brunn-Minkowski Inequality | |
| |
| |
| |
Inequalities for Determinants | |
| |
| |
| |
Inequalities for Ratios of Determinants | |
| |
| |
Summary | |
| |
| |
Problems | |
| |
| |
Historical Notes | |
| |
| |
Bibliography | |
| |
| |
List of Symbols | |
| |
| |
Index | |