1 00:00:00,012 --> 00:00:05,408 So in this video we're going to learn how to compute the DFT efficiently. 2 00:00:05,408 --> 00:00:11,451 And what this has to do with is how much time does it take to compute a spectrum, 3 00:00:11,451 --> 00:00:16,723 and how does that time depend on the amount of data, the length of the 4 00:00:16,723 --> 00:00:20,132 transform. If you're like me you want that a 5 00:00:20,132 --> 00:00:24,207 spectral calculation to, come back as soon as possible. 6 00:00:24,207 --> 00:00:28,482 The computation to be quick. That's where efficiency comes in. 7 00:00:28,482 --> 00:00:32,982 We wanted to find out how to compute the DFT as quickly as possible. 8 00:00:32,982 --> 00:00:38,032 And it turns out, this has led to the discovery of something called The Fast 9 00:00:38,032 --> 00:00:41,962 Fourier Transform. Just a way of computing the DFT. 10 00:00:41,962 --> 00:00:47,767 It's not any, it's not a new transform it's just a way of computing the DFT. 11 00:00:47,767 --> 00:00:52,977 And it's known as the FFT in, in the DS digital processing book. 12 00:00:52,977 --> 00:00:58,317 To talk about this, we're going to introduce the concept of competition. 13 00:00:58,317 --> 00:01:02,112 The complexity that comes from computer science. 14 00:01:02,112 --> 00:01:08,293 That as a systematic way of evaluating how many computations and how many 15 00:01:08,293 --> 00:01:14,357 program a formula is going to require. So let's look at the DFT formula. 16 00:01:14,357 --> 00:01:20,792 So, we have to compute this formula, this is the formula we've seen before. 17 00:01:20,792 --> 00:01:26,096 And I want to look at, what do I have to do for each frequency? So, k is fixed 18 00:01:26,096 --> 00:01:29,904 here. The, the complex exponential is fixed, in 19 00:01:29,904 --> 00:01:33,606 terms of k. And now I want to do this multiplication, 20 00:01:33,606 --> 00:01:38,006 minus of n times the complex exponential, and add the results up. 21 00:01:38,006 --> 00:01:44,536 So, how much work is required? So, what work means computations means I'm 22 00:01:44,536 --> 00:01:50,102 consider multiplications and additions, in some detail. 23 00:01:50,102 --> 00:01:57,444 So every term in this sum has this multiply in it and, recall that that's a 24 00:01:57,444 --> 00:02:02,802 complex exponential which means it's a complex number. 25 00:02:02,802 --> 00:02:11,300 And in most computers the top computers I know are complex numbers are stored as 26 00:02:11,300 --> 00:02:17,091 real measurement for a convenient for doing multiplication. 27 00:02:17,091 --> 00:02:24,865 So, This formula becomes that, and that means I have to multiply, multiplications 28 00:02:24,865 --> 00:02:30,299 in here that are real multiplications and that's what we want to consider. 29 00:02:30,299 --> 00:02:35,651 No computer I knew of has inherently built in complex arithmatic qual 30 00:02:35,651 --> 00:02:39,099 properties. So, we're going to talk about this in 31 00:02:39,099 --> 00:02:44,262 terms of real multiplications. So, we have 2 real multiplications for 32 00:02:44,262 --> 00:02:48,703 every term in the sum. And we had n terms in the sum. 33 00:02:48,703 --> 00:02:52,449 So we get 2n for the number of real [INAUDIBLE]. 34 00:02:52,449 --> 00:02:56,601 How about additions? So, in terms of additions, 35 00:02:56,601 --> 00:03:00,603 I'll point out something rather straightforward. 36 00:03:00,603 --> 00:03:05,962 Suppose you're adding up 3 numbers. You only need to do 2 addition. 37 00:03:05,962 --> 00:03:12,302 So the number of additions in the sum with N terms is N-1, and because we have 38 00:03:12,302 --> 00:03:18,327 to sum the real and imaginary terms separately that's where the factor 2 39 00:03:18,327 --> 00:03:22,142 comes in. One for the real part and one for the 40 00:03:22,142 --> 00:03:26,885 imaginary. So, total number of computations Is going 41 00:03:26,885 --> 00:03:32,709 to be required is 4n-2 just adding up those two numbers. 42 00:03:32,709 --> 00:03:40,443 So but, this is for each frequency. Since we have to evaluate this for n 43 00:03:40,443 --> 00:03:49,759 different frequencies we come up with a total number of computations. 44 00:03:49,759 --> 00:04:00,121 That's n*4n-2 computations. So writing this out a little bit here. 45 00:04:00,121 --> 00:04:06,554 This is 4n^2-2n. Okay, so to summarize this in a way 46 00:04:06,554 --> 00:04:12,907 that's a bit more manageable. The term, the concept of computational 47 00:04:12,907 --> 00:04:18,424 complexity has arose. And computational complexity is worried 48 00:04:18,424 --> 00:04:24,508 about the worse case behavior. What happens as N goes to infinity, as N 49 00:04:24,508 --> 00:04:25,394 gets. Big. 50 00:04:25,394 --> 00:04:29,540 The term that dominates, clearly, is the, the quadratic term. 51 00:04:29,540 --> 00:04:33,100 You can essentially forget about this when n gets big. 52 00:04:33,100 --> 00:04:35,809 You want to see that, take n it'd be 1000, 53 00:04:35,809 --> 00:04:40,174 this is well over a million. And you should [INAUDIBLE] a couple of 54 00:04:40,174 --> 00:04:42,783 thousand. It doesn't matter very much. 55 00:04:42,783 --> 00:04:47,102 Furthermore, we don't worry about the constant [INAUDIBLE]. 56 00:04:47,102 --> 00:04:51,697 In computation complexity, because we're worried about how fast 57 00:04:51,697 --> 00:04:55,789 things compute. this is going to [UNKNOWN] depend on the 58 00:04:55,789 --> 00:05:01,428 speed of the computer and the fact that 4 really doesn't tell us much about that. 59 00:05:01,428 --> 00:05:06,568 What we want to know in essence is on the same computer how much more work is going 60 00:05:06,568 --> 00:05:12,862 to be required is a change. The number of points in a transform, 61 00:05:12,862 --> 00:05:19,178 return capital N. So, what is known as the computational 62 00:05:19,178 --> 00:05:27,564 complexity of this calculation is n^2. And this is red, as this is an order. 63 00:05:27,564 --> 00:05:31,175 N^2. Computation, then all you do is look at 64 00:05:31,175 --> 00:05:37,010 the number of computations and look at the worse case term, drop any constants 65 00:05:37,010 --> 00:05:42,727 they may be from and that tells you that this you that double the length of the 66 00:05:42,727 --> 00:05:46,169 transform is going to take you 4 times longer. 67 00:05:46,169 --> 00:05:49,722 That is the kind of information that you want. 68 00:05:49,722 --> 00:05:58,988 Well, not being satisfied with that result, some guy named Gauss, yes that 69 00:05:58,988 --> 00:06:07,968 Gauss, in 1805 figured out a more efficient, what that means is a smaller 70 00:06:07,968 --> 00:06:14,702 computational complexity. Then this formula would first appear, he 71 00:06:14,702 --> 00:06:20,747 can compute the DFT rather efficiently. And it's now known as the fast foray 72 00:06:20,747 --> 00:06:25,482 transform or the FFT. Turns out he discovered this in 1805. 73 00:06:25,482 --> 00:06:32,627 he never published it in his lifetime, he wrote it in his personal notes, put it in 74 00:06:32,627 --> 00:06:36,104 a drawer. Was only discovered after he died in his 75 00:06:36,104 --> 00:06:40,375 collected works, including what was in the drawer unpublished. 76 00:06:40,375 --> 00:06:45,611 if you want to read more about this, I wrote a paper about the history of the 77 00:06:45,611 --> 00:06:48,648 FFT and Gauss which you may find interesting. 78 00:06:48,648 --> 00:06:52,797 Well, let's see if we can learn what Gauss's thinking was. 79 00:06:52,797 --> 00:06:57,307 He made an assumption, which is not a very bad one we assume 80 00:06:57,307 --> 00:06:59,912 that they transform one goes 2 to a power. 81 00:06:59,912 --> 00:07:05,827 This is one of those reasons why those powers of 2 I showed you in a previous 82 00:07:05,827 --> 00:07:11,627 video are very important to learn. We have to do the transform ones in the 83 00:07:11,627 --> 00:07:15,027 FFT. Now we know from our discussion of the 84 00:07:15,027 --> 00:07:20,380 DFT But all that we have to have is that the transform length be greater or equal 85 00:07:20,380 --> 00:07:24,825 to the actual signal duration. So, what I'm doing, is changing the 86 00:07:24,825 --> 00:07:28,775 signal duration. I'm assuming that the transform length is 87 00:07:28,775 --> 00:07:34,110 to a real power, and so what's normally done in the, in the, in practice, is that 88 00:07:34,110 --> 00:07:40,104 whatever your length of data is 608. I pick up the next power to this, just 89 00:07:40,104 --> 00:07:45,192 bigger than that. And the DFT will work, and won't be any 90 00:07:45,192 --> 00:07:49,559 problem. I mean, I have to pad with zeros, okay? 91 00:07:49,559 --> 00:07:53,670 So that's okay. So, let's see what Gauss did. 92 00:07:53,670 --> 00:08:00,432 What Gauss did was he separated this sum into the sum of the even numbered terms, 93 00:08:00,432 --> 00:08:05,287 and the sum of the odd numbered terms. So he hasn't changed any kind of 94 00:08:05,287 --> 00:08:10,227 computation complexity at all. He's just, he's a mathematician he's 95 00:08:10,227 --> 00:08:13,252 going to play with the formulas a little bit. 96 00:08:13,252 --> 00:08:17,912 You then notice he could, he'd write them a bit more succinctly. 97 00:08:17,912 --> 00:08:28,408 In the following way, and so he pulls out a faze factor out of the the expression 98 00:08:28,408 --> 00:08:36,982 for the odd numbered terms. Then he knows that these exponentials. 99 00:08:36,982 --> 00:08:41,209 For corresponding terms and the two are the same. 100 00:08:41,209 --> 00:08:47,770 So, we have the same computation doing up here as we are doing down here and we 101 00:08:47,770 --> 00:08:54,062 take the one for the odd number terms, multiply by this and add them up and that 102 00:08:54,062 --> 00:08:59,149 gives the DFT. Again this hasn't saved any work yet. 103 00:08:59,149 --> 00:09:04,769 And in fact it may look like we're going to have to do more work because we're 104 00:09:04,769 --> 00:09:09,382 going to have to multiply by this thing to use this result. 105 00:09:09,382 --> 00:09:15,176 Gauss has a little surprise for us. So let's look at this expression again. 106 00:09:15,176 --> 00:09:22,669 So Here's our formula for the DFT. And, I want to point out. 107 00:09:22,669 --> 00:09:32,252 What's critical here, is, we have to evaluate this right at our, n frequency 108 00:09:32,252 --> 00:09:37,369 values. So, I have to evaluate this thing 109 00:09:37,369 --> 00:09:43,595 [UNKNOWN] and value this thing [UNKNOWN] multiplied by this [UNKNOWN] and now 110 00:09:43,595 --> 00:09:49,241 we'll add them up. Well, what he noticed first of all was 111 00:09:49,241 --> 00:09:59,772 that each of these is an N/2 DFT. You can see, I am sampling here, that 112 00:09:59,772 --> 00:10:05,652 k/n/2. So these are DFT formulas, 113 00:10:05,652 --> 00:10:16,337 well that's kind of interesting I guess. so, this is a DFT of the even numbered 114 00:10:16,337 --> 00:10:20,285 terms. This is a DFT of the odd numbered terms. 115 00:10:20,285 --> 00:10:26,299 I multiply the one for the odd numbered terms by a complex exponential, 116 00:10:26,299 --> 00:10:32,712 add them up, and I get that I want. Again, I still haven't saved anything 117 00:10:32,712 --> 00:10:39,567 yet, until Gauss being a very smart mathematician, realized one of the 118 00:10:39,567 --> 00:10:44,968 properties of the DFT. The DFT is periodic in its length. 119 00:10:44,968 --> 00:10:49,289 This thing is periodic, with a period of N/2. 120 00:10:49,289 --> 00:10:57,107 So, what does that mean? That means that once I calculate this formula, for zero 121 00:10:57,107 --> 00:11:05,217 up to N/2-1, what happens at N/2, is the same thing that happens at zero, and what 122 00:11:05,217 --> 00:11:10,992 happens at N/2+1, is the same thing that happened at 1. 123 00:11:10,992 --> 00:11:17,282 I don't need to compute these formulas for the higher values of K. 124 00:11:17,282 --> 00:11:24,612 I can reuse my previous computations. The only ones I need to compute are the 125 00:11:24,612 --> 00:11:31,297 ones here for the First half after that to evaluate these 2 DFTs I just reuse my 126 00:11:31,297 --> 00:11:36,197 values, it's periodic because of the properties of the DFT. 127 00:11:36,197 --> 00:11:41,657 I do have to multiply this for every value of k, there are no special 128 00:11:41,657 --> 00:11:45,612 properties of that. But still, I'm saved half my 129 00:11:45,612 --> 00:11:49,942 computations. Say that again, I've saved 1/2 right 130 00:11:49,942 --> 00:11:53,890 away. So, let's see in terms of a block diagram 131 00:11:53,890 --> 00:11:59,545 what Gauss' insight was. He says I can take the original sequence, 132 00:11:59,545 --> 00:12:05,680 original data and I can divide it into the even numbered terms and the odd 133 00:12:05,680 --> 00:12:10,219 numbered terms. I can take the Length-4 DFT of each So 134 00:12:10,219 --> 00:12:14,913 this is this expression and that is this expression. 135 00:12:14,913 --> 00:12:21,903 And to compute the S0 I take the value [UNKNOWN]k=0 from that DFT, the value for 136 00:12:21,903 --> 00:12:28,919 k=0 from that DFT multiplying by the complex exponential, which is pretty easy 137 00:12:28,919 --> 00:12:34,138 and add him up. And I do the same thing, a similar thing 138 00:12:34,138 --> 00:12:39,340 for s1, s2, s3. But when it comes down to s4, I can reuse 139 00:12:39,340 --> 00:12:43,669 the values I've already computed for the DFT. 140 00:12:43,669 --> 00:12:49,222 I have to multiply the odd numbered DFT by a different. 141 00:12:49,222 --> 00:12:53,487 A complex exponential. But, that's what I do. 142 00:12:53,487 --> 00:12:57,437 Alright. So, and this saves half the work. 143 00:12:57,437 --> 00:13:03,297 It's pretty clear. I do not have to evaluate, these length 4 144 00:13:03,297 --> 00:13:08,372 DFTs for 8 different values. I'm going to do it for 4 each. 145 00:13:08,372 --> 00:13:15,240 Well, this is a power of 2. What [INAUDIBLE]knows is that N, since N 146 00:13:15,240 --> 00:13:19,519 is a power of 2, N/2, is also a power of 2. 147 00:13:19,519 --> 00:13:27,461 I can do it again, and keep doing it until I get N, a length-2 transforms. 148 00:13:27,461 --> 00:13:34,471 So in our length-8 example. here's what the first stage of this 149 00:13:34,471 --> 00:13:42,100 decomposition he then decomposes each of these into 2, length 2 DFTs and he 150 00:13:42,100 --> 00:13:47,782 decomposes the length 4 DFT it evens into 2 length DFTs. 151 00:13:47,782 --> 00:13:52,131 Now he saved another factor of 2 Computations. 152 00:13:52,131 --> 00:13:57,893 So this keeps going if you have a higher power of 2 you keep doing this and doing 153 00:13:57,893 --> 00:14:01,795 it and doing it. Keep increasing your computation of 154 00:14:01,795 --> 00:14:05,390 savings. So now let's look at the details and see 155 00:14:05,390 --> 00:14:09,890 what you've got. So the, FFT divides the everything into 156 00:14:09,890 --> 00:14:14,173 stages. And the number of stages is equal to the 157 00:14:14,173 --> 00:14:22,728 number of times we had to divide by 2. So, since n, we assumed was 2 to a power. 158 00:14:22,728 --> 00:14:29,672 The number of stages is the log 2 of n. Which, of course, is equal to l. 159 00:14:29,672 --> 00:14:36,755 So we have L stages, each of which consist of N/2 length-2 DFTs. 160 00:14:36,755 --> 00:14:44,225 If you look at every stage in this diagram you see that that's true. 161 00:14:44,225 --> 00:14:49,482 Alright, now, every pair of length-2 DFTs... 162 00:14:49,482 --> 00:14:56,644 is combined after one is multiplied by complex exponential these, these are 163 00:14:56,644 --> 00:15:02,261 combined together. so if cannot deliver computations, its a 164 00:15:02,261 --> 00:15:07,117 real multiplies and adds you get ten computations each. 165 00:15:07,117 --> 00:15:09,848 So for each stage, you get 5*N/2. 166 00:15:11,017 --> 00:15:17,663 The reason it's 5 is because this 10 applied for every pair. 167 00:15:17,663 --> 00:15:23,123 So, we do 5N/2 computations for every stage. 168 00:15:23,123 --> 00:15:31,478 The number of stages we got was log2N. So the total complexity is going to be 169 00:15:31,478 --> 00:15:39,484 obtained by multiplying those together, and sure enough we obtain the rather 170 00:15:39,484 --> 00:15:47,645 interesting result with the complexity of computing the FFT is NlogN so The 171 00:15:47,645 --> 00:15:52,886 question is, is this really a savings. And this looks to be a bit more 172 00:15:52,886 --> 00:15:58,457 complicated program you have to write than the straightforward DFT. 173 00:15:58,457 --> 00:16:04,142 So let's compare their complexities. So on this plot, I have the DFT 174 00:16:04,142 --> 00:16:12,148 complexity which is N squared. And I've compared that with that of the 175 00:16:12,148 --> 00:16:21,064 FFT log 2 of N and log2N. However, only for the powers of 2 and I think you can 176 00:16:21,064 --> 00:16:27,717 see that there is a huge gap. Look at the far apart they are and I want 177 00:16:27,717 --> 00:16:32,939 you to look at the verical scale, that's in millions of operations. 178 00:16:32,939 --> 00:16:39,106 It is spectacularly more efficient to use the FFT than just to use the DFT in it's 179 00:16:39,106 --> 00:16:42,973 raw form. Turns out, it's been shown that there is 180 00:16:42,973 --> 00:16:49,591 no other algorithm for computing the spectrum that has a smaller complexity 181 00:16:49,591 --> 00:16:53,133 the FFT. The FFT is some sense is the most 182 00:16:53,133 --> 00:16:59,794 efficient algorithm you can have. It has the smallest possible complexity. 183 00:16:59,794 --> 00:17:07,223 There is no other algorithm yet to be discovered that has a smaller complexity. 184 00:17:07,223 --> 00:17:11,877 So, this is why the FFT is used pervasively. 185 00:17:11,877 --> 00:17:19,295 In fact, if you want to compute the DFT using cctave and Matlab, the function 186 00:17:19,295 --> 00:17:24,307 name is FFT. So, the one that point out that the FFT 187 00:17:24,307 --> 00:17:29,402 is spectacularly efficient for computing the DFT, 188 00:17:29,402 --> 00:17:33,792 much more so the just programming the formula from DFT. 189 00:17:33,792 --> 00:17:40,172 But I do want to emphasize that this is not a new Fourier transform instead it's 190 00:17:40,172 --> 00:17:46,644 a algorithm a way of computing the DFT. It does nothing different then compute 191 00:17:46,644 --> 00:17:51,112 the DFT but very efficient which means very quickly. 192 00:17:51,112 --> 00:17:57,876 also so, so it has no more proprietaries in terms of linearity and the properties, 193 00:17:57,876 --> 00:18:04,217 signal properties that we associate with the DFT, it's just a way of computing it. 194 00:18:04,217 --> 00:18:10,857 So there's nothing new in that regard. But it's so efficient that it really 195 00:18:10,857 --> 00:18:18,462 opens the door to many signal processing ideas including computing a filter. 196 00:18:18,462 --> 00:18:26,030 The input output of a filter within the frequency domain, it turns out that is 197 00:18:26,030 --> 00:18:30,442 really the way to go in many applications and we're going to talk about that in the 198 00:18:30,442 --> 00:18:30,975 next video.