What is FFT (Cooley Tukey Algorithm)?

Fourier transformFourier transforms tries to represents a function using sinusoides. is used in almost every signal processing and data compression application. The algorithm used to calculate the discrete version of the Fourier transform is the Fast Fourier Transform (FFT).

It is used in data analysis, audio and visual data compression, and signal denoising. It is also used in calculating derivatives which in turn is used to solve PDEs and other scientific computing. Before diving into the details of the FFT, we shall take a look at Discrete Fourier Transform (DFT) as the FFT is just a faster way to calculate DFT.

Discrete Fourier Transform (DFT)

We know that Fourier transform tries to approximate a continuous function into the sum of sines and cosines. But computers work with discrete data. For example, a continuous signal will be stored in a computer by taking samples from the signal at some sampling rate. These samples form the discrete data that computers work with. These samples can also be approximated as a sum of sines and cosines. DFT returns a series of transforms. It can be calculated by the following equation:

Here, $\hat{y}_k$ is the $k^{th}$ transform and $x_j$ represents the $j^{th}$ element in $n$ discrete values. The complex term $e^{-i2\pi jk/n}$ tells us the type of sines and cosines that will be used in approximation using $j$ and $k$, which are integers. This term is generalized as:

This is called fundamental frequency for $n$ discrete values.

The inverse of DFT is pretty similar to the equation above. It is given as:

Matrix formula

We are multiplying $n$ terms and summing them for one transform. This can be simplified by using matrix multiplication as follows:

The big matrix in the middle is just a simplified version of the equations for every $k^{th}$ transform. It is represented by $F_n$. The same can be applied to the inverse of DFT.

For $n$ transforms, we will have $n^2$ multiplications. This simple calculation will be of the order $O(n^2)$, which is really expensive for large values of $n$. This is where FFT comes to play its role.

Fast Fourier Transform (FFT)

As mentioned earlier, FFT is just a fast way of calculating DFT. There are many implementations for this, but the most used one is the Cooley Tukey algorithm. FFT allows us to compute DFT in $O(n\log n)$ using divide-and-conquer.

For simplicity, we assume that $n$ is a number in powers of two.

Pseudocode

This divide-and-conquer algorithm recursively divides the matrix multiplication in half until it reaches the base case, which is $n = 1$. The algorithm is given as follows:

The algorithm divides the vector into two smaller vectors. One contains all the elements from the even index and the other from the odd. This division is continued until every element reaches the base case.

The real magic happens in the combining of these results. In lines 17 and 18, we are using the periodic property of sinusoids which simplifies our calculations.

Note: Even if $n$ is not in powers of two, we can pad zeros for the calculations.

Example

Implementing this algorithm from scratch can be tedious and prone to errors. Luckily, SciPy provides a good implementation for its calculation.

Explanation

• Line 5: We create a NumPy array which will be the discrete values of which we would like to calculate FFT.

• Line 7: Here, we used the fft() function to calculate the FFT. One required parameter is the x which is an array-like object. It can also have complex values.

• Line 8: The ifft() function implements the inverse of FFT. It has the same required parameter.