Sampling, DFT and FFT · Definition

Discrete Fourier transform

signal processingsampling, dft and fft

Before you start you need to know

The DFT is obtained from the continuous Fourier transform by sampling the spectrum of a finite sequence at N equally spaced points. It is the central tool of digital signal processing for spectral analysis and filtering.

Definition

The discrete Fourier transform (DFT) maps a finite sequence of N complex values \(x[n]\) to N values \(X[k]\) representing its components at the frequencies \(2\pi k/N\).

\[X[k]=\sum_{n=0}^{N-1}x[n]\,e^{-j2\pi kn/N}\]

The DFT is linear and periodic with period N, so \(X[k+N]=X[k]\). Its inverse, the IDFT, recovers the sequence through \(x[n]=\frac{1}{N}\sum_{k=0}^{N-1}X[k]\,e^{j2\pi kn/N}\), and Parseval's theorem relates the energy in both domains. The N-th roots of unity \(W_N=e^{-j2\pi/N}\) are the coefficients appearing in each term of the sum.

Consider \(x[n]=\{1,2,0,1\}\) with N=4. Since \(W_4=-j\), we have \(W_4^2=-1\) and \(W_4^3=j\), so \(X[0]=4\), \(X[1]=1-j\), \(X[2]=-2\) and \(X[3]=1+j\), which can be verified with the IDFT.

A typical mistake is confusing the DFT with the continuous transform and forgetting that the DFT implies periodicity: when computing a linear convolution via the DFT without zero-padding, circular convolution appears and the values at the edges are wrong. To avoid this, enough zeros must be appended before multiplying spectra.

Think about it

Why does the DFT have only N distinct values even if indices k outside 0 to N-1 are evaluated?

Because \(W_N^{k+N}=W_N^k\), so \(X[k+N]=X[k]\) and only N independent values are needed.

Exercises 10

  1. How many complex values does the DFT of a sequence of length N produce?
  2. What is the period of the sequence \(X[k]\) of an N-point DFT?
  3. Which expression defines the factor \(W_N\) used in the DFT?
  4. What is the transformation called that recovers the original sequence from its values \(X[k]\)?
  5. Which DFT property states that the transform of a sum of sequences is the sum of their transforms?
  6. Compute \(X[0]\) for the sequence \(x[n]=\{2,1,3\}\) of length N=3.
  7. For N=4, what is \(W_4^2\)?
  8. What is the relation between \(X[0]\) and the mean of the values of \(x[n]\) in an N-point DFT?
  9. For N=4, what is \(W_4^3\)?
  10. Let \(x[n]=\{1,2,1,0\}\) with N=4. What is \(X[2]\)?

References

  • Alan V. Oppenheim, Alan S. Willsky, Signals and Systems, 2nd edition, Pearson, 1996.
  • Alan V. Oppenheim, Ronald W. Schafer, Discrete-Time Signal Processing, 3rd edition, Pearson, 2010.