DFT and FFT Interview Questions

Q1. What is the DFT and what does it compute?

The DFT (Discrete Fourier Transform) converts an N-point discrete time-domain sequence into N complex frequency-domain coefficients, where each coefficient represents the amplitude and phase of a specific frequency component. For a 1024-point DFT of an audio signal sampled at 44.1 kHz, bin k represents frequency k × 44100/1024 ≈ 43.07 Hz, giving frequency resolution of about 43 Hz. The DFT assumes the input signal is periodic with period N, which is why applying it to a non-periodic signal without windowing causes spectral leakage at the endpoints.

Follow-up: What is the computational complexity of a direct DFT computation?

Q2. What is the FFT and how does it differ from the DFT in terms of computation?

The FFT (Fast Fourier Transform) is an algorithm that computes the exact DFT result using O(N log₂N) multiplications instead of the O(N²) operations required by direct DFT computation. For N=1024, direct DFT requires about 1,048,576 complex multiplications while radix-2 FFT needs only 5,120 — a 200x speedup. The FFT produces identical results to the DFT; it is purely a computational optimization exploiting the periodicity and symmetry of the DFT twiddle factors.

Follow-up: What are twiddle factors in the FFT?

Q3. What is the radix-2 Cooley-Tukey FFT algorithm?

The Cooley-Tukey radix-2 FFT recursively splits an N-point DFT into two N/2-point DFTs of the even and odd indexed samples, combining them with a butterfly operation scaled by twiddle factors W_N^k = e^(-j2πk/N). An 8-point radix-2 FFT requires 3 stages (log₂8) each with 4 butterflies, totalling 12 complex multiplications versus 64 for direct DFT. The constraint is that N must be a power of 2; for arbitrary N, mixed-radix FFT (Bluestein, Rader, or Prime-Factor algorithms) are used, though these are more complex to implement in fixed-point DSP.

Follow-up: What is a butterfly operation in the FFT?

Q4. What is spectral leakage in DFT and how do you reduce it?

Spectral leakage occurs when the signal frequency is not an integer multiple of the DFT frequency resolution (not exactly at a bin), causing the energy to spread across many bins instead of concentrating in one. A 1 kHz sine wave sampled at 8 kHz for 1024 points has bin spacing of 7.8125 Hz; if the signal is 1001 Hz it is between bins and leaks into adjacent bins, hiding nearby weaker signals. Applying a window function like Hanning or Blackman before the DFT tapers the signal to zero at both endpoints, reducing leakage at the cost of slightly wider main lobe (reduced frequency resolution).

Follow-up: What is the trade-off between main lobe width and side lobe level in window functions?

Q5. What are twiddle factors and why are they precomputed?

Twiddle factors are the complex exponentials W_N^k = e^(-j2πk/N) used in each butterfly stage of the FFT to rotate phasors in the frequency domain. For an N=1024 FFT, there are N/2=512 unique twiddle factors; precomputing them as a table of 512 complex float pairs at initialization takes 4 KB but avoids evaluating sin() and cos() at each butterfly, which is critical on a TMS320C6748 where trigonometric functions cost 20–50 cycles each while a table lookup costs 1–2 cycles. In fixed-point DSP implementations, twiddle factors are stored as Q15 integers to fit in a 16-bit data bus without floating-point hardware.

Follow-up: How many unique twiddle factors are needed for a 1024-point FFT?

Q6. What is the relationship between DFT bin spacing and time record length?

Frequency resolution (bin spacing) equals the sampling frequency divided by the number of DFT points: Δf = fs/N. To achieve 1 Hz frequency resolution with a 44.1 kHz sample rate, you need N = 44100 points, which corresponds to a 1-second time record. In a real-time FFT spectrum analyzer like those in audio analyzers or vibration monitoring systems, increasing frequency resolution always comes at the cost of increased measurement time — there is no way to get both fine frequency resolution and short measurement time simultaneously.

Follow-up: What is the uncertainty principle in digital signal processing?

Q7. What is zero-padding in FFT and does it improve frequency resolution?

Zero-padding appends zeros to the input sequence before taking the FFT, increasing N and producing more closely spaced frequency bins, but it does not improve true frequency resolution because no new information is added. A 256-point FFT of a signal zero-padded to 1024 points produces 1024 bins but the frequency resolution (ability to distinguish two close tones) remains that of 256 points — it only interpolates between the original 256 bins. Zero-padding is useful for picket fence effect reduction (finding the amplitude of a tone between bins more accurately) and for making N a power of 2 for radix-2 FFT algorithms.

Follow-up: What is the picket fence effect in DFT?

Q8. How is the inverse DFT (IDFT) related to the DFT and how is it implemented efficiently?

The IDFT is computed as x[n] = (1/N) Σ X[k] e^(+j2πkn/N), which differs from the DFT only in the sign of the exponent and the 1/N scaling factor. The FFT algorithm is directly reused for IDFT by conjugating the input spectrum, computing the forward FFT, conjugating the output, and dividing by N — avoiding a separate IDFT implementation entirely. On the TMS320C674x DSP, the DSPF_sp_ifftSPxSP library function uses exactly this conjugate-FFT-conjugate trick to perform IFFT at the same speed as the forward FFT.

Follow-up: What is the Parseval's theorem and how does it relate DFT to energy conservation?

