Vector Quantization and Signal Compression

1 Introduction.- 1.1 Signals, Coding, and Compression.- 1.2 Optimality.- 1.3 How to Use this Book.- 1.4 Related Reading.- I Basic Tools.- 2 Random Processes and Linear Systems.- 2.1 Introduction.- 2.2 Probability.- 2.3 Random Variables and Vectors.- 2.4 Random Processes.- 2.5 Expectation.- 2.6 Linear Systems.- 2.7 Stationary and Ergodic Properties.- 2.8 Useful Processes.- 2.9 Problems.- 3 Sampling.- 3.1 Introduction.- 3.2 Periodic Sampling.- 3.3 Noise in Sampling.- 3.4 Practical Sampling Schemes.- 3.5 Sampling Jitter.- 3.6 Multidimensional Sampling.- 3.7 Problems.- 4 Linear Prediction.- 4.1 Introduction.- 4.2 Elementary Estimation Theory.- 4.3 Finite-Memory Linear Prediction.- 4.4 Forward and Backward Prediction.- 4.5 The Levinson-Durbin Algorithm.- 4.6 Linear Predictor Design from Empirical Data.- 4.7 Minimum Delay Property.- 4.8 Predictability and Determinism.- 4.9 Infinite Memory Linear Prediction.- 4.10 Simulation of Random Processes.- 4.11 Problems.- II Scalar Coding.- 5 Scalar Quantization I.- 5.1 Introduction.- 5.2 Structure of a Quantizer.- 5.3 Measuring Quantizer Performance.- 5.4 The Uniform Quantizer.- 5.5 Nonuniform Quantization and Companding.- 5.6 High Resolution: General Case.- 5.7 Problems.- 6 Scalar Quantization II.- 6.1 Introduction.- 6.2 Conditions for Optimality.- 6.3 High Resolution Optimal Companding.- 6.4 Quantizer Design Algorithms.- 6.5 Implementation.- 6.6 Problems.- 7 Predictive Quantization.- 7.1 Introduction.- 7.2 Difference Quantization.- 7.3 Closed-Loop Predictive Quantization.- 7.4 Delta Modulation.- 7.5 Problems.- 8 Bit Allocation and Transform Coding.- 8.1 Introduction.- 8.2 The Problem of Bit Allocation.- 8.3 Optimal Bit Allocation Results.- 8.4 Integer Constrained Allocation Techniques.- 8.5 Transform Coding.- 8.6 Karhunen-Loeve Transform.- 8.7 Performance Gain of Transform Coding.- 8.8 Other Transforms.- 8.9 Sub-band Coding.- 8.10 Problems.- 9 Entropy Coding.- 9.1 Introduction.- 9.2 Variable-Length Scalar Noiseless Coding.- 9.3 Prefix Codes.- 9.4 Huffman Coding.- 9.5 Vector Entropy Coding.- 9.6 Arithmetic Coding.- 9.7 Universal and Adaptive Entropy Coding.- 9.8 Ziv-Lempel Coding.- 9.9 Quantization and Entropy Coding.- 9.10 Problems.- III Vector Coding.- 10 Vector Quantization I.- 10.1 Introduction.- 10.2 Structural Properties and Characterization.- 10.3 Measuring Vector Quantizer Performance.- 10.4 Nearest Neighbor Quantizers.- 10.5 Lattice Vector Quantizers.- 10.6 High Resolution Distortion Approximations.- 10.7 Problems.- 11 Vector Quantization II.- 11.1 Introduction.- 11.2 Optimality Conditions for VQ.- 11.3 Vector Quantizer Design.- 11.4 Design Examples.- 11.5 Problems.- 12 Constrained Vector Quantization.- 12.1 Introduction.- 12.2 Complexity and Storage Limitations.- 12.3 Structurally Constrained VQ.- 12.4 Tree-Structured VQ.- 12.5 Classified VQ.- 12.6 Transform VQ.- 12.7 Product Code Techniques.- 12.8 Partitioned VQ.- 12.9 Mean-Removed VQ.- 12.10 Shape-Gain VQ.- 12.11 Multistage VQ.- 12.12 Constrained Storage VQ.- 12.13 Hierarchical and Multiresolution VQ.- 12.14 Nonlinear Interpolative VQ.- 12.15 Lattice Codebook VQ.- 12.16 Fast Nearest Neighbor Encoding.- 12.17 Problems.- 13 Predictive Vector Quantization.- 13.1 Introduction.- 13.2 Predictive Vector Quantization.- 13.3 Vector Linear Prediction.- 13.4 Predictor Design from Empirical Data.- 13.5 Nonlinear Vector Prediction.- 13.6 Design Examples.- 13.7 Problems.- 14 Finite-State Vector Quantization.- 14.1 Recursive Vector Quantizers.- 14.2 Finite-State Vector Quantizers.- 14.3 Labeled-States and Labeled-Transitions.- 14.4 Encoder/Decoder Design.- 14.5 Next-State Function Design.- 14.6 Design Examples.- 14.7 Problems.- 15 Tree and Trellis Encoding.- 15.1 Delayed Decision Encoder.- 15.2 Tree and Trellis Coding.- 15.3 Decoder Design.- 15.4 Predictive Trellis Encoders.- 15.5 Other Design Techniques.- 15.6 Problems.- 16 Adaptive Vector Quantization.- 16.1 Introduction.- 16.2 Mean Adaptation.- 16.3 Gain-Adaptive Vector Quantization.- 16.4 Switched Codebook Adaptation.- 16.5 Adaptive Bit Allocation.- 16.6 Address VQ.- 16.7 Progressive Code Vector Updating.- 16.8 Adaptive Codebook Generation.- 16.9 Vector Excitation Coding.- 16.10 Problems.- 17 Variable Rate Vector Quantization.- 17.1 Variable Rate Coding.- 17.2 Variable Dimension VQ.- 17.3 Alternative Approaches to Variable Rate VQ.- 17.4 Pruned Tree-Structured VQ.- 17.5 The Generalized BFOS Algorithm.- 17.6 Pruned Tree-Structured VQ.- 17.7 Entropy Coded VQ.- 17.8 Greedy Tree Growing.- 17.9 Design Examples.- 17.10 Bit Allocation Revisited.- 17.11 Design Algorithms.- 17.12 Problems.