Instructor (Brad Osgood):All right, by popular demand, today, Iím going to talk about the basics of the fast Fourier transform algorithm, the famous FFT. Weíre not gonna do it in all detail, that is, Iím not gonna carry it out to the bitter end. And in fact, itís actually a highly refined art. Itís almost more art than science these days. Thereís actually, these days, not one single FFT algorithm. There are a number of them. They share common ideas, they share similar properties, but they are often tailored to particular applications for each context.
But what weíre gonna talk about today is the main idea that underlies any of them and itís the one that was sort of originally put forth by Cooley and Tukey back in the Ď50s I guess it was, something like that. I canít remember the dates on this.
Itís very interesting. You should read about the history of these things and as youíve probably heard, I mentioned in the notes, the idea behind the fast Fourier transform algorithm actually was known to Gauss way back when, when he was trying to carry out calculations of estimating the orbit of an asteroid. So a lot of interesting history.
Now, what this means in particular, I have to give you a little caution on this, is that thereís sort of one more general topic on this fast Fourier transform that I would ordinarily talk about and that is convolution, circular convolution, so Iím not going to do that. I will leave that up to you to read. Thereís not much. There wouldnít be much to do other than talk about the formulas and basic applications. The applications weíll do in the context of linear systems coming up, so youíll see some of that later.
But the definition of convolution and some of the basic properties of convolution again, is theyíre similar to the continuous case. Iíll let you just read the notes about them, all right? And I think there are some problems on that. I think there are already some problems on that, actually.
Okay, so thatís the plan. This is going to put us a little bit behind because I was going to start talking about it sooner. I was gonna start talking about linear systems, linear time and variance systems, so weíll try to trim things a little bit after we leave the discreet world, after we leave this discussion of DFT.
So let me explain whatís going on here. Let me set the stage for you. Hereís the FFT algorithm. Now, let me remind you that Ė well, there are a couple ways of looking at it. Maybe the simplest way of understanding what the challenge is, as I mentioned last time, to write the DFT as an N x N matrix. So you can write the DFT as an N x N matrix. Itís a very simple entrance, very simply described. F is just Omega to the minus NM, where remember Iím using this notation now just to simplify things so I donít have to constantly write complex exponentials.
So Omega is the primitive N root of unity, so Omega to the minus nm is just e to the minus 2pi nm over capital N. And the way we index things is from 0 to N minus 1. Indexed from 0 to N minus 1.
So to compute discreet Fourier transform, the discreet signal is to multiply the matrix by the column vector, is to regard F as a column vector and multi-matrices. All right, so there is an end-by-end matrix that would seem to require N2 computations. Never mind that you just also have to add up the N elements, but the main computation and intensive aspect of it is the multiplication.
So this requires Ė would seem to require Ė so let me just use the big O notation here, meaning that some multiple of N2 to the dominant term is N2, O(N2,) capital O(N2), big O(N2) operations.
And how could it require any less than this? I mean everything has to be accounted for here. I mean you canít just throw things out while computing the DFT. It would seem to require every element of the matrix be involved, when in fact, what the FFT algorithm does is reduce this enormously. The FFT algorithm reduces this to big O of N log N operations, usually meaning log base 2 here, but it doesnít really matter.
Now, if weíre saying why something like this might be possible because itís not obvious, you have to realize that thatís an enormous savings in computation. To go from N 2 to N log N is a huge savings. For example, itís a huge savings Ė so N is equal to 103, if N is equal to 1,000, and of course, N2 is a million, that N log N is 103 log 103, log of 103 is 3, so itís just 3 times 103. So itís a thousand operations, or a constant times a thousand operations, versus a million operations. All right, thatís an enormous savings. And of course, the larger N is, the savings are even more dramatic.
Now, why should you be able to do this? Well, there are a couple of different sort of intuitive reasons why this should be the case. The intuition is one thing; carrying it out is something else. Let me tell you one way of thinking about it that weíre not going to do, although itís discussed a little bit in the notes, and this is a very common way of approaching the DFT and the FFT algorithms, and that is sticking with a matrix, notation of the matrix idea.
One way is that there are a lot of structures to the matrix and thereís a lot of structure to the DFT, so when you reduce it, you want to exploit the structure in the DFT. Well, thatís not Ė thatís a vacuous statement. Of course, youíre going to exploit the structure in the DFT. It depends on only parameter. It depends on the parameter Omega and this complex exponential, and that has a lot of nice algebraic properties via ray of properties of the complex exponential. Thatís the main thing thatís involved.
Now, in the matrix approach, what this amounts to, the reason why there can be such a dramatic reduction is that you can factor the DFT into a product of other matrices, which have lots of zeroes in them. So one approach is to write the DFT matrix as a product of simpler matrices; that is, to use the algebraic properties of the exponential, to carry out this matrix factorization. The simpler matrices have lots Ė as it turns out, the simpler matrices have lots of zeroes in them and when matrices have lots of zeroes in them, they effectively donít count in the calculation. When you multiply by zero, youíre not doing anything. Simple matrices have lots of zeroes, so fewer multiplications are required. Fewer multiplications are required to carry out the matrix multiplication, to carry out the product. Thatís one reason, thatís one approach to the FFT algorithm, and in fact, thatís explained in the notes. Iím not gonna do this; Iím not gonna go through that particular approach, but thatís often done, all right? And in some of the sort of highly refined approaches to the FFT, you often find theyíre presented in terms of matrix factorizations, and if any of you have taken 263, or are taking 263, you know that matrix factorization is a big business. Writing a matrix, writing a complicated matrix as a product of simpler matrices is something that can often, not only simplify a calculation, but can also often really illuminate some ideas that you wouldnít see, that are a little bit, that are somewhat subtle. They canít be somewhat subtle.
So itís a standard approach that weíre not gonna do, but you can easily find many references to the literature on this approach. We are gonna take really a more directly algebraic approach thatís based on the formula. So although Iím thinking in terms of writing a matrix, although we did the basic counts of the number of operations in terms of the matrix, Iím actually not going to work with a matrix to develop the algorithm. Iím just gonna work with the formula for it for the DFT as we have written it before and I wanna use the Ė I wanna exploit the algebraic properties of the complex exponential to write it in a more Ė I donít know Ė simple form or just Ė well, youíll see. Youíll see.
Itís one thing to have the idea and itís not an obvious thing to have the idea. Itís not a thing to really carry it out. Itís really quite beautiful and I say this as someone whoís orientation in life is not Fourier algorithms necessarily, so I really have a grand appreciation for it and the whole idea behind it.
All right, now, letís write down the formula. So once again, as always, the Fourier transform of the discrete signal is given by Ė we write it like this. The F component Ė when we write it out like that Ė is the sum from Ė so Iím indexing from 0 to N Ė 1, so the sum from n = 0, N Ė 1 of F(N), the N component of F, times Ė if I use this notation for the complex exponential, just the Omega to the minus N x N. Itís a simple formula. All right, now, what weíre gonna do is we are going to write the sum as a sum over even and odd powers. Weíre gonna write the complete sum as a sum over even and odd indices and then also, therefore, powers of Omega. Well, let me just say even/odd indices. And in doing so, itís the algebra thatís gonna allow us to do this in a helpful way. You can say Iím gonna do that. Itís one thing to, again, itís one thing to say that; itís another thing to actually give you any resulting savings. Youíll see in just a sec.
The purpose of this is to try to write the N for order DFT as a combination of two DFTs of order N over 2, capital N over 2. The purpose is to write the order N DFT as a combination, really a sum Ė thereís a little bit more to it than just a straight sum Ė as a combination of two DFTs of order N over 2, all right, and then iterate. And as you write these DFTs of order N over 2, you apply the same rules to the DFT of the order N over 2 to write them as combinations of DFT of order N over 4 and then iterate and so on and so on and so on. Okay? Now, so first of all, to make this work, you have to assume that N is even and if you want to keep iterating, you have to assume actually that N is a power of 2. So to do this, you need to assume that N is even. Even to get started, we need to assume itís even. To iterate, you need to assume that N is a power of 2.
So this is where all these special things come in when you have a signal and you wanna apply it and you wanna compute numerically a discrete Fourier transform, and your signal, your discrete signal doesnít happen to have the length of a power of 2. What do you do? They zero padding; they do all sorts of things like this. There actually are other Fourier transform discrete Fourier transform algorithms, or DFT algorithms, that donít require this, but they all require something like this. So sometimes you have to modify your signal and again, Iím not gonna get into this. Iím just gonna talk about the algorithm per se assuming all these things. But there are ways of trying to address this and they can introduce some extra complications, so if the signal is not a power of 2, you add a bunch of zeroes, so-called ďzero padding,Ē until you get it to be a power of 2. Of course, thatís not the original signal, so youíve changed things a little bit and have those changes affected things? Well, thatís something that depends, again, on the particular context. So weíre gonna make this assumption. So sue me. Iím gonna assume this now. Iím gonna assume that N is even and then in general to iterate, Iím gonna assume that N is a power of 2. Okay, now, it depends Ė the algorithm and this way of arranging things, way of rearranging things, depends on the algebraic properties of the complex exponential. I want to introduce some notation here. Sorry; you know Iím always introducing some extra notation, just so I can keep track of things without Ė a little bit more easily, a little bit more neatly. I wanna keep track of things, so I use a notation to keep track of powers, really, of the complex exponential. Thatís whatís involved. All right, so let me write Ė sorry, but let write this. Iím only using it for this performance only. Omega P (q) is e to the 2p q over p, because whatís involved is both the denominator here and the power that youíre raising it to.
Iím gonna use that notation and Iím gonna write my Fourier transforms in terms of that notation. Now in terms of this, how we write down the usual properties of complex exponentials because Iím gonna use them all, well, if I put down p, say q1 + q2, thatís taking e = 2pi(q1+q2) over p, and of course, complex exponentials being what they are, that multiplies. So this is Omega p (q1) times Omega p (q2). Nothing there. Absolutely everything I do today is gonna be Ė is dead simple, okay? A high school student could do this if you explain to them at every stage what to do. But thereís nothing here thatís at all involved. Itís just extremely clever. Now, letís look what happens when I change the power, or change the order maybe I should say. First, by the way, let me just comment here. So Omega, for the terms that are entering into the Fourier transform, DFT, Omega and n and m, minus nm is what is the power that occurs here, so thatís Omega to the minus nm that is equal to each of the e = 2pi nm over N. Okay, so what is our Ė I wanna follow my notes here because I donít wanna get this wrong. So Omega, so Iím assuming that N is even, capital N is even, so what is Omega, the sort of N over 2nd order when I have such a power here, which is what it comes up nm in the transform, so that is Ė letís work it out Ė e to the minus 2pi nm divided by N over 2. So itís 2p nm over N over 2. The two comes upstairs. This is e to the minus 2pi times 2nm divided by N. That is to say, if in terms of my notation, this is Omega, the F order complex exponential weighs to the power of minus 2nm. So in words, a power of the half order exponential is an even power of the four exponential. Thatís one way of saying it. If I think of N as sort of the order of exponential that Iím worried about, then in words, say a power, in this case nm, half order exponential, thatís N over 2, is an even power, that is, 2nm, of the 4 exponential thatís N.
I think Iím developing tennis elbow, by the way, over the course of this quarter. Iím in a lot of pain, but I can play through it. All right. So that side is the even powers. What about odd powers? Well, odd powers Ė Iím thinking about N being odd. Letís go over to odd powers, the power being 1. So then Iím gonna look at Omega Ė careful, careful here; careful, careful here Ė Omega N of 2n + 1. Now be careful. I donít want to get any wrong. 2n minus Ė 2n + 1 because all of my powers are minus m. So thatís an odd power of N. See, once again, powers of N over 2 here led to even powers of N, so I wanna look at what happens to odd powers of N and relate those to certain powers of N over 2. So what is this? This is Omega N Ė 2nm Ė m, okay, right. Now, remember, complex exponentials being what they are, this is the product of the two, the product of the N for exponential N raise to this power and raise to this power. So thatís to say this is Omega to the nth order exponential to the power -2nm times the nth order exponential to the power of minus m. I did get my minus signs right over here, right? Yeah, okay.
All right, now, this youíve already seen. This is the first term is Omega, the half-order exponential at the power nm, minus nm, times Ė this one I leave alone; nothing I can do with that. Okay, so once again, what happens to even order powers? An ordinary power of N over 2 is an even power of N, all right? Or you can say it this way. An even power of nth order exponential is an ordinary power of the N of the half-order exponential. Here, an odd power of the 4 exponential is a product of an ordinary power of the half-exponential, half-order exponential times this extra factor here. Okay. All right, now, letís go back to the formula for the DFT and plug this in. Iíll put this into the formula for the DFT. All right, so what is that? That is the DFT, the nth component once again, is to just write it down again, is sum from N=0 to N-1 of the nth component of F times the power of the complex exponential, so Iím writing this in the form Omega N Ė nm. Okay?
All right, now, Iím gonna write this sum as a sum over even indices and odd indices. All right, so Iím gonna write this as sum over even indices plus the sum over odd indices. So what does that mean? Well, that means Ė I mean what does it mean in symbols? That means that the discreet Fourier transform is gonna be Ė Iím gonna take the sum from N=0 to N over 2 minus 1. Weíll write it down and make sure we have it right. So this is N over 2 minus Ė let me write this a little more Ė give us a little more room here. The Fourier transform of F, the nth component is gonna be the sum over even indices. Thatís half the indices are even; half the indices are odd. So if I go to the half indices, there are N over 2 of them here, from 0 to N over 2 minus 1 or N over 2, those are the even indices and that is gonna be F of 2n, right, since Iím summing over the even indices, times Omega N, -2nm plus Ė to be continued on the next board Ė the sum over the odd indices, and again, half of the indices are odd, so itís gonna be the sum N = 0 up to N over 2 minus 1, the odd indices. So an odd number is the form 2N plus 1. Omega N, minus 2n plus 1m. Now everythingís accounted for there, right? Everythingís accounted for. These indices, 0, 2, 4, 6, 8, and so on, these are the indices. The components 1, 3, 5, 7, 9 and so on and so on; theyíre all there. I havenít lost anything. Okay, now, watch this. Put that up there and we put this up there. How about that for professionalism? And now Ė almost. Okay, now use the way that I have written the nth order complex exponential in terms of complex exponentials of order N over 2, the kind of stuff that Iím just about to erase.
So the sum over the even indices gives me the sum from N = 0 to N over 2 minus 1. F of 2n and this is the ordinary power N nth power of the half-order complex exponential, capital N over 2. Plus the sum of the odd indices over 2 minus 1 F of 2n plus 1. So what happened here, here was Omega n minus m times Omega N over 2 minus nm, if I had that correct. Do I have that correct? I believe I do, so that is what happens when you look at this complex exponential for an odd index, for an odd power. Now this doesnít depend on the sum over N, this doesnít depend on N, so that comes out of the sum. So let me just rewrite this quickly. So this is the sum from N = 0 to N over 2 minus 1 F of 2n times Omega N over 2(n-nm) plus Omega N minus m times the sum Ė very similar sum Ė and equals 0 to N over 2 minus 1 F(2n) plus 1 Omega of half-order exponential minus nm. Make sure I got all this right. Okay. Okay, nm, mn, doesnít matter. Again, everything is there, right? Everything is accounted for, mn, everything is accounted for. All the indices are there; all the components are there.
All right, now, this is looking like youíve expressed an nth order DFT in terms of two DFTs of order N over 2 because the DFT of order capital N over 2 involves exactly the complex exponentials of power, to the power of the denominator or the power youíre dividing by is capital N over 2. So this is looking like Ė this is almost, but not quite, for reasons you have to understand, this is almost the Fourier transform of Ė let me write it like this Ė of N, all right. The nth order of DFT looks like the N over 2nd Fourier transform of the even indices. If I take F, but I just divide it by the even indices, plus this power Omega and minus m, the DFT of order N over 2 applied to the odd indices, which is what Iím trying Ė Iím trying to get something like this. Iím trying to say you can evaluate an nth order DFT in terms of a combination of two DFTs of order half that. Not quite right. Itís not quite right because Ė you have to think about this Ė the DFT of order n accepts an n-tuple and returns an n-tuple. The DFT of order N over 2 accepts an N over 2 tuple and returns an N over 2 tuple. So how are you getting an n-tuple out of two N over 2 tuples, and how would you like to say that a couple times fast? F (N over 2) accepts an N over 2 tuple and it returns an N over 2 tuple. So writing this statement canít be right, all right? Youíre missing something because if I just had the right hand side, the right hand side makes sense because F even is an N over 2 tuple, F odd is an N over 2 tuple, but what returns are two N over 2 tuples, not an n-tuple, which is the nth order Fourier transform of F. So we have to tickle this a little bit. We have to tickle the formula. Tickle the formula. Sounds so cute. Sounds so human. All right, now, I have to find Ė I have to get the formula for the Fourier Ė for the nth order Fourier transform of F for m going all the way from zero to N minus 1. I need to get all N components of it.
Now, for the first N over 2 minus 1 components, these are okay. That formula would apply. For m = 0 up to N over 2 minus 1, we can use the above formula, the formula above. That is to say Ė let me just rewrite it; make sure I havenít missed anything here Ė we can write, and all is well, the formula of the Fourier transform, the discreet Fourier transform of F, the N for this Fourier transform is exactly the N over 2nd, the Fourier transform of order N over 2, DFT order of N over 2 at m plus Omega(n-m), the N over 2 half-order Fourier transform of F odd, the nth component of that. All right, thatís correct. Thatís correct for m going from zero to N over 2 minus 1. Okay? Now, that gets half of it. So what about the second half? So what about indices m indices from N over 2 up to N minus 1? All right. Write these in the form m plus N over 2, where m goes from zero up to N over 2 minus 1. That is, if m is ranging over the indices that index the half-order DFT, write the indices that index the second half of the nth order DFT in this form, all right? That is, the indices from N over 2, N over 2 plus 1, up to N minus 1 are of the form Ė if I started with zero here, I get N over 2, N over 2 plus 1. Then I would get N over 2 minus 1 plus N over 2 gives you m minus 1. It covers all of them. Okay? That covers all of them.
All right, now, what I mean by this, you have to write right now, what happens if I substitute this expression, an index in this form, into the expression that I have for the nth order DFT, which I am now stupidly erasing? Then the nth order Fourier transform at an index of the form m plus N over 2 is according to what Iíve already written down, which is valid for all of these indices, sum from N = 0 to N over 2 minus 1, F of 2n Ė this is what I had before Ė Omega N over 2, m plus N over 2, N times N plus over Ė minus Ė there were 2n, right? Plus Omega N minus m plus N over 2 times the sum from N = 0 to N over 2 minus 1 of F of 2n plus 1 the odd indices Omega Ė what was here? The same sort of thing, right? N over 2 minus m plus N over 2n. All right? Once again, let me make sure I have not screwed the pooch on this. Not, good, all right. Everybody with me? So that was the formula for the DFT writing it as the sum over even indices plus the sum over odd indices, but now Iím seeing what happens if you plug in an index in the form m plus N over 2, and again here, m is gonna range from zero to N over 2.
Well, now, letís just see what happens to these complex exponentials. Thatís what we have to answer. All right, but itís not hard. A high school student could do this if you told him what to do at every stage. Omega Ė a lot of research is like that. Itís a big secret. N over 2 minus m plus N over 2n, so thatís Omega N over 2 minus mn plus N times N over 2 Ė minus N times N over 2. Now once again, these exponentials being what they are, this multiplies. This is Omega of N over 2, minus mn times Omega N over 2, minus N times N over 2. But this is a complex exponential. This is an N over 2 root of unity raised to the N over 2nd power, or an integer times N over 2nd power. So this is equal to 1. This is like e = 2pi over N to nth power. So this is 1. So what remains there is just Omega to the N over 2 minus nm. Omega to the N over 2 minus nm Ė mn, same thing. And that comes up in both these sums, right? Yeah, itís the same thing in both these sums, so in the sum over the odd indices and the sum over the even indices, the only other thing you have to figure out is this up front. That bracket out front. This comes up in both sums, even and odd indices. This expression. The only other thing that comes up is the factor out front, which is Omega Ė what is it? Omega N minus m plus N over 2. So thatís Omega N minus m minus N over 2, and again, complex exponentials being what they are, this is Omega N minus m times Omega N, N over 2. Minus, it doesnít matter, minus.
Now, what is that second expression? This expression, fine, thatís what we had before actually. Thatís what we had before as a factor out front. What about this expression? Well, this is e = 2pi over N raised to the minus N over 2 power. So what happens is the N cancels out the N, the 2 cancels out the Ĺ there and itís e = pi, which is also known as minus 1. So the factor out front changes to minus what is was before. So Omega, in other words, Omega N, minus m plus N over 2 is just minus Omega N minus m. Correct? Correct. All right, so what is the actual retail value of the expression? So we have Fourier to nth order of the DFT of F and an index to the form m plus N over 2, which is what Iím worried about here, for little m going from zero to 1, 2, 3, up to capital N over 2 minus 1 is equal to the sum over one half of the first sum Ė the first sum didnít really change very much Ė over N over 2 minus 1, F(2n) Ė thatís the sum of the even indices Ė Omega N over 2, minus nm. Was that right? Was it right, the first sum didnít change, the first factor didnít change? Help me here. Thank you. Yes, I believe thatís the case that the first sum didnít change. The second sum Ė the only thing that happened in the second sum was this factor out front and the factor out front changed to minus itself. So minus Omega nm times the sum from N = 0 to N over 2 minus 1, F of 2n plus 1 Omega N over 2 minus nm.
Thatís the result of plugging in an index of the form little m plus N over 2 into the original form we had to decompose the nth order DFT into the sum over even indices plus sum over odd indices. Okay. But look! Once again, this is okay Ė m is ranging from zero to N over 2 minus 1 here. This is again a DFT of order N over 2 returning an N over 2 tuple and this is a DFT of order N over 2 returning an N over 2 tuple. So this says Ė itís exactly what we want Ė this says that Fourier transform, the discreet Fourier transform of order N at m plus N over 2 is equal to the discreet Fourier transform of order N over 2 of F of the even indices applied to m minus Omega N, minus m, the Fourier transform of N over 2 of F applied just keeping the odd indices at m, and this is again, m from zero up to N over 2 minus 1. All the components of the nth order DFT of F have now been accounted for and they are computed by finding half-order DFTs. The first half of them Ė let me summarize. The first half of them are computed by the first formula that we had up there. The second half of them are computed by this formula and the only difference between the two is this is a minus sign here instead of a plus sign. So in summary, Iím gonna erase this, but Iím gonna write it again. Glutton for punishment that I am. So to summarize, for m equal zero, 1, up to N over 2 minus 1. The Fourier transform, the nth order Fourier transform of F at m, the first half of the coefficients, is the Fourier transform of order N over 2 applied to the even indexed elements of the original input plus Omega nm, the Fourier transform order N over 2 of the odd indexed version of the original input, and the second half Ė so thatís the first half of the indices. For the second half of the indices, the nth order Fourier transform of F at m plus N over 2. Again, m is just ranging from zero to N over 2 minus 1. Thatís the index range for the half-order DFT. This is equal to the half-order Fourier transform F applied to the even indices, evaluated m, minus Omega minus m of the half-order Fourier transform of F the odd indices evaluated at m. And thatís all of them, okay? Thatís all of them. That writes the DFT as a combination of two half-order DFTs or maybe I should say two DFTs of half the order.
And now, iterate. If capital N is a power of 2, then you cut each one of these things down, okay? You cut each one of those things down and so on and so on and so on till youíre down to a single 2. Now, hereís what Iím not gonna do because weíre almost out of time, although thatís never stopped me before, but itís what Iím not gonna do. So Iím not gonna show you Ė so this is the FFT algorithm, or rather maybe I should say this is the basis for the FFT algorithm. All right, again, the idea is that half the work is twice the fun somehow. I mean youíre cutting down the nth order DFT to 2 N over 2 DFTs and then iterate. Now, so what Iím not gonna show you is why, theoretically and practically, this gives you the savings going from N2 to N log N. Thatís discussed in the notes and if you have any experience with what they call computational complexity, youíll see how the argument goes. If you donít, we can work through it some time, but Iím not going to go through that part. I donít want to somehow detract from this beautiful arrangement of the algorithm we have here. The second thing that Iím not gonna Ė so Iím not gonna do that, but this savings, cutting it down by 2 each stage, reduces the number of steps from N2 to N log N. Iím also not going to show you the sort of final form of the algorithm. If you look Ė and I actually donít have this in the notes, but if you look in other books, itís quite common to display, to sort of carry the step out, and thereís this gorgeous Ė or not, depending on your point of view Ė diagram called the ďButterfly DiagramĒ about how the individual inputs, original inputs, of the discreet signal sort of snake their way through the algorithm if you keep iterating it like this.
You know, what happens to the zero of output, what happens to the first output, what happens to the even inputs Ė it shouldnít be even Ė but the zero input, the first input, and so on, what happens to the even input, what happens to the odd input and so on. So Iím also not gonna show you that and that I actually donít do in the book, in the notes, but you can find that elsewhere if youíre interested in it. And finally, Iím also not gonna show you Ė Iím sorry for all these things Iím not gonna show you Ė Iím also not gonna show you how this leads to the matrix factorization, all right? But thatís exactly what happens. I mean you can translate from one to the other, that is, the fast Fourier transform algorithm leads to a factorization of the DFT matrix into a product of matrices where there are lots of zeroes. And the fact that you have lots of zeroes is another reason why thereís such a savings in computation because when you have zeroes in your matrix, thatís effectively not an operation, not a multiplication that happens. So those are the things Iím not gonna show you. But what I did want you to see is I wanted you to see how this arrangement works. The crucial first step in going from an nth order DFT to an order to 2 DFTs to order N over 2, thatís really the crucial observation here and how this was done. It really is quite striking and of course, how much of the modern worldís economy depends on this algorithm. Thatís also really Ė I think itís right up there at the top of the list for the number for the algorithms that are in constant day-to-day use. So we say goodbye right now to the DFT and its properties. Next time, Iím gonna talk about linear systems. We have to do a little rearranging here because I wanted to be sure to cover this, by popular demand, and then weíll move on to a discussion of linear systems, linear time variance systems, and then higher dimensional Fourier transforms. Thank you all.
End of Audio
Duration: 51 minutes