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

Rick LyonsJuly 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}$$

This article is available in PDF format for easy printing

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

Comments:

[ - ]
Comment by jithinrjOctober 8, 2015
Thanks for this article. #3 & #4 really inspire me to mathematically prove them.

To post reply to a comment, click on the 'reply' button attached to each comment. To post a new comment (not a reply to a comment) check out the 'Write a Comment' tab at the top of the comments.

Registering will allow you to participate to the forums on ALL the related sites and give you access to all pdf downloads.

Sign up
or Sign in