How exactly do you compute the Fast Fourier Transform?

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开发者_JAVA技巧'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?

---

You're right, "the" Fast Fourier transform is just a name for any algorithm that computes the discrete Fourier transform in O(n log n) time, and there are several such algorithms.

Here's the simplest explanation of the DFT and FFT as I think of them, and also examples for small N, which may help. (Note that there are alternative interpretations, and other algorithms.)

Discrete Fourier transform

Given N numbers f₀, f₁, f₂, …, f_N-1, the DFT gives a different set of N numbers.

Specifically: Let ω be a primitive Nth root of 1 (either in the complex numbers or in some finite field), which means that ω^N=1 but no smaller power is 1. You can think of the f_k's as the coefficients of a polynomial P(x) = ∑f_kx^k. The N new numbers F₀, F₁, …, F_N-1 that the DFT gives are the results of evaluating the polynomial at powers of ω. That is, for each n from 0 to N-1, the new number F_n is P(ωⁿ) = ∑_0≤k≤N-1 f_kω^nk.

[The reason for choosing ω is that the inverse DFT has a nice form, very similar to the DFT itself.]

Note that finding these F's naively takes O(N²) operations. But we can exploit the special structure that comes from the ω's we chose, and that allows us to do it in O(N log N). Any such algorithm is called the fast Fourier transform.

Fast Fourier Transform

So here's one way of doing the FFT. I'll replace N with 2N to simplify notation. We have f₀, f₁, f₂, …, f_2N-1, and we want to compute P(ω⁰), P(ω¹), … P(ω^2N-1) where we can write

P(x) = Q(x) + ω^NR(x) with

Q(x) = f₀ + f₁x + … + f_N-1x^N-1

R(x) = f_N + f_N+1x + … + f_2N-1x^2N-1

Now here's the beauty of the thing. Observe that the value at ω^k+N is very simply related to the value at ω^k:
P(ω^k+N) = ω^N(Q(ω^k) + ω^NR(ω^k)) = R(ω^k) + ω^NQ(ω^k). So the evaluations of Q and R at ω⁰ to ω^N-1 are enough.

This means that your original problem — of evaluating the 2N-term polynomial P at 2N points ω⁰ to ω^2N-1 — has been reduced to the two problems of evaluating the N-term polynomials Q and R at the N points ω⁰ to ω^N-1. So the running time T(2N) = 2T(N) + O(N) and all that, which gives T(N) = O(N log N).

Examples of DFT

Note that other definitions put factors of 1/N or 1/√N.

For N=2, ω=-1, and the Fourier transform of (a,b) is (a+b, a-b).

For N=3, ω is the complex cube root of 1, and the Fourier transform of (a,b,c) is (a+b+c, a+bω+cω², a+bω²+cω). (Since ω⁴=ω.)

For N=4 and ω=i, and the Fourier transform of (a,b,c,d) is (a+b+c+d, a+bi-c-di, a-b+c-d, a-bi-c+di). In particular, the example in your question: the DFT on (1,0,0,0) gives (1,1,1,1), not very illuminating perhaps.

---

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.

---

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)

---

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.

---

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://blogs.zynaptiq.com/bernsee/dft-a-pied/

I couldn't have explained it better myself.