Summary of Digital Signal Processing: DFT and FFT

Digital Signal Processing: DFT and FFT Explained for Students

SummaryKnowledge testFlashcardsPodcastMindmap

Introduction

The Discrete Fourier Transform (DFT) is a fundamental tool in digital signal processing that converts a finite sequence of time-domain samples into a discrete set of frequency-domain coefficients. The DFT provides a sampled estimate of the signal's spectral content and is the basis for practical algorithms such as the Fast Fourier Transform (FFT).

Definition: The Discrete Fourier Transform (DFT) of a sequence $x[n]$ of length $N$ is the sequence $X[k]$ given by $$X[k] = \sum_{n=0}^{N-1} x[n],e^{-j,2\pi,\frac{k}{N},n}\quad\text{for }k=0,1,\dots,N-1.$$

Basic Concepts

Time and Frequency Domains

  • Time domain: sequence $x[n]$ sampled at sampling frequency $F_s$ (Hz).
  • Frequency domain: DFT coefficients $X[k]$ correspond to discrete frequency samples.
  • Actual frequency mapping: $f_k = \dfrac{k}{N}F_s$ for $k=0,1,\dots,N-1$.

Definition: Relative (normalized) frequency $F$ is the number of signal cycles per DFT length: $F = f,\dfrac{N}{F_s}$.

Amplitude and Phase

  • The DFT outputs complex numbers; magnitude and phase are used to interpret spectral components.
  • Convert DFT output to amplitude per original signal by dividing by $N$:

$$C[k] = \dfrac{X[k]}{N}.$$

  • Magnitude: $|C[k]| = \sqrt{\Re{C[k]}^2 + \Im{C[k]}^2}$.
  • Phase: $\arg(C[k]) = \operatorname{atan2}\left(\Im{C[k]},\Re{C[k]}\right)$, usually displayed in degrees in $(-180^{\circ},180^{\circ}]$.

Practical Details and Interpretations

Spectral Sampling and Resolution

  • DFT gives frequency samples of the underlying Discrete-Time Fourier Transform (DTFT).
  • Frequency resolution is $\Delta f = \dfrac{F_s}{N}$ (Hz). Increasing $N$ improves resolution.

Definition: Zero padding is extending the time sequence by zeros to increase the number of DFT points and provide finer sampling of the DTFT; it does not add new information but improves visual resolution.

Coherent and Incoherent Sampling

  • Coherent sampling: the signal contains an integer number of periods within the sampled segment ($F$ integer). Leads to isolated DFT peaks at exact bin indices.
  • Incoherent sampling: $F$ is not integer. The sampled segment does not contain an integer number of periods, causing spectral leakage across bins.
💡 Věděli jste?Fun fact: Spectral leakage arises because the DFT assumes the sampled segment repeats periodically; mismatched period boundaries produce discontinuities that spread energy across many frequency bins.

Leakage and Windowing

  • Leakage: energy from a pure sinusoid spreads into adjacent bins when sampling is incoherent.
  • Windowing reduces leakage by tapering the segment at the edges; common windows include Rectangular (no window), Hann, and Hamming.

Definition: A window $w[n]$ is a weighting sequence applied to $x[n]$ to form $x_w[n]=x[n]w[n]$ before computing the DFT.

  • Typical windows and formulae:
    • Hamming: $$w[n]=0.54-0.46\cos\left(\dfrac{2\pi n}{N-1}\right)\quad n=0,\dots,N-1.$$
    • Hann: $$w[n]=0.5-0.5\cos\left(\dfrac{2\pi n}{N-1}\right)\quad n=0,\dots,N-1.$$
  • Normalizing a window ensures the amplitude estimate remains correct. If $w[n]$ is applied, compute

$$\mathrm{Norm} = \sum_{n=0}^{N-1} w[n],\quad C[k]=\dfrac{\sum_{n=0}^{N-1} x[n]w[n]e^{-j2\pi\frac{k}{N}n}}{\mathrm{Norm}}.$$

Logarithmic Scale and Display Choices

  • Amplitude is often shown in decibels: $$A_{\mathrm{dB}}[k] = 20\log_{10}\left(|C[k]|\right).$$
  • For real signals the DFT is conjugate symmetric; often only the range $0\le f\le F_s/2$ is displayed.

Examples

Example 1: Coherent Sampling of a Single Tone

  • Analog tone: $s(t)=A\cos\left(2\pi f_0 t + \phi\right)$ with $A=1$, $f_0=1,$Hz, $F_s=16,$Hz, $N=32$ samples, and phase $\phi=60^{\circ}$.
  • Relative frequency $F = f_0N/F_s = 1\cdot 32/16 = 2$ (integer) so DFT bins show two symmetric peaks at $k=2$ and $k=N-2$.
  • Amplitude after correction $\approx A/2$ per complex exponential pair so compute $C[k]=X[k]/N$ to obtain amplitude.

Example 2: Incoherent Sampling and Leakage

Zaregistruj se pro celé shrnutí
FlashcardsKnowledge testSummaryPodcastMindmap
Start for free

Already have an account? Sign in

DFT Fundamentals

