Fourier Transform

calendarDec 12, 2024 · 4 min read · signals fourier fft dft frequency-analysis dsp  ·
Share on: linkedincopy

Transform signals between time and frequency domains.

Overview

The Fourier Transform decomposes a signal into its constituent frequencies, revealing the frequency content of time-domain signals.

Continuous Fourier Transform (CFT)

Forward Transform

$$ X(f) = \int_{-\infty}^{\infty} x(t) e^{-j2\pi ft} dt $$

Inverse Transform

$$ x(t) = \int_{-\infty}^{\infty} X(f) e^{j2\pi ft} df $$

Discrete Fourier Transform (DFT)

For finite-length discrete signals.

Forward DFT

$$ X[k] = \sum_{n=0}^{N-1} x[n] e^{-j\frac{2\pi}{N}kn}, \quad k = 0, 1, \ldots, N-1 $$

Inverse DFT

$$ x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j\frac{2\pi}{N}kn}, \quad n = 0, 1, \ldots, N-1 $$

Frequency Bins

$$ f[k] = \frac{k \cdot f_s}{N}, \quad k = 0, 1, \ldots, N-1 $$

Where:

  • $f_s$ = sampling frequency
  • $N$ = number of samples
  • Frequency resolution: $\Delta f = \frac{f_s}{N}$

Fast Fourier Transform (FFT)

Efficient algorithm for computing DFT. Complexity: $O(N \log N)$ vs $O(N^2)$ for naive DFT.

Requirement: $N$ should be a power of 2 for best performance.

Practical Implementation

Python (NumPy)

 1import numpy as np
 2import matplotlib.pyplot as plt
 3
 4def analyze_spectrum(signal, sample_rate):
 5    """
 6    Compute and plot frequency spectrum
 7    """
 8    N = len(signal)
 9    
