Abstract/Details

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)


Subject
Electrical engineering
Classification
0544: Electrical engineering
Identifier / keyword
Applied sciences
Title
Residual quantizers
Author
Barnes, Christopher Floyd
Number of pages
173
Publication year
1989
Degree date
1989
School code
0022
Source
DAI-B 50/12, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
Advisor
Frost, Richard L.
University/institution
Brigham Young University
University location
United States -- Utah
Degree
Ph.D.
Source type
Dissertations & Theses
Language
English
Document type
Dissertation/Thesis
Dissertation/thesis number
9012755
ProQuest document ID
303667897
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
http://search.proquest.com/docview/303667897
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.