Hi,
i am trying to understand this FFT mystry, i am worked with DFTs and i have managed to solve a few DFT problems , i have come accross the butterfly algorithm , i want to solve a 4/8 point DFT with the help of FFT algorithm to see how it works, i have check web for sometime but all i could find is graphical respresentation but nothing else.
can any one help me find a good link which manually solves a 4 or 8 point FFT.
i'll really apprecaite any positive idea, i need to solve this problem ASAP..
thanks in anticipation
Ali

The cases N=4 and N=8 are just special cases of equation 12.2.3 in the Numerical Recipes book. For example, the case N=4 gives:


F[k] = {f[0] + exp(pi*i*k)*f[2])*f[2]} + exp(pi*i*k/2)*{f[1] + exp(pi*i*k)*f[3]}


This leads to the four equations:


F[0] = (f[0] + f[2]) + (f[1] + f[3])
F[1] = (f[0] - f[2]) + i*(f[1] - f[3])
F[2] = (f[0] + f[2]) - (f[1] + f[3])
F[3] = (f[0] - f[2]) - i*(f[1] - f[3])


These would be evaluated using intermediate computations, as the FFT does, to avoid the recalculation of quantities that are used more than once:


a[0] = f[0] + f[2]
a[1] = f[1] + f[3]
b[0] = f[0] - f[2]
b[1] = f[1] - f[3]

F[0] = a[0] + a[1]
F[1] = b[0] + i*b[1]
F[2] = a[0] - a[1]
F[3] = b[0] - i*b[1]


You can see that in this low-N case the FFT does not have a huge advantage in speed, as it has for larger N, over just evaluating the individual terms of a Fourier transform.

If I got the math right, the case N=8 would be calculated in the following order:


a[0] = f[0] + f[4] b[0] = f[0] - f[4]
a[1] = f[2] + f[6] b[1] = f[2] - f[6]
a[2] = f[1] + f[5] b[2] = f[1] - f[5]
a[3] = f[3] + f[7] b[3] = f[3] - f[7]

c[0] = a[0] + a[1] d[0] = a[2] + a[3]
c[1] = b[0] + i*b[1] d[1] = b[2] + i*b[3]
c[2] = a[0] - a[1] d[2] = a[2] - a[3]
c[3] = b[0] - i*b[1] d[3] = b[2] - i*b[3]

K = exp(i*pi/4)

F[0] = c[0] + d[0]
F[1] = c[1] + K*d[1]
F[2] = c[2] + i*d[2]
F[3] = c[3] + i*K*d[3]
F[0] = c[0] - d[0]
F[1] = c[1] - K*d[1]
F[2] = c[2] - i*d[2]
F[3] = c[3] - i*K*d[3]