Residual quantizers

1989 1989

Other formats: Order a copy

Abstract (summary)

The memory and computational costs of an exhaustive search vector quantizer (ESVQ) increase exponentially with the product of vector dimension and rate. This exponential increase in costs limits practical VQ code book and vector sizes; and hence, also limits VQ performance below that achievable with large vectors or limits that maximum rate at which VQ can operate. Juang and Gray proposed a multistage vector quantizer, which we call a residual quantizer (RQ), that reduces both the memory and computational costs of VQ. We determine conditions necessary for the optimality of scalar and vector RQs. The condition necessary for optimal encoding requires in general an exhaustive search of the RQ tree structure; hence, only memory savings are possible with exhaustive search RQs. We give a monotonically convergent design algorithm that yields exhaustive search RQs for sources characterized by either analytic or training set descriptions. Residual quantizers designed by this algorithm yield a joint optimization between all RQ stages instead of an independent optimization obtained with sequential use of the Generalized Lloyd Algorithm.

Exhaustive search RQs are tested extensively on memoryless Gaussian, memoryless Laplacian, Gaus-Markov and intensity imagery sources. For sources with memory, exhaustive search RQs may give memory saving of 4 to 16 times that required of ESVQs for a normalized SQNR performance at rates of 2, 1 and 0.5 bps.

We impose additional structure on RQs that does not invalidate the necessary RQ optimality conditions but which allows computationally efficient searches of the RQ tree structure. This additional structure forces a "reflecting" or "folding" symmetry on the tree structure that gives simple hyperplane partition boundaries between equivalence classes. We call these residual quantizers reflected RQs or origami RQs are demonstrated to give both memory and computational savings over that required by ESVQs for normalized SQNR performance.

The M-algorithm is also evaluated as an efficient but suboptimal search strategy in the implementation and design of RQ codes. We test several RQs designed with the use of the M-algorithm.

Indexing (details)

Electrical engineering
0544: Electrical engineering
Identifier / keyword
Applied sciences
Residual quantizers
Barnes, Christopher Floyd
Number of pages
Publication year
Degree date
School code
DAI-B 50/12, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
Frost, Richard L.
Brigham Young University
University location
United States -- Utah
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.