Introduction to Information Theory and Data Compression Darrel Hankerson, Greg A. Harris, and Peter D. Johnson Jr.

Table of Contents

Part I: Information Theory

1.1 Introduction
1.2 Events
1.3 Conditional probability
1.4 Independence
1.5 Bernoulli trials
1.6 An elementary counting principle
1.7* On drawing without replacement
1.8 Random variables and expected, or average, value
1.9 The law of large numbers

2.1 Systems of events
2.2 Information
2.3 Entropy
2.4 Information and entropy

3.1 Discrete memoryless channels
3.2 Transition probabilities and binary symmetric channels
3.3 Input frequencies
3.4 Channel capacity
3.5* Proof of Theorem 3.4.1

4.1 Encoding and decoding
4.2 Prefix-condition codes and the Kraft-McMillan inequality
4.3 Average code word length and Huffman's algorithm
4.3.1 The validity of Huffman's algorithm
4.4 Optimizing the input frequencies
4.5 Error correction, maximum likelihood decoding, nearest code word decoding, and reliability
4.6 Shannon's Noisy Channel Theorem
4.7 Error correction with binary symmetric channels and equal source frequencies

Part II: Data Compression

5.1 Replacement via encoding scheme
5.2 Review of the prefix condition
5.3 How to choose an encoding scheme
5.3.1 Shannon's method
5.3.2 Fano's method
5.3.3 Huffman's algorithm
5.4 The Noiseless Coding Theorem and Shannon's bound

6.1 Pure zeroth-order arithmetic coding: dfwld
6.1.1 Rescaling while encoding
6.1.2 Decoding
6.2 What's good about dfwld coding: the compression ratio
6.3 What's bad about dfwld coding and some ways to fix it
6.3.1 Supplying the source word length
6.3.2 Computation
6.3.3 Must decoding wait until encoding is completed?
6.4 Implementing arithmetic coding
6.4.1 Use of integer arithmetic
6.4.2 Implementation and performance issues
6.5 Notes

7.1 Higher-order Huffman encoding
7.2 The Shannon bound for higher-order encoding
7.3 Higher-order arithmetic coding
7.4 Statistical models, statistics, and the possibly unknowable truth

8.1 Adaptive Huffman encoding
8.1.1 Compression and readjustment
8.1.2 Higher-order adaptive Huffman encoding
8.2 Maintaining the tree in adaptive Huffman encoding: the method of Knuth and Gallager
8.2.1 Gallager's method
8.2.2 Knuth's algorithm
8.3 Adaptive arithmetic coding
8.4 Interval and recency rank encoding
8.4.1 Interval encoding
8.4.2 Recency rank encoding

9.1 LZ77 (sliding window) schemes
9.1.1 An LZ77 implementation
9.1.2 Case study: GNU zip
9.2 The LZ78 approach
9.2.1 The LZW variant
9.2.2 Case study: Unix compress
9.3 Notes

10.1 Transforms
10.2 Periodic signals and the Fourier transform
10.2.1 The Fourier transform and compression: an example
10.3 The cosine and sine transforms
10.3.1 A general orthogonal transform
10.3.2 Summary
10.4 Two-dimensional transforms
10.4.1 The 2D Fourier, cosine, and sine transforms
10.4.2 Matrix expressions for 2D transforms
10.5 An application: JPEG image compression
10.6 A brief introduction to wavelets
10.6.1 2D Haar wavelets
10.7 Notes

A JPEGtool User's Guide (available for download)

A.1 Using the tools
A.2 Reference
A.3 Obtaining Octave

C Resources, Patents, and Illusions

C.1 Resources
C.2 Data compression and patents
C.3 Illusions

D Notes on the Exercises

Bibliography

Index