Goseeko blog

What is FFT?

by Team Goseeko

Certain algorithms permit implementations of Discrete Fourier transform with considerable savings in computation time. These algorithms are known as Fast Fourier Transform. Also known as FFT.

FFT algorithms are based on the fundamental principle of decomposing the computation of DFT of sequence length into successively smaller discrete Fourier transforms.

They are basically two classes of FFT algorithms

  • Decimation in time
  • Decimation in frequency

Decimation-in-time algorithm FFT

This algorithm is known as Radix-2 DIT-FFT algorithm which means the number of output points N can be expressed as a power of 2 that is N = 2M  where M is an integer.

Let x(n) be a sequence where N is assumed to be a power of 2. Decimate or break this sequence into two sequences of length N/2 where one sequence consists of even-indexed values of x(n) and the other of odd-indexed values of x(n).

xe(n)  = x(2n)   n= 0,1,……….. N/2-1

xo(n) = x(2n+1)  n= 0,1,……….. N/2 -1

The N-point DFT of x(n) can be written as 

Separating x(n) into even and odd indexed values of x(n) we obtain 

W84 = -1

and W8 5 = – W 81

also W86 = – W82

W87 = – W83

G(0) – H(0) = x(4)

G(1)  – W 81 H(1) = x(5)

G(2) – W82 H(2) = x(6)

G(3) – W83  H(3) = x(7)

Let  us consider one example now, to understand the concept.

Consider the sequence x[n]={ 2,1,-1,-3,0,1,2,1}. Calculate the FFT.

Arrange the sequence as x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7)

Since N=8 find the values W8 0 to W 87

Apply the butterfly diagram to obtain the  values.

Decimation in Frequency

Apart from time sequence, we can represent an N-point sequence in frequency. Let us take a four-point sequence to understand it better.

Let the sequence be x[0],x[1],x[2],x[3]………..x[7]

Mathematically, this sequence will be as follows

Now let us make one group of sequence numbers 0 to 3 and another group of sequence 4 to 7. Now, mathematically this will be as follows

Let us replace n by r, where r = 0, 1 , 2….N/2−1. 

We take the first four points  x[0],x[1],x[2],x[3] initially, and try to represent them mathematically as follows –

Interested in learning about similar topics? Here are a few hand-picked blogs for you!

You may also like