1 00:00:00,280 --> 00:00:04,030 Hi, and welcome to module 7.1 of Digital Signal Processing. 2 00:00:04,030 --> 00:00:06,700 Today we will talk about Stochastic signal processing. 3 00:00:06,700 --> 00:00:08,350 Stochastic means random. 4 00:00:08,350 --> 00:00:11,450 And so we'll start with a simple example of a random signal. 5 00:00:11,450 --> 00:00:14,012 We will describe its power spectral density, 6 00:00:14,012 --> 00:00:17,240 which is the spectral representation of a random signal. 7 00:00:17,240 --> 00:00:20,890 We will see what happens when we filter a stochastic signal. 8 00:00:20,890 --> 00:00:23,230 And then we will talk about the concept of noise. 9 00:00:23,230 --> 00:00:25,550 So why stochastic signal processing? 10 00:00:25,550 --> 00:00:29,950 So far in the class we have assumed that every discrete time signal we used, 11 00:00:29,950 --> 00:00:32,050 could be described exhaustively. 12 00:00:32,050 --> 00:00:36,630 Either via a close form representation like so, or, and this is really 13 00:00:36,630 --> 00:00:41,990 the advantage of discrete time signals, simply by enumerating its non zero values. 14 00:00:41,990 --> 00:00:44,810 However interesting signals are not known in advance. 15 00:00:44,810 --> 00:00:47,690 For instance what I'm going to say next contains information that this 16 00:00:47,690 --> 00:00:49,350 not known in advance. 17 00:00:49,350 --> 00:00:53,628 But I do know that what I'm going to say next, is going to be a speech signal. 18 00:00:53,628 --> 00:00:58,120 So I could try to describe stochastic signals in terms of a probabilistic model. 19 00:00:58,120 --> 00:01:02,570 The good news is that we can do signal processing with stochastic signals. 20 00:01:02,570 --> 00:01:05,810 Using the same tools that we have developed so far. 21 00:01:05,810 --> 00:01:09,180 In this module, we will not try to treat the subject of stochastic signal 22 00:01:09,180 --> 00:01:12,420 processing, either exhaustively or very rigorously. 23 00:01:12,420 --> 00:01:14,450 But we will try to give you enough intuition and 24 00:01:14,450 --> 00:01:18,949 the mathematical tools to deal with ubiquitous random signals, such as noise. 25 00:01:20,360 --> 00:01:23,580 So let's start with a simple example of a stochastic signal. 26 00:01:23,580 --> 00:01:27,890 Suppose we generate a discrete time signal by tossing a coin for each sample and 27 00:01:27,890 --> 00:01:31,630 setting the sample's value to +1 if the outcomes head. 28 00:01:31,630 --> 00:01:33,510 And -1 if the outcomes tail. 29 00:01:34,630 --> 00:01:37,360 So because of the mechanics of the coin toss, 30 00:01:37,360 --> 00:01:39,680 each sample is independent from all others, and 31 00:01:39,680 --> 00:01:45,340 each sample has a 50% probability of being +1, and a 50% probability of being -1. 32 00:01:45,340 --> 00:01:48,380 So this is our stochastic signal generator, and 33 00:01:48,380 --> 00:01:52,070 every time we turn on the generator, every time we repeat this experiment of 34 00:01:52,070 --> 00:01:56,450 coin tossing, we get what we call a different realization of the signal. 35 00:01:56,450 --> 00:01:58,407 We can plot it, and so for 36 00:01:58,407 --> 00:02:04,700 instance the first run of cost gives us this series of +1 and -1. 37 00:02:04,700 --> 00:02:09,695 And then if we repeat the experiment again, we toss the coin another 32 times. 38 00:02:09,695 --> 00:02:14,225 We got a different realization, and we can repeat the experiment as many times as we 39 00:02:14,225 --> 00:02:19,765 want and the outcome will likely be different every time we run the machine. 40 00:02:19,765 --> 00:02:22,835 Although we cannot describe in advance the values of the signal, 41 00:02:22,835 --> 00:02:26,275 we know the mechanics behind the generation of the signal. 42 00:02:26,275 --> 00:02:28,385 And the question is can we analyze this signal for 43 00:02:28,385 --> 00:02:32,900 instance can we get a spectral representation of a random signal? 44 00:02:32,900 --> 00:02:38,370 So, let's try by taking the DFT of a finite set of random samples. 45 00:02:38,370 --> 00:02:43,430 So, if we do that, we just run the machine for 32 samples and then we take a DFT. 46 00:02:43,430 --> 00:02:47,080 But every time we'll repeat the experiment, we get a different plot. 47 00:02:47,080 --> 00:02:49,756 And the values don't really seem to follow any pattern. 48 00:02:49,756 --> 00:02:55,150 So maybe, we tell ourselves, maybe we don't have enough 49 00:02:55,150 --> 00:02:59,980 data to discover a pattern in the DFT, so maybe we should take longer realizations. 50 00:02:59,980 --> 00:03:02,820 Instead of 32 points, maybe we should take more. 51 00:03:02,820 --> 00:03:06,370 And so let's try and take 64 points. 52 00:03:06,370 --> 00:03:08,220 And still we don't see any pattern. 53 00:03:08,220 --> 00:03:10,920 So let's try and take a 128 points. 54 00:03:10,920 --> 00:03:13,760 And again, the spectrum doesn't seem to show any trait 55 00:03:13,760 --> 00:03:15,800 that we can readily understand. 56 00:03:15,800 --> 00:03:17,340 So we need a new strategy. 57 00:03:17,340 --> 00:03:21,110 When faced with random data an intuitive response is to take averages. 58 00:03:21,110 --> 00:03:24,950 So we average out the values in order to eliminate the fluctuations. 59 00:03:24,950 --> 00:03:29,240 In probability theory the average is computed across a realization 60 00:03:29,240 --> 00:03:30,810 not along the time access. 61 00:03:30,810 --> 00:03:33,760 But, across different repetitions of the experiment. 62 00:03:33,760 --> 00:03:35,400 So, for the coin toss signal, 63 00:03:35,400 --> 00:03:40,600 the expectation of each sample is minus one times the probability that 64 00:03:40,600 --> 00:03:46,420 the n-th toss is tail plus one times the probability that the n-th toss is head. 65 00:03:46,420 --> 00:03:49,450 But we know that these probabilities are one half each, so 66 00:03:49,450 --> 00:03:51,310 this sum ends up being zero. 67 00:03:52,520 --> 00:03:54,980 Since the DFT is a linear operator 68 00:03:54,980 --> 00:03:57,600 averaging the DFT values will not work either. 69 00:03:57,600 --> 00:04:00,680 If we try and do that we quickly realize that the average of 70 00:04:00,680 --> 00:04:03,740 each DFT sample will be zero as well. 71 00:04:03,740 --> 00:04:06,990 However, the signal does move from minus one to plus one. 72 00:04:06,990 --> 00:04:09,790 So its energy or it's power must be non zero. 73 00:04:09,790 --> 00:04:14,000 If you remember the definition of energy and power of the signal from module 2.1. 74 00:04:14,000 --> 00:04:17,480 We can readily see that the energy is infinite. 75 00:04:17,480 --> 00:04:20,710 Because the limit for N goes to infinity of the sum. 76 00:04:20,710 --> 00:04:25,210 From minus n to n of the values of the sequence squared 77 00:04:25,210 --> 00:04:27,190 It's simply two n plus one. 78 00:04:27,190 --> 00:04:29,460 Because each value squared will be equal to one. 79 00:04:29,460 --> 00:04:31,500 And so, as n going to infinity. 80 00:04:31,500 --> 00:04:32,740 this will diverge. 81 00:04:32,740 --> 00:04:36,320 However, the signal does have finite power over any interval. 82 00:04:36,320 --> 00:04:39,720 We take the energy over a minus n to n interval, and 83 00:04:39,720 --> 00:04:42,170 we normalize that by the length of the interval. 84 00:04:42,170 --> 00:04:46,910 And we find out that the power is actually 1, regardless of the interval's length. 85 00:04:46,910 --> 00:04:48,400 Let's try the following strategy. 86 00:04:48,400 --> 00:04:51,650 Let's try to average the DFT's square magnitude, normalized. 87 00:04:51,650 --> 00:04:53,710 So we pick an interval N. 88 00:04:53,710 --> 00:04:55,480 We pick a number of iterations, so 89 00:04:55,480 --> 00:04:58,290 a number of times that we will repeat the experiment. 90 00:04:58,290 --> 00:05:04,300 We run the signal generator M times, and we obtain M N-point realizations. 91 00:05:04,300 --> 00:05:06,670 We compute the DFT of each realizations, and 92 00:05:06,670 --> 00:05:11,110 we average their square magnitude, divided by the length of the interval. 93 00:05:11,110 --> 00:05:12,670 So if we do that, well, of course, 94 00:05:12,670 --> 00:05:16,120 the first DFT will be this random pattern that we have seen before. 95 00:05:16,120 --> 00:05:18,420 But as we increase the number of realizations, 96 00:05:18,420 --> 00:05:21,910 we see that the points seem to converge to something. 97 00:05:21,910 --> 00:05:27,010 And indeed, by the time M hits 5000, we see that the average 98 00:05:27,010 --> 00:05:31,790 of the squared managed of the DFT seems to converge to the constant one. 99 00:05:31,790 --> 00:05:37,450 So we have defined a quantity here, P[k] which is the expected value of the squared 100 00:05:37,450 --> 00:05:42,830 magnitude of the kth bin of the of the DFT over capital N points. 101 00:05:42,830 --> 00:05:46,550 Divided by capital N, and it looks very much as if P[k], 102 00:05:46,550 --> 00:05:50,170 this expectation, is equal to one for all k's. 103 00:05:50,170 --> 00:05:52,730 So, if the square magnitude 104 00:05:52,730 --> 00:05:57,110 of the DFT tends to the energy distribution in frequency of the signal. 105 00:05:58,120 --> 00:06:01,380 Then the normalized square magnitude of the DFT. 106 00:06:01,380 --> 00:06:05,580 Tends to the power distribution, or the power density, in frequency. 107 00:06:05,580 --> 00:06:09,660 So what we just have derived is a new frequency representation for signals that 108 00:06:09,660 --> 00:06:15,160 have infinite energy but finite power, and it's called the power spectral density. 109 00:06:15,160 --> 00:06:18,600 Let's try to develop some intuition about the power spectral density 110 00:06:18,600 --> 00:06:20,010 of the coin toss signal. 111 00:06:20,010 --> 00:06:21,850 The fact that it is constant. 112 00:06:21,850 --> 00:06:26,160 Means that the power is equally distributed over all frequencies. 113 00:06:26,160 --> 00:06:30,890 In other words, we cannot predict if the signal will move slowly or super-fast. 114 00:06:30,890 --> 00:06:35,430 We cannot predict that because each sample is independent of each other. 115 00:06:35,430 --> 00:06:38,890 So we could actually have a realization where just by luck. 116 00:06:38,890 --> 00:06:43,030 We have a constant signal because all coin tosses are heads. 117 00:06:43,030 --> 00:06:47,710 Or we could have a realization in which at each coin toss we have a different outcome 118 00:06:47,710 --> 00:06:51,700 and so the signal will oscillate at the maximum digital frequency. 119 00:06:51,700 --> 00:06:53,720 The power spectrum of presentation. 120 00:06:53,720 --> 00:06:57,250 Embodies this behavior by distributing the probability of power 121 00:06:57,250 --> 00:06:58,930 over the entire frequency axis. 122 00:07:00,160 --> 00:07:02,570 Lets try now to filter a random process. 123 00:07:02,570 --> 00:07:05,750 And to run this experiment, we take our coin toss signal once again. 124 00:07:05,750 --> 00:07:09,100 And we take what is probably the simplest filter we can think of 125 00:07:09,100 --> 00:07:11,130 just a 2-point Moving Average. 126 00:07:11,130 --> 00:07:13,680 So the output of the filter will the average 127 00:07:13,680 --> 00:07:17,120 of two neighboring points in the input random signal. 128 00:07:17,120 --> 00:07:19,320 And the question we want to find an answer to is, 129 00:07:19,320 --> 00:07:21,360 what is the power spectral density of the output? 130 00:07:22,550 --> 00:07:27,150 So we complete this numerically, we run the experiment as before. 131 00:07:27,150 --> 00:07:29,440 We generate a random signal. 132 00:07:29,440 --> 00:07:30,590 This time we filter it. 133 00:07:30,590 --> 00:07:34,250 And then we take the average over several realizations 134 00:07:34,250 --> 00:07:37,140 of the DFT squared of the filtered output. 135 00:07:37,140 --> 00:07:38,960 So, we run the experiment like before, 136 00:07:38,960 --> 00:07:41,980 which was an interval M, we generate the random signal. 137 00:07:41,980 --> 00:07:43,500 This time we filter it. 138 00:07:43,500 --> 00:07:48,230 And then we take the average over several realizations of the DFT squared. 139 00:07:48,230 --> 00:07:50,648 For M equal to one, we don't really see a pattern. 140 00:07:50,648 --> 00:07:56,310 But as we see that the power spectral density converges to a very precise shape. 141 00:07:56,310 --> 00:08:01,310 Now, if you remember the frequency response of the 2-point Moving Average, 142 00:08:01,310 --> 00:08:05,632 that is just H of e to the j omega equal to one plus e to the j omega divided 143 00:08:05,632 --> 00:08:06,170 by two. 144 00:08:06,170 --> 00:08:10,690 And this shape here Is nothing but 145 00:08:10,690 --> 00:08:16,360 the square magnitude of this frequency response evaluated at the DFT points, i.e. 146 00:08:16,360 --> 00:08:19,220 At a two pi over N K. 147 00:08:19,220 --> 00:08:23,260 So indeed, if we plot this we see that the match is almost perfect. 148 00:08:23,260 --> 00:08:26,770 The power spectral density of the output 149 00:08:26,770 --> 00:08:29,870 seems to be the power spectral density of the input, i.e. 150 00:08:29,870 --> 00:08:34,570 The constant one, multiplied, by the square magnitude 151 00:08:34,570 --> 00:08:38,970 of the frequency response of the filter this time computed on the DFT grid. 152 00:08:38,970 --> 00:08:42,860 We can generalize these results beyond the numerical experiments and 153 00:08:42,860 --> 00:08:46,360 move it to the world of infinite support stochastic processes. 154 00:08:46,360 --> 00:08:50,350 The details are in the book but here we will summarize the key points. 155 00:08:50,350 --> 00:08:53,580 So, stochastic process is characterized in frequency 156 00:08:53,580 --> 00:08:56,630 by its power spectral density and it can be shown. 157 00:08:56,630 --> 00:08:59,510 That the power spectral density is the DTFT 158 00:08:59,510 --> 00:09:01,890 of the autocorrelation of the process. 159 00:09:01,890 --> 00:09:06,130 Where each sample of the autocorrelation is obtained by taking the expectation 160 00:09:06,130 --> 00:09:11,860 of the product of the stochastic signal times a delayed copy of itself. 161 00:09:11,860 --> 00:09:15,620 For a filtered stochastic process, the general result is that the power 162 00:09:15,620 --> 00:09:20,240 spectral density of the output Is equal to the power spectral density of the input, 163 00:09:20,240 --> 00:09:23,970 times the frequency response in magnitude squared. 164 00:09:23,970 --> 00:09:26,870 The good news is that this result guarantees that the filters that we 165 00:09:26,870 --> 00:09:31,320 designed in the deterministic case can still be used with stochastic signals. 166 00:09:31,320 --> 00:09:34,809 A low pass will remain a low pass and a high pass will remain a high pass. 167 00:09:35,910 --> 00:09:39,580 We do however lose the concept of phase, and this is understandable, since we don't 168 00:09:39,580 --> 00:09:42,990 really have any advanced information of the shape on the stochastic signal. 169 00:09:42,990 --> 00:09:45,520 That will depend on the particular realization. 170 00:09:45,520 --> 00:09:48,000 All we know is where the power is distributed in frequency. 171 00:09:49,280 --> 00:09:53,490 Now that we have some stochastic tools in place, let's attack the concept of noise. 172 00:09:53,490 --> 00:09:54,910 So, noise is everywhere. 173 00:09:54,910 --> 00:09:57,940 It appears in the form of thermal noise and circuits. 174 00:09:57,940 --> 00:10:02,920 It could be the sum of various extraneous interferences in communication systems. 175 00:10:02,920 --> 00:10:08,150 Or the quantization on numerical errors that complex digital system produced and 176 00:10:08,150 --> 00:10:10,330 that we cannot predict in advance. 177 00:10:10,330 --> 00:10:13,240 Because of a lack of knowledge about the sources of the noise, 178 00:10:13,240 --> 00:10:16,400 we will model the noise as a stochastic signal. 179 00:10:16,400 --> 00:10:19,120 And the most important type of noise is white noise. 180 00:10:19,120 --> 00:10:22,590 With the term white we indicate a stochastic process where 181 00:10:22,590 --> 00:10:24,880 all the samples are uncorrelated. 182 00:10:24,880 --> 00:10:28,590 If the samples are uncorrelated, the auto-correlation of the process will be 183 00:10:28,590 --> 00:10:33,810 zero everywhere except at zero, where it will take the value of the variant. 184 00:10:33,810 --> 00:10:37,590 As a consequence, the power spectral density is the constant sigma squared, 185 00:10:37,590 --> 00:10:40,610 where sigma is the variance of the stochastic signal. 186 00:10:40,610 --> 00:10:44,770 Graphically the power spectral density of the white signal couldn't be any simpler. 187 00:10:44,770 --> 00:10:48,290 We have seen the example of this in the coin toss experiment. 188 00:10:48,290 --> 00:10:51,200 The power spectral density of white noise is independent 189 00:10:51,200 --> 00:10:54,640 of the probability distribution function for the single sample. 190 00:10:54,640 --> 00:10:57,960 Distribution however will be important to estimate 191 00:10:57,960 --> 00:11:01,169 the bounce of the noise signal in the time domain. 192 00:11:02,200 --> 00:11:04,600 Very often we use a Gaussian distribution 193 00:11:04,600 --> 00:11:08,590 to model the underlying probability distribution function for the samples. 194 00:11:08,590 --> 00:11:12,510 The reason for that is that the Gaussian distribution is the model of choice when 195 00:11:12,510 --> 00:11:17,885 we want to represent the effective, many unknown, super impose sources. 196 00:11:17,885 --> 00:11:20,035 As is the case for noise. 197 00:11:20,035 --> 00:11:20,635 In this case, 198 00:11:20,635 --> 00:11:25,055 the noises were called additive white Gaussian noise, or AWGN for short.