Block-constrained methods of fixed-rate entropy-coded quantization.
Ahmed Balamesh · Deep Blue (University of Michigan) · 1993
Entropy-coded scalar quantization (ECSQ) is an efficient method of data compression for analog sources. It performs within 1.53 dB of the distortion-rate function, which is the best possible performance for a given source. The main disadvantage of ECSQ is its variable rate, which necessitates buffering if transmission over a fixed-rate channel is intended. In this thesis, we propose a new class of fixed-rate methods called block-constrained quantization (BCQ) that asymptotically (in dimension) achieves the performance of ECSQ. Simply speaking, a BCQ constrains the number of bits produced by an ECSQ for a block of n source samples. It does so by searching over all sequences produceable by the ECSQ for one that is closest to the source block and that generates no more than nr bits, for a desired rate r. BCQ includes the quantizers recently introduced by Laroia and Farvardin and shown to achieve the performance of ECSQ. It also includes some new low-complexity methods based on prefix and arithmetic codes. Overall, we propose a rich class of quantizers with good performance-complexity tradeoff. We propose three simple methods to perform the BCQ search. One uses reduced-state dynamic programming, another is greedy and the third is Lagrange-multiplier-based. These greatly reduce the search complexity of BCQ as compared to the full-search, dynamic programming proposed by Laroia and Farvardin. An extensive asymptotic analysis of these schemes is given. Explicit asymptotic forms for the distortion, the rate, the optimum distortion vs. rate performance and other relevant quantities are given. These turn out to be related to analogous quantities for scalar quantization, which causes these schemes to be limited by the performance of scalar quantizers. However, these schemes can also be used to convert entropy-coded, trellis-coded quantizers into fixed rate. Some intermediate results in the thesis are of interest in their own right. For example, we show that Pasco's arithmetic codes can be implemented, in the same manner as Jones', using fixed-point arithmetic. Also, we give results on the uniform, almost-sure convergence of the empirical distortion and average length of a scalar quantizer.