Vector Quantization and Signal Compression

Front Cover
Springer Science & Business Media, Nov 30, 1991 - Technology & Engineering - 732 pages
0 Reviews
Herb Caen, a popular columnist for the San Francisco Chronicle, recently quoted a Voice of America press release as saying that it was reorganizing in order to "eliminate duplication and redundancy. " This quote both states a goal of data compression and illustrates its common need: the removal of duplication (or redundancy) can provide a more efficient representation of data and the quoted phrase is itself a candidate for such surgery. Not only can the number of words in the quote be reduced without losing informa tion, but the statement would actually be enhanced by such compression since it will no longer exemplify the wrong that the policy is supposed to correct. Here compression can streamline the phrase and minimize the em barassment while improving the English style. Compression in general is intended to provide efficient representations of data while preserving the essential information contained in the data. This book is devoted to the theory and practice of signal compression, i. e. , data compression applied to signals such as speech, audio, images, and video signals (excluding other data types such as financial data or general purpose computer data). The emphasis is on the conversion of analog waveforms into efficient digital representations and on the compression of digital information into the fewest possible bits. Both operations should yield the highest possible reconstruction fidelity subject to constraints on the bit rate and implementation complexity.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Introduction
1
12 Optimality
8
13 How to Use this Book
12
14 Related Reading
13
Basic Tools
15
Random Processes and Linear Systems
17
22 Probability
18
23 Random Variables and Vectors
23
103 Measuring Vector Quantizer Performance
323
104 Nearest Neighbor Quantizers
327
105 Lattice Vector Quantizers
335
106 High Resolution Distortion Approximations
338
107 Problems
340
Vector Quantization II Optimality and Design
345
112 Optimally Conditions for VQ
349
113 Vector Quantizer Design
358

