8-Point FFT Step-by-Step

 

8-Point FFT Using Butterfly Method

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

Step 1: Split into Even & Odd

Even: {0,2,4,6}
Odd: {1,3,5,7}

Step 2: FFT of Even Part

Split:
{0,4} → {4, -4}
{2,6} → {8, -4}

Combine:
E = {12, -4+4j, -4, -4-4j}

Step 3: FFT of Odd Part

Split:
{1,5} → {6, -4}
{3,7} → {10, -4}

Combine:
O = {16, -4+4j, -4, -4-4j}

Step 4: Twiddle Factors

W₈ = e^-j2π/8 = e^-j45°

k	W8k
0	1
1	(1/√2)(1 - j)
2	-j
3	(-1 - j)/√2

Step 5: Final Combination

X[0] = 12 + 16 = 28
X[4] = 12 - 16 = -4

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

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

X[3] = -4 + 1.656j
X[7] = -4 - 9.656j

Final Answer:

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