8-point DIF-FFT of {1,1,2,2,1,1,2,1}

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

Each butterfly: A' = A + B, B' = (A − B)·W. Stage 1 pairs n and n + 4 (twiddle W₈ⁿ on the difference), stage 2 pairs n and n + 2 (W₄ⁿ), stage 3 pairs adjacent samples (W₂⁰ = 1). The outputs come out in bit-reversed order.

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

Output positions 0, 1, 2, 3, 4, 5, 6, 7 hold X(0), X(4), X(2), X(6), X(1), X(5), X(3), X(7) (bit-reversed). Rearranging:

Result:

X(0) = 11
X(1) = −0.7071 − j0.7071
X(2) = −2 + j1
X(3) = 0.7071 − j0.7071
X(4) = 1
X(5) = 0.7071 + j0.7071
X(6) = −2 − j1
X(7) = −0.7071 + j0.7071

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

Answer: X(k) = {11, −0.7071 − j0.7071, −2 + j1, 0.7071 − j0.7071, 1, 0.7071 + j0.7071, −2 − j1, −0.7071 + j0.7071}.