Question

What is the value of the variance of quantization error in FFT algorithm, compared to that of direct computation?

(a) Greater

(b) Less

(c) Equal

(d) Cannot be compared

The question was asked during an internship interview.

My question is taken from Quantization Effects in the Computation of DFT topic in chapter DFT Efficient Computation – Fast Fourier Transform Algorithms of Digital Signal Processing

Answer 1

Correct choice is (c) Equal

To elaborate: If we assume that the quantization errors in each butterfly are uncorrelated with the errors in the other butterflies, then there are 4(N-1) errors that affect the output of each point of the FFT. Consequently, the variance of the quantization error due to FFT algorithm is given by

4(N-1)(Δ^2/12)=N(Δ^2/3)(approximately)

Thus, the variance of quantization error due to FFT algorithm is equal to the variance of the quantization error due to direct computation.