Questions: Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) Algorithms

Question 1

You compute a 1024-point DFT of a real-valued audio signal. The output array X[k] has 1024 complex values. How many of these values carry unique frequency information?

• A. 1024 — every output bin represents a distinct frequency
• B. 512 — because the spectrum is conjugate symmetric for real inputs, the second half mirrors the first
• C. 513 — bins 0 through 512 inclusive (DC, positive frequencies, and the Nyquist bin)
• D. 256 — only the bins below the Nyquist frequency divided by two are unique

Answer: (C)

For a real-valued input, the DFT satisfies X[N−k] = X[k]*, so X[513] mirrors X[511], X[514] mirrors X[510], and so on. The unique bins are X[0] (DC), X[1] through X[511] (positive frequencies), and X[512] (the Nyquist frequency) — 513 values. Software that plots 'single-sided' spectra is discarding the redundant second half. Understanding conjugate symmetry is essential for correctly interpreting spectral output.

Question 2

The Cooley-Tukey FFT achieves O(N log N) complexity by exploiting which property of the DFT computation?

• A. It uses floating-point approximations instead of exact arithmetic, trading precision for speed
• B. It computes the inverse DFT instead of the forward DFT, which is mathematically simpler
• C. The twiddle factors W^(kn) are periodic and repeat, so many identical multiplications can be shared rather than recomputed
• D. It only computes the real part of the output, discarding imaginary components to halve the work

Answer: (C)

The FFT computes exactly the same result as the DFT — no approximation. The speedup comes from the algebraic structure of the twiddle factor W = e^(−j2π/N). Since W^(kn) has period N in both k and n, the N² complex multiplications in the naive DFT contain enormous redundancy. The Cooley-Tukey algorithm recursively splits the N-point DFT into two N/2-point DFTs (even and odd indexed), each of which splits further, until reaching trivial 1-point DFTs. At each level, 'butterfly' operations combine results, reusing twiddle factors shared across multiple outputs.

Question 3

The FFT computes an approximation of the DFT that is close enough for practical engineering applications.

• T. True
• F. False

Answer: False

The FFT computes the exact DFT — not an approximation. The Cooley-Tukey FFT is a mathematically exact algorithm that produces the same result as directly evaluating X[k] = Σ x[n]·W^(kn) for every k. The only difference is the order of operations: by exploiting algebraic symmetry, the same result is reached in O(N log N) operations rather than O(N²). Floating-point rounding errors exist in both methods equally; the FFT introduces no additional approximation error.

Question 4

X[0] in a DFT output represents the DC component — the sum (and therefore the average, up to scaling) of all input samples.

• T. True
• F. False

Answer: True

At k=0, the DFT formula reduces to X[0] = Σ x[n]·e^0 = Σ x[n] — the sum of all N input samples. Dividing by N gives the sample mean. This is why X[0] is called the DC component: in signal processing, 'DC' refers to the zero-frequency (constant) component of a signal, which corresponds to its average value. A signal with zero mean has X[0] = 0; a signal shifted upward by a constant has a large positive X[0].

Question 5

Why does the FFT reduce the number of operations from O(N²) to O(N log N), and what specific property of the DFT makes this possible?

Model answer: The DFT formula computes each of N outputs as a sum of N products, requiring N² operations naively. The FFT exploits the fact that the twiddle factor W^(kn) = e^(−j2πkn/N) is periodic with period N in both k and n, so many of the N² multiplications produce identical twiddle factors. The Cooley-Tukey algorithm recursively splits an N-point DFT into two N/2-point DFTs (for even- and odd-indexed inputs), reducing to 1-point DFTs after log₂(N) levels. At each level, O(N) butterfly operations combine the sub-results. The total work is O(N) per level times O(log N) levels = O(N log N).

The key is recognizing that the DFT matrix has deep structure — it is not a generic N×N matrix requiring N² multiplications but a highly structured matrix built from roots of unity. The FFT algorithm does not skip any computation; it reorganizes it to share intermediate results. This structural insight, formalized by Cooley and Tukey in 1965 (though discovered earlier by Gauss), is one of the most practically impactful algorithmic discoveries in history.