24 Random Processes
26
25 Expectation
29
26 Linear Systems
32
27 Stationary and Ergodic Properties
35
28 Useful Processes
39
29 Problems
42
Sampling
49
32 Periodic Sampling
50
33 Noise in Sampling
57
34 Practical Sampling Schemes
60
35 Sampling Jitter
65
36 Multidimensional Sampling
67
37 Problems
78
Linear Prediction
83
42 Elementary Estimation Theory
84
43 FiniteMemory Linear Prediction
93
44 Forward and Backward Prediction
98
45 The LevinsonDurbin Algorithm
104
46 Linear Predictor Design from Empirical Data
108
47 Minimum Delay Property
112
48 Predictability and Determinism
115
49 Infinite Memory Linear Prediction
117
410 Simulation of Random Processes
125
Scalar Coding
131
Scalar Quantization I Structure and Performance
133
52 Structure of a Quantizer
138
53 Measuring Quantizer Performance
142
54 The Uniform Quantizer
151
55 Nonuniform Quantization and Companding
156
General Case
161
57 Problems
168
Scalar Quantization II Optimality and Design
173
63 High Resolution Optimal Companding
185
64 Quantizer Design Algorithms
187
65 Implementation
194
66 Problems
198
Predictive Quantization
203
72 Difference Quantization
204
73 ClosedLoop Predictive Quantization
206
74 Delta Modulation
214
75 Problems
220
Bit Allocation and Transform Coding
225
82 The Problem of Bit Allocation
226
83 Optimal Bit Allocation Results
228
84 Integer Constrained Allocation Techniques
233
85 Transform Coding
235
86 KarhunenLoeve Transform
240
87 Performance Gain of Transform Coding
243
88 Other Transforms
245
89 Subband Coding
246
810 Problems
252
Entropy Coding
259
92 VariableLength Scalar Noiseless Coding
261
93 Prefix Codes
269
94 Huffman Coding
271
95 Vector Entropy Coding
276
96 Arithmetic Coding
277
97 Universal and Adaptive Entropy Coding
284
98 ZivLempel Coding
288
99 Quantization and Entropy Coding
295
910 Problems
302
Vector Coding
307
Vector Quantization I Structure and Performance
309
Basic Definitions
310
102 Structural Properties and Characterization
317
114 Design Examples
372
115 Problems
401
Constrained Vector Quantization
407
122 Complexity and Storage Limitations
408
123 Structurally Constrained VQ
409
124 TreeStructured VQ
410
125 Classified VQ
423
126 Transform VQ
424
127 Product Code Techniques
430
128 Partitioned VQ
434
129 MeanRemoved VQ
435
1210 ShapeGain VQ
441
1211 Multistage VQ
451
1212 Constrained Storage VQ
459
1213 Hierarchical and Multiresolution VQ
461
1214 Nonlinear Interpolative VQ
466
1215 Lattice Codebook VQ
470
1216 Fast Nearest Neighbor Encoding
479
1217 Problems
482
Predictive Vector Quantization
487
132 Predictive Vector Quantization
491
133 Vector Linear Prediction
496
134 Predictor Design from Empirical Data
504
135 Nonlinear Vector Prediction
506
136 Design Examples
509
137 Problems
517
FiniteState Vector Quantization
519
142 FiniteState Vector Quantizers
524
143 LabeledStates and LabeledTransitions
528
144 EncoderDecoder Design
533
145 NextState Function Design
537
146 Design Examples
545
147 Problems
552
Tree and Trellis Encoding
555
152 Tree and Trellis Coding
557
153 Decoder Design
568
154 Predictive Trellis Encoders
573
155 Other Design Techniques
584
156 Problems
585
Adaptive Vector Quantization
587
162 Mean Adaptation
590
163 GainAdaptive Vector Quantization
594
164 Switched Codebook Adaptation
602
165 Adaptive Bit Allocation for Multiple Vectors
605
166 Address VQ
611
167 Progressive Code Vector Updating
618
168 Adaptive Codebook Generation
620
169 Vector Excitation Coding
621
1610 Problems
628
Variable Rate Vector Quantization
631
172 Variable Dimension VQ
634
173 Alternative Approaches to Variable Rate VQ
638
174 Pruned TreeStructured VQ
640
175 The Generalized BFOS Algorithm
645
176 Pruned TreeStructured VQ
652
177 Entropy Coded VQ
653
178 Greedy Tree Growing
654
179 Design Examples
656
1710 Bit Allocation Revisited
677
1711 Design Algorithms
682
1712 Problems
688
Bibliography
691
Index
720
Copyright

Other editions - View all

Common terms and phrases

Popular passages

Page 720 - Compression of individual sequences via variablerate coding," IEEE Transactions on Information Theory, vol.
Page 718 - PH Westerink, J. Biemond and DE Boekee "An Optimal Bit Allocation Algorithm for Subband Coding", Proc.
Page 714 - EA Riskin, T. Lookabaugh, PA Chou, and RM Gray, "Variable rate vector quantization for medical image compression," IEEE Trans, on Medical Imaging, Vol.
Page 694 - Image Compression Using Non-adaptive Spatial Vector Quantization,
Page 712 - Neuhoff, RM Gray, and LD Davisson ["Fixed Rate Universal Block Source Coding with a Fidelity Criterion,
Page 717 - Sufficient conditions for uniqueness of a locally optimal quantizer for a class of convex error weighting functions", IEEE Trans.
Page 708 - Juang and AH Gray, Jr. Multiple stage vector quantization for speech coding.
Page 705 - RM Gray. A. Buzo. AH Gray, Jr., and Y. Matsuyama, "Distortion measures for speech processing,

References to this book

All Book Search results »

About the author (1991)

Robert M. Gray received his PhD from the University of Southern California, and is Professor and Vice Chair of Electrical Engineering at Stanford University. He has written over 200 scientific papers in areas including information theory, applied probability, signal processing, speech and image processing and coding, ergodic thoery, and the theory of Toeplitz matrices. He is a Fellow of the IEEE and the Institute of Mathematical Statistics.

Bibliographic information