Source and channel coding with vector quantization
K. Zeger, A. Gersho · 1990
Many low bit-rate speech and image communication systems use the block source coding technique of Vector Quantization (VQ) as a fundamental building block in more complex coding structures. As the demand for precious communication channel bandwidth grows, an increasing need arises for more efficient source coding algorithms that are robust to channel noise. In this dissertation, new VQ-based combined source/channel coding techniques are developed and analyzed which lead to substantial performance gains in terms of mean-square error for a wide variety of discrete memoryless channels. In addition, comprehensive theories of VQ design using Stochastic Relaxation and Competitive Learning are developed and empirically tested for noiseless channels. Stochastic Relaxation is a probabilistic search method that generalizes the notion of Simulated Annealing. It is shown that when combined with generalized Lloyd quantization, substantial improvements in quantizer performance can result. A new deterministic soft-competition form of Competitive Learning (arising in neural network theory) and an adaptation of the Partial Conjugate Gradient Descent optimization technique are also developed for VQ design, which gives improved results over the generalized Lloyd method. For VQ with noisy channels, a technique we call pseudo-Gray coding is introduced, that assigns quantizer codevector indices to binary channel words in such a manner that the overall average distortion between the input source vector and the output VQ codevector is reduced, without adding any redundancy bits to the transmitted information. Experimental results are presented which demonstrate significant performance gains by using pseudo-Gray coding for a variety of Gauss-Markov, speech, and image sources. The technique is then generalized to incorporate VQ systems with explicit block error control coding. One particularly interesting result shows that a good index assignment for a quantizer with no channel coder can often be superior in performance to a poor index assignment for the same quantizer using redundancy coding. A complexity analysis of the pseudo-Gray algorithm is given and some complexity reduction techniques are presented that make the index assignment algorithm practical to use for real systems. Generalizations to noisy channels of the well-known nearest-neighbor and centroid necessary conditions for quantizer optimality are analyzed in terms of the geometric properties they induce on the encoder and decoder structures of an optimal quantizer. It is shown, for example, that for the quantizer decoder, the optimality conditions of the generalized theorems coincide with the original conditions only when the channel is noiseless, whereas for the encoder the conditions remain unaltered for certain noisy channels.