FFT explanation for non math guys
Hi!
I´m looking for the simple fft explanation for guys that have no idea about math. That´s 13/14 years old guys. As programmer I can read the source code and understand every line but i can´t grasp the general concept. I tried seaching for a sipmle explanation and i got algorithms of 10 lines long but i couldn´t find anything that gives a simple example of what´s happening... what i mean let´s try to multiply 2 smalls int 23 and 12 for example... what does happens on a simple fft algorithm? i tried to follow the steps on a paper with a pencil and i couldn´t get it any help? Creative1 
Re: fft explanation for non math guys
[quote="creative1"]I´m looking for the simple fft explanation for guys that have no idea about math. That´s 13/14 years old guys.[/quote]
I hate to be skeptical, but I'm not aware of any texts or web pages that explain FFTs in extremely elementary terms. It took me a long time for me to grasp FFT concepts well enough to code one. FFTs are complex beasts. Most FFT articles and textbooks quickly get sidetracked with optimization techniques which contribute nothing to your understanding of what they are and why they work. You really want to find a text that talks about Fourier Transforms, rather than Fast Fourier Transforms. Good luck in your search, hopefully someone can make a recommendation 
FT is at least a first year uni subject. I think it is rather diffcult to explain to someone with a mathematic knowledge of a 13/14 year old though :)

