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

Only seven values are printed for an 8-point DFT, so I read the sequence as x(n) = {1, 1, 0, 1, 0, 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, 1, 0, 1, 2, 0}

Result:

X(0) = 6
X(1) = 0.2929 + j1.2929
X(2) = −1 − j1
X(3) = 1.7071 − j2.7071
X(4) = 0
X(5) = 1.7071 + j2.7071
X(6) = −1 + j1
X(7) = 0.2929 − j1.2929

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

Answer: X(k) = {6, 0.2929 + j1.2929, −1 − j1, 1.7071 − j2.7071, 0, 1.7071 + j2.7071, −1 + j1, 0.2929 − j1.2929}.