Design and Performance Evaluation of a Class of Finite-State Vector Quantizers

Abstract

The finite-state vector quantizer (FSVQ), introduced by Foster, Dunham and Gray, is a finite-state machine that can be viewed as a collection of memoryless full-searched vector quantizers, where each input vector is encoded using a vector quantizer associated with the current encoded state; the current state and selected codeword determine the next encoder state. It is generally assumed that the state codebooks are unstructured and have the same cardinality leading to a fixed-rate scheme. In this thesis, we present two variable-rate variations of the FSVQ scheme with the possibility of using structured as well as unstructured state codebooks. In the first scheme, we let the state codebook sizes be different for different states, implying different rate distribution among the states. In the second scheme, in addition to this flexibility, we use pruned tree-structured vector quantizers as the state quantizers, i.e., we let each of the state quantizers be a variable-rate encoder. For encoding sampled speech data, both of these schemes perform significantly better than the fixed-rate FSQV scheme with the second scheme giving the best performance.<P>We also consider that 2-D extension of the above mentioned schemes and describe two bit rate image coding systems based on these schemes. A compression ratio in excess of 26 is achieved for encoding the 512 x 512 version of "Lena" using the schemes employing variable-rate FSVQs.<P>An implicit assumption made in all the systems mentioned above is that the channel is noiseless. Under noisy channel conditions, all of the above systems suffer from severe performance degradations calling for the need to reformulate the FSVQ design problem taking into account the channel noise. Using some of the developments in joint source-channel trellis coding, we describe two different methods leading to two types of noisy channel FSVQs. We show by means of simulations on the Gauss- Markov source and speech LSP parameters and for a binary symmetric channel that both schemes are fairly robust to channel noise. In particular, for speech LSP parameters, the proposed noisy channel FSVQs lead to a saving of 1.5-4 bits/frame over the channel-optimized vector quantizer depending on the level of noise in the channel.