# Four Ways to Compute an Inverse FFT Using the Forward FFT Algorithm

July 7, 20151 comment

If you need to compute inverse fast Fourier transforms (inverse FFTs) but you only have forward FFT software (or forward FFT FPGA cores) available to you, below are four ways to solve your problem.

Preliminaries
To define what we're thinking about here, an N-point forward FFT and an N-point inverse FFT are described by:

$$Forward \ FFT \rightarrow X(m) = \sum_{n=0}^{N-1} x(n)e^{-j2\pi nm/N} \tag{1}$$ $$Inverse \ FFT \rightarrow x(n) = {1 \over N} \sum_{m=0}^{N-1} X(m)e^{j2\pi mn/N}$$

$$\qquad \qquad \qquad = {1 \over N} \sum_{m=0}^{N-1} [X_{real}(m) + jX_{imag}(m)]e^{j2\pi mn/N} \tag{2}$$

Inverse FFT Method# 1
The first method of computing inverse FFTs using the forward FFT was proposed as a "novel" technique in 1988 [1]. That method is shown in Figure 1.

Figure 1: Method# 1 for computing the inverse FFT
using forward FFT software.

Inverse FFT Method# 2
The second method of computing inverse FFTs using the forward FFT, similar to Method#1, is shown in Figure 2(a). This Method# 2 has an advantage over Method# 1 when the input $X(m)$ spectral samples are conjugate symmetric. In that case, shown in Figure 2(b), only one data flipping operation is needed because the output of the forward FFT will be real-only.

Figure 2: Method# 2 Processing flow: (a) standard Method# 2;
(b) Method# 2 when X(m) samples are conjugate symmetric.

The next two inverse FFT methods are of interest because they avoid the data reversals necessary in Method# 1 and Method# 2.

Inverse FFT Method# 3
The third method of computing inverse FFTs using the forward FFT, by way of data swapping, is shown in Figure 3.

Figure 3: Method# 3 for computing the inverse FFT
using forward FFT software.

Inverse FFT Method# 4
The fourth method of computing inverse FFTs using the forward FFT, by way of complex conjugation, is shown in Figure 4.

Figure 4: Method# 4 for computing the inverse FFT
using forward FFT software.

References
[1] Duhamel P., el al, "On Computing the Inverse DFT", IEEE Trans. on Acoustics, Speech, and Signal Processing, Vol. 36, No. 2, Feb. 1988.

Previous post by Rick Lyons:
Correcting an Important Goertzel Filter Misconception
Next post by Rick Lyons:
The Most Interesting FIR Filter Equation in the World: Why FIR Filters Can Be Linear Phase