A reasonable measure of quantizer complexity is the expected number of quanta per input sample for which distortion is computed. Given this measure, a rate-distortion-complexity theory is obtained by extending earlier work in alphabet-constrained rate-distortion theory. Numerical results show that operation on the alphabet-constrained rate-distortion bound can be obtained with a complexity of two. Furthermore, Lloyd-Max conditions are shown to describe the minimum of a slightly constrained version of the rate-distortion-complexity problem. Complexity-constrained design methods are applied first to trellis-coded quantizers, where they are shown to reduce arithmetic operations by at least 25%. They are then used to develop model-based trellis quantizers, the trellises of which are derived from a Markov model of the source. Simulation results confirm that excellent performance can be obtained with modest complexity.

A method is developed for decreasing the computational complexity of a trellis quantizer (TQ) encoder. We begin by developing a rate-distortion theory under a constraint on the average instantaneous number of quanta considered. This constraint has practical importance: in a TQ, the average instantaneous number of quanta is exactly the average number of multiplies required at the encoder. The theory shows that if the conditional probability of each quanta is restricted to a finite region of support, the instantaneous number of quanta considered can be made quite small at little or no cost in SQNR performance. Simulations of TQs confirm this prediction. This reduction in complexity makes practical the use of model-based TQs (MTQs), which had previously been considered computationally unreasonable. For speech, performance gains of several dB SQNR over adaptive predictive schemes at a similar computational complexity are obtained using only a first-order MTQ.