x = (1, 1, 1, 1)
X = (4, 0, 0, 0)
A constant signal.
The FFT splits a length- transform into two of length (even and odd samples) and combines them with the butterfly , .
This page is easier if you are comfortable with:
Take , . The even samples have transform , the odd samples have . For the twiddle factor is 1, so and . For the factor is , so : and . These are the values of the discrete Fourier transform, with twiddle factors that are roots of unity.
Check with Parseval: . Repeating the splitting times reduces the work from to (FFT cost). The complex arithmetic uses the complex exponential.
The FFT makes spectral methods, filtering and fast multiplication practical, and it computes the coefficients of Fourier series and the fast convolution of the convolution theorem.
The FFT computes the discrete Fourier transform by repeatedly splitting it into smaller transforms.
The values are 10, −2+2i, −2, −2−2i.
These examples are worked by hand, step by step, so you can compare your own working.
For find and from , .
Find and using the twiddle factor .
Check .
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
X = (4, 0, 0, 0)
A constant signal.
X = (1, 1, 1, 1)
An impulse.
X₀ = 10, X₂ = −2, X₁ = −2 + 2i
N = 4.
X_k = E_k + e^(−2πik/N) O_k
Even and odd halves.
The DFT is X_k = Σₙ xₙ e^(−2πikn/N). The FFT splits it into even- and odd-indexed sums, X_k = E_k + e^(−2πik/N)O_k, reducing the cost from N² to N log₂ N.
Find the DFT of (1, 1, 1, 1).
Find the DFT of (1, 0, 0, 0).
Find X₀ and X₂ for (1, 2, 3, 4).
Find X₁ for (1, 2, 3, 4) using e^(−iπ/2) = −i.
e^(+2πikn/N) ✗
e^(−2πikn/N) ✓
That is the inverse transform.
X_k = E_k + O_k ✗
X_k = E_k + e^(−2πik/N)O_k ✓
Include the twiddle.
radix-2 FFT for N = 6 ✗
pad or use mixed radix ✓
Radix-2 needs 2ᵐ.
forgetting 1/N on the inverse ✗
inverse includes 1/N ✓
Divide by N.
Try each one on paper, then open the answer. Use the solver above to see the full working.
20
-4
0
4
20
6
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
A fast algorithm for the discrete Fourier transform.
O(N log N).
The sum of the samples.
All ones.
FFT cost.
More in Numerical methods and optimisation and the formula sheets.