Introduction of Fast Fourier Transformation (FFT)

Introduction

Suppose you have an audio file, or even a video file, or let's say you have an image file. But the only problem is it has lots of noise. You can't distinguish between the required audio, frames, or the object in the three files respectively. So how are you supposed to distinguish between the noise and the actual signal?

The odds are quite high that the file may contain a term called noise. Though the terms are of the communication domain, they are also involved in the AI domain.

Noise

Noise is a random signal which consists of equal intensities or powers at every frequency. In computing, it is statistically defined as a sequence of random variables. So basically, in very simple terms, it is a random thing that may be a part of your signal.

Fourier Transformation (FT)

Fourier Transformation which is the main highlight of this article is a very useful tool for analyzing signals, especially noisy signals. It transforms or converts complex mathematical equations into simpler trigonometric functions in terms of sin or cos. Sin or Cos are used because the signal is easier to analyze in their format. In other terms, Fourier transformation is used to convert time signals into frequency signals and power signals. You are using the applications of Fourier Transformation unknowingly every day.

Implementation of FFT

Note: The codes are written and tested by the author. The outputs are the screenshots of Jupyter Notebook cells.

For this implementation, we will be using scipy library as a Fourier transformation calculator.

1. Let's import the libraries for python fft

import numpy as np
import matplotlib.pyplot as plt
from scipy.fftpack import fft, fftfreq

Note: If you have the latest package of scipy, use scipy.fft instead of scipy.fftpack

2. Defining a random signal

n = 500 # Number of data points
dx = 5.0 # Sampling period (in meters)
x = dx*np.arange(0,n) # x coordinates
w1 = 100.0 # wavelength (meters)
w2 = 50.0 # wavelength (meters)

fx = np.sin(2*np.pi*x/w1)
plt.title("Signal as a function of time")
plt.plot(x, fx)

3. Getting the Discrete Fourier Transform (DFT) using FFT

Fk = fft(fx)/n # Fourier coefficients (divided by n)

# To plot in the frequency domain
Fk =  fftshift(Fk) # Shift zero frequency to center
nu = fftfreq(n,dx) # Natural frequencies
nu = fftshift(nu) # Shift zero frequency to center

plt.title('DFT of the signal')
plt.plot(nu, np.abs(Fk))  # Get the absolute values of DFT

As you can see in the above image, the DFT of our signal is a simple graph in which we have a single pair of frequencies as I had mentioned earlier that DFTs are symmetrical. As the signal is a simple continuous signal and contains only one frequency component, it was expected to get a single pair of frequencies.

4. Adding a random noise

new_fx = np.sin(2*np.pi*x/w1) + 2*np.cos(2*np.pi*x/w2) 
# new = old + random signal/noise
plt.title('Modified Signal')
plt.plot(x, new_fx)

5. Getting the DFT for the modified signal

new_Fk = fft(new_fx)/n  # Fourier coefficients (divided by n)
new_Fk = fftshift(new_Fk)  # Shift zero frequency to center
plt.title('DFT of Modified Signal')
plt.plot(nu, np.abs(new_Fk))  # Get the absolute values of DFT

You can find more details with plotted images in this article

Blog