Digital Signal Processing: DFT and FFT

Digital Signal Processing (DSP) is a vast field, and at its core lie powerful tools like the Discrete Fourier Transform (DFT) and its faster counterpart, the Fast Fourier Transform (FFT). Understanding DFT and FFT is crucial for anyone studying signal analysis, offering a window into the frequency components of a digital signal. This article will break down these essential concepts, explaining how they work, how to interpret their results, and common pitfalls like leakage.

Digital Signal Processing: An Overview of DFT and FFT Fundamentals

Spectrum analysis is one of the most frequent tasks in Digital Signal Processing. Whether for recognition (like speaker or keyword detection) or diagnosis, evaluating a signal's spectrum is key. While periodic signals can be analyzed using Discrete-time Fourier series and non-periodic signals with the continuous Discrete-time Fourier Transform (DTFT), these methods often present practical challenges. DFT (and FFT) serves as a practical compromise, offering a discrete representation of the spectrum, though it requires careful interpretation to avoid inaccuracies.

Interpreting the DFT Spectrum: Frequency and Amplitude

The output of a DFT (or FFT) calculation doesn't directly give absolute frequency values or physical amplitudes. Instead, it provides relative information that needs to be recalculated. For students delving into DFT and FFT analysis, understanding this transformation is vital.

Frequency Interpretation:

The DFT output provides coefficients indexed k. To get the actual frequency f_k in Hertz, you use the formula:

f_k = k * Fs / N

Where:

• k is the DFT coefficient index.
• Fs is the sampling frequency in Hz.
• N is the DFT (FFT) length or the number of samples.

Amplitude Evaluation:

The coefficients returned by DFT represent a relative spectral density. To obtain the spectral coefficients of the signal's periodic extension, you divide them by the number of samples N. For a complex coefficient X_k, the amplitude C_k can be calculated as:

C_k = abs(X_k) / N

Software like MATLAB or Python's abs() function can directly compute the magnitude.

Displaying Phases in DFT and FFT

When presenting a spectrum, it's always best to plot it as two graphs: magnitude and phase. The phase, often normalized to the interval <−180°, 180°> (or <−π, π> radians), indicates the phase shift of each frequency component. While arctan can calculate phase, care must be taken for quadrant correction. Fortunately, angle() functions in MATLAB or np.angle() in Python handle this directly, providing the correct angle in radians.

Commercial spectrum analyzers sometimes omit the phase spectrum, focusing solely on magnitude, but for a comprehensive DFT and FFT summary, phase is equally important.

The Importance of Logarithmic Scale in Spectrum Analysis

Human perception is relative, making logarithmic scales useful for both frequency and amplitude in analog systems. Amplitudes are often plotted in decibels (dB), using the formula 20 * log10(C_k). In discrete-time systems, the frequency axis often uses a logarithmic scale less frequently because DFT/FFT coefficients are evenly distributed. It's common to display only half of the spectrum, typically from 0 to Fs/2, due to its symmetry for real signals.

Understanding Incoherent Sampling and Leakage in DFT

Consider sampling a sinusoidal signal. If the relative signal frequency F is not an integer number, it means the sampled segment doesn't contain an integer count of signal periods. This is known as incoherent sampling.

When incoherent sampling occurs, a phenomenon called leakage manifests in the DFT spectrum. Instead of a single, sharp peak at the signal's frequency, the energy spreads out to neighboring frequency bins. This happens because the DFT inherently assumes the sampled signal segment is periodic. If the segment isn't truly periodic, extending it outside its original interval creates a discontinuity, leading to spectral leakage.

How to Minimize Leakage in DFT and FFT

Leakage can obscure accurate frequency analysis, making its minimization a critical aspect of Digital Signal Processing: DFT and FFT. Several methods exist:

• Correct Sampling Frequency: Ideally, sample with a frequency that ensures an integer number of signal periods within the segment. However, this is often impractical or impossible due to technical limitations.
• Signal Resampling: Use interpolation techniques (like splines) to resample the signal, a method often employed in spectral analyzers.
• Windowing: This is a widely used technique where the signal segment is multiplied by a weighting function that attenuates the signal at its margins. This reduces the abrupt discontinuities at the segment boundaries. Common windows include:
• Hamming window
• Hann window (equivalent to Hamming for a = 0.5)
• Using Longer Windows: Increasing the number of samples (N) generally improves the resolution and minimizes the impact of leakage.

Windowing Techniques: Hamming, Hann, and Normalization

Windowing functions like the Hamming and Hann windows are designed to prevent edge phenomena such as the Gibbs phenomenon and spectrum leakage. These functions smoothly taper the signal towards zero at the beginning and end of the segment. For example, the Hann window's formula is w[n] = 0.5 - 0.5 * cos(2 * pi * n / N).

Most window functions are not normalized by default, meaning their sum of weights is not unity. This can lead to incorrect amplitude values in the resulting spectrum. To correct this, a normalized variant of the window is used:

w_norm[n] = w[n] / sum(w[n])

This ensures that the amplitudes in the DFT spectrum accurately reflect the original signal's amplitudes after windowing.

Enhancing DFT Resolution with Zero Padding

The resolution of the DFT spectrum is directly related to the length of the signal segment (N). To artificially increase this resolution, a technique called zero padding is used. This involves extending the original signal segment by adding zeros to its end. For instance, if you have N samples, you can pad it to M samples where M > N.

Software functions like fft() in MATLAB or Python can often add zeros automatically when a desired DFT length is specified. While zero padding doesn't add new information to the signal, it effectively samples the DTFT at more points, providing a smoother, higher-resolution estimate of the spectrum, making it easier to distinguish closely spaced frequency components.

Fourier Filtering: Leveraging DFT for Signal Processing

Fourier filtering applies the principles of DFT (or FFT) to implement Linear Time-Invariant (LTI) system responses in the frequency domain. The core idea is that the output spectrum Y_k of an LTI system can be calculated by multiplying the input signal's spectrum X_k by the system's frequency response G_k:

Y_k = X_k * G_k

Subsequently, an Inverse FFT (IFFT) is used to transform Y_k back into the time domain to get the filtered signal y[n].

The Challenge of Circular Convolution and How to Prevent It

A critical issue when performing Fourier filtering with DFT/FFT is the phenomenon of circular convolution. Standard convolution implies that the response extends indefinitely. However, DFT operates on finite-length signals and implicitly treats them as periodic. When filtering, if the combined length of the input signal and the impulse response exceeds the DFT length, the