8-point DFT by FFT of {1,−1,2,2,1,1,2,2}

The question does not name the algorithm, so DIT-FFT is used.

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, and stage 3 uses W₈⁰ … W₈³.

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

Result:

X(0) = 10
X(1) = −1.4142 + j1.4142
X(2) = −2 + j4
X(3) = 1.4142 + j1.4142
X(4) = 2
X(5) = 1.4142 − j1.4142
X(6) = −2 − j4
X(7) = −1.4142 − j1.4142

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

Answer: X(k) = {10, −1.4142 + j1.4142, −2 + j4, 1.4142 + j1.4142, 2, 1.4142 − j1.4142, −2 − j4, −1.4142 − j1.4142}.