DSPRelated.com
Blogs

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.



[ - ]
Comment by jithinrjOctober 7, 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.

Please login (on the right) if you already have an account on this platform.

Otherwise, please use this form to register (free) an join one of the largest online community for Electrical/Embedded/DSP/FPGA/ML engineers: