DIT-FFT of {1,1,2,0,1,2,0,1} and spectrum

Method: radix-2 decimation in time (N = 8, 3 stages)

Input in bit-reversed order: x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7). Each butterfly: A' = A + W·B, B' = A − W·B, with W₈⁰ = 1, W₈¹ = 0.7071 − j0.7071, W₈² = −j, W₈³ = −0.7071 − j0.7071. Stage 1 uses W₂ (= ±1), stage 2 uses W₄⁰ = 1 and W₄¹ = −j, stage 3 uses W₈⁰ … W₈³.

x(n) = {1, 1, 2, 0, 1, 2, 0, 1}

Result:

X(0) = 8
X(1) = −j0.5858
X(2) = −j2
X(3) = j3.4142
X(4) = 0
X(5) = −j3.4142
X(6) = j2
X(7) = j0.5858

Check: Σx(n) = 8 = X(0); the result equals the direct 8-point DFT.

Spectrum

Magnitude spectrum (stem plot, one # ≈ 0.5):

k=0 |################ 8.00
k=1 |# 0.59
k=2 |#### 2.00
k=3 |####### 3.41
k=4 | 0.00
k=5 |####### 3.41
k=6 |#### 2.00
k=7 |# 0.59

The magnitude is symmetric about k = 4 (|X(k)| = |X(8 − k)|) and the phase is anti-symmetric because x(n) is real.

Answer: X(k) = {8, −j0.5858, −j2, j3.4142, 0, −j3.4142, j2, j0.5858}.