Elements of Information Theory 2nd Edition (Wiley Series in Telecommunications and Signal Processing)

The latest edition of this classic is updated with new problem sets and material The Second Edition of this fundamental textbook maintains the book's tradition of clear, thought-provoking instruction. Readers are provided once again with an instructive mix of mathematics, physics, statistics, and information theory. All the essential topics in information theory are covered in detail, including entropy, data compression, channel capacity, rate distortion, network information theory, and hypothesis testing. The authors provide readers with a solid understanding of the underlying theory and applications. Problem sets and a telegraphic summary at the end of each chapter further assist readers. The historical notes that follow each chapter recap the main points. The Second Edition features: * Chapters reorganized to improve teaching * 200 new problems * New material on source coding, portfolio theory, and feedback capacity * Updated references Now current and enhanced, the Second Edition of Elements of Information Theory remains the ideal textbook for upper-level undergraduate and graduate courses in electrical engineering, statistics, and telecommunications. An Instructor's Manual presenting detailed solutions to all the problems in the book is available from the Wiley editorial department. Cover......Page 1 Title page......Page 4 ISBN- 9780471241959 Copyright @ 2006 by John Wiley & Sons......Page 5 Contents......Page 6 Preface To The Second Edition......Page 16 Preface To The First Edition......Page 18 Acknowledgements for the Second Edition......Page 22 Acknowledgements for the first Edition......Page 24 1. Introduction and Preview......Page 26 1.1 Preview of the Book......Page 30 2.1 Entropy......Page 38 2.2 Joint Entropy and Conditional Entropy......Page 41 2.3 Relative Entropy and Mutual Information......Page 44 2.4 Relationship Between Entropy and Mutual Information......Page 45 2.5 Chain Rules for Entropy, Relative Entropy, and Mutual Information......Page 47 2.6 Jensen’s Inequality and Its Consequences......Page 50 2.7 Log Sum Inequality and Its Applications......Page 55 2.8 Data-Processing Inequality......Page 59 2.9 Sufficient Statistics......Page 60 2.10 Fano’s Inequality......Page 62 Summary......Page 66 Problems......Page 68 Historical Notes......Page 79 3. Asymptotic Equipartition Property......Page 82 3.1 Asymptotic Equipartition Property Theorem......Page 83 3.2 Consequences of the AEP: Data Compression......Page 85 3.3 High-Probability Sets and the Typical Set......Page 87 Problems......Page 89 Historical Notes......Page 94 4.1 Markov Chains......Page 96 4.2 Entropy Rate......Page 99 4.3 Example: Entropy Rate of a Random Walk on a Weighted Graph......Page 103 4.4 Second Law of Thermodynamics......Page 106 4.5 Functions of Markov Chains......Page 109 Summary......Page 112 Problems......Page 113 Historical Notes......Page 125 5.1 Examples of Codes......Page 128 5.2 Kraft Inequality......Page 132 5.3 Optimal Codes......Page 135 5.4 Bounds on the Optimal Code Length......Page 137 5.5 Kraft Inequality for Uniquely Decodable Codes......Page 140 5.6 Huffman Codes......Page 143 5.7 Some Comments on Huffman Codes......Page 145 5.8 Optimality of Huffman Codes......Page 148 5.9 Shannon–Fano–Elias Coding......Page 152 5.10 Competitive Optimality of the Shannon Code......Page 155 5.11 Generation of Discrete Distributions from Fair Coins......Page 159 Summary......Page 166 Problems......Page 167 Historical Notes......Page 182 6.1 The Horse Race......Page 184 6.2 Gambling and Side Information......Page 189 6.3 Dependent Horse Races and Entropy Rate......Page 191 6.4 The Entropy of English......Page 193 6.5 Data Compression and Gambling......Page 196 6.6 Gambling Estimate of the Entropy of English......Page 198 Summary......Page 200 Problems......Page 201 Historical Notes......Page 207 7. Channel Capacity......Page 208 7.1.1 Noiseless Binary Channel......Page 209 7.1.2 Noisy Channel with Nonoverlapping Outputs......Page 210 7.1.3 Noisy Typewriter......Page 211 7.1.4 Binary Symmetric Channel......Page 212 7.1.5 Binary Erasure Channel......Page 213 7.2 Symmetric Channels......Page 214 7.4 Preview of the Channel Coding Theorem......Page 216 7.5 Definitions......Page 217 7.6 Jointly Typical Sequences......Page 220 7.7 Channel Coding Theorem......Page 224 7.8 Zero-Error Codes......Page 230 7.9 Fano’s Inequality and the Converse to the Coding Theorem......Page 231 7.10 Equality in the Converse to the Channel Coding Theorem......Page 233 7.11 Hamming Codes......Page 235 7.12 Feedback Capacity......Page 241 7.13 Source–Channel Separation Theorem......Page 243 Summary......Page 247 Problems......Page 248 Historical Notes......Page 265 8.1 Definitions......Page 268 8.2 AEP for Continuous Random Variables......Page 270 8.3 Relation of Differential Entropy to Discrete Entropy......Page 272 8.4 Joint and Conditional Differential Entropy......Page 274 8.5 Relative Entropy and Mutual Information......Page 275 8.6 Properties of Differential Entropy, Relative Entropy, and Mutual Information......Page 277 Problems......Page 281 Historical Notes......Page 284 9. Gaussian Channel......Page 286 9.1 Gaussian Channel: Definitions......Page 288 9.2 Converse to the Coding Theorem for Gaussian Channels......Page 293 9.3 Bandlimited Channels......Page 295 9.4 Parallel Gaussian Channels......Page 299 9.5 Channels with Colored Gaussian Noise......Page 302 9.6 Gaussian Channels with Feedback......Page 305 Summary......Page 314 Problems......Page 315 Historical Notes......Page 324 10.1 Quantization......Page 326 10.2 Definitions......Page 328 10.3.1 Binary Source......Page 332 10.3.2 Gaussian Source......Page 335 10.3.3 Simultaneous Description of Independent GaussianRandom Variables......Page 337 10.4 Converse to the Rate Distortion Theorem......Page 340 10.5 Achievability of the Rate Distortion Function......Page 343 10.6 Strongly Typical Sequences and Rate Distortion......Page 350 10.7 Characterization of the Rate Distortion Function......Page 354 10.8 Computation of Channel Capacity and the Rate Distortion Function......Page 357 Summary......Page 360 Problems......Page 361 Historical Notes......Page 370 11.1 Method of Types......Page 372 11.2 Law of Large Numbers......Page 380 11.3 Universal Source Coding......Page 382 11.4 Large Deviation Theory......Page 385 11.5 Examples of Sanov’s Theorem......Page 389 11.6 Conditional Limit Theorem......Page 391 11.7 Hypothesis Testing......Page 400 11.8 Chernoff–Stein Lemma......Page 405 11.9 Chernoff Information......Page 409 11.10 Fisher Information and the Cram ́er–Rao Inequality......Page 417 Summary......Page 422 Problems......Page 424 Historical Notes......Page 433 12.1 Maximum Entropy Distributions......Page 434 12.2 Examples......Page 436 12.3 Anomalous Maximum Entropy Problem......Page 438 12.4 Spectrum Estimation......Page 440 12.5 Entropy Rates of a Gaussian Process......Page 441 12.6 Burg’s Maximum Entropy Theorem......Page 442 Summary......Page 445 Problems......Page 446 Historical Notes......Page 450 13. Universal Source Coding......Page 452 13.1 Universal Codes and Channel Capacity......Page 453 13.2 Universal Coding for Binary Sequences......Page 458 13.3 Arithmetic Coding......Page 461 13.4 Lempel–Ziv Coding......Page 465 13.4.1 Sliding Window Lempel–Ziv Algorithm......Page 466 13.4.2 Tree-Structured Lempel–Ziv Algorithms......Page 467 13.5.1 Sliding Window Lempel–Ziv Algorithms......Page 468 13.5.2 Optimality of Tree-Structured Lempel–Ziv Compression......Page 473 Summary......Page 481 Problems......Page 482 Historical Notes......Page 486 14. Kolmogorov Complexity......Page 488 14.1 Models of Computation......Page 489 14.2 Kolmogorov Complexity: Definitions and Examples......Page 491 14.3 Kolmogorov Complexity and Entropy......Page 498 14.4 Kolmogorov Complexity of Integers......Page 500 14.5 Algorithmically Random and Incompressible Sequences......Page 501 14.6 Universal Probability......Page 505 14.7 Kolmogorov complexity......Page 507 14.8 \Omega......Page 509 14.9 Universal Gambling......Page 512 14.10 Occam’s Razor......Page 513 14.11 Kolmogorov Complexity and Universal Probability......Page 515 14.12 Kolmogorov Sufficient Statistic......Page 521 14.13 Minimum Description Length Principle......Page 525 Summary......Page 526 Problems......Page 528 Historical Notes......Page 532 15. Network Information Theory......Page 534 15.1.1 Single-User Gaussian Channel......Page 538 15.1.2 Gaussian Multiple-Access Channel with m Users......Page 539 15.1.3 Gaussian Broadcast Channel......Page 540 15.1.4 Gaussian Relay Channel......Page 541 15.1.5 Gaussian Interference Channel......Page 543 15.1.6 Gaussian Two-Way Channel......Page 544 15.2 Jointly Typical Sequences......Page 545 15.3 Multiple-Access Channel......Page 549 15.3.1 Achievability of the Capacity Region for the Multiple-Access Channel......Page 555 15.3.2 Comments on the Capacity Region for theMultiple-Access Channel......Page 557 15.3.3 Convexity of the Capacity Region of the Multiple-AccessChannel......Page 559 15.3.4 Converse for the Multiple-Access Channel......Page 563 15.3.5 m-User Multiple-Access Channels......Page 568 15.3.6 Gaussian Multiple-Access Channels......Page 569 15.4 Encoding of Correlated Sources......Page 574 15.4.1 Achievability of the Slepian–Wolf Theorem......Page 576 15.4.2 Converse for the Slepian–Wolf Theorem......Page 580 15.4.3 Slepian–Wolf Theorem for Many Sources......Page 581 15.4.4 Interpretation of Slepian–Wolf Coding......Page 582 15.5 Duality Between Slepian–Wolf Encoding and Multiple-Access Channels......Page 583 15.6 Broadcast Channel......Page 585 15.6.1 Definitions for a Broadcast Channel......Page 588 15.6.2 Degraded Broadcast Channels......Page 589 15.6.3 Capacity Region for the Degraded Broadcast Channel......Page 590 15.7 Relay Channel......Page 596 15.8 Source Coding with Side Information......Page 600 15.9 Rate Distortion with Side Information......Page 605 15.10 General Multiterminal Networks......Page 612 Summary......Page 619 Problems......Page 621 Historical Notes......Page 634 16.1 The Stock Market: Some Definitions......Page 638 16.2 Kuhn–Tucker Characterization of the Log-Optimal Portfolio......Page 642 16.3 Asymptotic Optimality of the Log-Optimal Portfolio......Page 644 16.4 Side Information and the Growth Rate......Page 646 16.5 Investment in Stationary Markets......Page 648 16.6 Competitive Optimality of the Log-Optimal Portfolio......Page 652 16.7 Universal Portfolios......Page 654 16.7.1 Finite-Horizon Universal Portfolios......Page 656 16.7.2 Horizon-Free Universal Portfolios......Page 663 16.8 Shannon–McMillan–Breiman Theorem (General AEP)......Page 669 Summary......Page 674 Problems......Page 677 Historical Notes......Page 680 17.1 Basic Inequalities of Information Theory......Page 682 17.2 Differential Entropy......Page 685 17.3 Bounds on Entropy and Relative Entropy......Page 688 17.4 Inequalities for Types......Page 690 17.5 Combinatorial Bounds on Entropy......Page 691 17.6 Entropy Rates of Subsets......Page 692 17.7 Entropy and Fisher Information......Page 696 17.8 Entropy Power Inequality and Brunn–Minkowski Inequality......Page 699 17.9 Inequalities for Determinants......Page 704 17.10 Inequalities for Ratios of Determinants......Page 708 Problems......Page 711 Historical Notes......Page 712 Bibliography......Page 714 List of Symbols......Page 748 A......Page 752 B......Page 753 C......Page 755 E......Page 758 G......Page 760 H......Page 761 I......Page 762 L......Page 763 M......Page 764 P......Page 767 R......Page 768 S......Page 769 T......Page 771 V......Page 772 Z......Page 773

