FFT-DFT
This page describes FFT-Fast Fourier Transform or DFT.
FFT refers to Fast Fourier Transform. There are several ways to calculate DFT i.e. Discrete Fourier Transform. FFT is one such method to calculate DFT. There are three main steps to perform FFT.
The FFT works by decomposition method. Decomposition is done for N point signal till each signal represent single time domain signal.
These N points of time domain signals are converted into a single frequency domain signal spectrum.
As mentioned Fast Fourier Transform is a discrete Fourier transform algorithm, which reduces the number of computation needed for N points from 2*square(N) to 2*N*log(N) which converts a sampled complex-valued function of time into a sampled complex-valued function of frequency. A discrete Fourier transform can be computed using an FFT, if the number of points N is a power of two.This rule is defined by Danielson Lanczos lemma. Which further mentions "a transform can be performed on sets of points corresponding to the prime factors of N,which is slightly degraded in speed".
The discrete Fourier transform of length N (where N is even) can be rewritten as the sum of two DFT, each of length N/2. One is formed from the even-numbered points; the other from the odd-numbered points. Denote the kth point of the DFT by Fn . Then
The basis of FFT is the divide-and-conquer approach in which the original N point sample is broken down into two N/2 sequences. This process is continued further till we obtain sequences having only 2 sample points as inputs. We now find DFT of these small sequences and then recombine their results to give the final FFT result.
FFT can be used in OFDM, Radar, Signal Processing, Modem, Magnetic resonance imaging (MRI),
Sound harmonic content.
For more information reader can refer book by title The Scientist and Engineer's Guide to Digital Signal
Processing, by Steven W. Smith, Ph.D. Chapter 8 describes DFT and Chapter 12 describes FFT.
Source code for 16 point in MATLAB can be downloaded from
our web site's Academic Section. DOWNLOAD the same. The source code does not use any built in matlab function hence can be used as a basis for higher FFTs for example 64 point FFT ,128 point FFT, 512 point FFT, 1024 point FFT and 2048 point FFTs used mainly in Wireless LANs and Wireless MANs.