8.1 DFT Definition and Properties

The Discrete Fourier Transform (DFT) is a powerful tool for analyzing signals in the frequency domain. It converts a sequence of samples into a set of complex coefficients, revealing the frequency content of the original signal.

DFT has key properties like linearity, periodicity, and symmetry. These properties make it useful for various signal processing tasks, including convolution and spectral analysis. Understanding DFT is crucial for grasping more advanced concepts in digital signal processing.

Discrete Fourier Transform

Definition and Formulas

• The Discrete Fourier Transform (DFT) converts a finite sequence of equally-spaced samples of a function into a sequence of coefficients of a finite combination of complex sinusoids
• DFT formula: $X[k] = \sum_{n=0}^{N-1} x[n] * e^{-j*2*\pi*k*n/N}$, where $x[n]$ is the input sequence, $X[k]$ is the output sequence, $N$ is the length of the input sequence, and $k$ is the frequency index
• Inverse DFT (IDFT) formula: $x[n] = \frac{1}{N} * \sum_{k=0}^{N-1} X[k] * e^{j*2*\pi*k*n/N}$, maps the sequence of coefficients $X[k]$ back to the original sequence $x[n]$

Linearity, Periodicity, and Symmetry

• DFT and IDFT are linear transformations
  • DFT of a sum of sequences equals the sum of the DFTs of each sequence
  • IDFT of a sum of sequences equals the sum of the IDFTs of each sequence
• DFT and IDFT are periodic with period $N$
  • $X[k+N] = X[k]$ and $x[n+N] = x[n]$ for all $k$ and $n$
• DFT and IDFT are symmetric
  • $X[N-k] = X^*[k]$ and $x[N-n] = x^*[n]$, where $^*$ denotes complex conjugation

DFT Properties

Linearity, Periodicity, and Symmetry

• Linearity
  • DFT of a sum of sequences equals the sum of the DFTs of each sequence
  • DFT of a scalar multiple of a sequence equals the scalar multiple of the DFT of the sequence
• Periodicity
  • DFT is periodic with period $N$, $X[k+N] = X[k]$ for all $k$
  • Consequence of the input sequence $x[n]$ being assumed periodic with period $N$
• Symmetry
  • Conjugate symmetry: $X[N-k] = X^*[k]$
  • Even symmetry: $Re\{X[k]\} = Re\{X[N-k]\}$
  • Odd symmetry: $Im\{X[k]\} = -Im\{X[N-k]\}$

Parseval's Theorem and Convolution Theorem

• Parseval's Theorem
  • DFT preserves the energy of the input sequence
  • Sum of squares of input sequence equals sum of squares of DFT coefficients, scaled by $N$
• Convolution Theorem
  • DFT of the convolution of two sequences equals the product of the DFTs of each sequence
  • IDFT of the product of two DFTs equals the convolution of the IDFTs of each sequence

DFT and Fourier Series

Relationship between DFT and Fourier Series

• DFT is a discrete approximation of the Fourier Series
  • Fourier Series represents a periodic function as a sum of complex exponentials
• Fourier Series coefficients of a periodic function $x(t)$ with period $T$: $c_k = \frac{1}{T} * \int_0^T x(t) * e^{-j*2*\pi*k*t/T} dt$, where $k$ is an integer
• DFT coefficients $X[k]$ are samples of the Fourier Series coefficients $c_k$, taken at equally-spaced frequencies $\omega_k = 2*\pi*k/N$, where $N$ is the length of the input sequence

Convergence and Periodicity

• As the length of the input sequence $N$ approaches infinity, the DFT coefficients $X[k]$ converge to the Fourier Series coefficients $c_k$
  • DFT becomes equivalent to the Fourier Series
• DFT assumes the input sequence is periodic with period $N$, analogous to the periodicity assumption of the Fourier Series

Frequency Spectrum Analysis with DFT

Computing the Frequency Spectrum

• DFT computes the frequency spectrum of a discrete-time signal
  • Frequency spectrum represents the distribution of the signal's energy across different frequencies
• Frequency spectrum $X[k]$ is obtained by computing the DFT of the input sequence $x[n]$, where $k$ represents the frequency index
• Magnitude spectrum $|X[k]|$ represents the amplitude of each frequency component
• Phase spectrum $\angle X[k]$ represents the phase shift of each frequency component

Frequency Resolution and Spectral Leakage

• Frequency resolution of the DFT: $\Delta f = f_s/N$, where $f_s$ is the sampling frequency and $N$ is the length of the input sequence
  • DFT can only resolve frequencies that are integer multiples of $\Delta f$
• DFT assumes the input sequence is periodic with period $N$
  • Can lead to spectral leakage if the input sequence is not truly periodic
  • Windowing techniques (Hann or Hamming window) can reduce spectral leakage

Fast Fourier Transform (FFT)

• FFT is an efficient algorithm for computing the DFT
  • Computational complexity of $O(N \log N)$ instead of $O(N^2)$ for the naive DFT algorithm
• FFT exploits the symmetry and periodicity properties of the DFT to reduce the number of computations required
  • Recursively divides the DFT into smaller sub-problems (divide-and-conquer approach)
• Commonly used FFT algorithms include the Cooley-Tukey algorithm and the Prime-Factor algorithm