| |
| |
| Preface | |
| |
| |
| |
| Information Theory | |
| |
| |
| |
| Elementary Probability | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Events | |
| |
| |
| |
| Conditional probability | |
| |
| |
| |
| Independence | |
| |
| |
| |
| Bernoulli trials | |
| |
| |
| |
| An elementary counting principle | |
| |
| |
| |
| On drawing without replacement | |
| |
| |
| |
| Random variables and expected, or average, value | |
| |
| |
| |
| The Law of Large Numbers | |
| |
| |
| |
| Information and Entropy | |
| |
| |
| |
| How is information quantified? | |
| |
| |
| |
| Naming the units | |
| |
| |
| |
| Information connecting two events | |
| |
| |
| |
| The inevitability of Shannon's quantification of information | |
| |
| |
| |
| Systems of events and mutual information | |
| |
| |
| |
| Entropy | |
| |
| |
| |
| Information and entropy | |
| |
| |
| |
| Channels and Channel Capacity | |
| |
| |
| |
| Discrete memoryless channels | |
| |
| |
| |
| Transition probabilities and binary symmetric channels | |
| |
| |
| |
| Input frequencies | |
| |
| |
| |
| Channel capacity | |
| |
| |
| |
| Proof of Theorem 3.4.3, on the capacity equations | |
| |
| |
| |
| Coding Theory | |
| |
| |
| |
| Encoding and decoding | |
| |
| |
| |
| Prefix-condition codes and the Kraft-McMillan inequality | |
| |
| |
| |
| Average code word length and Huffman's algorithm | |
| |
| |
| |
| The validity of Huffman's algorithm | |
| |
| |
| |
| Optimizing the input frequencies | |
| |
| |
| |
| Error correction, maximum likelihood decoding, nearest code word decoding, and reliability | |
| |
| |
| |
| Shannon's Noisy Channel Theorem | |
| |
| |
| |
| Error correction with binary symmetric channels and equal source frequencies | |
| |
| |
| |
| The information rate of a code | |
| |
| |
| |
| Data Compression | |
| |
| |
| |
| Lossless Data Compression by Replacement Schemes | |
| |
| |
| |
| Replacement via encoding scheme | |
| |
| |
| |
| Review of the prefix condition | |
| |
| |
| |
| Choosing an encoding scheme | |
| |
| |
| |
| Shannon's method | |
| |
| |
| |
| Fano's method | |
| |
| |
| |
| Huffman's algorithm | |
| |
| |
| |
| The Noiseless Coding Theorem and Shannon's bound | |
| |
| |
| |
| Arithmetic Coding | |
| |
| |
| |
| Pure zeroth-order arithmetic coding: dfwld | |
| |
| |
| |
| Rescaling while encoding | |
| |
| |
| |
| Decoding | |
| |
| |
| |
| What's good about dfwld coding: the compression ratio | |
| |
| |
| |
| What's bad about dfwld coding and some ways to fix it | |
| |
| |
| |
| Supplying the source word length | |
| |
| |
| |
| Computation | |
| |
| |
| |
| Must decoding wait until encoding is completed? | |
| |
| |
| |
| Implementing arithmetic coding | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Higher-order Modeling | |
| |
| |
| |
| Higher-order Huffman encoding | |
| |
| |
| |
| The Shannon bound for higher-order encoding | |
| |
| |
| |
| Higher-order arithmetic coding | |
| |
| |
| |
| Statistical models, statistics, and the possibly unknowable truth | |
| |
| |
| |
| Probabilistic finite state source automata | |
| |
| |
| |
| Adaptive Methods | |
| |
| |
| |
| Adaptive Huffman encoding | |
| |
| |
| |
| Compression and readjustment | |
| |
| |
| |
| Higher-order adaptive Huffman encoding | |
| |
| |
| |
| Maintaining the tree in adaptive Huffman encoding: the method of Knuth and Gallager | |
| |
| |
| |
| Gallager's method | |
| |
| |
| |
| Knuth's algorithm | |
| |
| |
| |
| Adaptive arithmetic coding | |
| |
| |
| |
| Interval and recency rank encoding | |
| |
| |
| |
| Interval encoding | |
| |
| |
| |
| Recency rank encoding | |
| |
| |
| |
| Dictionary Methods | |
| |
| |
| |
| LZ77 (sliding window) schemes | |
| |
| |
| |
| An LZ77 implementation | |
| |
| |
| |
| Case study: GNU zip | |
| |
| |
| |
| The LZ78 approach | |
| |
| |
| |
| The LZW variant | |
| |
| |
| |
| Case study: Unix compress | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Transform Methods and Image Compression | |
| |
| |
| |
| Transforms | |
| |
| |
| |
| Periodic signals and the Fourier transform | |
| |
| |
| |
| The Fourier transform and compression: an example | |
| |
| |
| |
| The cosine and sine transforms | |
| |
| |
| |
| A general orthogonal transform | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Two-dimensional transforms | |
| |
| |
| |
| The 2D Fourier, cosine, and sine transforms | |
| |
| |
| |
| Matrix expressions for 2D transforms | |
| |
| |
| |
| An application: JPEG image compression | |
| |
| |
| |
| A brief introduction to wavelets | |
| |
| |
| |
| 2D Haar wavelets | |
| |
| |
| |
| Notes | |
| |
| |
| Appendices | |
| |
| |
| |
| JPEGtool User's Guide | |
| |
| |
| |
| Using the tools | |
| |
| |
| |
| Reference | |
| |
| |
| |
| Obtaining Octave | |
| |
| |
| |
| Source Listing for LZRW1-A | |
| |
| |
| |
| Resources, Patents, and Illusions | |
| |
| |
| |
| Resources | |
| |
| |
| |
| Data compression and patents | |
| |
| |
| |
| Illusions | |
| |
| |
| |
| Notes on and Solutions to Some Exercises | |
| |
| |
| Bibliography | |
| |
| |
| Index | |