What is FFT?
- We use N-point DFT to convert an N-point time domain sequence x(n) to an N-point frequency domain sequence x(k).
- The purpose of performing a DFT operation is so that we get a discrete-time signal to perform other processing like filtering and spectral analysis on it.
- However, the process of calculating DFT is quite complex.
- It requires NxN complex multiplications and N(N+1) complex additions.
- Cooley and Turkey were two mathematicians who came up with FFT – Fast Fourier Transforms. This is a method of calculating DFT a bit faster.
- To be precise, the FFT took down the complexity of complex multiplications from to .
- Thus, the FFT (Fast Fourier Transform) is nothing but a more efficient way of calculating the DFT (Discrete Fourier Transform).
- The FFT is basically two algorithms that we can use to compute DFT.
- Decimation in Time algorithm (DIT).
- Decimation in Frequency algorithm (DIF).
- The gist of these two algorithms is that we break up the signal in either time and frequency domains and calculate the DFTs for each and then add the results up.
- We have taken an in-depth look into both of these algorithms in this Digital Signal Processing course.
How can we use the FFT algorithm to calculate inverse DFT (IDFT)?
Check out the formulae for calculating DFT and inverse DFT below.
DFT: x(k) =
IDFT: x(n) =
As you can see, there are only three main differences between the formulae.
- In DFT we calculate discrete signal x(k) using a continuous signal x(n). Whereas in the IDFT, it’s the opposite.
- In the IDFT formula, we have two different multiplying factors.
- The factor 1/N
- The factor which is the complex conjugate of the twiddle factor .
- Thus if we multiply with a factor of 1/N and replace the twiddle factor with its complex conjugate in the DIF algorithm’s butterfly structure, we can get the IDFT using the same method as the one we used to calculate FFT.
- In this case, DIF and DIT algorithms are the same.
- We’ll see the modified butterfly structure for the DIF FFT algorithm being used to calculate IDFT.
- From the above butterfly diagram, we can notice the changes that we have incorporated. The inputs are multiplied by a factor of 1/N, and the twiddle factors are replaced by their complex conjugates.
How to calculate values of conjugate twiddle factor?
Calculating the complex conjugates of the twiddle factor is easy. Just invert the sign of the complex part of the non-conjugate values. The table below will help you understand it better.
|= 1||= 1|
|= 0.707-0.707j||= 0.707+0.707j|
|= -j||= j|
|= -0.707-0.707j||= -0.707+0.707j|
|= -1||= -1|
|= -0.707+0.707j||= -0.707-0.707j|
|= j||= -j|
|= 0.707+0.707j||= 0.707-0.707j|
|= 1||= 1|
What is Inverse Fast Fourier Transform (IFFT)?
This method of using the FFT algorithms to calculate Inverse Discrete Fourier Transform (IDFT) is known as IFFT (Inverse Fast Fourier Transform).