Quantization
Robert M.Gray,Fellow,IEEE,and David L.Neuhoff,Fellow,IEEE
(Invited Paper)
Abstract—The history of the theory and practice of quan-
tization dates to1948,although similar ideas had appeared
in the literature as long ago as1898.The fundamental role
of quantization in modulation and analog-to-digital conversion
wasfirst recognized during the early development of pul-
code modulation systems,especially in the1948paper of Oliver,
Pierce,and Shannon.Also in1948,Bennett published thefirst
high-resolution analysis of quantization and an exact analysis of
quantization noi for Gaussian process,and Shannon pub-
lished the beginnings of rate distortion theory,which would
provide a theory for quantization as analog-to-digital conversion
and as data compression.Beginning with the three papers of
fifty years ago,we trace the history of quantization from its
origins through this decade,and we survey the fundamentals of
the theory and many of the popular and promising techniques
for quantization.
Index Terms—High resolution theory,rate distortion theory,
source coding,quantization.
电灯简笔画
I.I NTRODUCTION
培养近义词
T HE dictionary(Random Hou)definition of quantization
is the division of a quantity into a discrete number
of small parts,often assumed to be integral multiples of
a common quantity.The oldest example of quantization is
rounding off,which wasfirst analyzed by Sheppard[468]
for the application of estimating densities by histograms.Any
real number
,with a resulting quantization error so that
is ordinarily a collection of concutive integers
beginning with,together with a t of reproduction
values or points or levels
Fig. 2.A uniform quantizer.
If the distortion is measured by squared
error,
into a binary
reprentation or channel codeword of the quantizer index possible levels and all of the
binary reprentations or binary codewords have equal length (a temporary assumption),the binary vectors will
need (or the next larger
integer,
,unless explicitly specified otherwi.
In summary,the goal of quantization is to encode the data from a source,characterized by its probability density function,into as few bits as possible (i.e.,with low rate)in such a way that a reproduction may be recovered from the bits with as high quality as possible (i.e.,with small average distortion).Clearly,there is a tradeoff between the two primary performance measures:average distortion (or simply distortion ,as we will often abbreviate)and rate.This tradeoff may be quantified as the operational distortion-rate
function or less.That
is,
or less,which is the inver
of
or less.We will also be interested in the
best possible performance among all quantizers.Both as a preview and as an occasional benchmark for comparison,we informally define the class of all quantizers as the class of quantizers that can 1)operate on scalars or vectors instead of only on scalars (vector quantizers),2)have fixed or variable rate in the n that the binary codeword describing the quantizer output can have length depending on the input,and 3)be memoryless or have memory,for example,using different ts of reproduction levels,depending on the past.In addition,we restrict attention to quantizers that do not c
hange with time.That is,when confronted with the same input and the same past history,a quantizer will produce the same output regardless of the time.We occasionally u the term lossy source code or simply code as alternatives to quantizer .The rate is now defined as the average number of bits per source symbol required to describe the corresponding reproduction symbol.We informally generalize the operational distortion-rate
function
or less.
Thus
GRAY AND NEUHOFF:QUANTIZATION2327
for special nonasymptotic cas,such as Clavier,Panter, and Grieg’s1947analysis of the spectra of the quantization error for uniformly quantized sinusoidal signals[99],[100], and Bennett’s1948derivation of the power spectral density of a uniformly quantized Gaussian random process[43]. The most important nonasymptotic results,however,are the basic optimality conditions a
nd iterative-descent algorithms for quantizer design,such asfirst developed by Steinhaus(1956) [480]and Lloyd(1957)[330],and later popularized by Max (1960)[349].
Our goal in the next ction is to introduce in historical context many of the key ideas of quantization that originated in classical works and evolved over the past50years,and in the remaining ctions to survey lectively and in more detail a variety of results which illustrate both the historical development and the state of thefield.Section III will prent basic background material that will be needed in the remainder of the paper,including the general definition of a quantizer and the basic forms of optimality criteria and descent algorithms. Some such material has already been introduced and more will be introduced in Section II.However,for completeness, Section III will be largely lf-contained.Section IV reviews the development of quantization theories and compares the approaches.Finally,Section V describes a number of specific quantization techniques.
In any review of a large subject such as quantization there is no space to discuss or even mention all work on the subject. Though we have made an effort to lect the most important work,no doubt we have misd some important work due to bias,misunderstanding,or ignorance.For this we apologize, both to the reader and to the rearchers who work we may have neglected.
II.H ISTORY
小说的三要素
The history of quantization often takes on veral parallel paths,which caus some problems in our clustering of topics. We follow roughly a chronological order within each and order the paths as best we can.Specifically,we willfirst track the design and analysis of practical quantization techniques in three paths:fixed-rate scalar quantization,which leads directly from the discussion of Section I,predictive and transform coding,which adds linear processing to scalar quantization in order to exploit source redundancy,and variable-rate quantiza-tion,which us Shannon’s lossless source coding techniques [464]to reduce rate.(Lossless codes were originally called noiless.)Next we follow early forward-looking work on vector quantization,including the minal work of Shannon and Zador,in which vector quantization appears more to be a paradigm for analyzing the fundamental limits of quantizer performance than a practical coding technique.A surprising amount of such vector quantization theory was developed out-side the conventional communications and signal processing literature.Subquently,we review briefly the developments from the mid-1970’s to the mid-1980’s which mainly concern the emergence of vector quantization as a practical technique. Finally,we sketch briefly developments from the mid-1980’s to the prent.Except where stated otherwi,we presume squared error as the distortion measure.A.Fixed-Rate Scalar Quantization:
PCM and the Origins of Quantization Theory
Both quantization and source coding with afidelity crite-rion have their origins in pul-code modulation(PCM),a technique patented in1938by Reeves[432],who25years later wrote a historical perspective on and an appraisal of the future of PCM with Deloraine[120].The predictions were surprisingly accurate as to the eventual ubiquity of digital speech and video.The technique wasfirst successfully imple-mented in hardware by Black,who reported the principles and implementation in1947[51],as did another Bell Labs paper by Goodall[209].PCM was subquently analyzed in detail and popularized by Oliver,Pierce,and Shannon in1948[394]. PCM was thefirst digital technique for conveying an analog information signal(principally telephone speech)over an analog channel(typically,a wire or the atmosphere).In other words,it is a modulation ,an alternative to AM, FM,and various other types of pul modulation.It consists of three main components:a sampler(including a prefilter),a quantizer(with afixed-rate binary encoder),and a binary pul modulator.The sampler converts a continuous-time
waveform into a quence of
samples,
where
and the high-frequency power removed by the lowpassfilter.The binary pul modulator typically us the bits produced by the quantizer to determine the amplitude,frequency,or pha of a sinusoidal carrier waveform.In the evolutionary development of modulation techniques it was found that the performance of pul-amplitude modulation in the prence of noi could be improved if the samples were quantized to the nearest of a t
of
levels had been transmitted in the prence of noi could be done with such reliability that the overall MSE was substantially reduced.Reducing the number of quantization
levels
at a value giving acceptably small quantizer MSE and to binary encode the levels,so that the receiver had only to make binary decisions,something it can do with great reliability.The resulting system,PCM,had the best resistance to noi of all modulations of the time.
As the digital era emerged,it was recognized that the sampling,quantizing,and encoding part of PCM performs an analog-to-digital(A/D)conversion,with us extending much beyond communication over analog channels.Even in the communicationsfield,it was recognized that the task of analog-to-digital conversion(and source coding)should be factored out of binary modulation as a parate task.Thus
2328IEEE TRANSACTIONS ON INFORMATION THEORY,VOL.44,NO.6,OCTOBER1998 PCM is now generally considered to just consist of sampling,
quantizing,and ,it no longer includes the binary
pul modulation.
Although quantization in the information theory literature
is generally considered as a form of data compression,its
u for modulation or A/D conversion was originally viewed
as data expansion or,more accurately,bandwidth expansion.
For example,a speech waveform occupying roughly4kHz
would have a Nyquist rate of8kHz.Sampling at the Nyquist
rate and quantizing at8bits per sample and then modulating
the resulting binary puls using amplitude-or frequency-shift
如鱼得水近义词
keying would yield a signal occupying roughly64kHz,a
16–fold increa in bandwidth!Mathematically this constitutes
compression in the n that a continuous waveform requiring
an infinite number of bits is reduced to afinite number of bits,
but for practical purpos PCM is not well interpreted as a
compression scheme.
In an early contribution to the theory of quantization,
Clavier,Panter,and Grieg(1947)[99],[100]applied Rice’s
characteristic function or transform method[434]to provide
exact expressions for the quantization error and its moments
resulting from uniform quantization for certain specific inputs,
including constants and sinusoids.The complicated sums of
Besl functions rembled the early analys of another
nonlinear modulation technique,FM,and left little hope for
general clod-form solutions for interesting signals.
Thefirst general contributions to quantization theory came
in1948with the papers of Oliver,Pierce,and Shannon[394]
and Bennett[43].As part of their analysis of PCM for
communications,they developed the oft-quoted result that for
large rate or resolution,a uniform quantizer with cell
width
levels and
rate,and the source has input
wps怎么截图
range(or support)of
width
dB
showing that for large rate,the SNR of uniform quantization
increas6dB for each one-bit increa of rate,which is often
referred to as the“6-dB-per-bit rule.”
The
for companders,systems that preceded a
uniform quantizer by a monotonic smooth nonlinearity called
a“compressor,”
say
was given
by is a
uniform quantizer.Bennett showed that in this
海棠台风
ca
is the cellwidth of the uniform
quantizer,and the integral is taken over the granular range of
the input.(The
constant
maps to the unit interval
can be interpreted,as Lloyd
would explicitly point out in1957[330],as a constant times
a“quantizer point-density
function
共青团100周年number of quantizer levels
in
over a region gives the fraction of
quantizer reproduction levels in the region,it is evident
that
,which when integrated
over
rather than the fraction.In the current
situation
is infinite.
Rewriting Bennett’s integral in terms of the point-density
function yields its more common
form
(7)
The idea of a quantizer point-density function will generalize
to vectors,while the compander approach will not in the n
that not all vector quantizers can be reprented as companders
[192].
Bennett also demonstrated that,under assumptions of high
resolution and smooth densities,the quantization error behaved
much like random“noi”:it had small correlation with the
signal and had approximately aflat(“white”)spectrum.This
led to an“additive-noi”model of quantizer error,since with
the properties the
formula
GRAY AND NEUHOFF:QUANTIZATION2329 is uniformly quantized,providing one of the very few exact
computations of quantization error spectra.
In1951Panter and Dite[405]developed a high-resolution
formula for the distortion of afixed-rate scalar quantizer using
approximations similar to Bennett’s,but without reference to
Bennett.They then ud variational techniques to minimize
their formula and found the following formula for the opera-
tional distortion-rate function offixed-rate scalar quantization:
for large values
of
(9)
Indeed,substituting this point density into Bennett’s integral
and using the fact
that yields(8).As an example,
if the input density is Gaussian with
variance,
then
as
or less.(It was not until Shannon’s1959
paper[465]
主题团日活动
that
the rate is0.72bits/sample larger than
that achievable by the best quantizers.
In1957,Smith[474]re-examined companding and PCM.
Among other things,he gave somewhat cleaner derivations of
1They also indicated that it had been derived earlier by P.R.Aigrain.
Bennett’s integral,the optimal compressor function,and the
Panter–Dite formula.
Also in1957,Lloyd[330]made an important study of
quantization with three main contributions.First,he found
necessary and sufficient conditions for afixed-rate quantizer to
be locally ,conditions that if satisfied implied that
small perturbations to the levels or thresholds would increa
distortion.Any optimal quantizer(one with smallest distortion)
will necessarily satisfy the conditions,and so they are often
called the optimality conditions or the necessary conditions.
Simply stated,Lloyd’s optimality conditions are that for a
fixed-rate quantizer to be optimal,the quantizer partition must
be optimal for the t of reproduction levels,and the t of
reproduction levels must be optimal for the partition.Lloyd
derived the conditions straightforwardly fromfirst principles,
without recour to variational concepts such as derivatives.
For the ca of mean-squared error,thefirst condition implies
a minimum distance or nearest neighbor quantization rule,
choosing the clost available reproduction level to the source
sample being quantized,and the cond condition implies that
the reproduction level corresponding to a given cell is the
conditional expectation or centroid of the source value given
that it lies in the specified ,it is the minimum mean-
squared error estimate of the source sample.For some sources
there are multiple locally optimal quantizers,not all of which
are globally optimal.
Second,bad on his optimality conditions,Lloyd devel-
oped an iterative descent algorithm for designing quantizers for
a given source distribution:begin with an initial collection of
reproduction levels;optimize the partition for the levels by
using a minimum distortion mapping,which gives a partition
of the real line into intervals;then optimize the t of levels for
the partition by replacing the old levels by the centroids of the
partition cells.The alternation is continued until convergence
to a local,if not global,optimum.Lloyd referred to this
design algorithm as“Method I.”He also developed a Method
II bad on the optimality properties.First choo an initial
smallest reproduction level.This determines the cell threshold
to the right,which in turn implies the next larger reproduction
level,and so on.This approach alternately produces a level
and a threshold.Once the last level has been chon,the
initial level can then be rechon to reduce distortion and
the algorithm continues.Lloyd provided design examples
for uniform,Gaussian,and Laplacian random variables and
showed that the results were consistent with the high resolution
approximations.Although Method II would initially gain more
popularity when rediscovered in1960by Max[349],it is
Method I that easily extends to vector quantizers and many
types of quantizers with structural constraints.
Third,motivated by the work of Panter and Dite but
apparently unaware of that of Bennett or Smith,Lloyd re-
derived Bennett’s integral and the Panter–Dite formula bad
on the concept of point-density function.This was a critically
important step for subquent generalizations of Bennett’s
integral to vector quantizers.He also showed directly that
in situations where the global optimum is the only local
optimum,quantizers that satisfy the optimality conditions
have,asymptotically,the optimal point density given by(9).
