VECTOR QUANTIZERS WITH DIRECT SUM CODEBOOKS

The use of direct sum codebooks to minimize the memory requirements of vector quantizers is investigated. Assuming arbitrary fixed partitions, necessary conditions for minimum distortion codebooks are derived: first for scalar codebooks, assuming mean-squared error distortion, and then for vector codebooks and a broader class of distortion measures. An iterative procedure is described for designing locally optimal direct sum codebooks. Both optimal and computationally efficient suboptimal encoding schemes are considered. It is shown that although an optimal encoding can be implemented by a sequential encoder, the complexity of implementing optimal stagewise partitions generally exceeds the complexity of an exhaustive search of the direct sum codebook. It is also shown that sequential nearest-neighbor encoders, which encode each stagewise residual with the nearest-neighbor code vector from the associated stagewise codebook, can be extremely inefficient. This is particularly true for direct sum quantizers with high output rates or with many stages. The M-search method is explored as one method of improving the effectiveness of suboptimal sequential encoders. Representative results of simulated direct sum quantizers are presented for Laplacian Gaussian and Gauss-Markov sources.