1960

Max: Qu,antixingfor Minimum Distortion

tions for the maximum likelihood estimate of the random function, W(t), which was previously obtained by Youla follows. There also results another system of equations determining that estimate of the random function W(t) which is equivalent to Youla s system of equations. The general method discussed in the preceding section also yields the solution of many other problems of optimum system theory and similar problems of many other branches of science. IV. CONCLUDING REMARKS We see that the general method presented above yields the effective solution of various problems of applied statistical decision theory, particularly, of the statistical theory of signal detection and reproduction. The algorithm given by the method for obtaining a
I1 D. Youla, The use of the method of maximum likelihood in estimating continuous-modulated intelligence which has been corrupted by noise, IRE TRANS. ON INFORMATION THEORY, vol. IT-3, pp. 90-105; March, 1954.

signal estimate may be used as a base for real system design. The main difficulty which arises in the practical realization of such systems is generally the absence of necessary data characterizing the a priori distribution of the signal parameter U [i.e., the probability density f(u)]. To avoid this difficulty, the same algorithm may be applied to obtain the signal parameter U estimate in each cycle of the system acting, and to construct for each cycle an estimate for f(u) using estimates of U obtained in all previous cycles. Using such estimates of f(u) for each cycle of the system acting, we obtain a self-learning system which will be nearer and nearer with each new cycle to the true optimum system corresponding to the true probability distribution of the vector U.12
I2 K. Winkelbauer, Experience in Games of Strategy and In Statistical Decision, Trans. of the First Prague Conf. on Information Theory, Statistical Decision Functions and Random Processes, Liblice, November 28-30, 1956, Czech. Acad. of SC., Prague, pp. 297-354, 1957.

Quantizing

for Minimum
JOEL MAXI-

Distortion*

Summary-This paper discussesthe problem of the minimization of the distortion of a signal by a quantizer when the number of

output levels of the quantizer is fixed. The distortion is delined as the expected value of some function of the errorbetween the input and the output of the quantizer. Equations are derived for the parameters of a quantizer with minimum distortion. The equations are not soluble without recourse to numerical methods, so an algorithm is developed to simplify their numerical solution. The case of an input signal with normally distributed amplitude and an expected squared error distortion measure is explicitly computed and values of the optimum quantizer parameters are tabulated. The optimization of a quantizer subject to the restriction that both input and output levels be equally spaced is also treated, and appropriate parameters are tabulated for the same case as above.

* Manuscript received by the PGIT, September 25, 1959. This work was performed by the Lincoln Lab., Mass. Inst. Tech., Lexington, Mass., with the joint support of the U. S. Army, Navy, and Air Force. t Lincoln Lab., Mass. I&. Tech., Lexington, Mass.

N MANY data-transmission systems, analog input signals are first converted to digital form at the transmitter, transmitted in digital form, and finally reconstituted at the receiver as analog signals. The resulting output normally resembles the input signal but is not precisely the same since the quantizer at the transmitter produces the same digits for all input amplitudes which lie in each of a finite number of amplitude ranges. The receiver must assign to each combination of digits a single value which will be the amplitude of the reconstituted signal for an original input anywhere within the quantized range. The difference between input and output signals, assuming errorless transmission of the digits, is the quantization error. Since the digital transmission rate of any system is finite, one has to use a quantizer which sorts the input into a finite number of ranges, N. For a given N, the system is described by specifying the end

IRE TRANSACTIONS

ON INFORMATION

THEORY

March

