The miracle of FFT

I’ve always admired discrete signals. Without them I’d not be able to write this blog and make you able to read it. But with discrete signals comes the need for a method of efficient signal processing. And that is where FFT has helped a lot. Fast Fourier transform is a method of calculating the DFT of a given signal. But the catch is that it reduces the computational step to that extent where our digital processors can easily compute.  FFT has many variations such as FFT by decimation in time, FFT by decimation in frequency etc. I’ll briefly talk about the FFT using decimation in frequency, how it works and how it helps in computation.

We know that for a discrete signal x(n) the DFT is given as,

Now in order to understand FFT we analyze the property of W_N. We can easily to arrive to following results:

W_N^N=1

W_N^N/2=-1 and W_N^N+K= W_N^K_.  Now let N be the total number of discrete data sequence and N=2^L where L is an integer. Now since N is even we’ll have N/2 also even. Then we can write,

Splitting X(k) into even and odd samples we’ve

Now the beauty of the above equations is that DFT of signal with 8 samples can be calculated using 4 DFTs as shown below in the picture.

And again 2 DFT can be calculated as shown below.

Now the 8-point DFT can be computed with the following butterfly diagram.

From all these what is interesting is that for normal 8-point DFT we would require N² complex multiplication and N(N-1) complex addition. Whereas using FFT we only require (N/2)log₂N complex multiplication and Nlog₂N complex addition. This is way less! Due to this FFT can be employed in Digital processors to calculate and manipulate the discrete data. I’ll talk more on this later. Ciao!