On universal quantization

IEEE Transactions on Information TheoryPublished 1 May 1985

J. Ziv

DOI10.1109/tit.1985.1057034

Source URL

Citations181

SJR quartileQ1

SJR score1.46

SNIP1.76

TL;DR

It is demonstrated that a uniform, one-dimensional quantizer followed by a noiseless digital variable-rate encoder can yield a rate that is, for any n, no more than 0.754 bit-per-sample higher than the rate associated with the optimal n -dimensionai quantizer.

Abstract

The quantization of n -dimensional vectors in R^{n} with an arbitrary probability measure, under a mean-square error constraint, is discussed. It is demonstrated that a uniform, one-dimensional quantizer followed by a noiseless digital variable-rate encoder ("entropy encoding") can yield a rate that is, for any n , no more than 0.754 bit-per-sample higher than the rate associated with the optimal n -dimensionai quantizer, regardless of the probabilistic characterization of the input n -vector for the allowable mean-square error.

Keywords

Computer Science

IEEE Transactions on CommunicationsAn Algorithm for Vector Quantizer Design

7,183 Citations1980Y. Linde, A. Buzo +1 more

An efficient and intuitive algorithm is presented for the design of vector quantizers based either on a known probabilistic model or on a long training sequence of data.

IEEE Transactions on Information TheoryCompression of individual sequences via variable-rate coding

3,452 Citations1978J. Ziv, A. Lempel

The proposed concept of compressibility is shown to play a role analogous to that of entropy in classical information theory where one deals with probabilistic ensembles of sequences rather than with individual sequences.

IEEE Transactions on Information TheoryAsymptotically optimal block quantization

869 Citations1979A. Gersho

A heuristic argument generalizing Bennett's formula to block quantization where a vector of random variables is quantized is given, leading to a rigorous method for obtaining upper bounds on the minimum distortion for block quantizers.

IEEE Transactions on Information TheoryAsymptotically efficient quantizing

466 Citations1968H. Gish, John R. Pierce

It is shown that uniform quantizing yields an output entropy which asymptotically is smaller than that for any other quantizer, independent of the density function or the error criterion, and the discrepancy between the entropy of the uniform quantizer and the rate distortion function apparently lies with the inability of the optimal quantizing shapes to cover large dimensional spaces without overlap.

IEEE Transactions on Information TheoryFast quantizing and decoding and algorithms for lattice quantizers and codes

436 Citations1982J. Conway, N. J. A. Sloane

A very fast algorithm is given for finding the closest lattice point to an arbitrary point if these lattices are used for vector quantizing of uniformly distributed data.

IEEE Transactions on Information TheoryVoronoi regions of lattices, second moments of polytopes, and quantization

323 Citations1982J. Conway, N. J. A. Sloane

The answers to the squared distance questions and a description of the Voronoi (or nearest neighbor) regions of these lattices have applications to quantization and to the design of signals for the Gaussian channel.

IEEE Transactions on Information TheoryOn the structure of vector quantizers

317 Citations1982A. Gersho

Vector quantization is intrinsically superior to predictive coding, transform coding, and other suboptimal and {\em ad hoc} procedures since it achieves optimal rate distortion performance subject only to a constraint on memory or block length of the observable signal segment being encoded.