FFT Butterfly Method Explained (with Simulations)

4-Point FFT Using Butterfly Method

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

Step 1: Split into Even & Odd

Even indices: x_e = {x[0], x[2]} = {0, 2}
Odd indices: x_o = {x[1], x[3]} = {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 + 2] = E[k] - W₄^k O[k]

Twiddle Factors (N=4): W₄⁰ = 1, W₄¹ = -j

Final Calculations:
X[0] = E[0] + W₄⁰O[0] = 2 + (1)(4) = 6
X[2] = E[0] - W₄⁰O[0] = 2 - (1)(4) = -2

X[1] = E[1] + W₄¹O[1] = -2 + (-j)(-2) = -2 + 2j
X[3] = E[1] - W₄¹O[1] = -2 - (-j)(-2) = -2 - 2j

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

---

8-Point FFT Using Butterfly Method

Given: x[n] = {0,1,2,3,4,5,6,7}

Step 1: Split into Bit-Reversed Order

To perform DIT-FFT, split the 8 points into pairs of two:
Group A: {x[0], x[4]} = {0, 4} | Group B: {x[2], x[6]} = {2, 6}
Group C: {x[1], x[5]} = {1, 5} | Group D: {x[3], x[7]} = {3, 7}

Step 2: FFT of Even Part (Combine A & B)

1. 2-pt DFTs: A={4, -4}, B={8, -4}
2. Combine using W₄^k to get 4-pt DFT (E):
E[0] = 4 + (1)(8) = 12 | E[2] = 4 - (1)(8) = -4
E[1] = -4 + (-j)(-4) = -4+4j | E[3] = -4 - (-j)(-4) = -4-4j
E = {12, -4+4j, -4, -4-4j}

Step 3: FFT of Odd Part (Combine C & D)

1. 2-pt DFTs: C={6, -4}, D={10, -4}
2. Combine using W₄^k to get 4-pt DFT (O):
O[0] = 6 + (1)(10) = 16 | O[2] = 6 - (1)(10) = -4
O[1] = -4 + (-j)(-4) = -4+4j | O[3] = -4 - (-j)(-4) = -4-4j
O = {16, -4+4j, -4, -4-4j}

Step 4: 8-Point Twiddle Factors

W₈^k = e^-j2πk/8

k	0	1	2	3
W8k	1	0.707 - 0.707j	-j	-0.707 - 0.707j

Step 5: Final Combination (Butterfly)

Formula: X[k] = E[k] + W₈^kO[k] and X[k+4] = E[k] - W₈^kO[k]

X[0] = 12 + (1)(16) = 28
X[4] = 12 - (1)(16) = -4

X[1] = (-4+4j) + (0.707-0.707j)(-4+4j) = -4 + 9.656j
X[5] = (-4+4j) - (0.707-0.707j)(-4+4j) = -4 - 1.656j

X[2] = (-4+4j) + (-j)(-4-4j) = -4+4j + (-4+4j) = -4+4j (Simplified)
... (continue for remaining k)

Final Answer:

X[k] = {28, -4+9.656j, -4+4j, -4+1.656j, -4, -4-1.656j, -4-4j, -4-9.656j}

Radix-2 FFT Butterfly Simulator

Select FFT Size (N): 2-Point 4-Point 8-Point

Butterfly Step: X_top = A + W_N^kB  |  X_bottom = A - W_N^kB

Try Other Interactive Online Simulations

1. Interactive FFT Online Simulator (For understanding Fundamentals) 
2. Interactive FFT Online Simulator (Analyze .CSV, .MP3, .MP4, etc.

Further Reading

1. Fourier Transform
2. OFDM

Return to Fourier Transform Main Page →