First published in print format 2009 ISBN-13 978-0-511-50684-0 eBook (EBL) ISBN-13 978-0-521-88171-5 hardback Cambridge University Press has no responsibility for the persistence or accuracy of urls for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate. Contents Foreword page xi Introduction Acknowledgments Probability basics Events, event space, and probabilities 1.2 Combinatorics Combined, joint, and conditional probabilities 1.4 Exercises Probability distributions Mean and variance Exponential, Poisson, and binomial distributions Continuous distributions Uniform, exponential, and Gaussian (normal) distributions Central-limit theorem 2.6 Exercises Measuring information Making sense of information Measuring information Information bits Rényi's fake coin 3.5 Exercises Entropy From Boltzmann to Shannon Entropy in dice Language entropy Maximum entropy (discrete source) 4.5 Exercises Contents Mutual information and more entropies Joint and conditional entropies Mutual information Relative entropy 5.4 Exercises Differential entropy Entropy of continuous sources 6.2 Maximum entropy (continuous source) 6.3 Exercises Algorithmic entropy and Kolmogorov complexity Defining algorithmic entropy The Turing machine Universal Turing machine Kolmogorov complexity 7.5 Kolmogorov complexity VS. Shannon's entropy 7.6 Exercises Information coding Coding numbers Coding language The Morse code Mean code length and coding efficiency Optimizing coding efficiency 8.6 Shannon's source-coding theorem 8.7 Exercises Optimal coding and compression Huffman codes 9.2 Data compression Block codes 9.4 Exercises Integer, arithmetic, and adaptive coding 10.1 Integer coding Arithmetic coding Adaptive Huffman coding 10.4 Lempel-Ziv coding 10.5 Exercises Contents Error coszrrection Communication channel Linear block codes 11.3 Cyclic codes Error-correction code types Corrected bit-error-rate 11.6 Exercises Channel entropy Bina