---
title: "How fast is FFT; X(7) by DIT-FFT"
subject: "Digital Signal Analysis and Processing"
chapter: 7
key: "semester_7/digital_signal_analysis_and_processing:fft-speed-x7"
source: https://www.bctengineer.com/q/semester_7/digital_signal_analysis_and_processing/fft-speed-x7
site: BCT Engineering
---

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

Digital Signal Analysis and Processing · Chapter 7: Discrete Fourier Transform

- Asked in: 2071 Chaitra, 2+6 marks; 2070 Asar, 2+6 marks (asked 2 times)
- Video: [DIT FFT algorithm | Butterfly diagram | Digital signal processing](https://www.youtube.com/watch?v=RioJKiSBlyg) — Smart Engineer
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/digital_signal_analysis_and_processing/fft-speed-x7
- Whole chapter: https://www.bctengineer.com/md/semester_7/digital_signal_analysis_and_processing/chapter-7

## Question

How fast is FFT? Draw the butterfly diagram and compute the value of X(7) using 8-point DIT-FFT for the sequence x(n) = {1, 0, 0, 0, 0, 0, 0, 0}.

## Short answer

For N=8, direct DFT needs 64 multiplications and FFT needs 12 (speed-up ~5.3×). Using 8-point DIT-FFT with bit-reversed input {1,0,0,0,0,0,0,0}, all butterflies yield unity, so X(7)=1.

## Answer

#### 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:

| Quantity | Direct DFT | FFT |
|---|---|---|
| Complex multiplications | 64 | 12 |
| Complex additions | 56 | 24 |

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):

```text
 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).**

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. For N = 8, how many complex multiplications does the radix-2 FFT need?
   A. 64
   B. 12
   C. 24
   D. 8
   Answer: B. (8/2) log2 8 = 12, vs 64 for the direct DFT. (Key point: Complexity table)

2. In 8-point DIT-FFT, in what order is the input arranged?
   A. Natural
   B. Reverse natural
   C. Bit-reversed
   D. Random
   Answer: C. The output is then in natural order. (Key point: Input order)

3. How many stages are there?
   A. 2
   B. 4
   C. 8
   D. 3
   Answer: D. log2 8 = 3. (Key point: Number of stages)

4. What is X(7) for x(n) = delta(n)?
   A. 1
   B. 0
   C. -1
   D. j
   Answer: A. The DFT of a unit impulse is 1 for all k. (Key point: X(7) result)

## Related in Digital Signal Analysis and Processing

- [DIF-FFT butterfly; compute X(2) and X(1)](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Adifft-x2-x1-only) — Digital Signal Analysis and Processing, chapter 7
- [8-point DIT-FFT of {1,1,0,1,0,1,2}](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Aditfft-8pt-72k) — Digital Signal Analysis and Processing, chapter 7, asked 3×
- [8-point DIT-FFT of {1,1,0,0,1,1,2}](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Aditfft-8pt-70c) — Digital Signal Analysis and Processing, chapter 7, asked 3×
- [DIT-FFT of {1,1,2,0,1,2,0,1} and spectrum](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Adit-fft-spectrum-71s) — Digital Signal Analysis and Processing, chapter 7
- [8-point DIF-FFT of {1/2,1/2,1/2,1/2,0,0,0,0}](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Adif-fft-half-ones) — Digital Signal Analysis and Processing, chapter 7
- [FFT of {1,1,2,4,3,1,2,1} by DIT-FFT](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Adit-fft-72c) — Digital Signal Analysis and Processing, chapter 7

## Related in other subjects

- [Discrete and Fast Fourier Transform](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Adft-fft-brief) — Computational Techniques in Civil Engineering, chapter 2
- [Money transfer sequence diagram questions](https://www.bctengineer.com/question.md?key=semester_6%2Fobject_oriented_analysis_and_design%3Amoney-transfer-sequence-diagram) — Object Oriented Analysis and Design, chapter 2
- [Short note: Sequence diagram](https://www.bctengineer.com/question.md?key=semester_6%2Fobject_oriented_analysis_and_design%3Ashort-note-sequence-diagram) — Object Oriented Analysis and Design, chapter 2
- [Food ordering system sequence diagram](https://www.bctengineer.com/question.md?key=semester_6%2Fobject_oriented_analysis_and_design%3Afood-ordering-system-sequence-diagram) — Object Oriented Analysis and Design, chapter 2