What area's of mathematics are needed to make a basic understanding of the FFT algorithm ?

Question

I know FFT is used in signal processing ( at last check), the Lucas-Lehmer Test and probably many other things. But what is the Fast Fourier Transform and what area's of math will help me understand transforms like it ( and yes I know of the area Fourier analysis, just not if anything about it) I've read a little of the FFT wikipedia article and some on DFT etc. But I'm not even sure I understand them enough. and yes I know it's not for simpletons like me.

Answer 1

http://download.ni.com/evaluation/pxi/Understanding%20FFTs%20and%20Windowing.pdf

I used this for my senior thesis on signal processing. Just make an account and you'll be able to open the paper, it is very reliable.

Answer 2

First let me begin with a simple explanation of the fourier transform. It takes a signal from the time-domain to the frequency domain. This means that instead of seeing a sine wave we see a point on a graph. And because any real signal can be described as the sum of sines, we get many points, that if connected form a line graph in the frequency plot.

The Fast fourier transform is a mathematical trick that significantly reduces the time it takes to do a fourier transform significantly. FFT algorithms require that you have samples in powers of 2, because they all divide the problem into tiny parts. The small parts are faster to calculate (here the discrete fourier transform formula is used), and the final result is combined from all the small ones. So instead of doing 1 DFT of size 4096, it can do 256 DFTs of size 16.

The mathematical explanation is pretty advanced, check out the Cooley Tukey algorithm.