What is FFT?

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 = 2^M  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 

W₈⁴ = -1

and W₈ ⁵ = – W ₈¹

also W₈⁶ = – W₈²

W₈⁷ = – W₈³

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

G(1)  – W ₈¹ H(1) = x(5)

G(2) – W₈² H(2) = x(6)

G(3) – W₈³  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 W₈ ⁰ to W ₈⁷

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!

• Types of UPS
• Flip-Flops in sequential circuits
• What is PLA?
• What is SMPS?
• Working of Stepper Motor