FFT Butterfly Method Explained (with Example of 4-point DFT)

 

FFT Using Butterfly Method

Given:
x[n] = {0, 1, 2, 3}

Step 1: Split into Even & Odd

Even indices: x_e = {0, 2}
Odd indices: x_o = {1, 3}

Step 2: 2-point DFT

For any {a, b}:
DFT = {a + b, a - b}

Even Part:
E = {0+2, 0-2} = {2, -2}

Odd Part:
O = {1+3, 1-3} = {4, -2}

Step 3: Combine Using Butterfly

X[k] = E[k] + W^k O[k]
X[k + N/2] = E[k] - W^k O[k]

For N = 4:
W⁰ = 1
W¹ = -j

Final Calculations

X[0] = 2 + 4 = 6
X[2] = 2 - 4 = -2

X[1] = -2 + (-j)(-2) = -2 + 2j
X[3] = -2 - (-j)(-2) = -2 - 2j

Final Answer:

X[k] = {6, -2 + 2j, -2, -2 - 2j}