10    # Compute FFT
11    fft_result = np.fft.fft(signal)
12    
13    # Compute magnitude spectrum
14    magnitude = np.abs(fft_result)
15    
16    # Compute frequency bins
17    freqs = np.fft.fftfreq(N, 1/sample_rate)
18    
19    # Only plot positive frequencies
20    positive_freqs = freqs[:N//2]
21    positive_magnitude = magnitude[:N//2]
22    
23    return positive_freqs, positive_magnitude
24
25# Example usage
26fs = 1000  # 1 kHz sampling rate
27duration = 1.0
28t = np.arange(0, duration, 1/fs)
29
30# Create signal: 50 Hz + 120 Hz
31signal = np.sin(2*np.pi*50*t) + 0.5*np.sin(2*np.pi*120*t)
32
33# Analyze
34freqs, magnitude = analyze_spectrum(signal, fs)
35
36# Plot
37plt.plot(freqs, magnitude)
38plt.xlabel('Frequency (Hz)')
39plt.ylabel('Magnitude')
40plt.title('Frequency Spectrum')
41plt.grid(True)
42plt.show()

Python (Real FFT for Real Signals)

 1def real_fft_analysis(signal, sample_rate):
 2    """
 3    More efficient FFT for real-valued signals
 4    """
 5    N = len(signal)
 6    
 7    # Use rfft for real signals (more efficient)
 8    fft_result = np.fft.rfft(signal)
 9    magnitude = np.abs(fft_result)
10    phase = np.angle(fft_result)
11    
12    # Frequency bins for rfft
13    freqs = np.fft.rfftfreq(N, 1/sample_rate)
14    
15    # Power spectral density
16    psd = (magnitude ** 2) / N
17    
18    return freqs, magnitude, phase, psd

Go

 1package signals
 2
 3import (
 4    "math"
 5    "math/cmplx"
 6)
 7
 8// FFT computes Fast Fourier Transform (Cooley-Tukey radix-2)
 9func FFT(x []complex128) []complex128 {
10    N := len(x)
11    
12    // Base case
13    if N <= 1 {
14        return x
15    }
16    
17    // Divide
18    even := make([]complex128, N/2)
19    odd := make([]complex128, N/2)
20    for i := 0; i < N/2; i++ {
21        even[i] = x[2*i]
22        odd[i] = x[2*i+1]
23    }
24    
25    // Conquer
26    evenFFT := FFT(even)
27    oddFFT := FFT(odd)
28    
29    // Combine
30    result := make([]complex128, N)
31    for k := 0; k < N/2; k++ {
32        t := cmplx.Exp(complex(0, -2*math.Pi*float64(k)/float64(N))) * oddFFT[k]
33        result[k] = evenFFT[k] + t
34        result[k+N/2] = evenFFT[k] - t
35    }
36    
37    return result
38}
39
40// Magnitude computes magnitude spectrum
41func Magnitude(fft []complex128) []float64 {
42    mag := make([]float64, len(fft))
43    for i, v := range fft {
44        mag[i] = cmplx.Abs(v)
45    }
46    return mag
47}

Important Properties

Linearity

$$ \mathcal{F}{ax_1(t) + bx_2(t)} = aX_1(f) + bX_2(f) $$

Time Shift

$$ \mathcal{F}{x(t - t_0)} = X(f) e^{-j2\pi f t_0} $$

Frequency Shift

$$ \mathcal{F}{x(t) e^{j2\pi f_0 t}} = X(f - f_0) $$

Convolution Theorem

$$ \mathcal{F}{x(t) * h(t)} = X(f) \cdot H(f) $$

This is why filtering in frequency domain is often faster!

Parseval's Theorem

Energy is conserved:

$$ \int_{-\infty}^{\infty} |x(t)|^2 dt = \int_{-\infty}^{\infty} |X(f)|^2 df $$

Common Applications

1. Frequency Analysis

1# Find dominant frequency
2freqs, magnitude = analyze_spectrum(signal, fs)
3dominant_freq = freqs[np.argmax(magnitude)]
4print(f"Dominant frequency: {dominant_freq} Hz")

2. Filtering in Frequency Domain

 1def lowpass_filter_fft(signal, cutoff_freq, sample_rate):
 2    """Low-pass filter using FFT"""
 3    N = len(signal)
 4    fft_signal = np.fft.fft(signal)
 5    freqs = np.fft.fftfreq(N, 1/sample_rate)
 6    
 7    # Zero out frequencies above cutoff
 8    fft_signal[np.abs(freqs) > cutoff_freq] = 0
 9    
10    # Inverse FFT
11    filtered = np.fft.ifft(fft_signal)
12    return np.real(filtered)

3. Spectral Leakage Reduction

1# Apply window before FFT
2window = np.hanning(len(signal))
3windowed_signal = signal * window
4fft_result = np.fft.fft(windowed_signal)

Practical Tips

  1. Zero-padding: Increase frequency resolution

    1N_padded = 2**int(np.ceil(np.log2(len(signal)))) * 2
2signal_padded = np.pad(signal, (0, N_padded - len(signal)))

  2. DC component: $X[0]$ is the average value

    1dc_component = fft_result[0] / N

  3. Nyquist frequency: Maximum usable frequency is $f_s/2$

  4. Symmetric spectrum: For real signals, negative frequencies are conjugate symmetric

Frequency Resolution vs Time Resolution

Trade-off governed by uncertainty principle:

$$ \Delta t \cdot \Delta f \geq \frac{1}{4\pi} $$

  • Long signals: Better frequency resolution, poor time localization
  • Short signals: Better time localization, poor frequency resolution
  • Solution: Short-Time Fourier Transform (STFT) or Wavelets

Common Pitfalls

  1. Forgetting to normalize: DFT magnitude scales with $N$
  2. Ignoring spectral leakage: Use windows for non-periodic signals
  3. Aliasing: Ensure $f_s > 2f_{max}$
  4. DC offset: Remove before FFT if not needed
  5. Not using power-of-2 length: FFT is fastest for $N = 2^k$

Further Reading

Related Snippets