FFT of {1,1,2,4,3,1,2,1} by DIT-FFT

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, 4, 3, 1, 2, 1}

Result:

X(0) = 15
X(1) = −4.1213 − j2.1213
X(2) = j3
X(3) = 0.1213 − j2.1213
X(4) = 1
X(5) = 0.1213 + j2.1213
X(6) = −j3
X(7) = −4.1213 + j2.1213

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

Answer: X(k) = {15, −4.1213 − j2.1213, j3, 0.1213 − j2.1213, 1, 0.1213 + j2.1213, −j3, −4.1213 + j2.1213}.