8-point DIT-FFT of {1,1,0,0,1,1,2}

Only seven values are printed for an 8-point DFT, so I read the sequence as x(n) = {1, 1, 0, 0, 1, 1, 2} followed by x(7) = 0 (zero-padded to 8 points).

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

Result:

X(0) = 6
X(1) = j2
X(2) = −j2
X(3) = −j2
X(4) = 2
X(5) = j2
X(6) = j2
X(7) = −j2

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

Answer: X(k) = {6, j2, −j2, −j2, 2, j2, j2, −j2}.