Pa. Chon et al., A VECTOR QUANTIZATION APPROACH TO UNIVERSAL NOISELESS CODING AND QUANTIZATION, IEEE transactions on information theory, 42(4), 1996, pp. 1109-1138
Citations number
58
Categorie Soggetti
Information Science & Library Science","Engineering, Eletrical & Electronic
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 amon
g a collection of codes, and the second stage codes the data using the
identified code, The collection of codes may be noiseless codes, fixe
d-rate quantizers, or variable-rate quantizers. We take a vector quant
ization approach to two-stage coding, in which the first stage code ca
n 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 induce
d 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 dist
ortion-rate function of the first-stage quantizer determines the optim
al rate of convergence of the redundancy of a universal sequence of tw
o-stage codes, We show that there exist two-stage universal noiseless
codes, fixed-rate quantizers, and variable-rate quantizers whose per-l
etter rate and distortion redundancies converge to zero as (k/2)n(-1)
log n, when the universe of sources has finite dimension h. This exten
ds the achievability part of Rissanen's theorem from universal noisele
ss codes to universal quantizers. Further, we show that the redundanci
es converge as O(n(-1)) when the universe of sources is countable, and
as O(n(-1+epsilon)) when the universe of sources is infinite-dimensio
nal, under appropriate conditions.