| |
| |
| 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 | |
| |
| |
| |
| Noiseless Binary Channel | |
| |
| |
| |
| Noisy Channel with Nonoverlapping Outputs | |
| |
| |
| |
| Noisy Typewriter | |
| |
| |
| |
| Binary Symmetric Channel | |
| |
| |
| |
| Binary Erasure Channel | |
| |
| |
| |
| 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 | |
| |
| |
| |
| Binary Source | |
| |
| |
| |
| Gaussian Source | |
| |
| |
| |
| Simultaneous Description of Independent Gaussian Random Variables | |
| |
| |
| |
| 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 Cramer-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 | |
| |
| |
| |
| Sliding Window Lempel-Ziv Algorithm | |
| |
| |
| |
| Tree-Structured Lempel-Ziv Algorithms | |
| |
| |
| |
| Optimality of Lempel-Ziv Algorithms | |
| |
| |
| |
| Sliding Window Lempel-Ziv Algorithms | |
| |
| |
| |
| Optimality of Tree-Structured Lempel-Ziv 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 | |
| |
| |
| |
| [Omega] | |
| |
| |
| |
| 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 | |
| |
| |
| |
| Single-User Gaussian Channel | |
| |
| |
| |
| Gaussian Multiple-Access Channel with m Users | |
| |
| |
| |
| Gaussian Broadcast Channel | |
| |
| |
| |
| Gaussian Relay Channel | |
| |
| |
| |
| Gaussian Interference Channel | |
| |
| |
| |
| Gaussian Two-Way Channel | |
| |
| |
| |
| Jointly Typical Sequences | |
| |
| |
| |
| Multiple-Access Channel | |
| |
| |
| |
| Achievability of the Capacity Region for the Multiple-Access Channel | |
| |
| |
| |
| Comments on the Capacity Region for the Multiple-Access Channel | |
| |
| |
| |
| Convexity of the Capacity Region of the Multiple-Access Channel | |
| |
| |
| |
| Converse for the Multiple-Access Channel | |
| |
| |
| |
| m-User Multiple-Access Channels | |
| |
| |
| |
| Gaussian Multiple-Access Channels | |
| |
| |
| |
| Encoding of Correlated Sources | |
| |
| |
| |
| Achievability of the Slepian-Wolf Theorem | |
| |
| |
| |
| Converse for the Slepian-Wolf Theorem | |
| |
| |
| |
| Slepian-Wolf Theorem for Many Sources | |
| |
| |
| |
| Interpretation of Slepian-Wolf Coding | |
| |
| |
| |
| Duality Between Slepian-Wolf Encoding and Multiple-Access Channels | |
| |
| |
| |
| Broadcast Channel | |
| |
| |
| |
| Definitions for a Broadcast Channel | |
| |
| |
| |
| Degraded Broadcast Channels | |
| |
| |
| |
| Capacity Region for the Degraded 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 | |
| |
| |
| |
| Finite-Horizon Universal Portfolios | |
| |
| |
| |
| Horizon-Free Universal Portfolios | |
| |
| |
| |
| Shannon-McMillan-Breiman Theorem (General AEP) | |
| |
| |
| 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 | |