FFT explanation for non math guys

[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

[Prime95]

Originally Posted by creative1

I´m looking for the simple fft explanation for guys that have no idea about math. That´s 13/14 years old guys.

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

[xtreme2k]

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 :)

[Prime Monster]

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

[ewmayer]

Originally Posted by 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

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*x2-y1*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 r-parts together, and add the theta-parts 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 next-higher-order 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:

in Fourier space (which is where we consider the transform to have taken our input vectors), convolution looks just like digit-by-digit multiplication.

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 Fourier-transformed 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 Fourier-transformed form) we do an inverse transform on the single vector resulting from the digit- by-digit multiply of A^ and B^. (Using our x,y-versus-polar analogy, this is analogous to converting the polar-form 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 digit-by-digit 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 grammar-school 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 FFT-based multiply is "asymptotically faster" than grammar school. To put numbers on this: let's consider the grammar-school 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:

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

In words:

For 10-digit numbers, FFT is only around 60% as fast as GS.
For 100-digit numbers, FFT is about 3 times faster.
For 1000-digit numbers, FFT is about 20 times faster.
For million-digit numbers, FFT is about 10,000 times faster.
For billion-digit 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 base-10 vectors, i.e. we form our input vectors simply by separating out the digits of the above base-10 representation of the numbers. One important practical detail here, which I glossed over in my earlier discussion: if we want to FFT-multiply 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 length-2N 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 least-significant digit of each number is leftmost. The Fourier transform of a length-4 vector (a,b,c,d) is given in matrix-multiply form as

|+1 +1 +1 +1| |a| a+b+c+d
|+1 +i -1 -i|*|b|=(a-c)+i*(b-d)
|+1 -1 +1 -1| |c| a-b+c-d
|+1 -i -1 +i| |d| (a-c)-i*(b-d)

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, 2-i) and B^ = (5, 3+2i, 1, 3-2i). The Fourier-transformed discrete convolution of A and B is then simply A^*B^, where the '*' means component-by-component (the fancy word is 'dyadic') multiply, which gives (15, 4+7i, 1, 4-7i). To get the digits of the product we're after, we need to inverse-Fourier-transform this vector. For length-4 vectors, the IFT looks just like the FT, but with the signs on the i-terms in the above matrix switched and a factor of one-fourth multiplying the whole thing. (We always have the factor of 1/N for a length-N 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 length-4 IFT of our vector (15, 4+7i, 1, 4-7i) has entries

[15+(4+7i)+1+(4-7i)]/4 = 24/4 = 6,
[(15-1)-i*(4+7i-4+7i)]/4 = [14+14]/4 = 7,
[15-(4+7i)+1-(4-7i)]/4 = 8/4 = 2,
[(15-1)+i*(4+7i-4+7i)]/4 = [14-14]/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 least-significant 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 right-hand 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 = a-c
y = b+d
z = b-d

Then,

output 1 = w+y
output 2 = x+i*z
output 3 = w-y
output 4 = y-i*z

Exploiting those types of symmetries in the DFT matrix is what the FFT does.

[creative1]

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

[wpolly]

Originally Posted by 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?

[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!

[creative1]

Originally Posted by 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.......

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) ?

[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.

P.S. I'm only 15. Guess I'm not the only young cruncher around here.

[ewmayer]

Originally Posted by 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.

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 DFT-multiply two general length-2 numbers, one
must zero-pad the input vectors to double the number of input digits, i.e.
one must use a length-4 DFT. Note that for modular multiplication
for certain moduli of special form (which happen to include the Mersenne
numbers), one can use additional clever tricks to avoid the zero-padding.
That's because a length-n discrete cyclic convolution (working with base-X
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 length-2
DFT instead of length-4 (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 DFT-multiply 12 and 23 using base-10 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
least-significant digit of each number is leftmost. The Fourier transform
of a length-2 vector (a,b) is given in matrix-multiply form as

[code:1]
|+1 +1| |a| a+b
|+1 -1|*|b|=a-b .
[/code:1]

Doing this for our two input vectors, our transformed vectors are
A^ = (3, 1) and B^ = (5, 1). The Fourier-transformed 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 inverse-Fourier-transform this vector. For length-2
vectors, the IFT looks just like the FT, but with a factor of one-half
multiplying the whole thing.

That is, the length-2 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 least-significant
first, our result (written in normal decimal order) is 78. The exact
(full) product is 12*23 = 276, which indeed == 78 modulo 99.

-Ernst

[wpolly]

Originally Posted by creative1

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) ?

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 1---------That is, i.