How fast is FFT; X(7) by DIT-FFT

How fast is the FFT

An N-point DFT by definition needs N² complex multiplications and N(N − 1) additions. The radix-2 FFT needs (N/2) log₂N multiplications and N log₂N additions. For N = 8:

Speed-up is 64/12 ≈ 5.3 for N = 8, and it grows with N (about 200 for N = 1024).

Butterfly diagram (8-point DIT)

The input is taken in bit-reversed order: x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7). There are log₂8 = 3 stages. Each butterfly computes A + W·B and A − W·B.

Basic DIT butterfly (A, B are the two inputs, W the twiddle factor):

 A ───────────────(+)────────► A + W·B
              ╲   ╱
               ╲ ╱
                ╳
               ╱ ╲
              ╱   ╲
 B ──[× W]────────(−)────────► A − W·B

Per stage (bit-reversed order in, natural order out):

• Stage 1: butterflies on pairs (x0,x4), (x2,x6), (x1,x5), (x3,x7) with W₈⁰.
• Stage 2: butterflies on spacing 2 with twiddles W₈⁰ and W₈².
• Stage 3: butterflies on spacing 4 with twiddles W₈⁰, W₈¹, W₈², W₈³.

(Twiddle factors: W₈⁰ = 1, W₈¹ = 0.7071 − j0.7071, W₈² = −j, W₈³ = −0.7071 − j0.7071. In stage 3, X(k) = G(k) + W₈ᵏ H(k), X(k+4) = G(k) − W₈ᵏ H(k), where G is the DFT of the even-indexed samples and H of the odd-indexed.)

Computing X(7) for x(n) = {1, 0, 0, 0, 0, 0, 0, 0}

Bit-reversed input: {1, 0, 0, 0, 0, 0, 0, 0} (x(0) = 1 stays first).

• Stage 1 (pairs): (1, 0) → 1 + 0 = 1, 1 − 0 = 1; all other pairs give 0. Output: {1, 1, 0, 0, 0, 0, 0, 0}.
• Stage 2: the first 4 values (1, 1, 0, 0) → G(0) = 1 + 0 = 1, G(1) = 1 + W₈² · 0 = 1, G(2) = 1 − 0 = 1, G(3) = 1 − W₈² · 0 = 1. The second group (all zeros) gives H(k) = 0.
• Stage 3: X(7) = X(3 + 4) = G(3) − W₈³ H(3) = 1 − W₈³ · 0 = 1.

Check: x(n) = δ(n), so X(k) = Σ x(n)W₈^(kn) = x(0) = 1 for every k.

Answer: X(7) = 1 (indeed X(k) = 1 for k = 0 … 7).