# Introduction of Fast Fourier Transformation (FFT)

This article comprises of introduction to the Fourier series, Fourier analysis, Fourier transformation, why do we use it, an explanation of the FFT algorithm, and its implementation.
TKTejas Khare24.00
May 18, 2021

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.

### But is Noise an unwanted signal?

The answer is Yes and No. I will tell you why. Like I mentioned in the scenario above, if you have one or all three files (audio, video, and image), they may contain noise or unwanted signals (in audio), or a spectrum of wavelengths (in frames or images). Here the noise will be defined as unwanted because if you have a music file and there is a random muting, distortion of the sound, you certainly don't want that.

Now white noise can also be a wanted noise. In deep learning, noise can be intentionally fed to a neural network to improve its performance. In the previous article, Understanding of Regularization in Neural Networks, we talked about how the dropout method drops some neurons or zeroes them out. This is nothing but a form of adding noise to those neurons. Furthermore, in Generative Adversarial Networks (GAN), you feed random noise so that the discriminator can train the GAN.

Let's talk about the noise as an unwanted signal and how can we remove it.

## 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.

## Why do we need to use Fourier Transformation?

Let's define some terms first

1. Frequency - It is defined as the speed or rate at which an entity changes. In the case of a signal, frequency is the rate at which the intensity/power of the signal changes. It is defined as samples/sec and the unit is Hertz (Hz).
2. Periodic Function - It is a type of function where the function retains its value after regular intervals. For example, a sine function.
3. Non-Periodic Function - It is a type of function where the function does not retain its value after regular intervals or multiples of the integer values. For example, an exponential function.

Let's just start with this. It helps in analyzing a signal in a different domain which is much simpler to understand and manipulate. You can't see how much noise is present in a signal when analyzing in the time domain. But after the transform, you can get what frequencies are present in your signal. FT is not only used in analyzing signals, but also in image compressions. It decomposes the image into sine or cosine components into the frequency domain. It gives an image that has a spectrum of wavelengths. Hence, it's pretty much clear that FT is a very useful tool not just in the communication domain, but also in computing.

## Explanation of FT

The Fourier series is defined as any function that is integrable can be represented as an infinite sum of sines and cosines.

where Tk is a continuous function.

The Fourier transform is an upgraded version of the Fourier series. It is defined as -

where x(t) is any integrable continuous function and X(f) is the FT of x(t) in the frequency domain.

The inverse transform is given by -

The term e^-j2(pi)ft and e^-j2(pi)ft are Euler's representation-

## e^jx = cos(x) + j*sin(x)

When the Fourier transform is represented into discrete parts, the Fourier Transform is called the Discrete Fourier Transform (DFT). For this article, we will be discussing the Fast Fourier Transform algorithm and its implementation.

## Fast Fourier Transform (FFT)

The FFT is a very efficient algorithm for calculating the DFT of a continuous signal and hence the name, Fast Fourier Transform. The working of this algorithm is not that complex. What it does is decomposes the DFT recursively into smaller DFT so that the computation required is very sublime. This method enables the algorithm to achieve a time complexity of O(nlogn), where n is the size of data. The reason it can break down the DFT even further is because of the symmetrical property of DFT.

where X is the DFT of any x(t) continuous periodic function.

So as the DFT is symmetric, you don't need to calculate its complementary part because it would be equal. Hence, by this method, the algorithm can achieve such fast computations. This reduction in the computation is highly significant because when the size of the data 'n' is large, the time required would be quite large without FFT.

## 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



Note: You can check the DFT one by one by using np.real() and np.imag() to get the real and imaginary components of DFT. Here is the combined graph of both -

Now from the above two images, you can see we have a different pair of frequencies, and that's because we have two signals mixed with different frequencies and hence the resultant frequency has a different frequency. In step 4, the image is noisy and cannot be analyzed easily. But in the above image, the task is made simpler by Fourier Transformation, and hence is the use case of it.

That's it for this article. Hope now you are comfortable with FT.

Thank you and Cheers :)