Fast Fourier Transform Explained with Worked Examples

The FFT splits a length- transform into two of length (even and odd samples) and combines them with the butterfly , .

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

  • complex numbers and roots of unity
  • sums Σ xₙ e^(−2πikn/N)
  • radians

What Fast Fourier transform (butterfly) means

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.

What is it used for?

The FFT computes the discrete Fourier transform by repeatedly splitting it into smaller transforms.

How to use fast fourier transform (butterfly)

  1. Split the samples into even and odd indices.
  2. Transform each half (recursively).
  3. Multiply the odd part by the twiddle factor .
  4. Combine with plus and minus to get and .

Graph

Magnitudes |Xk| of the transform of (1, 2, 3, 4)|X0| = 10|X1| = 2.83|X2| = 200.511.522.533.544.55024681012Magnitudes |Xk| of the transform of (1, 2, 3, 4)k + 1yGraph with x from 0 to 5 and y from 0 to 12. Shows bars (4); point |X0| = 10 at (1, 10); point |X1| = 2.83 at (2, 2.83); point |X2| = 2 at (3, 2).

The values are 10, −2+2i, −2, −2−2i.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: X₀ and X₂

For find and from , .

Worked example
Answer
X0=10, X2=−2X_0=10,\ X_2=-2
  1. X₀
  2. X₂

Example 2: X₁ and X₃

Find and using the twiddle factor .

Worked example
Answer
X1=−2+2i, X3=−2−2iX_1=-2+2i,\ X_3=-2-2i
  1. -i·O₁
  2. X₁
  3. X₃

Example 3: Parseval check

Check .

Worked example
Answer
120120
  1. Left
  2. Right

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

x = (1, 1, 1, 1)

X = (4, 0, 0, 0)

A constant signal.

x = (1, 0, 0, 0)

X = (1, 1, 1, 1)

An impulse.

x = (1, 2, 3, 4)

X₀ = 10, X₂ = −2, X₁ = −2 + 2i

N = 4.

Splitting

X_k = E_k + e^(−2πik/N) O_k

Even and odd halves.

Word problems

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.

Constant

Find the DFT of (1, 1, 1, 1).

  1. X₀4
  2. Others0
  3. Check: ✓(4, 0, 0, 0).

Impulse

Find the DFT of (1, 0, 0, 0).

  1. Every X_k1
  2. Check: ✓(1, 1, 1, 1).

A ramp Higher

Find X₀ and X₂ for (1, 2, 3, 4).

  1. X₀10
  2. X₂ = 1 − 2 + 3 − 4−2
  3. Check: ✓10 and −2.

X₁ Higher

Find X₁ for (1, 2, 3, 4) using e^(−iπ/2) = −i.

  1. 1 + 2(−i) + 3(−1) + 4(i)−2 + 2i
  2. Check: real part −2, imaginary part 2 ✓−2 + 2i.

Common mistakes

Wrong sign in the exponent

e^(+2πikn/N) ✗

e^(−2πikn/N) ✓

That is the inverse transform.

Forgetting the twiddle factor

X_k = E_k + O_k ✗

X_k = E_k + e^(−2πik/N)O_k ✓

Include the twiddle.

N not a power of 2

radix-2 FFT for N = 6 ✗

pad or use mixed radix ✓

Radix-2 needs 2ᵐ.

Scaling

forgetting 1/N on the inverse ✗

inverse includes 1/N ✓

Divide by N.

Exam tips

  1. X₀ = sum of samples.
  2. Even/odd split.
  3. Twiddle factor.
  4. N = 2ᵐ.
  5. Inverse has 1/N.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. X₀ of (2, 4, 6, 8) Foundation

20

2. X₂ of (2, 4, 6, 8): 2 − 4 + 6 − 8 Foundation

-4

3. X₀ of (1, −1, 1, −1) Foundation

0

4. X₂ of (1, −1, 1, −1): 1 + 1 + 1 + 1 Higher

4

5. X₀ of (5, 5, 5, 5) Higher

20

6. X₀ of (0, 1, 2, 3) Higher

6

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

DFT
Discrete Fourier transform.
FFT
Fast algorithm for the DFT.
Twiddle factor
e^(−2πik/N).
Radix-2
Splits into halves.
Impulse
Single non-zero sample.
Frequency bin
Index k.

Frequently asked questions

What is the FFT?

A fast algorithm for the discrete Fourier transform.

How fast is it?

O(N log N).

What is X₀?

The sum of the samples.

What is the DFT of an impulse?

All ones.

Which page covers the cost?

FFT cost.

Which page covers Crank–Nicolson?

Crank–Nicolson scheme.

More in Numerical methods and optimisation and the formula sheets.