Complexity-constrained trellis quantizers
We develop a rate-distortion-complexity theory, using as a measure of complexity the average number of quanta for which the distortion is computed. Complexity is constrained by confining to a finite region the support of the conditional probability of each quanta. Numerical results show that the regions of support can be made quite small at little or no cost in SQNR. This constraint can be incorporated into existing Lloyd-Max design procedures by adopting a shared boundary (SB) constraint on cth-nearest-neighbor quanta. The SB constraint is applied to the design of model-based TQs (MTQs), which have previously been considered computationally unreasonable. Robust performance is obtained on a variety of sources. On composite sources MTQ gives the best results reported in the literature. On the AR sources, MTQ is within a few dB of the rate-distortion bound. On speech, good performance is obtained with nearly an order of magnitude reduction in complexity over comparable methods.