Fast Fourier Transform (FFT)

The Fast Fourier Transform (FFT) is an algorithm that computes the Discrete Fourier Transform (DFT) of a sequence in O(n log n) time.

Step 1 / 13

0.20+0.00i

Idx 0

1.80+0.00i

Idx 1

0.40+0.00i

Idx 2

-0.60+0.00i

Idx 3

-1.30+0.00i

Idx 4

0.70+0.00i

Idx 5

-0.30+0.00i

Idx 6

-0.50+0.00i

Idx 7

Initial signal after bit-reversal reordering. This optimizes memory layout for butterfly operations.

Signal Input (Real Parts)

x[0]

x[1]

x[2]

x[3]

x[4]

x[5]

x[6]

x[7]

Butterfly Detail

Play step through to see details.

Recursive Logic

Pseudocode

1function FFT(a):
2  n = length(a)
3  if n == 1: return a
4  ω_n = exp(-2πi/n)
5  ω = 1
6  a_even = [a[0], a[2], ..., a[n-2]]
7  a_odd = [a[1], a[3], ..., a[n-1]]
8  y_even = FFT(a_even)
9  y_odd = FFT(a_odd)
10  for k = 0 to n/2 - 1:
11    y[k] = y_even[k] + ω * y_odd[k]
12    y[k + n/2] = y_even[k] - ω * y_odd[k]
13    ω = ω * ω_n
14  return y