1 00:00:00,480 --> 00:00:05,182 Hi and welcome to module 7.2. Now that we know more or less how to deal 2 00:00:05,182 --> 00:00:09,655 with stochastic serials, we are ready to look into the inner workings of the 3 00:00:09,655 --> 00:00:12,560 quantizer. And try to describe the kind of distortion 4 00:00:12,560 --> 00:00:16,787 introduced by the quantizer itself. The way we will do that is by equating the 5 00:00:16,787 --> 00:00:21,765 distortion to a source of white noise, and by analyzing the properties of this noise. 6 00:00:21,766 --> 00:00:27,775 Of course, we're analyzing the very simple type of quantization over a very simple 7 00:00:27,775 --> 00:00:30,890 class of signals. And quantization it can be designed to be 8 00:00:30,890 --> 00:00:34,462 much more complicated than that. But this is a very good starting point and 9 00:00:34,462 --> 00:00:38,620 we will leave the design of more complex systems to your next signal processing 10 00:00:38,620 --> 00:00:42,481 class. Hi, and welcome to module 7.2 of Digital 11 00:00:42,481 --> 00:00:47,923 Signal Processing, in which we will talk about Quantization. 12 00:00:47,923 --> 00:00:52,285 We will examine quantization in general terms, and then concentrate on uniform 13 00:00:52,285 --> 00:00:55,083 quantization and the associated error analysis. 14 00:00:55,084 --> 00:00:59,162 And then we will briefly talk about clipping, saturation and companding. 15 00:00:59,162 --> 00:01:03,444 Quantization is really the second half of this story in the digital signal 16 00:01:03,444 --> 00:01:07,100 processing, the first half being the discretization of time. 17 00:01:07,100 --> 00:01:11,861 We soon realize that digital devices can only deal with integers no matter how many 18 00:01:11,861 --> 00:01:16,346 bits we use inside each memory cell, and so we need to map the numeric range that 19 00:01:16,346 --> 00:01:20,014 discreet time samples live on onto a finite set of values. 20 00:01:20,015 --> 00:01:24,388 In so doing, the reason irreversible loss of information because we're chopping the 21 00:01:24,388 --> 00:01:27,810 amplitudes according to the resolution that our system allows for. 22 00:01:27,810 --> 00:01:32,943 If we are to represent the situation graphically, we have a sequence of 23 00:01:32,943 --> 00:01:38,370 discrete time samples here that belong, say to the set of complex numbers. 24 00:01:38,370 --> 00:01:43,620 These samples go through a quantizer and the sequence of quantized samples come out 25 00:01:43,620 --> 00:01:47,630 where each quantized sample now belongs to the set of integers. 26 00:01:47,631 --> 00:01:52,991 When modeled input as a stochastic process and to study the facts of the system we 27 00:01:52,991 --> 00:01:58,502 have to consider several factors. How many bits per sample this quantizer 28 00:01:58,502 --> 00:02:01,430 will allocate? What is the storage scheme used to 29 00:02:01,430 --> 00:02:05,330 represent the quantized samples, for instance, is it fixed point or floating 30 00:02:05,330 --> 00:02:08,192 point. And what are the properties of the input 31 00:02:08,192 --> 00:02:11,600 as a stochastic process? What is it's range, and what is it's 32 00:02:11,600 --> 00:02:15,584 probability distribution? The simplest quantizer is the scalar 33 00:02:15,584 --> 00:02:19,010 quantizer. In this quantizer, each sample is encoded 34 00:02:19,010 --> 00:02:24,654 visually so we don't take into account relationship between neighboring samples. 35 00:02:24,655 --> 00:02:29,032 Each sample is quantized independently, so there is no memory of previous 36 00:02:29,032 --> 00:02:33,828 quantization operations. And each sample is encoded using R bits. 37 00:02:33,828 --> 00:02:39,234 So, the rate here is R bits per sample. Let's see what happens when we scalar 38 00:02:39,234 --> 00:02:43,118 quantize an input. Assume we know that each input sample Is 39 00:02:43,118 --> 00:02:46,978 strictly between A and B. Each sample is quantized over 2 to the R 40 00:02:46,978 --> 00:02:50,010 possible values, because we are using R bits per sample. 41 00:02:50,010 --> 00:02:54,413 And this define 2 to the R intervals over the range A to B. 42 00:02:54,414 --> 00:02:58,786 Each interval will be associated to a quantization value. 43 00:02:58,787 --> 00:03:02,800 Which means that whenever the sample say, falls into this interval here. 44 00:03:02,800 --> 00:03:08,054 It will be replaced by this representative value for the interval, and similarly for 45 00:03:08,054 --> 00:03:12,324 the other intervals. So, let's look at an example for R equal 46 00:03:12,324 --> 00:03:17,634 to 2, the range a to be would be divided into 4 intervals and these are the 47 00:03:17,634 --> 00:03:20,662 boundaries of each interval. We would associate a representative point 48 00:03:20,662 --> 00:03:21,746 to each interval. And we would encode each interval using 2 49 00:03:21,746 --> 00:03:24,983 bits. So the sequence zero-zero would be 50 00:03:24,983 --> 00:03:30,050 associated to the first interval, and so on and so forth. 51 00:03:30,051 --> 00:03:42,689 In other words, the quantized values would be one of these four possible values. 52 00:03:42,690 --> 00:03:48,429 And internally the quantizer would know how to associate this binary value to this 53 00:03:48,429 --> 00:03:51,620 real value. The two natural questions at this point 54 00:03:51,620 --> 00:03:55,540 are what are the optimal interval boundaries i of k, and what are the 55 00:03:55,540 --> 00:03:59,159 optimal quantization values for each interval had x of k. 56 00:03:59,160 --> 00:04:02,934 To find an answer, let's consider the quantization error. 57 00:04:02,935 --> 00:04:06,873 So, this is defined as the difference between the quantized value. 58 00:04:06,874 --> 00:04:11,690 Namely, the representative value for each interval, minus the real value. 59 00:04:11,690 --> 00:04:15,298 We modeled the input as a stochastic process, as we said in the beginning. 60 00:04:15,298 --> 00:04:18,580 And we modeled the error as a white noise sequence. 61 00:04:18,580 --> 00:04:22,102 In other words, we assume the, the samples are uncorrelated. 62 00:04:22,102 --> 00:04:25,640 And we assume that all error samples have the same distribution. 63 00:04:25,640 --> 00:04:30,470 This is a rather drastic assumptions, but as a first approximation, it will give us 64 00:04:30,470 --> 00:04:33,192 a good feeling for the effects of a quantizer. 65 00:04:33,193 --> 00:04:37,035 In order to proceed further, we need the statistical description of the input 66 00:04:37,035 --> 00:04:39,292 samples. Let's also make some assumptions on the 67 00:04:39,292 --> 00:04:43,261 internal structure of the quantizer. And let's consider the simple but very 68 00:04:43,261 --> 00:04:48,006 common case of uniform quantization. The range in this case is split into 2 to 69 00:04:48,006 --> 00:04:52,777 the R equal intervals. But with delta, which is equal to B minus 70 00:04:52,777 --> 00:04:59,212 A, the range of the input samples, divided by the 2 to the R, the number of levels 71 00:04:59,212 --> 00:05:05,055 afforded to by a rate of R bits per sum. So in case of R is equal to 2 as before, a 72 00:05:05,055 --> 00:05:08,470 range will be split into 4 equal with intervals. 73 00:05:08,470 --> 00:05:13,369 The mean square quantization error is the variance of the error signal, namely the 74 00:05:13,369 --> 00:05:18,055 expectation of the difference between the quantized samples and the original 75 00:05:18,055 --> 00:05:22,544 samples. If we know the probability distribution 76 00:05:22,544 --> 00:05:27,809 function for the input, we can write that as the integral from A to B of the PDF of 77 00:05:27,809 --> 00:05:33,479 the input times the error function, which is the quantized value of the integration 78 00:05:33,479 --> 00:05:37,160 variable minus the integration variable squared. 79 00:05:37,160 --> 00:05:40,142 This is a standard application of the expectation theorem. 80 00:05:40,142 --> 00:05:46,048 And we can finally split the integral over the independent quantization intervals, 81 00:05:46,048 --> 00:05:51,316 and we get this last formulation here. Now, in order to proceed, we need to know 82 00:05:51,316 --> 00:05:56,561 the probability distribution function of the input to compute these integrals. 83 00:05:56,561 --> 00:05:59,730 So now, we make a further hypothesis on the input. 84 00:05:59,730 --> 00:06:02,179 We assume that it is uniformly distributed. 85 00:06:02,180 --> 00:06:09,798 That means that the probability distribution function is just a constant 86 00:06:09,798 --> 00:06:15,086 from A to B, A value 1 over B minus A. The mean square error becomes before the 87 00:06:15,086 --> 00:06:17,292 sum of 2 to the R minus 1 independent integrals. 88 00:06:17,293 --> 00:06:23,473 Each one of which, is the integral over the quantization interval of the 89 00:06:23,473 --> 00:06:30,580 representative value for the interval which we haven't determined yet, minus tau 90 00:06:30,580 --> 00:06:35,095 square divided by B minus A. In order to find the optimal quantization 91 00:06:35,095 --> 00:06:39,166 points, we minimize the mean square error with respect to the quantization points 92 00:06:39,166 --> 00:06:42,914 themselves. We take partial derivatives of the error 93 00:06:42,914 --> 00:06:47,134 with respect to x hat of m. When we take partial derivatives of the 94 00:06:47,134 --> 00:06:51,486 sum, the partial derivative will kill all terms of the sum except the one that 95 00:06:51,486 --> 00:06:56,810 depends on the derivation variable. So we're left with an integral over the 96 00:06:56,810 --> 00:07:03,610 interval i m of two times the quantization point minus tau divided by B minus A and d 97 00:07:03,610 --> 00:07:06,590 tau. We have to compute this integral over the 98 00:07:06,590 --> 00:07:11,821 quantization interval number m. And you remember the range is from A to B, 99 00:07:11,821 --> 00:07:16,763 we divide this into two to the r-equal intervals of size delta. 100 00:07:16,764 --> 00:07:23,430 And the lower and upper boundary for the interval number m will be a plus m minus 101 00:07:23,430 --> 00:07:29,746 delta and A plus m minus delta plus delta. In order to minimize the error we set the 102 00:07:29,746 --> 00:07:34,354 partial derivatives to zero for all quantization intervals and we find that 103 00:07:34,354 --> 00:07:39,322 this happens when then quantization point is the interval's midpoint with this we 104 00:07:39,322 --> 00:07:44,890 can plot the quantizers characteristic. Here we show it for R equal to 3, 3 bits 105 00:07:44,890 --> 00:07:49,470 per sample. And you can see that the quantizer 106 00:07:49,470 --> 00:07:54,097 associates each quantization interval to its midpoint. 107 00:07:54,098 --> 00:07:59,267 And you have the typical staircase characteristic of the uniform quantizer. 108 00:07:59,267 --> 00:08:04,515 Back to the mean square error, we now replace into the expression for the mean 109 00:08:04,515 --> 00:08:08,952 square error, the values that we found in the previous analysis. 110 00:08:08,952 --> 00:08:15,094 Namely, the boundaries for each quantization interval, the value for the 111 00:08:15,094 --> 00:08:21,263 meet point and the expression for the priority distribution of the input. 112 00:08:21,263 --> 00:08:26,198 And if we compute this integral, we obtain the fundamental result of uniform 113 00:08:26,198 --> 00:08:31,280 quanitization, the mean square error for uniform quanitizer is equal to delta 114 00:08:31,280 --> 00:08:37,287 square over 12. Where delta is B minus A divided by 2 to 115 00:08:37,287 --> 00:08:40,480 the R. If we analyze the error a little bit 116 00:08:40,480 --> 00:08:45,772 further, we can relate the expression of the error to the expression for the 117 00:08:45,772 --> 00:08:49,000 signal's energy. Since we assume that the input is 118 00:08:49,000 --> 00:08:53,770 uniformly distributed. We can compute its variance, ie, its 119 00:08:53,770 --> 00:08:58,612 energy, as B minus A squared over 12. It's the variance of a uniformly 120 00:08:58,612 --> 00:09:02,902 distributed variable. And so we can compute the signal to noise 121 00:09:02,902 --> 00:09:08,067 ratio as the power of the signal divided by the power of the error. 122 00:09:08,068 --> 00:09:12,894 And the signal to noise ratio happens to be 2 to the 2R, so if the input is 123 00:09:12,894 --> 00:09:18,704 uniformly distributed, and the quantizer is a uniform quantizer, which means it's 124 00:09:18,704 --> 00:09:22,626 matched to the input. The signal to noise ratio is only a 125 00:09:22,626 --> 00:09:26,757 function of the number of bits per sample that we allocate. 126 00:09:26,758 --> 00:09:33,040 We can express this result in decibels by taking 10 times the log in base 10 of 2 to 127 00:09:33,040 --> 00:09:37,815 the power of 2R. And we get the famous and handy formula, 128 00:09:37,815 --> 00:09:41,639 of 6 dBs per bit. In other words, every bit we add to the 129 00:09:41,639 --> 00:09:46,616 internal representation of a quantized signal adds 6 dBs of signal to noise 130 00:09:46,616 --> 00:09:49,528 ratio. So, for instance, a compact disc has 16 131 00:09:49,528 --> 00:09:54,553 bits per sample, so, the maximum signal to noise ratio that you can achieve in a CD 132 00:09:54,553 --> 00:09:59,002 is 96 dBs. A DVD on the other hand, has 24 bits per 133 00:09:59,002 --> 00:10:03,222 sample, so your signal to noise ratio grows to 144 dBs. 134 00:10:03,223 --> 00:10:07,942 So what happens if, as is very likely to happen in real life, the input is not 135 00:10:07,942 --> 00:10:12,128 bounded to a known interval A, B. Well, we have two choices, the first one 136 00:10:12,128 --> 00:10:16,199 is to clip samples. So if the sample is smaller than A, we set 137 00:10:16,199 --> 00:10:19,670 it to A and if it's greater than B we set it to B. 138 00:10:19,670 --> 00:10:23,034 In this case, we introduce linear distortion in the signal and this is 139 00:10:23,034 --> 00:10:26,031 really the principle behind distortion boxes for guitars. 140 00:10:26,032 --> 00:10:30,582 So, interesting, but not necessarily what we want to hear all the time. 141 00:10:30,582 --> 00:10:37,252 Alternatively, we can use a saturation curve to smoothly map the input onto the 142 00:10:37,252 --> 00:10:40,733 desired range. This is closer to the saturation 143 00:10:40,733 --> 00:10:44,804 characteristic of old electronic components, such as tubes, that are 144 00:10:44,804 --> 00:10:48,419 praised by audiophiles for their lack of audible distortion. 145 00:10:48,420 --> 00:10:52,884 We can plot the clipping and saturation curves by taking for instance, the 146 00:10:52,884 --> 00:10:58,146 interval minus 1, 1. And we can see the clipping curve would 147 00:10:58,146 --> 00:11:03,404 map values outside of the range to the edge of the range. 148 00:11:03,404 --> 00:11:08,988 Whereas, the saturation curve is linear around zero and then tapers off 149 00:11:08,988 --> 00:11:13,600 asymtodically. If the input is not uniform, we can still 150 00:11:13,600 --> 00:11:17,230 use a uniform quantizer, and accept an error penalty. 151 00:11:17,230 --> 00:11:22,791 For instance, if the input is Gaussian, it can be shown that the mean square error 152 00:11:22,791 --> 00:11:26,486 has this form. It depends now of course on the variance 153 00:11:26,486 --> 00:11:31,296 of the input, but even for input signals with unit variance, it would be larger 154 00:11:31,296 --> 00:11:35,122 than delta squared over 12. Alternatively, if we know the exact 155 00:11:35,122 --> 00:11:39,946 probability distribution function for the input, we can use the Lloyd-Max algorithm 156 00:11:39,946 --> 00:11:42,536 to design an optimal quantizer for the input. 157 00:11:42,536 --> 00:11:46,446 Alternatively, a common practice in audio signal processing is the use of 158 00:11:46,446 --> 00:11:49,765 companders. The idea is that samples from signals such 159 00:11:49,765 --> 00:11:55,021 as speech or music will be generally small in amplitude with the occasional excursion 160 00:11:55,021 --> 00:11:59,852 into the outer reaches of the range. So for instance, this is a mu law 161 00:11:59,852 --> 00:12:06,652 compander, commonly used in radio and you see that small values, say between here 162 00:12:06,652 --> 00:12:12,011 and here get allocated to a wide number of quantization levels. 163 00:12:12,011 --> 00:12:17,272 Whereas the rest of the range will share the other half. 164 00:12:17,272 --> 00:12:23,520 So there's a, so say, 10% of the range will get 50% of the quantization level and 165 00:12:23,520 --> 00:12:27,217 the remaining 90% will get the remaining 50%. 166 00:12:27,218 --> 00:12:36,843 So we have more precision for the values that we know to be more probable.