How exactly do you compute the Fast Fourier Transform?

Question

Hello,

I've been reading a lot about Fast Fourier Transform and am trying to understand the low-level aspect of it. Unfortunately, Google and Wikipedia are not helping much at all.. and I have like 5 different algorithm books open that aren't helping much either.

I'm trying to find the FFT of something simple like a vector [1,0,0,0]. Sure I could just plug it into Matlab but that won't help me understand what's going on underneath. Also, when I say I want to find the FFT of a vector, is that the same as saying I want to find the DFT of a vector just with a more efficient algorithm?

Answer 1

Yes, the FFT is merely an efficient DFT algorithm. Understanding the FFT itself might take some time unless you've already studied complex numbers and the continuous Fourier transform; but it is basically a base change to a base derived from periodic functions.

(If you want to learn more about Fourier analysis, I recommend the book Fourier Analysis and Its Applications by Gerald B. Folland)

Answer 2

The FFT is just an efficient implementation of the DFT. The results should be identical for both, but in general the FFT will be much faster. Make sure you understand how the DFT works first, since it is much simpler and much easier to grasp.

When you understand the DFT then move on to the FFT. Note that although the general principle is the same, there are many different implementations and variations of the FFT, e.g. decimation-in-time v decimation-in-frequency, radix 2 v other radices and mixed radix, complex-to-complex v real-to-complex, etc.

A good practical book to read on the subject is Fast Fourier Transform and Its Applications by E. Brigham.

Answer 3

I'm also new to Fourier transforms and I found this online book very helpful:

The Scientists and Engineer's Guide to Digital Signal Processing

The link takes you to the chapter on the Discrete Fourier Transform. This chapter explains the difference between all the Fourier transforms, as well as where you'd use which one and pseudocode that shows how you go about calculating the Discrete Fourier Transform.

Answer 4

If you seek a plain English explanation of DFT and a bit of FFT as well, instead of academic goggledeegoo, then you must read this: http://www.dspdimension.com/admin/dft-a-pied/

I couldn't have explained it better myself.