Question

In FFT computation, reducing complexity from $O(N^2)$ to $O(N \log_2 N)$ relies fundamentally on _______.

• A. periodicity of time-domain signal
• B. symmetry and periodicity of twiddle factors
• C. linearity of DFT
• D. convolution theorem

Hint:

The computational savings of the FFT rely on the twiddle factor $W_N^{kn}$: - Symmetry: $W_N^{k + N/2} = -W_N^k$ - Periodicity: $W_N^{k + N} = W_N^k$ Without these two properties, the reduction from $O(N^2)$ to $O(N\log N)$ would not be possible.

Answer 1

The Correct Option is B

Concept: The standard Discrete Fourier Transform (DFT) of an $N$-point sequence requires $N^2$ complex multiplications. Fast Fourier Transform (FFT) algorithms (such as Cooley-Tukey decimation-in-time or decimation-in-frequency) break down large transformations into smaller ones by exploiting the mathematical properties of the complex exponential phase multiplier, or twiddle factor: \[ W_N^{kn} = e^{-j\frac{2\pi}{N}kn} \]

Step 1: The Periodicity Property of the Twiddle Factor.
The twiddle factor repeats its values cyclically over a range of $N$ units. Mathematically: \[ W_N^{k + N} = e^{-j\frac{2\pi}{N}(k+N)} = e^{-j\frac{2\pi}{N}k} \cdot e^{-j2\pi} \] Since $e^{-j2\pi} = 1$, we find: \[ W_N^{k + N} = W_N^k \]

Step 2: The Symmetry Property of the Twiddle Factor.
The twiddle factor exhibits a half-period phase inversion property, meaning: \[ W_N^{k + \frac{N}{2}} = e^{-j\frac{2\pi}{N}(k + \frac{N}{2})} = e^{-j\frac{2\pi}{N}k} \cdot e^{-j\pi} \] Since $e^{-j\pi} = -1$, we obtain: \[ W_N^{k + \frac{N}{2}} = -W_N^k \]

Step 3: Impact on Computational Redundancy.
By applying these properties, the algorithm avoids redundant calculations of identical phase vectors across different stages. This enables the decomposition of an $N$-point DFT into progressively smaller sub-DFTs, reducing the total complex multiplication steps from $N^2$ down to $\frac{N}{2}\log_2 N$, or an overall complexity order of $O(N \log_2 N)$.