DFT Basics

The Discrete Fourier Transform (DFT) is the computational tool that bridges theoretical frequency analysis and practical digital signal processing. It takes a finite-length discrete sequence and produces a finite set of frequency-domain samples, making it the only Fourier-type transform that is directly implementable on digital hardware.

For GATE and university exams, DFT problems are extremely common. Questions test DFT computation, identification of frequency bins, interpretation of DFT output, and properties like circular shift and symmetry. A strong grip on DFT basics makes all higher topics like FFT and circular convolution straightforward.

Core Concept Explanation

The DFT converts a finite sequence of N samples into exactly N complex-valued frequency-domain coefficients called frequency bins. Each bin X[k] represents the amplitude and phase of a specific sinusoidal component in the original signal. The k=0 bin is called the DC component and represents the average value of the signal. The k=N/2 bin corresponds to the Nyquist frequency.

The DFT is actually a sampled version of the DTFT. If you evaluate the DTFT X(e^jw) at N equally spaced points w = 2pi*k/N for k = 0 to N-1, you get exactly the N-point DFT. This means the DFT does not reveal everything about the frequency content of a signal; it gives only N samples of the continuous DTFT spectrum. Increasing N gives better frequency resolution.

The key building block of DFT is the twiddle factor W_N = e^{-j2pi/N}. The factor W_N^{nk} is a complex exponential at frequency 2pi*k/N evaluated at time index n. The DFT formula computes X[k] by multiplying each time sample x[n] by the corresponding twiddle factor and summing all N products.

The DFT is periodic in both time and frequency. Even though the input x[n] is defined only for n = 0 to N-1, the DFT implicitly treats it as periodic with period N. Similarly X[k] is periodic with period N. This periodicity assumption underlies why circular convolution appears when multiplying DFTs, not linear convolution.

Mathematical Expression

The N-point DFT of a sequence x[n] for n = 0, 1, ..., N-1 is defined as X[k] = sum_{n=0}^{N-1} x[n] W_N^{nk} where W_N = e^{-j2pi/N} is the twiddle factor. The result X[k] is a complex number whose magnitude |X[k]| gives the amplitude of frequency component k and whose angle gives the phase.

The Inverse DFT (IDFT) is: x[n] = (1/N) sum_{k=0}^{N-1} X[k] W_N^{-nk}. The only differences from the forward DFT are the sign of the exponent (positive instead of negative) and the 1/N normalization factor. Some textbooks distribute this factor as 1/sqrt(N) in both directions.

The frequency resolution of the DFT is delta_f = Fs/N, where Fs is the sampling frequency in Hz. To distinguish two frequencies separated by delta_f Hz, you need at least N = Fs/delta_f points in your DFT. Increasing N by zero-padding improves apparent resolution by interpolating the DTFT, but does not add real new frequency information.

Practical Understanding

In a spectrum analyzer or audio processing application, you capture N samples, compute the N-point DFT, and look at |X[k]| to identify strong frequency components. The bin with the largest magnitude tells you the dominant frequency in the signal. This is directly used in applications like pitch detection, motor fault diagnosis, and communication channel estimation.

Direct DFT computation requires N^2 complex multiplications and additions. For N = 1024, that is over one million operations. The Fast Fourier Transform (FFT) reduces this to N*log2(N) operations, which for N = 1024 is only about 10,000. This computational saving is what made real-time DSP possible in practice.

Given:
Sequence x[n] = {1, 0, -1, 0}  for n = 0, 1, 2, 3
N = 4 point DFT
Find X[0], X[1], X[2], X[3]

Why this formula applies:
X[k] = sum_{n=0}^{3} x[n] W_4^(nk),  W_4 = e^(-j2pi/4) = e^(-jpi/2) = -j

Formula:
X[k] = x[0]*W4^0 + x[1]*W4^k + x[2]*W4^2k + x[3]*W4^3k

Twiddle factor powers:
W4^0 = 1
W4^1 = -j
W4^2 = -1
W4^3 = j
W4^4 = 1  (periodic)

Substitution:
X[0] = 1(1) + 0(1) + (-1)(1) + 0(1) = 1 + 0 - 1 + 0 = 0
X[1] = 1(1) + 0(-j) + (-1)(-1) + 0(j) = 1 + 0 + 1 + 0 = 2
X[2] = 1(1) + 0(-1) + (-1)(1) + 0(-1) = 1 + 0 - 1 + 0 = 0
X[3] = 1(1) + 0(j) + (-1)(-1) + 0(-j) = 1 + 0 + 1 + 0 = 2

Final Answer:
X[0]=0, X[1]=2, X[2]=0, X[3]=2
The signal has energy only at bins k=1 and k=3 (fundamental and its mirror).

Exam Tip: For GATE, always compute W_N powers first as a table before substituting. W_4 cycle is {1, -j, -1, j} and W_8 cycle has 8 values. Memorizing the 4-point and 8-point twiddle cycles saves critical time.

Quick Revision

• DFT formula: X[k] = sum_{n=0}^{N-1} x[n] W_N^{nk}, where W_N = e^{-j2pi/N}. Both input and output are length N.
• IDFT: x[n] = (1/N) sum_{k=0}^{N-1} X[k] W_N^{-nk}. Only differences from DFT are sign of exponent and 1/N factor.
• X[0] = sum of all x[n]. This is the DC value and equals N times the average of the sequence.
• Frequency resolution = Fs/N. Better resolution requires larger N or longer observation window.
• Direct DFT costs O(N^2). FFT costs O(N log2 N). For N=1024, FFT is 100 times faster.
• DFT assumes periodic extension of x[n]. This is why multiplying DFTs gives circular convolution, not linear convolution.
• Exam trap: Do not confuse bin index k with analog frequency. Always use f_k = k*Fs/N to convert bin index to Hz.