Cambridge University Press Information Theory, Inference, And Learning Algorithms - Mackay.pdf

Information Theory, Inference, and Learning Algorithms
David . MacKay
Information Theory,
Inference,
and Learning Algorithms
David . MacKay
******@
c 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004

c Cambridge University Press 2003

Version (third printing) August 25, 2004
Please send feedback on this book via
./
Version of this book was published by . in September 2003. It will
remain viewable on-screen on the above website, in postscript, djvu, and pdf
formats.
In the second printing (version ) minor typos were corrected, and the book
design was slightly altered to modify the placement of section numbers.
In the third printing (version ) minor typos were corrected, and chapter 8
was renamed ‘Dependent random variables’(instead of ‘Correlated’).
(. replace this page with their own page ii.)
Contents
Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
1 Introduction to Information Theory . . . . . . . . . . . . . 3
2 Probability, Entropy, and Inference . . . . . . . . . . . . . . 22
3 More about Inference . . . . . . . . . . . . . . . . . . . . . 48
I pression . . . . . . . . . . . . . . . . . . . . . . 65
4 The Source Coding Theorem . . . . . . . . . . . . . . . . . 67
5 Symbol Codes . . . . . . . . . . . . . . . . . . . . . . . . . 91
6 Stream Codes . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7 Codes for Integers . . . . . . . . . . . . . . . . . . . . . . . 132
II Noisy-Channel Coding . . . . . . . . . . . . . . . . . . . . 137
8 Dependent Random Variables . . . . . . . . . . . . . . . . . 138
munication over a Noisy Channel . . . . . . . . . . . . 146
10 The Noisy-Channel Coding Theorem . . . . . . . . . . . . . 162
11 Error-Correcting Codes and Real Channels . . . . . . . . . 177
III Further Topics in Information Theory . . . . . . . . . . . . . 191
12 Hash Codes: Codes for Efficient Information