# Fast Fourier transform

 Subject classification: this is a mathematics resource.

## Fast Fourier Transform

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)

The N-point DFT of a sequence is given by

${\displaystyle DFT\{x(n)\}=\sum _{n=0}^{N-1}x(n)w_{N}^{kn}{\text{ ; }}k=0,1,\cdots N-1.}$

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

Let ${\displaystyle x(n)}$ be a finite length sequence of length equal to N. Given sequence is : ${\displaystyle x(n)=x(1),x(2),x(3),\cdots x(N-2),x(N-1).}$
Even indexed sequence is : ${\displaystyle x_{e}(n)=x(0),x(2),x(4)\cdots x(N-2).}$
and, odd indexed sequence is : ${\displaystyle x_{o}(n)=x(1),x(3),x(5)\cdots x(N-1).}$

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

${\displaystyle X(k)=\underbrace {\sum _{n=0}^{N-2}x(n)w_{N}^{kn}} ^{\text{Even indexed}}+\underbrace {\sum _{n=0}^{N-1}x(n)w_{N}^{kn}} ^{\text{Odd indexed}}}$

Letting ${\displaystyle N=2r}$ in the first summation and ${\displaystyle N=2r+1}$ in the second summation, we get :

${\displaystyle X(k)=\sum _{r=0}^{{\frac {N}{2}}-1}x(2r)w_{N}^{2kr}+\sum _{r=0}^{{\frac {N}{2}}-1}x(2r+1)w_{N}^{k(2r+1)}}$

since,

${\displaystyle w_{N}^{k2r)}=e^{-j{\frac {2\pi }{N}}k2r}=e^{-j{\frac {2\pi }{\left({\frac {N}{2}}\right)}}kr}=w_{\left({\frac {N}{2}}\right)}^{kr}}$

We get

${\displaystyle X(k)=\sum _{r=0}^{{\frac {N}{2}}-1}x(2r)w_{\left({\frac {N}{2}}\right)}^{kr}+w_{N)}^{k}\sum _{r=0}^{{\frac {N}{2}}-1}x(2r+1)w_{\left({\frac {N}{2}}\right)}^{kr}}$

${\displaystyle \implies X(k)=G(k)+w_{N}^{k}H(k){\text{ ; }}k=0,1,2\cdots {\frac {N}{2}}-1{\text{ or just }}0\leq k\leq {\frac {N}{2}}-1}$

Where ${\displaystyle G(k)}$ and ${\displaystyle H(k)}$ are ${\displaystyle {\frac {N}{2}}}$ point DFTs of even indexed and odd indexed sequences, respectively. For computing ${\displaystyle X(k)}$ for ${\displaystyle {\frac {N}{2}}\leq k\leq N-1}$ , the periodicity of ${\displaystyle G(k)}$ and ${\displaystyle H(k)}$ are exploited. Since ${\displaystyle G(k)}$ and ${\displaystyle H(k)}$ are ${\displaystyle {\frac {N}{2}}}$-point DFTs, they are implicit periodic with a fundamental period ${\displaystyle {\frac {N}{2}}}$ . Hence, we may write

${\displaystyle X(k)=G(k)+w_{N}^{k}H(k){\text{ when }}0\leq k\leq {\frac {N}{2}}-1{\text{ and }}}$

${\displaystyle X(k)=G(k+{\frac {N}{2}})+w_{N}^{k}H(k+{\frac {N}{2}}){\text{ when }}{\frac {N}{2}}-1\leq k\leq N-1}$

Now, after first decimation, the total number of complex multiplications is, ${\displaystyle \eta _{1}=2\left({\frac {N}{2}}^{2}\right)+N}$

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

## Notes

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

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.