Fast Fourier transform

Subject classification: this is a mathematics resource.

This page is still under construction. Any contribution is appreciated.

Fast Fourier Transform Edit

Fast fourier transform or FFT is an algorithm mainly developed for digital computing of a Discrete Fourier transform or DFT of a discrete signal. Computing of DFT of a digital signal (discrete-time signal) involves N2 Complex multiplications [1] , where N is the number of points to which we consider taking DFT of the input periodic signal [2]. Using an FFT algorithm, the number of complex multiplications can be reduced to a greater extent. Reduction is mainly due to decimation [3] either in time domain or in frequency domain [4]

Decimation in time FFT algorithm (Radix 2) Edit

The N-point DFT of a sequence is given by


every time x(n) gets multiplied by   , we get one complex multiplication. Therefore when the above summation is expanded for a given   , we get   complex multiplications. Which means that, to compute Npoint DFT, we have   complex multiplications.
Our aim is to reduce the number of complex multiplications. In the following presentation, The number of samples of   is assumed to be a power of 2. i.e,   where v is some fixed positive integer.
In this approach, N point transforms are broken into   point DFTs which are further broken into   point DFTs. And this process is continued until we get 2-point DFT. This technique is known as Divide and Conquer approach.

Let   be a finite length sequence of length equal to N. Given sequence is :  
Even indexed sequence is :  
and, odd indexed sequence is :  

Now we can split the above DFT equation into even and odd parts as below :


Letting   in the first summation and   in the second summation, we get :




We get



Where   and   are   point DFTs of even indexed and odd indexed sequences, respectively. For computing   for   , the periodicity of   and   are exploited. Since   and   are  -point DFTs, they are implicit periodic with a fundamental period   . Hence, we may write



Now, after first decimation, the total number of complex multiplications is,  

The same way will lead us to further decimation and thus a block diagram can be contructed as below :


Notes Edit

  1. multipication using complex numbers, which requires computation with real and imaginary part of a complex number and thus using up memory or resources on an embedded system or a computer where DFT must be computed
  2. i.e, to find DFT of a periodic discrete time signal of fundamental period N.
  3. The process of dividing N-point DFTs into lower-point DFTs so as to reduce the complexity of one single DFT computing section of the qhole system
  4. i.e, Decimation in time means taking lower point DFTs of the inputs and then manipulating them to form the DFT of the main input sequence and the same in frequency domain requires the reverse approach

Prepared from the notes of Dr. D. Ganesh Rao Tutorials, Bangalore Edit

The derivation or the text in this article written by Sushruth Sastry 22:13, 19 November 2010 (UTC) is the content from the Tution notes of Dr. D. Ganesh rao, Prof. at MSRIT, bangalore.