Fast Fourier Transforms: Algorithms, Structure, and Applications

All flashcards

What is a fast Fourier transform (FFT)?

An algorithm that efficiently computes the DFT or its inverse; it reorganizes the computation rather than defining a different transform.

What is the direct DFT operation count?

It is $O(n^2)$ because each of $n$ outputs sums $n$ terms.

How does Cooley–Tukey reduce a DFT?

It recursively breaks a larger DFT into smaller DFTs and combines their results using twiddle factors.

How does the Rader algorithm handle a prime-sized DFT?

It expresses the DFT as a cyclic convolution of size $n-1$.

What does the short-time Fourier transform provide?

It analyzes shorter, overlapping signal windows to retain some time localization.

Quiz questions

1. In the DFT formula $X_k=\sum_{m=0}^{n-1}x_m e^{-i2\pi km/n}$, what does $m$ index?Answer: An input sample in the finite sequence.
2. What is the role of $e^{i2\pi/n}$ in an $n$-point DFT?Answer: It is a primitive $n$th root of unity.
3. When is a radix-2 FFT especially convenient?Answer: When the transform length is a power of two.
4. How does the Good–Thomas prime-factor algorithm use coprime transform sizes?Answer: It uses the Chinese remainder theorem and avoids the usual twiddle factors.
5. What does the Bluestein algorithm do for a prime-sized DFT?Answer: It rewrites the DFT as a convolution of the same size.