Preface | p. v |
Information Theory | |
Elementary Probability | p. 1 |
Introduction | p. 1 |
Events | p. 3 |
Conditional probability | p. 7 |
Independence | p. 11 |
Bernoulli trials | p. 13 |
An elementary counting principle | p. 15 |
On drawing without replacement | p. 17 |
Random variables and expected, or average, value | p. 18 |
The Law of Large Numbers | p. 22 |
Information and Entropy | p. 25 |
How is information quantified? | p. 25 |
Naming the units | p. 27 |
Information connecting two events | p. 29 |
The inevitability of Shannon's quantification of information | p. 30 |
Systems of events and mutual information | p. 33 |
Entropy | p. 40 |
Information and entropy | p. 43 |
Channels and Channel Capacity | p. 47 |
Discrete memoryless channels | p. 47 |
Transition probabilities and binary symmetric channels | p. 50 |
Input frequencies | p. 52 |
Channel capacity | p. 56 |
Proof of Theorem 3.4.3, on the capacity equations | p. 67 |
Coding Theory | p. 71 |
Encoding and decoding | p. 71 |
Prefix-condition codes and the Kraft-McMillan inequality | p. 75 |
Average code word length and Huffman's algorithm | p. 79 |
The validity of Huffman's algorithm | p. 86 |
Optimizing the input frequencies | p. 90 |
Error correction, maximum likelihood decoding, nearest code word decoding, and reliability | p. 95 |
Shannon's Noisy Channel Theorem | p. 106 |
Error correction with binary symmetric channels and equal source frequencies | p. 111 |
The information rate of a code | p. 115 |
Data Compression | |
Lossless Data Compression by Replacement Schemes | p. 119 |
Replacement via encoding scheme | p. 120 |
Review of the prefix condition | p. 123 |
Choosing an encoding scheme | p. 126 |
Shannon's method | p. 127 |
Fano's method | p. 130 |
Huffman's algorithm | p. 131 |
The Noiseless Coding Theorem and Shannon's bound | p. 134 |
Arithmetic Coding | p. 141 |
Pure zeroth-order arithmetic coding: dfwld | p. 142 |
Rescaling while encoding | p. 146 |
Decoding | p. 150 |
What's good about dfwld coding: the compression ratio | p. 155 |
What's bad about dfwld coding and some ways to fix it | p. 160 |
Supplying the source word length | p. 161 |
Computation | p. 162 |
Must decoding wait until encoding is completed? | p. 164 |
Implementing arithmetic coding | p. 167 |
Notes | p. 179 |
Higher-order Modeling | p. 181 |
Higher-order Huffman encoding | p. 182 |
The Shannon bound for higher-order encoding | p. 186 |
Higher-order arithmetic coding | p. 191 |
Statistical models, statistics, and the possibly unknowable truth | p. 193 |
Probabilistic finite state source automata | p. 197 |
Adaptive Methods | p. 205 |
Adaptive Huffman encoding | p. 206 |
Compression and readjustment | p. 209 |
Higher-order adaptive Huffman encoding | p. 210 |
Maintaining the tree in adaptive Huffman encoding: the method of Knuth and Gallager | p. 212 |
Gallager's method | p. 215 |
Knuth's algorithm | p. 216 |
Adaptive arithmetic coding | p. 219 |
Interval and recency rank encoding | p. 221 |
Interval encoding | p. 221 |
Recency rank encoding | p. 224 |
Dictionary Methods | p. 229 |
LZ77 (sliding window) schemes | p. 230 |
An LZ77 implementation | p. 232 |
Case study: GNU zip | p. 235 |
The LZ78 approach | p. 237 |
The LZW variant | p. 240 |
Case study: Unix compress | p. 242 |
Notes | p. 244 |
Transform Methods and Image Compression | p. 245 |
Transforms | p. 247 |
Periodic signals and the Fourier transform | p. 249 |
The Fourier transform and compression: an example | p. 256 |
The cosine and sine transforms | p. 267 |
A general orthogonal transform | p. 270 |
Summary | p. 271 |
Two-dimensional transforms | p. 273 |
The 2D Fourier, cosine, and sine transforms | p. 275 |
Matrix expressions for 2D transforms | p. 279 |
An application: JPEG image compression | p. 281 |
A brief introduction to wavelets | p. 291 |
2D Haar wavelets | p. 296 |
Notes | p. 300 |
Appendices | p. 303 |
JPEGtool User's Guide | p. 303 |
Using the tools | p. 304 |
Reference | p. 314 |
Obtaining Octave | p. 319 |
Source Listing for LZRW1-A | p. 321 |
Resources, Patents, and Illusions | p. 333 |
Resources | p. 333 |
Data compression and patents | p. 335 |
Illusions | p. 338 |
Notes on and Solutions to Some Exercises | p. 343 |
Bibliography | p. 357 |
Index | p. 361 |
Table of Contents provided by Rittenhouse. All Rights Reserved. |