The sort of f one would want to use would be a good points, xk, of the N input ranges, and an output level, yk, metric function, i.e., f(x) is monotonically nondecreasing corresponding to each input range. If the amplitude probability density of the signal which is the quantizer f(O) = 0 input is given, then the quantizer output is a quantity whose amplitude probability density may easily be deterf(x) = f(-4. mined as a function of the zk s and ylk s. Often it is approIf we require that f(x) be monotonicallyincreasing (with x) priate to define a distortion measure for the quantization then (1) implies process, which will be some statistic of the quantization j = 2, ... ,N error. Then one would like to choose the N yk s and the I xi - Yi-1 I = I xi - Yi I associated xk s so as to minimize the distortion. If we which implies (since yiPI and yi should not coincide) that define the distortion, D, as the expected value of f(e), where f is some function (differentiable), and E is the ( h lfxi ;b;;w~e;;d/ / d y, ,= 2, ... , N quantization error, and call the input amplitude prob2, is a wa ability density p(z), then We now take a sped& example of f(z) to further illuminate the situation. Let f(x) = 2

= g j= zi+ fb -

Y&(X)

dx

(3) implies Xj = (yj + yjm1)/2 or ?Ji = 22, - vi-1

where xN+, = 00, x, = - ~0, and the convention is that an input bet.ween xi and xi+, has a corresponding output yi. If we wish to minimize D for fixed N, we get necessary conditions by differentiating D with respect to the xi s and yi s and setting derivatives equal to zero:

= 2,

. . .

,&-

(5)

(4) implies zi +I (x - yJp(x) dx = 0 s =i

j = 1, ...

, N.

(6)

2,

. . .

,hl

(1)

aD -=aYi

zi +1 szi
f (x - yj)p(x) dx = 0 j = 1, .a. ,N (2)

(1) becomes (for p(xj) # 0) f(Xi - Yj-1) = f(Xi - YJ (2) becomes zj +1 s zi

j = 2, -es , N

(3)

- y,)p(x) dx = 0

j = 1, s-0 , N.

(4)

We may ask when these are sufficient conditions. The best answer one can manage in a general case is that if all the second partial derivatives of D with respect to the xi s and yi s exist, then the critical point determined by conditions (3) and (4) is a minimum if the matrix whose ith row and jth column element is a2 D
api apj
critical point

That is, yi is the centroid of the area of p(x) between xi and x~+~. Because of the complicated functional relationships which are likely to be induced by p(x) in (B), this is not a set of simultaneous equations we can hope to solve with any ease. Note, however, that if we choose y, correctly we can generate the succeeding xi s and yi s by (5) and (6), the latter being an implicit equation for xjil in terms of xi and yi. A method of solving (5) and (6) is to pick yl, calculate the succeeding xi s and yi s by (5) and (6) and then if u,,, is the centroid of the area of p(x) between xN and ~3, y1 was chosen correctly. (Of course, a different choice is appropriate to each value of N.) If yN is not the appropriate centroid, then of course y1 must be chosen again. This search may be systematized so that it can be performed on a computer in quite a short time. This procedure has been carried out numerically on the IBM 709 for the distribution p(x) = l/ d.% e-ZZ Z,under the restriction that xN/Z+l = 0 for N even, and Y(,~+~)/~= 0 for N odd. This procedure gives symmetric results, i.e.,
1 Obtaining ezplicit solutions to the quantizer problem for a nontrivial D(Z) is easily the most difficult part of the problem. The problem may be so&d analytically where p(z) = l/d% e-z-/z --m,y,=0,z2= -j-m. ForN =2,x1 = -w,y, = --2/2/?r,z2 = 0, y2=fl,x3 = fm, (423 is the centroid of the portion of l/d/27; e-z*/2 between the origin and + a.) For N & 3, some sort of numerical estimation is required. A somewhat dtierent approach, which yields results somewhat short of the ontimum. is to be found in V. A. Gamash. Quantization of signals-with non-uniform steps, Electrosvyaz, vol: 10, pp. 11-13; October, 1957.

where the p s are the x s and y s, is positive definite. In a specific case, one may determine whether or not the matrix is positive definite or one may simply find all the critical points (i.e., those satisfying necessary conditions) and evaluate D at each. The absolute minimum must be at one of the critical points since end points can be easily ruled out.

1960

Max: Quantizing for Minimum Distortion

if a signal amplitude x is quantized as yk, then -x is For a minimum we require quantized as -yJh. The answers appear in Table I on page 11. dD -zz -x (2i - 1) l 1,,. f (x - [y]r)p(x) dx An attempt has been made to determine the functional dr dependence of the distortion on the number of output levels. A log-log plot of the distortion vs the number of -(2N - 1) l,l,r f (x - [E2s]r)p(x) dx = 0. (8) output levels is in Fig. 1. The curve is not a straight line. The tangent t,o the curve at N = 4 has the equation D = 1.32 N-74 and the tangent at N = 36 has the A similar expression exists for the case of an odd number equation D = 2.21 x- . ~. One would expect this sort of output levels. In either case the problem is quite of behavior for large N. When N is large, the amplitude susceptible to machine computation when f(x), p(x) and N probability density does not vary appreciably from one are specified. Results have been obtained for f(x) = x2, end of a single input range to another, except for very p(x) = l/-&i e+, N = 2 to 36. They are indicated large amplitudes, which are sufficiently improbable so in Table II on page 12. that their influence is slight. Hence, most of the output A log-log plot of distortion vs number of output levels levels are very near to being the means of the end points appears in Fig. 1. This curve is not a straight line. The of the corresponding input ranges. Now, the best way tangent to the curve at N = 36 has the equation D = of quant,izing a uniformly distributed input signal is to 1.47 N- .74. A log-log plot of output level spacing vs space the output levels uniformly and to put the end number of outputs for the equal spacing which yields points of the input ranges halfway between the output lowest distortion is shown in Fig. 4. This curve is also levels, as in Fig. 2, shown for N = 1. The best way of not a straight line. Lastly, a plot of the ratio of the distorproducing a quantizer with 2N output levels for this t,ion for the optimum quantizer to that for the optimum distribution is to divide each input &nge in half and equally spaced level quantizer can be seen in Fig. 5. put the new output levels at the midpoints of these ranges, as in Fig. 3. It is easy to see that the distortion KEY TO THE TABLES in the second case is $ that in the first. Hence, D = kNe2 The numbering system for the table of output levels, where k is some constant. In fact, lc is the variance of the distribution. ylj, and input interval end points, xi, for the minimum If this sort of equal division process is performed on mean-squared error quantization scheme for inputs with a normal amplitude probability density with standard each input range of the optimum quantizer for a normally distributed signal with N output levels where N is large deviation unity and mean zero is as follows: then again a reduction in distortion by a factor of 4 is For the number of ,output levels, N, even, x1 is the expected. Asymptotically then, the equation for the first end point of an input range to the right of the tangent to the curve of distortion vs the number of output origin. An input between xi and xi+1 produces an levels should be D = lcN- where k is some constant. output yj. Commercial high-speed analog-to-digital conversion For the number of output levels, N, odd, y1 is the equipment is at present limited to transforming equal smallest non-negative output. An input between x,-~ input ranges to outputs midway between the ends of and xi produces an output ylj. the input ranges. In many applications one would like to know the best interval length to use, i.e., the one This description, illustrated in Fig. 6, is sufficient because yielding minimum distortion for a given number of output of the symmetry of the quantizer. The expected squared levels, N. This is an easier problem than the first, since error of the quantization process and informational it is only two-dimensional (for N 2 2), i.e., D is a funcentropy of the output of the quantizer are also tabulated tion of the common length r of the intervals and of for the optimal quantizers calculated. (If ps is the probany particular output level, yk. If the input has a symability of the kth output, then the informational entropy metric distribution and a symmetric answer is desired, is defined as -cF= =l p, log, pk.) the problem becomes one dimensional. If p(x) is the input Table II also pertains to a normally distributed input amplitude probability density and f(x) is the function with standard deviation equal to unity. The meaning of such that the distortion D is E[f(s,,, - sin)], then, for the entries is self-explanatory. an even number 2N of outputs,

D= x /l;;,l, f(x - [+-jr)p(x) dx

2 The values of informational entropy given show the minimum average number of binary digits required to code the quantize1 output. It can be seen from the tables that this number is always a rather large fraction of log, N, and in most cases quite near 0.9 log, N. In the cases where N = 2, n an integer, a simple n binary digit code for the outputs of the quantizer makes near optimum use of the digital transmission capacity of the system.

IRE TRANXACTIONX

ON INFORMATION

THEORY

March

Fig. l-Mean squared error vs number of outputs for optimum quantizer and optimum equally spaced level quantizer. (Minimum mean squared error for normally distributed input with D = 1.)

Fig. 4-Output level sp;cing vs number of output levels for equal optimum case. (Minimum mean squared error for normally distributed input with Q = 1.)

I
-0 0

P(X)

I
---I 2a

.6 c

i i

i
wx a

Fig. 2-Optimum quantization for the uniformly distributed case, N = 1. (Short strokes mark output levels and long strokes mark end points of corresponding input ranges.)

Fig. 5-Ratio of error for optimum quantizer to error for optimum equally spaced level quantizer vs number of outputs. (Minimum mean squared error for normally distribured input with a = 1).

, P(X)

----

-1 20

cx

-$

?L
2

L
Fig. G-Labeling of input range end points and output levels,for the optimum quantizer. (Short strokes . ,\mark output 1evels;and long strokes mark input range end points.)

Fig. 3-Optimum quantization for the uniformly distributed case, N = 2. (Short strokes mark output levels and long strokes mark end points of corresponding input ranges.)

TABLE
PARAMETERS FORTHE

I N = 19 Xi Yi 0.0 0.2184 0.4404 0.6698 0.9117 1.173 1.464 1.803 2.232 2.869

OPTIMUM &U.4NTIZER --Xi 0.0

N=l

N=2 -g--I--&-0.0 0.0 0.7980 0.3634 1.000

N=3 silT0.0 0.6120 1.224

N = 20
Yi

N = 21 Xi 0.09918 0.2989 0.5027 0.7137 0.9361 1.175 1.440 1.743 2.116 2.635 Yi

--z-I-G-j=l 2 ~~~-____~ Error Entropy -

1.000 0.0

0.1902 1.536
N=6

N=4 ______ -------!!Ij=l -~Error I 0.1175 1.911 I Xi

0.1092 0.3294 0.5551 0.7908 1.042 1.318 1.634 2.018 2.550

::;,1,

::::z

0.3823 1.244 -~ 2.203 I N=8

0.0 Y: E6

0.07994

Xi -yi 0.0 0.3177 0.6589 1.000 1.447 1.894 ______ 0.05798 2.443

0.2083 0.4197 0.6375 0.8661 1.111 1.381 1.690 2.068 2.594

0.3128 0.5265 0.7486 0.9837 1.239 1.524 1.857 2.279 2.908

0.1038

_Error Entropy 0.006844 4.002 N = 22

--

0.006203 4.074

0.0 0.1984 0.3994 0.6059 0.8215 1.051 1.300 1.579 1.908 2.324 2.946 -0.005648 4.141

Entropy

_. _.

---

N=23
xi Yi

1 Xi

IV = 21

N=7 Yi 0.0 0.5606 1.188 2.033

I
Yi xi

N=9
Yi

xi ~___~-

0.0 ;:;J; 1.748

0.2451 0.7560 1.344 2.152

0.2218 ;.G& 1:sss

0.0 0.4436 0.9188 1.476 2.255

F 4 Error Entropy

0.8744 1.611

0.04400 2.647

0.03454 2.825

0.02785 2.983 Error Entropy

-~ 0.0 0.09469 I0.09085 0.0 0.1900 0.2852 0.2736 0.1817 0.3822 0.4793 0.4594 0.3654 0.5794 0.6795 0.6507 0.5534 0.7844 0.8893 0.8504 0.7481 1.001 1.113 1.062 0.9527 1.172 1.235 1.357 1.291 1.632 1.546 1.411 1.495 1.681 1.793 1.955 1.841 2.203 2.000 2.160 2.366 2.711 2.406 2.674 2.982 3.016 -___0.005165 0.004741 j
--

xi

Yi

Yi
0.08708 0.2621 0.4399 0.6224 0.8122 1.012 1.227 1.462 1.728 2.042 2.444 3.048

:?746 0:3510 0.5312 0.7173 0.9122 1.119 1.344 1.595 1.885 2.243 2.746

0.004367 4.327 N = 27

4.206 N = 25
xi

4.268 N=26 Yi 0.0 0.1676 0.3368 0.5093 0.6870 0.8723 1.068 1.279 1.510 1.772 2.083 2.480 3.079 Xi 0.0 0.1616 0.3245 0.4905 0.6610 0.8383 1.025 1.224 1.442 1.685 1.968 2.318 2.811

I j

j=l I ---Error i 6

kzo47 0:8339 1.325 1.968

EE 1.058 1.591 2.345

0.1837 0.5599 0.9656 1.436 2.059

0.0 0.3675 :%;4 1:693 2.426

0.0 0.3401 0.6943 1.081 1.534 2.141

0.1684 0.5119 0.8768 1.286 1.783 2.499

_-__.Yi

_-

0.02293 3.125 N = 13 ______

0.01922 3.253

0.01634 3.372 N = 15
Xi Yi 0.0 0.2739

Entropy 1

-_xi

N = 14

j=l 5 t F 8

-...-.-yi 0.1569 0.4760 0.8126 1.184 1.623 2.215

xi

Yi
0.1457 0.4413 0.7505 1.086 1.468 1.939 2.625

0.0 0.3138 0.6383 0.9870 1.381 1.865 2.565

0.0 0.2935 0.5959 0.9181 1.277 1.703 2.282

0.1369 0.4143 0.7030 1.013 1.361 1.776 2.344

I.08381 0 2522 0.4231 0 5982 0.7797 0.9702 1.173 1.394 1.641 1.927 2.281 2.779

Yi _--___ t3.08060 0.07779 0.0

Xi

0.2425 0.4066 0.5743 0.7477 0.9289 1,121 1.328 1.556 1.814 2.121 2.514 3.109

0.2340 0.3921 0.5537 0.7202 .0.8936 1.077 1.273 1.487 1.727 2.006 2.352 2.842

_0.01406 3.481 N = 16 Xi Yi 0.1284 0.3881 0.6568 0.9424 1.256 1.618 2.069 2.733

0.5548 0.8512 1.175 1.546 2.007 2.681

Error Entropy

0.004036 4.384 N = 28
_-

-- -----A0.003741
4.439
N = 29 xj
_-

-4.491

0.1556 0.3124 0.4719 0.6354 0.8049 0.9824 1.171 1.374 1.599 1.854 2.158 2.547 3.137

0.003477

N = 30 Yi Xi 0.0 0.1406 0.2821 0.4255 0.5719 0.7225 0.8788 1.043 1.217 1.404 1.609 1.840 2.111 2.448 2.926 Yi 0.07016 0.2110 iELE 0.6460 0.7990 0.9586 1.127 1.306 1.501 1.717 1.964 2.258 2.638 3.215

Error Entropy

--

0.01223 3.582

0.01073 3.677 1 N = 18 0.0 0.1503 0.3018 0.4556 0.6132 0.7760 0.9460 1.126 1.319 1.529 1.766 2.042 2.385 2.871

Yi

__Xi

N=17

j=l z 4 5 i Error Entropy

fi.582 0: 5224 0.7996 1.099 1.437 1.844 2.401

0.1215 0.3670 0.6201 0.8875 1.178 1.508 1.906 2.454

_0.009497 3.765

0.0 0.2430 0.4909 0.7493 1.026 1.331 1.685 2.127 2.781 1

0.0 0.2306 0.4653 0.7091 0.9680 1.251 1.573 1.964 2.504

0.1148 0.3464 0.5843 0.8339 1.102 1.400 1.746 2.181 2.826 Error Entropy

0.07502 0 2256 0 3780 0.5333 0.6930 0.8589 1.033 1.218 1.419 1.640 1.892 2.193 2.578 3.164
_-

0.07257 0.2182 0.3655 0.5154 0.6693 0.8287 0.9956 1.172 1.362 1.570 1.804 2.077 2.417 2.899

__0.003240 4.542

kz451 0: 2913 0.4396 0.5912 0.7475 0.9100 1.081 1.263 1.461 1.680 1.929 2.226 2.609 3.190

_-

0.008463
3.849

0.007589
3.928

0.003027
_-

0.002834 4.639
Cont d next pug2

4.591

12 d TABLEI, Cont
N = 31 Xj
I.06802 0.2045 0.3422 0.4822 0.6254 0.7730

IRE TRANXACTIONS
-Yj 0.0
0.1360 0.4115 0.5528

ON INFORMATION

THEORY
TABLE II Mean Squared Error 1.000
0.3634

March

N = 32 Xi 0.0
0.1320 0.2648

N = 33

--

PARAMETERSFORTHEOPTI~\IUMEQUALLYS~ACEDLEVELQUANTIZER
Output Level Spacing 1.596 1.224 0.9957
0.8430 0.7334 0.6508 0.5860 0.5338 0.4546 0.4238

--

--

-- Yi I 0.0 0.06590 0.0640(3

Informational Entropy

0.2729 0.6979
0.8481 1.005 1.170 1.347 1.540 1.753

0.3991 0.5359
0.6761 0.8210

0.1924 0.3218
0.4530 0.7245 0.8667 1.015 1.171 1.338 1.518 1.716

0.5869

0.1280 0.2567 0.3868 0.6547

0.1902
0.1188 0.08218 0.06065 0.04686 0.03744

0.5192 0.7943 0.9392 1.091 1.252 1.424 1.612 1.821

0.9265 1.259
1.444 1.646 1.875 2.143 2.477 1.088

2.952

1.997 2.289

0.9718 1.130 1.299 1.482 1.682 1.908 2.977

0.8947 1.049
1.212 1.387 1.577 1.788

:
7

1.904 2.183 2.409 2.598

1.536

i 10 11 :; 14
15

0.4908 0.3972 0.3739 0 3189

0 03069
0.02568 0.02185 0.01885 0.01645 0.01450

2.665

3.239

2.029 2.319 2.692

1.940
2.204 2.533 3.002

-Error Entropy

16 17

.-

0.002658 4.685

--

0.002499
4.730

0.002354 4.773

0.2909
0.2788 0.2678 0.2576 0.2482

0.01289 0.01154 0.01040 0.009430 0.008594 0.007869

0.0

N = 34

---

N = 35 Yf Xi
0.06043 0.1816 0.3036 0.4272 0.5530

N = 36
-1-

3.933 3.990 4.097

23

Xi
0.1244

_-

Yi 0.0 0.1209
0.2423 0.3650 0.6166 0.7471 0.8820 1.023 1.170 1.327

0.2495
0.3758 0.5043 0.6355 0.7705 1.057 1.211 1.375 1.553

0.06212 0.1867 0.3122

0.0

0.4394 0.5691
0.7020

0.2359
0.3552 0.4762

I.05876 -1; 0.1177 0.1765

YJ

;t
26 27 28

0.2396
0.2315 0.2240 0.2171 0.2105 0.2044

4.194
4.241 4.285 4.328 4.370 4.410 4.487 4.524 4.560

0.2952
0.4152 0.5372 0.6620

29

0.9104

1.749 1.971
2.232

0.8391 0.9818 1.131 1.290 1.460 1.646 1.853 2.090

0.6819
0.8146

0.4895

0.5996
0.7261 0.8567 1.134 1.285 1.445

i:
32 33 34

0.9523 1.096 1.248 1.411 1.587 1.781 2.001

0.9923

0.7903 0.9231 1.062

0.1987 0.1932 0.1881 0.1833 0.1787 0.1744

0.003905
0.003688

0.003490
0.003308 0.003141

4.449

0.002986
0.002843

0.1703

4.594

2.559
3.025

1.495 1.679 1.883 2.119 2.401

1.619 1.812
2.030 2.287

1.913

2.609
3.070

_Error

-0.002220

--

2.791 3.349

.Entropy -

0.002097
4.856

0.001985 4.895

4.815