| |
| |
| 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 | |