Introduction to Fourier Transform
May 25, 2018
Fourier Series
In simple terms, Fourier Series provides us with the quantitative formula to derive the individual components from a mixture of things. For Example, Fourier Series can help us to extract unique frequencies from a signal.
Fourier Transform
Being an Electrical Engineer we were always taught Fourier transform in our DSP courses but while doing re-researching on Fourier Transform, I found that it’s applied in many facets of computer science including but not limited to:
- Applied in compression algorithms like MP3 compression.
- Divide and Conquer algorithms.
- Digital Signal Processing.
- Every Image can be made from circles and can be achieved by Fourier Transform.
- Image Processing.
- PiedPiper Lossless Compression. Yes! in PiedPiper.
Fast Fourier Transform
FFT was rated one of the top 10 algorithms of the 20th century by IEEE Computer Society. It has revolutionized the way Digital communication works and we can see the implementation of some form of FFT or other in modern digital communication systems like 4G LTE and 5G New Radio. In fact, FFT is the base of these systems where we convert the signal in time domain and convert to Frequency domain by FFT and vice versa by IFFT (Inverse Fast Fourier Transform)
So what is FFT, it’s an efficient algorithm to perform Discrete Fourier Transform or DFT. MIT actually has a Speedy algorithm which works faster in some scenarios than FFT. But overall FFT holds the crown of being Faster universally.