Fast Fourier Transform (FFT)

The Fast Fourier Transform (FFT) is an algorithm for computing the Discrete Fourier Transform (DFT) of a sequence of N complex numbers in O(N log N) time, instead of the O(N^2) time required by the naive DFT algorithm.

 

The DFT is a mathematical technique used to analyze signals in the frequency domain. It converts a signal in the time domain, such as a function of time, into a function of frequency, which allows us to analyze the frequency components of the signal.

 

The FFT algorithm is based on the principle of divide-and-conquer, and it breaks the DFT of N points into smaller DFTs of size N/2. This process is repeated recursively until we reach DFTs of size 1, which are trivial to compute. Then, we combine the results of these smaller DFTs to obtain the final DFT of size N.

 

The FFT is a widely used algorithm in many fields, including signal processing, image processing, and data compression. It is particularly useful in cases where we need to compute the DFT of a large number of points, since it is much faster than the naive DFT algorithm.

 

import math

def fft(x):
    N = len(x)
    if N == 1:
        return x
    even = fft(x[0::2])
    odd = fft(x[1::2])
    T = [math.exp(-2j*math.pi*k/N)*odd[k] for k in range(N//2)]
    return [even[k] + T[k] for k in range(N//2)] + [even[k] - T[k] for k in range(N//2)]

# Generate a signal
t = np.linspace(0, 1, 1000)
f = 10  # frequency of the signal
signal = np.sin(2*np.pi*f*t)

# Compute the FFT
fft_signal = fft(signal)

# Compute the frequencies
freq = np.linspace(0, 1/(t[1]-t[0]), len(signal))

# Plot the signal and its FFT
import matplotlib.pyplot as plt

fig, (ax1, ax2) = plt.subplots(2, 1, figsize=(8, 6))

ax1.plot(t, signal)
ax1.set_xlabel('Time (s)')
ax1.set_ylabel('Amplitude')
ax1.set_title('Signal')

ax2.plot(freq, np.abs(fft_signal))
ax2.set_xlabel('Frequency (Hz)')
ax2.set_ylabel('Magnitude')
ax2.set_title('FFT')

plt.tight_layout()
plt.show()