How to Implement Discrete Fourier Transform with NumPy

How to Implement Discrete Fourier Transform with NumPy
Image by Editor | ChatGPT

The Discrete Fourier Transform (DFT) converts a signal from the time domain to the frequency domain. It helps analyze the frequency components in signals. NumPy provides functions to compute the DFT.

In this article, we will explore the implementation of DFT using NumPy in Python.

Importing Required Libraries

First, we need to import essential Python libraries:

import numpy as np
import matplotlib.pyplot as plt

Implementing DFT Manually

The following function implements the DFT using its mathematical formula:

def dft(x):
    """Compute the Discrete Fourier Transform (DFT) of a 1D array."""
    N = len(x)  # Number of samples
    X = np.zeros(N, dtype=complex)  # Initialize output array
    
    for k in range(N):  # Iterate over frequency bins
        for n in range(N):  # Iterate over time samples
            X[k] += x[n] * np.exp(-2j * np.pi * k * n / N)
    
    return X

Noe that this function has a complexity of $O(N^2)$. It becomes inefficient for large datasets.

Generating a Sample Signal

Let’s generate a signal with two sine waves of different frequencies:

# Define parameters
N = 100  # Number of samples
t = np.linspace(0, 1, N, endpoint=False)  # Time vector

# Generate a signal containing two frequencies (5 Hz and 20 Hz)
signal = np.sin(2 * np.pi * 5 * t) + 0.5 * np.sin(2 * np.pi * 20 * t)

# Plot the signal
plt.figure(figsize=(8, 4))
plt.plot(t, signal, label="Time-domain Signal")
plt.xlabel("Time [s]")
plt.ylabel("Amplitude")
plt.title("Original Signal (Time Domain)")
plt.legend()
plt.grid()
plt.show()

We create a time vector from 0 to 1 second to represent discrete time intervals. Next, we generate a composite signal by combining two sine waves of 5 Hz and 20 Hz, which introduces different frequency components.

signal

Computing the DFT Spectrum

Now, let’s apply our DFT function to transform the signal into the frequency domain.

# Compute the DFT
X_dft = dft(signal)

# compute frequency bins
freqs = np.array([k for k in range(N)])

# Plot the magnitude spectrum 
plt.figure(figsize=(8, 4))
plt.stem(freqs[:N//2], np.abs(X_dft)[:N//2] / (N/2)) # Normalize magnitude
plt.xlabel("Frequency [Hz]")
plt.ylabel("Magnitude")
plt.title("Manually Computed DFT Spectrum")
plt.grid()
plt.show()

This code computes the DFT using our custom dft function and then calculates the corresponding frequency bins for plotting. The magnitude is normalized by $N/2$ to correctly represent the amplitude of the original sine waves.

custom_dft

Using NumPy’s Fast Fourier Transform (FFT)

Since the above implementation has a time complexity of $O(N^2)$, it is inefficient for large datasets. Instead, NumPy provides an optimized Fast Fourier Transform (FFT) function, with a complexity of $O(N \log N)$.

# Compute FFT using NumPy
X_fft = np.fft.fft(signal)

# Plot FFT spectrum
plt.figure(figsize=(8, 4))
plt.stem(freqs[:N//2], np.abs(X_fft)[:N//2] / (N/2)) # Normalize magnitude
plt.xlabel("Frequency [Hz]")
plt.ylabel("Magnitude")
plt.title("FFT Spectrum (Using NumPy)")
plt.grid()
plt.show()

The function np.fft.fft() computes the FFT of the signal. We can then plot its magnitude against the same frequency bins calculated earlier, ensuring we normalize the magnitude correctly.

numpy_fft

Inverse Discrete Fourier Transform (IDFT)

The Inverse Discrete Fourier Transform (IDFT) is used to convert a signal from the frequency domain back to the time domain. It is the reverse process of the Discrete Fourier Transform (DFT) and reconstructs the original signal from its frequency components.

def idft(X):
    """Compute the Inverse Discrete Fourier Transform (IDFT)."""
    N = len(X)
    x = np.zeros(N, dtype=complex)

    for n in range(N):
        for k in range(N):
            x[n] += X[k] * np.exp(2j * np.pi * k * n / N)
        x[n] /= N
    
    return x.real  # Return only the real part

# Compute the inverse DFT
reconstructed_signal = idft(X_dft)

# Plot the reconstructed signal
plt.figure(figsize=(8, 4))
plt.plot(t, reconstructed_signal, label="Reconstructed Signal")
plt.xlabel("Time [s]")
plt.ylabel("Amplitude")
plt.title("Reconstructed Signal (Time Domain)")
plt.legend()
plt.grid()
plt.show()

The idft function shown above manually implements the inverse transform. At the end, we take the real part of the result (x.real) to discard any small imaginary components that arise from floating-point numerical errors.

reconstructed_signal

Conclusion

NumPy provides an easy way to compute the Discrete Fourier Transform using np.fft.fft() and its inverse with np.fft.ifft(). These functions help analyze and manipulate signal frequencies. Using NumPy, we can quickly transform signals between the time and frequency domains. This is useful in signal processing, image analysis, and other applications.

Leave a Reply

Your email address will not be published. Required fields are marked *