DIF-FFT butterfly; compute X(2) and X(1)

Reading of the question

A radix-2 algorithm needs N = 2^m points, but only six values are given. So I pad with two zeros: x[n] = {1.5, −1, 1.8, 0.6, 3, 1.7, 0, 0}, N = 8.

Butterfly structure (8-point DIF)

Basic DIF butterfly (A and B are the two inputs):

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

• Stage 1 butterflies: (x0,x4) with W₈⁰, (x1,x5) with W₈¹, (x2,x6) with W₈², (x3,x7) with W₈³
• Stage 2 butterflies: positions (0,2) with W₄⁰, (1,3) with W₄¹, (4,6) with W₄⁰, (5,7) with W₄¹
• Stage 3 butterflies: positions (0,1), (2,3), (4,5), (6,7), all with W₂⁰ = 1

In equations:

• Stage 1: a(n) = x(n) + x(n + 4), b(n) = [x(n) − x(n + 4)]·W₈ⁿ, n = 0 … 3
• Stage 2: on each half, c(n) = a(n) + a(n + 2), d(n) = [a(n) − a(n + 2)]·W₄ⁿ, n = 0, 1
• Stage 3: adjacent pairs e = c + c', f = c − c'
• The output is in bit-reversed order: positions 0 … 7 hold X(0), X(4), X(2), X(6), X(1), X(5), X(3), X(7).

Stage values

Required outputs

• X(2) is at position 2 (the bit-reversal of 2 = 010 is 010): X(2) = 2.7 − j0.1
• X(1) is at position 4 (the bit-reversal of 1 = 001 is 100): X(1) = −3.8335 − j0.3151

Check: X(2) = Σ x(n)(−j)ⁿ = [x(0) − x(2) + x(4) − x(6)] − j[x(1) − x(3) + x(5) − x(7)] = (1.5 − 1.8 + 3 − 0) − j(−1 − 0.6 + 1.7 − 0) = 2.7 − j0.1, the same as above.

Answer: X(2) = 2.7 − j0.1, X(1) = −3.8335 − j0.3151 (for the 8-point zero-padded sequence).