Digital Signal Processing: DFT and FFT

Welcome to our comprehensive guide on Digital Signal Processing: DFT and FFT! If you're studying signal processing, understanding the Discrete Fourier Transform (DFT) and its faster counterpart, the Fast Fourier Transform (FFT), is crucial. This article breaks down these complex topics into easy-to-understand concepts, perfect for students. We'll explore how they're used for spectrum analysis, interpretation of results, and common challenges like leakage and how to overcome them.

Unpacking Digital Signal Processing: DFT and FFT Core Concepts

At its heart, Digital Signal Processing often involves analyzing signals in the frequency domain. The DFT and FFT are fundamental tools for this. Zdeněk Kohl from the University of Defence, Brno, highlights that spectrum analysis is one of the most frequent tasks in DSP, essential for recognition (like speaker or keyword) and diagnosis.

When evaluating a signal's spectrum, we face choices:

• Periodic signals: Ideally, we'd use Discrete-time Fourier series, but knowing the exact signal frequency for coherent sampling is often a challenge.
• Non-periodic signals: The Discrete-time Fourier Transform (DTFT) is suitable, but it's a continuous function of frequency, which is difficult to work with digitally.

The DFT (and FFT) serves as a practical compromise. However, it's vital to use them with care, as this compromise can introduce inaccuracies or misleading results.

Displaying the Spectrum: Magnitude and Phase

The spectrum is a complex function, so it should always be plotted as two graphs to fully represent it. In DSP, we prefer a polar complex number representation:

• Magnitude (Amplitude): In Volts or other physical units.
• Phase: Usually normalized to the interval <-π, π> radians or <-180°, 180°> degrees.

Standard analog systems often omit the phase spectrum and focus on absolute values, with frequency in Hz.

Interpreting DFT Spectrum: Frequency and Amplitudes

The DFT output provides relative information, not absolute values directly. Here's how to interpret it:

1. Frequency Interpretation: The DFT output provides coefficient indexes, not actual frequencies. To get the actual frequency, use the formula: f_k = (k * F_s) / N, where f_k is the actual frequency (Hz), k is the DFT coefficient index, F_s is the sampling frequency (Hz), and N is the DFT (FFT) length.
2. Amplitude Evaluation: The DFT coefficients represent relative spectral density. To get spectral coefficients of the periodic extension of the signal, divide by the number of samples, N. For example, C_k = |X_k| / N. To get the amplitude of the original signal, which for A=1 becomes (2 * A) / N, you might see (2 * |X_k|) / N used for k ≠ 0 and k ≠ N/2.

MATLAB/Python functions like abs() can be used for magnitude calculation. For sinusoidal signals, the amplitudes X_k and X_(N-k) are typically (N * A) / 2.

Displaying Phases

Phase interpretation is crucial. The argument (angle) of a complex number is ambiguous (due to 2π periodicity). We usually prefer degrees in the interval <-180°, 180°>. The phase Φ_k can be calculated using arctan(Im(X_k) / Re(X_k)). MATLAB's angle() or Python's np.angle() functions can directly provide the correct angle in radians, handling quadrant corrections automatically.

Logarithmic Scale for Spectrum Analysis

The human ear perceives sound logarithmically, which is why logarithmic scales are often used for both frequency and amplitude in analog systems. Amplitude is commonly plotted in decibels (dB), calculated as 20 * log10(C_k). In discrete-time systems, however, two points are important:

• DFT coefficients are for evenly distributed frequencies, making a logarithmic frequency scale less common.
• Due to spectrum symmetry, we often display only frequencies in the interval <0, F_s/2>, as DFT moves coefficients for negative frequencies to the part above F_s/2.

Understanding Incoherent Sampling and Leakage

When analyzing signals with DFT, incoherent sampling is a significant issue. This occurs when the relative signal frequency F is not an integer number. Consequently, the sampled signal segment does not contain an integer count of signal periods. For example, if we sample a 1.2 Hz sine wave at F_s = 16 Hz for N = 32 samples, the relative frequency F = (f * N) / F_s = (1.2 * 32) / 16 = 2.4, which is not an integer.

The Problem of Leakage in DFT

Incoherent sampling leads to a phenomenon called leakage. The DFT spectrum is inherently valid only for a time-limited signal. If we consider the inverse DFT outside the base interval <0, N-1>, it implies a periodic extension of the signal. In cases of incoherent sampling, this periodic extension does not match the original analog signal, causing the spectrum to