FFT implementation

The Fourier transform and its reverse transform convert a signal from a time or space domain to a frequency domain and from the frequency domain to a time or space domain, respectively. These transforms are very important in electrical engineering, communication, geology, medicine and optics, and the list is endless. However, for speed, these transforms are optimised to run fast. This has led to many algorithms, amongst these being the fast Fourier transform (FFT) Cooley-Tukey algorithm, the prime-factor FFT algorithm and the split-radix FFT algorithm. This chapter introduces a derivation of an FFT algorithm and show its implementation. Any periodic signal represented by a function can be expressed by an infinite series of sines and cosines. A large amount of work has been devoted to reducing the computation time of a discrete Fourier transform (DFT). This has led to efficient algorithms known as FFT.