Posts tagged Signal Processing

How to Compute the IFFT using only the forward FFT

How can you calculate the IFFT (Inverse Fast Fourier Transform) using only the forward FFT (Fast Fourier Transform)? It is easier than you think! Read on to find out how.

  1. Cheat-Sheet: Just tell me how!
  2. Derivation of the Method

Cheat-Sheet: Just tell me how!

Let’s start with just saying straight out what you do. Take the input signal, let’s call it x, and take its complex conjugate. Then take the FFT of that result. Then take the complex conjugate again. Finally divide the resultant signal by N (the length of the signal). Here is the formula:

$$IFFT(X) = \frac{1}{N}conj(FFT(conj(X)))$$

Derivation of the Method

Hopefully you are also interested in the why! To start, let’s note that the FFT and DFT (Discrete Fourier Transform), and the IFFT and IDFT (Inverse Discrete Fourier Transform), are identical. The “Fast” in FFT and IFFT just means that the algorithm used to compute the DFT and IDFT is faster than a direct approach, but it still gives the same exact results.

The first thing we will need to do is to find out how the DFT and IDFT are related. Let’s write out the definitions:

$$DFT_N(x) = \sum_{n=0}^\infty x_n e^{-j\frac{2\pi n}{N}k}$$
$$IDFT_N(x) = \frac{1}{N} \sum_{n=0}^\infty X_k e^{j\frac{2\pi n}{N}k}$$
Notice that the only difference between the two is the scaling factor $\frac{1}{N}$ and the sign of the “j” in the exponential term. Using the complex conjugate, we can rewrite the exponential term in the DFT, and we will have:

$$DFT_N(x) = \sum_{n=0}^\infty x_n conj(e^{j\frac{2\pi n}{N}k})$$
This certainly looks more like the IDFT than it did before, but now we need some way to get rid of the complex conjugate. To do this we are going to use a property of complex conjugates:

$$conj(a) conj(b) = conj(ab)$$
So, let’s apply this property. But to do so, we need to first take the complex conjugate of $x_n$.

$$DFT_N(conj(x)) = \sum_{n=0}^\infty conj(x_n) conj(e^{j\frac{2\pi n}{N}k})$$
$$DFT_N(conj(x)) = \sum_{n=0}^\infty conj(x_n e^{j\frac{2\pi n}{N}k})$$
Now it’s time to apply another property of complex conjugates:

$$conj(a) + conj(b) = conj(a + b)$$
Using this property, we can pull the complex conjugate operator to the outside of the sum.

$$DFT_N(conj(x)) = conj(\sum_{n=0}^\infty x_n e^{j\frac{2\pi n}{N}k})$$
Now, take a look again at the definition of the IDFT posted at the start. The contents inside the conj() on the right hand side of the equation, match up with the definition of IDFT multiplied by a factor of N. So we can substitute it in.

$$DFT_N(conj(x)) = conj(N*IDFT_N(X))$$
From here, knowing that since N is real, conj(N) = N, and using some simple algebra, we can get to the final result.

$$DFT_N(conj(x)) = N conj(IDFT_N(X))$$
$$\frac{1}{N} DFT_N(conj(x)) = conj(IDFT_N(X))$$
$$\frac{1}{N} conj(DFT_N(conj(x))) = IDFT_N(X)$$
This is what we were looking for. Therefore we have shown that

$$IFFT(X) = \frac{1}{N}conj(FFT(conj(X)))$$