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_{8}^{4} = -1

and W_{8} ^{5} = – W _{8}^{1}

also W_{8}^{6} = – W_{8}^{2}

W_{8}^{7} = – W_{8}^{3}

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

G(1) – W _{8}^{1 }H(1) = x(5)

G(2) – W_{8}^{2 }H(2) = x(6)

G(3) – W_{8}^{3 } 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_{8} ^{0 }to W _{8}^{7}

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!**