A Caltech Library Service

A vector quantization approach to universal noiseless coding and quantization

Chou, Philip A. and Effros, Michelle and Gray, Robert M. (1996) A vector quantization approach to universal noiseless coding and quantization. IEEE Transactions on Information Theory, 42 (4). pp. 1109-1138. ISSN 0018-9448. doi:10.1109/18.508836.

See Usage Policy.


Use this Persistent URL to link to this item:


A two-stage code is a block code in which each block of data is coded in two stages: the first stage codes the identity of a block code among a collection of codes, and the second stage codes the data using the identified code. The collection of codes may be noiseless codes, fixed-rate quantizers, or variable-rate quantizers. We take a vector quantization approach to two-stage coding, in which the first stage code can be regarded as a vector quantizer that “quantizes” the input data of length n to one of a fixed collection of block codes. We apply the generalized Lloyd algorithm to the first-stage quantizer, using induced measures of rate and distortion, to design locally optimal two-stage codes. On a source of medical images, two-stage variable-rate vector quantizers designed in this way outperform standard (one-stage) fixed-rate vector quantizers by over 9 dB. The tail of the operational distortion-rate function of the first-stage quantizer determines the optimal rate of convergence of the redundancy of a universal sequence of two-stage codes. We show that there exist two-stage universal noiseless codes, fixed-rate quantizers, and variable-rate quantizers whose per-letter rate and distortion redundancies converge to zero as (k/2)n -1 log n, when the universe of sources has finite dimension k. This extends the achievability part of Rissanen's theorem from universal noiseless codes to universal quantizers. Further, we show that the redundancies converge as O(n-1) when the universe of sources is countable, and as O(n-1+ϵ) when the universe of sources is infinite-dimensional, under appropriate conditions.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:“©1996 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.” Manuscript received July 25, 1994; revised February 27, 1996. The material in this paper was presented in part at the 1991, 1993, and 1995 International Symposia on Information Theory. This paper is based on work partially supported by the NSF under Grant MIP-9501977, by an AT&T Bell Laboratories Ph.D. Scholarship, by a grant from the Center for Telecommunications at Stanford, and by an NSF Graduate Fellowship. The authors wish to thank the anonymous reviewers for suggestions that improved the quality of this paper.
Subject Keywords:Two-stage, adaptive, compression, minimum description length, clustering, source code design, source coding theory, universal source coding
Issue or Number:4
Record Number:CaltechAUTHORS:CHOieeetit96
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:320
Deposited By: Archive Administrator
Deposited On:26 May 2005
Last Modified:08 Nov 2021 19:01

Repository Staff Only: item control page