Fast Fourier transform

From Wikiversity
Jump to navigation Jump to search
Subject classification: this is a mathematics resource.

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

Fast Fourier Transform[edit | edit source]

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 | edit source]

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 | edit source]

  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 | edit source]

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.