# 1998Quantization.pdf

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 6, OCTOBER 1998 1 Quantization Robert M. Gray and David L. Neuho Abstract| The history of the theory and practice of quantization dates to 1948, although similar ideas had appeared in the literatureaslong agoas1898. Thefundamentalrole of quan- tization in modulation and analog-to-digital conversion was rst recognized during the early development of pulse code modulation systems, especially in the 1948 paper of Oliver, Pierce, and Shannon. Also in 1948, Bennett published the rst high-resolution analysis of quantization and an exact analysis of quantization noise for Gaussian processes, and Shannon published the beginnings of rate distortion theory, which would provide a theory for quantization as analog-to- digital conversion and as data compression. Beginning with these three papers of fty 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. Keywords| Quantization, source coding, rate distortion theory, high resolution theory I. Introduction T HE dictionary(Random House) de nitionofquantiza- tionis the divisionofa quantityintoa discrete number of small parts, often assumed to be integral multiples of a common quantity. The oldest example of quantization is roundingo , which was rst analyzed bySheppard [468]for the application of estimating densities by histograms. Any real number x can be rounded o to the nearest integer, say q(x), with a resulting quantization error e = q(x)?x so that q(x) = x+e. More generally, we can de ne a quantizer as consisting of a set of intervals or cells S = fS i ; i 2 Ig, where the index set I is ordinarily a collection of consec- utive integers beginning with 0 or 1, together with a set of reproduction values or points or levels C = fy i ; i 2 Ig, so that the overall quantizer q is de ned by q(x) = y i for x 2 S i , which can be expressed concisely as q(x) = X i y i 1 S i (x); (1) where the indicator function 1 S (x) is 1 if x 2 S and 0 otherwise. For this de nition to make sense we assume that S is a partition of the real line. That is, the cells are disjoint and exhaustive. The general de nition reduces to the rounding o example if S i = (i? 1=2;i + 1=2] and y i = i for all integers i. More generally the cells mighttake the form S i = (a i?1 ;a i ] where the a i s, which are called thresholds, form an increasing sequence. The width of a cell S i is its length, a i ? a i?1 . The function q(x) is often called the quantization rule. A simple quantizer with 5 reproduction levels is depicted in Figure 1 as a collection R.M. Gray is with the Departmentof Electrical Engineering,Stan- ford University, Stanford, CA 94305, and D.L. Neuho is with the EECS Department, University of Michigan, Ann Arbor, MI 48109. The work of the authors reported in this paper was partially sup- portedby the NationalScienceFoundationundergrantsNCR-941574 and MIP-931190. of intervals bordered by thresholds along with the levels for each interval. - x a 1 a 2 a 3 a 4 y 0 y 1 y 2 y 3 y 4 Fig. 1. A nonuniform Quantizer: a 0 = ?1, a 5 = 1 A quantizer is said to be uniform if, as in the roundo case, the levels y i are equispaced, say apart, and the thresholds a i are midway between adjacent levels. If an in nite number of levels are allowed, then all cells S i will have width equal to , the separation between levels. If only a nite number of levels are allowed, then all but two cells willhave width and the outermostcells willbe semi- in nite. An example of a uniformquantizer with cell width and N = 8 levels is given in Figure 2. Given a uni- - x ?4?3?2 ? 0 2 3 4 ? 9 2 ? 7 2 ? 5 2 ? 3 2 ? 2 2 3 2 5 2 7 2 9 2 Fig. 2. A Uniform Quantizer form quantizer with cell width , the region of the input space within =2 of some quantizer level is called the gran- ular region or simply the support and that outside (where the quantizer error is unbounded) is called the overload or saturation region. More generally, the support or granular region of a nonuniform quantizer is the region of the input space within a relatively small distance of some level, and the overload region is the complement of the granular re- gion. To be concrete, \small“ might be de ned as half the width of the largest cell of nite width. The quality of a quantizer can be measured by the good- ness of the resulting reproduction in comparison to the original. One way of accomplishing this is to de ne a distortion measure d(x;^x) that quanti es cost or distor- tion resulting from reproducing x as ^x and to consider the average distortion as a measure of the quality of a sys- tem, with smaller average distortion meaning higher qual- ity. The most common distortion measure is the squared error d(x;^x) = jx?^xj 2 , but we shall encounter others later. In practice the average will be a sample average when the quantizer is applied to a sequence of real data, but the the- ory views the data as sharing a common probability den- sity function (pdf) f(x) corresponding to a generic random variable X and the average distortion becomes an expec- tation D(q) = E[d(X;q(X))] = X i Z S i d(x;y i )f(x)dx: (2) 2 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 44, NO. 6, OCTOBER 1998 If the distortion is measured by squared error, D(q) be- comes the mean squared error (MSE), a special case on which we shall mostly focus. It is desirable to have the average distortion as small as possible, and in fact negligible average distortion is achiev- able by letting the cells become numerous and tiny. There is a cost in terms of the number of bits required to describe the quantizer output to a decoder, however, and arbitrarily reliable reproduction will not be possible for digital stor- age and communication media with nite capacity. A sim- ple method for quantifying the cost for communications or storage is to assume that the quantizer \codes“ an in- put x into a binary representation or channel codeword of the quantizer index i specifying which reproduction level should be used in the reconstruction. If there are N pos- sible levels and all of the binary representations or binary codewords have equal length (a temporary assumption), the binary vectors will need logN (or the next larger inte- ger, dlogNe, if logN is not an integer) components or bits. Thus one de nition of the rate of the code in bits per input sample is R(q) = logN: (3) A quantizer with xed-length binary codewords is said to have xed-rate because all quantizer levels are assumed to have binary codewords of equal length. Later this restric- tion will be weakened. Note that all logarithms in this paper will have base 2, unless explicitly speci ed otherwise. In summary, the goal of quantization is to encode the data from a source, characterized by its probability den- sity 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 tradeo be- tween the two primary performance measures: average dis- tortion (or simply distortion, as we will often abbreviate) and rate. This tradeo may be quanti ed as the opera- tional distortion-rate function (R), which is de ned to be the least distortion of any scalar quantizer with rate R or less. That is, (R) inf q:R(q)R D(q): (4) Alternatively,one can de ne the operationalrate-distortion function r(D) as the least rate of any xed-rate scalar quantizer with distortion D or less, which is the inverse of (R). We have so far described scalar quantization with xed- rate coding, a technique whereby each data sample is in- dependently encoded into a xed number of bits and de- coded into a reproduction. As we shall see, there are many alternative quantization techniques that permit a better tradeo of distortion and rate; e.g. less distortion for the same rate, or vice versa. The purpose of this paper is to review the development of such techniques, and the theory of their design and performance. For example, for each type of technique we will be interested in its operational distortion-rate function, which is de ned to be the least distortion of any quantizer of the given type with rate R or less. We will also be interested in the best possible per- formance among all quantizers. Both as a preview and as an occasional benchmark for comparison, we informally de ne 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 xed or variable rate in the sense 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 di erent sets of reproduction levels, depending on the past. In addition, we restrict attention to quantizers that do not change with time. That is, when confronted with the same input and the same past history, a quantizer will produce the sameoutputregardless ofthe time. Weoccasionallyuse the term lossy source code or simply code as alternatives to quantizer. The rate is now de ned as the average number of bits per source symbol required to describe the corre- sponding reproduction symbol. We informally generalize the operational distortion-rate function (R) providing the best performance for scalar quantizers, to (R), which is de ned as the in mum of the average distortion over all quantization techniques with rate R or less. Thus (R) can be viewed as the best possible performance over all quantizers with no constraints on dimension, structure, or complexity. Section II begins with an historical tour of the develop- ment of the theory and practice of quantization over the past fty years, a period encompassing almost the entire literature on the subject. Two complementary approaches dominate the history and present state of the theory, and three of the key papers appeared in 1948, two of them in Volume 27 (1948) of the Bell Systems Technical Journal. Likely the approach best known to the readers of these Transactions is that of rate distortion theory or source coding with a delity criterion | Shannon s information theoretic approach to source coding | which was rst sug- gested in his 1948 paper [464] providing the foundations of informationtheory, but which was not fullydeveloped until his 1959 source coding paper [465]. The second approach is that of high resolution (or high rate or asymptotic) quan- tization theory, which had its origins in the 1948 paper on PCM by Oliver, Pierce and Shannon [394], the 1948 paper on quantization error spectra by Bennett [43], and the 1951 paper by Panter and Dite [405]. Much of the history and state of the art of quantization derives from these seminal works. In contrast to these two asymptotic theories, there is also a smallbut important collection of results that are not asymptotic in nature. The oldest such results are the exact analyses for special nonasymptotic cases, such as Clavier, Panter, and Grieg s 1947 analysis of the spectra of the quantization error for uniformly quantized sinusoidal sig- nals [99], [100] and Bennett s 1948 derivation of the power spectral density of a uniformlyquantized Gaussian random process [43]. The most important nonasymptotic results, however, are the basic optimality conditions and iterative descent algorithms for quantizer design, such as rst de- veloped by Steinhaus (1956) [480] and Lloyd (1957) [330], GRAY AND NEUHOFF: QUANTIZATION 3 and later popularized by Max (1960) [349]. Our goal in the next section is to introduce in histor- ical context many of the key ideas of quantization that originated in classical works and evolved over the past 50 years, and in the remaining sections to survey selectively and in more detail a variety of results which illustrate both the historical development and the state of the eld. Sec- tion III will present basic background material that will be needed in the remainder of the paper, including the general de nition 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 self-contained. Section IV reviews the development of quantization theories and compares the approaches. Fi- nally,Section V describes a number of speci c quantization techniques. In any review of a large subject such as quantization there is not space to discuss or even mentionallwork on the subject. Though we have made an e ort to select the most important work, no doubt we have missed some important work due to bias, misunderstanding, or ignorance. For this we apologize, both to the reader and to the researchers whose work we may have neglected. II. History The history of quantization often takes on several paral- lel paths, which causes some problems in our clustering of topics. We followroughly a chronologicalorder within each and order the paths as best we can. Speci cally, we will rst track the design and analysis of practical quantization techniques in three paths: xed-rate scalar quantization, whichleads directly fromthe discussion ofSection I, predic- tive and transform coding, which adds linear processing to scalar quantization in order to exploit source redundancy, and variable-rate quantization, which uses Shannon s loss- less source coding techniques [464] to reduce rate. (Loss- less codes were originally called noiseless.) Next we follow early forward looking work on vector quantization, includ- ingthe seminalworkofShannonand Zador, inwhich 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 outside the con- ventional communications and signal processing literature. Subsequently, we review brie y 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 brie y developments fromthe mid1980 s to the present. Except where stated otherwise, 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 a delity cri- terion have their origins in pulse code modulation (PCM), a technique patented in 1938 by Reeves [432], who 25 years later wrote an 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 was rst success- fully implemented in hardware by Black, who reported the principles and implementation in 1947 [51], as did anoth