There are some fairly practical enginering maths books that are not too bad. They do not go too far into theory, but more into application. makes it a tiny bit easier to understand. ;)
Alf 
Re: fft explanation for non math guys
[quote="creative1"]Hi!
I´m looking for the simple fft explanation for guys that have no idea about math. That´s 13/14 years old guys. As programmer I can read the source code and understand every line but i can´t grasp the general concept. I tried seaching for a sipmle explanation and i got algorithms of 10 lines long but i couldn´t find anything that gives a simple example of what´s happening... what i mean let´s try to multiply 2 smalls int 23 and 12 for example... what does happens on a simple fft algorithm? i tried to follow the steps on a paper with a pencil and i couldn´t get it any help? Creative1[/quote] Hmm, it's difficult to explain the deeper theory underlying transforms to even a good student at that age level, but let me try to illustrate the basic features with an analogy you should be able to grasp. The basic idea behind most (if not all) mathematical transforms is to take some problem that appears (or simply is) difficult in its original form and turn it into a problem that is easier (or even trivial) to solve when transformed. A simple example is vector arithmetic in two dimensions. Vectors (x1,y1) and (x2,y2) are easily added in x,y coordinates  simply add their components to get (x1+x2, y1+y2)  but are harder to multiply together. (I'm thinking here of multiply as defined for complex numbers, i.e. with product = (x1*x2y1*y2, x1*y2+x2*y1).) OTOH, if I transform to polar coordinates and write each one as a pair (r, theta) (with r = sqrt(x^2+y^2) and theta = atan(y/x)), then they are easy to multiply simply multiply the rparts together, and add the thetaparts together to get the product (still in polar coordinates), (r1*r2, theta1+ theta2). By using polar form I've reduced the cost of getting the product from 4 (scalar) multiplies and 2 adds to just 1 multiply and one add. Of course I've also made it harder to do further vector additions  to do that efficiently I'll want to transform the result back to (x,y) coordinates  but that's the tradeoff. Now consider multiplying together two numbers A and B, each having N digits. The way one learns to do this in grammar school is to multiply each digit of B by the rightmost digit of A, then shift B to the left one place (i.e. add a 0 at the right end) and multiply that by the nexthigherorder digit of A, and so forth, then sum all the N intermediate products. That needs on the order of N^2 digit multiplications and a similar number of digit additions  in mathematical terms, it's an O(N^2) ("big oh of N squared" or "order of N squared") algorithm. Now this type of procedure has another name: discrete convolution. It's also used a lot in completely different fields, for instance signal processing  you typical cell phone does a lot of it. Now there's a famous transform which allows us to do discrete convolutions really fast, and it's called the Fast Fourier Transform. If we treat each of our input numbers A and B as a vector with N components (the digits of the number) and do an FFT on each of them, we get a pair of vectors A^ and B^ (that generally look nothing like the inputs) which have a very special property: [b][i] in Fourier space (which is where we consider the transform to have taken our input vectors), convolution looks just like digitbydigit multiplication. [/i][/b] In other words, if we multiply each individual component (just a number) of A^ with the corresponding one of B^, the result is guaranteed to be the Fouriertransformed version of the convolution of A and B. That is, in Fourier space, convolution costs just O(N) operations, much better than our original O(N^2). To get back the result we want (i.e. convolution(A, B), not in Fouriertransformed form) we do an inverse transform on the single vector resulting from the digit bydigit multiply of A^ and B^. (Using our x,yversuspolar analogy, this is analogous to converting the polarform product of our two vectors back to x,y coordinates, using the inverse transform x = r*cos(theta), y = r*sin(theta).) Now, it's an interesting feature of the FFT approach that doing the transform actually costs more than doing the digitbydigit multiply form of convolution that it enables. But doing the transform costs O(N*log2(N)) operations (and the "oh of" notation hides a constant of proportionality which is larger than one  typically around 5 in a good implementation), and of course we need to do two such transforms, so a reasonable estimate of the FFT cost of multiplication is around 10*N*log2(N). But for N sufficiently large, this is cheaper than the grammarschool way. And as N continues to get larger, the speed advantage continues to grow, since the ratio N/log2(N) grows without bound as N tends to infinity. In mathematical terms, we say that FFTbased multiply is "asymptotically faster" than grammar school. To put numbers on this: let's consider the grammarschool way to cost 2N^2 operations (N^2 digit multiplies and roughly the same number of adds, plus the carries in the output digits, which only cost O(N) work, i.e. which don't contribute appreciably to the operation count.) Here is a small table of 2N^2 vs. the opcount for FFT: [code] N 2N^2 10*n*log2(N)    10 200 332 100 20000 6640 10^3 2*10^6 ~10^5 10^6 2*10^12 ~2*10^8 10^9 2*10^18 ~3*10^11 [/code] In words: For 10digit numbers, FFT is only around 60% as fast as GS. For 100digit numbers, FFT is about 3 times faster. For 1000digit numbers, FFT is about 20 times faster. For milliondigit numbers, FFT is about 10,000 times faster. For billiondigit numbers, FFT is nearly ten million times faster. Now to your small example: let's multiply 12 and 23 the FFT way, representing them as base10 vectors, i.e. we form our input vectors simply by separating out the digits of the above base10 representation of the numbers. One important practical detail here, which I glossed over in my earlier discussion: if we want to FFTmultiply two numbers, each having N digits, we expect the product to have as many as 2*N digits, so we actually need to do a length2N FFT to leave room for the digits at the high end that will "fill in" when we do the multiply. That means we need to pad our input vectors with N zeros at the upper end. Thus, our input vectors are A = (2,1,0,0) and B = (3,2,0,0), where the leastsignificant digit of each number is leftmost. The Fourier transform of a length4 vector (a,b,c,d) is given in matrixmultiply form as [code] +1 +1 +1 +1 a a+b+c+d +1 +i 1 i*b=(ac)+i*(bd) +1 1 +1 1 c ab+cd +1 i 1 +i d (ac)i*(bd) [/code] where i = sqrt(1) is the usual imaginary constant. Doing this for our two input vectors, our transformed vectors are A^ = (3, 2+i, 1, 2i) and B^ = (5, 3+2i, 1, 32i). The Fouriertransformed discrete convolution of A and B is then simply A^*B^, where the '*' means componentbycomponent (the fancy word is 'dyadic') multiply, which gives (15, 4+7i, 1, 47i). To get the digits of the product we're after, we need to inverseFouriertransform this vector. For length4 vectors, the IFT looks just like the FT, but with the signs on the iterms in the above matrix switched and a factor of onefourth multiplying the whole thing. (We always have the factor of 1/N for a lengthN inverse transform, since we require that doing an FT of a vector followed by an IFT simply give us back our original vector). That is, the length4 IFT of our vector (15, 4+7i, 1, 47i) has entries [15+(4+7i)+1+(47i)]/4 = 24/4 = 6, [(151)i*(4+7i4+7i)]/4 = [14+14]/4 = 7, [15(4+7i)+1(47i)]/4 = 8/4 = 2, [(151)+i*(4+7i4+7i)]/4 = [1414]/4 = 0. Since all the output digits happen to be less than 10 and nonnegative, we don't need to do any carry step, and since the outputs are leastsignificant first, our result (written in normal decimal order) is 276. Hope this helped, Ernst p.s.: I was rather cavalier in my use of the term "FFT" above  the proper name for the transform we use is the Discrete Fourier Transform (DFT); FFT is simply a way of efficiently effecting a DFT. For example, a non FFT version of the above calculation would use a standard O(N^2) matrix multiply algorithm to do the DFT. But if you look at the righthand side of the matrix multiply, you see many repeated terms. To get the RHS, all we need to do is the following sequence: w = a+c x = ac y = b+d z = bd Then, output 1 = w+y output 2 = x+i*z output 3 = wy output 4 = yi*z Exploiting those types of symmetries in the DFT matrix is what the FFT does. 
sorry i delayed so much with this answer but i just realized that there was an answer back here...
thanks alot for the explaination but there still one thing i couldn´t grab how did you create the 'i' matrix to be able to make the transform? everything is was very nice explained but i couldn´t get how you filled that matrix with 1, 1, i, i values where did that come from? and in the case the numbers weren´t 23 and 12 and there was a carry on the multiplication... how would i handle that? Creative1 
[quote="creative1"]
how did you create the 'i' matrix to be able to make the transform? everything is was very nice explained but i couldn´t get how you filled that matrix with 1, 1, i, i values where did that come from? [/quote] [code:1] +1 +1 +1 +1 i^0 i^0 i^0 i^0 +1 +i 1 i=i^0 i^1 i^2 i^3 +1 1 +1 1 i^0 i^2 i^4 i^6 +1 i 1 +i i^0 i^3 i^6 i^9 [/code:1] For FFT size 2N, just replace the i with cos(pi/N)+i sin(pi/N)(That is, a 2Nth root of 1)and constuct the matrix as above....... P.S. I am only 14 years old! 
[quote="wpolly"]
For FFT size 2N, just replace the i with cos(pi/N)+i sin(pi/N)(That is, a 2Nth root of 1)and constuct the matrix as above....... [/quote] I didn´t understand that last part... the fft that we were using was size 2N right? and 'replace the i with cos(pi/N)+i sin(pi/N)' you mean: cos(pi/N)+ sqrt(1) sin(pi/N) ? 
I believe for the example given, a FFT size of 2 was used. The general formula uses cos(pi/n)+i sin(pi/n) , which reduces to i for a FFT size of 2.
P.S. I'm only 15. Guess I'm not the only young cruncher around here. 
[quote="Kevin"]I believe for the example given, a FFT size of 2 was used. The general formula uses cos(pi/n)+i sin(pi/n) , which reduces to i for a FFT size of 2.
[/quote] No, the (n)th complex roots of unity are given by exp(i*2*pi/n) = cos(2*pi/n)+i*sin(2*pi/n). The reason one sees the i's in my example is that to DFTmultiply two general length2 numbers, one must zeropad the input vectors to double the number of input digits, i.e. one must use a length4 DFT. Note that for [i]modular multiplication[/i] for certain moduli of special form (which happen to include the Mersenne numbers), one can use additional clever tricks to avoid the zeropadding. That's because a lengthn discrete cyclic convolution (working with baseX inputs, where X need not be 10) is really a polynomial multiplication modulo X^n  1. That means that in my example, if I had used a length2 DFT instead of length4 (and recall that I was using X = 10), I would have still obtained the correct result, but only in the sense that it is correct modulo 10^2  1 = 99. Let's try it: We again DFTmultiply 12 and 23 using base10 arithmetic, but this time we don't pad our input vectors with zeros. Thus, our input vectors are A = (2,1) and B = (3,2), where the leastsignificant digit of each number is leftmost. The Fourier transform of a length2 vector (a,b) is given in matrixmultiply form as [code:1] +1 +1 a a+b +1 1*b=ab . [/code:1] Doing this for our two input vectors, our transformed vectors are A^ = (3, 1) and B^ = (5, 1). The Fouriertransformed discrete convolution of A and B is then simply A^*B^, where the '*' means dyadic multiply, which gives (15, 1). To get the digits of the product we're after, we need to inverseFouriertransform this vector. For length2 vectors, the IFT looks just like the FT, but with a factor of onehalf multiplying the whole thing. That is, the length2 IFT of our vector (15, 1) has entries (16, 14)/2 = (8, 7). Since all the output digits happen to be < 10 and nonnegative, we don't need to do any carry step, and since the outputs are leastsignificant first, our result (written in normal decimal order) is 78. The exact (full) product is 12*23 = 276, which indeed == 78 modulo 99. Ernst 
[quote="creative1"][quote="wpolly"]
For FFT size 2N, just replace the i with cos(pi/N)+i sin(pi/N)(That is, a 2Nth root of 1)and constuct the matrix as above....... [/quote] I didn´t understand that last part... the fft that we were using was size 2N right? and 'replace the i with cos(pi/N)+i sin(pi/N)' you mean: cos(pi/N)+ sqrt(1) sin(pi/N) ?[/quote] Yes an 2Nth root of 1 is cos(2pi/2N)+ i*sin(2pi/2N). for the example given, we were using FFT size 4 so we'll have to use the fourth root of 1That is, i. 
All times are UTC. The time now is 03:09. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.