Klíčové pojmy: DFT definition: $X[k]=\sum_{n=0}^{N-1} x[n]e^{-j2\pi\frac{k}{N}n}$, Map bin index to frequency: $f_k=\dfrac{k}{N}F_s$, Normalize amplitudes: $C[k]=X[k]/N$ after DFT, Coherent sampling (integer relative frequency) avoids leakage, Incoherent sampling causes leakage; reduce via windows, Hann/Hamming windows trade main-lobe width vs sidelobe level, Zero padding increases frequency sampling but not true resolution, Use zero padding length $\ge N_x+N_g-1$ to avoid circular convolution, Amplitude in dB: $20\log_{10}(|C[k]|)$, FFT implements DFT in $O(N\log N)$ time

## Introduction The Discrete Fourier Transform (DFT) is a fundamental tool in digital signal processing that converts a finite sequence of time-domain samples into a discrete set of frequency-domain coefficients. The DFT provides a sampled estimate of the signal's spectral content and is the basis for practical algorithms such as the Fast Fourier Transform (FFT). > Definition: The Discrete Fourier Transform (DFT) of a sequence $x[n]$ of length $N$ is the sequence $X[k]$ given by > $$X[k] = \sum_{n=0}^{N-1} x[n]\,e^{-j\,2\pi\,\frac{k}{N}\,n}\quad\text{for }k=0,1,\dots,N-1.$$ ## Basic Concepts ### Time and Frequency Domains - Time domain: sequence $x[n]$ sampled at sampling frequency $F_s$ (Hz). - Frequency domain: DFT coefficients $X[k]$ correspond to discrete frequency samples. - Actual frequency mapping: $f_k = \dfrac{k}{N}F_s$ for $k=0,1,\dots,N-1$. > Definition: Relative (normalized) frequency $F$ is the number of signal cycles per DFT length: $F = f\,\dfrac{N}{F_s}$. ### Amplitude and Phase - The DFT outputs complex numbers; magnitude and phase are used to interpret spectral components. - Convert DFT output to amplitude per original signal by dividing by $N$: > $$C[k] = \dfrac{X[k]}{N}.$$ - Magnitude: $|C[k]| = \sqrt{\Re\{C[k]\}^2 + \Im\{C[k]\}^2}$. - Phase: $\arg(C[k]) = \operatorname{atan2}\left(\Im\{C[k]\},\Re\{C[k]\}\right)$, usually displayed in degrees in $(-180^{\circ},180^{\circ}]$. ## Practical Details and Interpretations ### Spectral Sampling and Resolution - DFT gives frequency samples of the underlying Discrete-Time Fourier Transform (DTFT). - Frequency resolution is $\Delta f = \dfrac{F_s}{N}$ (Hz). Increasing $N$ improves resolution. > Definition: Zero padding is extending the time sequence by zeros to increase the number of DFT points and provide finer sampling of the DTFT; it does not add new information but improves visual resolution. ### Coherent and Incoherent Sampling - Coherent sampling: the signal contains an integer number of periods within the sampled segment ($F$ integer). Leads to isolated DFT peaks at exact bin indices. - Incoherent sampling: $F$ is not integer. The sampled segment does not contain an integer number of periods, causing spectral leakage across bins. Fun fact: Spectral leakage arises because the DFT assumes the sampled segment repeats periodically; mismatched period boundaries produce discontinuities that spread energy across many frequency bins. ### Leakage and Windowing - Leakage: energy from a pure sinusoid spreads into adjacent bins when sampling is incoherent. - Windowing reduces leakage by tapering the segment at the edges; common windows include Rectangular (no window), Hann, and Hamming. > Definition: A window $w[n]$ is a weighting sequence applied to $x[n]$ to form $x_w[n]=x[n]w[n]$ before computing the DFT. - Typical windows and formulae: - Hamming: $$w[n]=0.54-0.46\cos\left(\dfrac{2\pi n}{N-1}\right)\quad n=0,\dots,N-1.$$ - Hann: $$w[n]=0.5-0.5\cos\left(\dfrac{2\pi n}{N-1}\right)\quad n=0,\dots,N-1.$$ - Normalizing a window ensures the amplitude estimate remains correct. If $w[n]$ is applied, compute > $$\mathrm{Norm} = \sum_{n=0}^{N-1} w[n],\quad C[k]=\dfrac{\sum_{n=0}^{N-1} x[n]w[n]e^{-j2\pi\frac{k}{N}n}}{\mathrm{Norm}}.$$ ### Logarithmic Scale and Display Choices - Amplitude is often shown in decibels: $$A_{\mathrm{dB}}[k] = 20\log_{10}\left(|C[k]|\right).$$ - For real signals the DFT is conjugate symmetric; often only the range $0\le f\le F_s/2$ is displayed. ## Examples ### Example 1: Coherent Sampling of a Single Tone - Analog tone: $s(t)=A\cos\left(2\pi f_0 t + \phi\right)$ with $A=1$, $f_0=1\,$Hz, $F_s=16\,$Hz, $N=32$ samples, and phase $\phi=60^{\circ}$. - Relative frequency $F = f_0N/F_s = 1\cdot 32/16 = 2$ (integer) so DFT bins show two symmetric peaks at $k=2$ and $k=N-2$. - Amplitude after correction $\approx A/2$ per complex exponential pair so compute $C[k]=X[k]/N$ to obtain amplitude. ### Example 2: Incoherent Sampling and Leakage