Q9. What is aliasing in the context of DFT and how does sampling rate affect it?

Aliasing in DFT occurs when the input signal contains frequency components above fs/2 (Nyquist frequency), which fold back and appear as false lower-frequency components in the computed spectrum. A 3 kHz tone sampled at 8 kHz produces a DFT with the tone appearing correctly at bin 3000 × 1024/8000 ≈ 384, but a 7 kHz tone (above Nyquist) aliases to 8000-7000=1000 Hz and appears at bin 128, indistinguishable from a real 1 kHz tone. Anti-aliasing filters (lowpass filters at fs/2) before the ADC are essential in any DFT-based measurement system — spectrum analyzers, vibration monitors, and audio codecs all include them.

Follow-up: What type of filter is an anti-aliasing filter and why must it be analog?

Q10. What is the DFT symmetry property for real-valued signals?

For a real-valued input signal x[n], the DFT output X[k] is conjugate symmetric: X[N-k] = X*[k], meaning the second half of the spectrum is the complex conjugate mirror of the first half. This means only N/2+1 unique complex coefficients exist for a real N-point DFT, which is exploited by rfft algorithms — CMSIS-DSP's arm_rfft_fast_f32() computes an N-point real FFT using an N/2-point complex FFT, halving both computation and memory requirements. Forgetting this symmetry and using a full complex FFT on real data wastes half the computation on redundant conjugate bins.

Follow-up: How does the RFFT algorithm pack the N/2+1 complex outputs into N real values?

Q11. What is windowing and why must the window be applied before the FFT, not after?

Windowing multiplies the time-domain signal by a tapering window function (Hanning, Hamming, Blackman, Kaiser) to reduce the spectral leakage caused by DFT's implicit rectangular window at the block boundaries. The window must be applied in the time domain before the FFT because multiplying in time is equivalent to convolving in frequency — applying it after would require convolving the already-computed spectrum which is more expensive and produces the same result. In a CMSIS-DSP audio FFT implementation, the Hanning window coefficients are precomputed and applied to the 1024-point audio buffer with arm_mult_f32() before calling arm_rfft_fast_f32().

Follow-up: What is a flat-top window and when is it preferred over a Hanning window?

Q12. How do you interpret the magnitude and phase of DFT output bins?

The magnitude of DFT bin k is |X[k]| = sqrt(Re(X[k])² + Im(X[k])²), representing the amplitude of the sinusoidal component at frequency k×fs/N, and the phase is angle(X[k]) = atan2(Im, Re), representing the phase offset of that component relative to a cosine. For an audio signal with a 440 Hz A-note sampled at 44.1 kHz with N=4096, the tone appears at bin k=440×4096/44100≈40.85 — the energy splits between bins 40 and 41. Calibrating a spectrum analyzer requires dividing the raw magnitude by N/2 (for real signals) to get the actual signal amplitude in volts, a step beginners commonly miss.

Follow-up: What is the difference between a power spectrum and a magnitude spectrum?

Q13. What is the DFT of a delta function and why is it significant?

The DFT of an impulse δ[n] (value 1 at n=0, zero elsewhere) is a flat spectrum with all N bins equal to 1+j0, meaning the impulse contains all frequencies at equal amplitude — this is the basis of impulse response testing. In an acoustic echo measurement, playing a click (approximating an impulse) through a speaker and recording the room response, then taking the FFT of the recording gives the room's frequency response directly without requiring a swept sine measurement. The flat spectrum of a true impulse is why white noise (spectrally flat random signal) is used as a practical substitute for impulse testing when a true impulse has insufficient energy.

Follow-up: What is the DFT of a pure cosine and what bins does energy appear in?

Q14. How is the DFT used in practical OFDM communication systems?

In OFDM (Orthogonal Frequency Division Multiplexing) used in LTE and 5G NR, the IFFT converts frequency-domain data symbols on multiple subcarriers into a time-domain waveform for transmission, and the FFT at the receiver demodulates all subcarriers simultaneously. A 5G NR numerology 1 OFDM symbol with 4096-point FFT at 61.44 MHz sampling rate carries up to 3276 active subcarriers spaced 30 kHz apart, processing the entire wideband spectrum in one FFT operation. The FFT's property that orthogonal subcarriers do not interfere with each other after OFDM demodulation (when CP is longer than the channel delay spread) is the mathematical foundation that makes 5G spectral efficiency possible.

Follow-up: What is the role of the cyclic prefix in OFDM and how does it relate to DFT properties?

Q15. What is overlap-add or overlap-save and why are they used for FFT-based filtering?

Overlap-add and overlap-save are block-processing methods that use FFT-based fast convolution (multiplication in frequency domain = convolution in time domain) to filter long signals with an FIR filter without the boundary artifacts of direct block convolution. For filtering a continuous audio stream with a 512-tap FIR filter, using a 1024-point FFT with 512-sample input blocks and overlap-add processing reduces the convolution cost from 512 multiplications per sample to roughly 5 multiplications per sample equivalent. These methods are used in professional audio plug-ins, software-defined radios, and DSP-based equalizers where the filter length is long enough that FFT-based convolution outperforms direct computation.

Follow-up: At what FIR filter length does FFT-based convolution become faster than direct convolution?