The latest edition of this classic is updated with new problem sets and material

The Second Edition of this fundamental textbook maintains the book's tradition of clear, thought-provoking instruction. Readers are provided once again with an instructive mix of mathematics, physics, statistics, and information theory.

All the essential topics in information theory are covered in detail, including entropy, data compression, channel capacity, rate distortion, network information theory, and hypothesis testing. The authors provide readers with a solid understanding of the underlying theory and applications. Problem sets and a telegraphic summary at the end of each chapter further assist readers. The historical notes that follow each chapter recap the main points.

The Second Edition features:

• Chapters reorganized to improve teaching

• 200 new problems

• New material on source coding, portfolio theory, and feedback capacity

• Updated references

Now current and enhanced, the Second Edition of Elements of Information Theory remains the ideal textbook for upper-level undergraduate and graduate courses in electrical engineering, statistics, and telecommunications.

Booknews

The authors introduce the basic quantities of entropy, relative entropy, and mutual information and show how they arise as natural answers to questions of data compression, channel capacity, rate distortion, hypothesis testing, information flow in networks, and gambling. Accessible to students of communication theory, computer science, and statistics. Annotation c. Book News, Inc., Portland, OR (booknews.com)

"The latest edition of this classic is updated with new problem sets and material The Second Edition of this fundamental textbook maintains the book's tradition of clear, thought-provoking instruction. Readers are provided once again with an instructive mix of mathematics, physics, statistics, and information theory. All the essential topics in information theory are covered in detail, including entropy, data compression, channel capacity, rate distortion, network information theory, and hypothesis testing. The authors provide readers with a solid understanding of the underlying theory and applications. Problem sets and a telegraphic summary at the end of each chapter further assist readers. The historical notes that follow each chapter recap the main points. The Second Edition features: * Chapters reorganized to improve teaching * 200 new problems * New material on source coding, portfolio theory, and feedback capacity * Updated references Now current and enhanced, the Second Edition of Elements of Information Theory remains the ideal textbook for upper-level undergraduate and graduate courses in electrical engineering, statistics, and telecommunications. An Instructor's Manual presenting detailed solutions to all the problems in the book is available from the Wiley editorial department."--Publisher's website

The latest edition of this classic is updated with new problem sets and material
The Second Edition of this fundamental textbook maintains the book's tradition of clear, thought-provoking instruction. Readers are provided once again with an instructive mix of mathematics, physics, statistics, and information theory. All the essential topics in information theory are covered in detail, including entropy, data compression, channel capacity, rate distortion, network information theory, and hypothesis testing. The authors provide readers with a solid understanding of the underlying theory and applications. Problem sets and a telegraphic summary at the end of each chapter further assist readers. The historical notes that follow each chapter recap the main points. The Second Edition features:
* Chapters reorganized to improve teaching
* 200 new problems
* New material on source coding, portfolio theory, and feedback capacity
* Updated references Now current and enhanced, the Second Edition of Elements of Information Theory remains the ideal textbook for upper-level undergraduate and graduate courses in electrical engineering, statistics, and telecommunications.