0xCODE
Published in

0xCODE

Fast Fourier Transform (FFT) Algorithm Implementation In Python

Fast Fourier Transform (FFT) are used in digital signal processing and training models used in Convolutional Neural Networks (CNN). We demonstrate how to apply the algorithm using Python.

FFT has many applications in component analysis.

One application of FFT is in digital signal processing. It can be used as a tool for decomposing signals from the time domain to the frequency domain. This is a good way of separating signals like when quantizing analog waves to discrete signals.

Another application of FFT is in image processing. In convolutional layer overlays a kernel can scan a section of an image. This takes all values from that location to perform operations. The kernel then shifts to another section of the image and repeats the process until it scans the entire image.

FFT is also the computation of Discrete Fourier Transforms (DFT) into an algorithmic format. It is a way to compute Fourier Transforms much faster than using the conventional method. Let us take a look at DFT to get some idea of how FFT makes computing results faster.

DFT transforms a sequence of N numbers …

… to a sequence of another set of complex numbers:

Without going over the entire theorem, DFT is basically taking any quantity or signal that varies over time and decomposing it into its components (e.g. frequency). This can be the pixels in an image or the pressure of sound in radio waves (used in DSP chips).

The problem with DFT is that it takes more calculations to arrive at an answer. This is because you have to do N(multiplications) with N(additions), which in Big O Notation is O(N²) in terms of time complexity.

With FFT we save some steps by reducing the number of calculations in DFT. As a result we can reduce a domain of size N from O(N²) to O(Nlog2N).

DFT using FFT can be written using the following formula:

We have the discrete signal x(n) multiplied with e (raised to a function specified) , with N representing the size of the domain for the results of the sum of a value n.

As the name implies, it is a fast or a faster way to compute Fourier Transforms. This becomes more noticeable when the size of the domain becomes larger. Take for example this table (taken from Towards Data Science article by Cory Maklin):

Let us say it takes 1 nanosecond per operation performed in a system. With FFT, it takes approximately 30 seconds to complete operations of size N = 10⁹. If FFT was not used, it would take 31.7 years (10¹⁸) using the conventional algorithm formula.

Let us start with a simple example. From a Python environment at the prompt (you can also write a Python or py file), import the numpy library.

We will now specify a function and use matrix operations to arrive at the result of the computation.

Now let us generate a random array of numbers to use with the calculations.

Check the value of x:

The next example makes use of a notebook using a recursive approach.

This produces the graph plot:

Next we can calculate the Fourier Transform of the signal from the graph.

Here are more examples using Python libraries, with numpy and scipy. We used numpy earlier, but here are more advanced examples.

Let us first generate the signal.

The signal is identical to the previous recursive example.

We will now use the fft and ifft functions from numpy to calculate the FFT amplitude spectrum and inverse FFT to obtain the original signal. We then plot both results and time the fft function using a 2000 length signal.

We get the result:

Next, we will use scipy instead of numpy.

We get the result:

Using the FFT algorithm is a faster way to get DFT calculations. The built-in Python functions for FFT are quite fast and easy to use, notably the scipy library. It significantly lessens the amount of time, which can also save costs. These functions are available in Python, so developers can build ready-to-use systems that can utilize these library modules.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Vincent Tabora

Editor HD-PRO, DevOps Trusterras (Cybersecurity, Blockchain, Software Development, Engineering, Photography, Technology)