DSP Tricks: Computing inverse FFTs using the forward FFT
There are many signal processing applications where the capability to perform the inverse FFT is necessary. This can be a problem if available hardware, or software routines, have only the capability to perform the forward FFT. Fortunately, there are two slick ways to perform the inverse FFT using the forward FFT algorithm.
Inverse FFT Method #1. The first inverse FFT calculation scheme is implemented following the processes shown in Figure 13–14 below.
Figure 13–14. Processing for first inverse FFT calculation method.
To see how this works, consider the expressions for the forward and inverse DFTs. They are:
To reiterate our goal, we want to use the process in Eq. (13–51) to implement Eq. (13–52). The first step of our approach is to use complex conjugation.
Remember, conjugation (represented by the superscript * symbol) is the reversal of the sign of a complex number’s imaginary exponent—if x = ejø, then x* = e–jø. So, as a first step we take the complex conjugate of both sides of Eq. (13–52) to give us
One of the properties of complex numbers, discussed in Appendix A, is that the conjugate of a product is equal to the product of the conjugates. That is, if c = ab, then c* = (ab)* = a*b*. Using this, we can show the conjugate of the right side of Eq. (13–53) to be
Hold on; we’re almost there. Notice the similarity of Eq. (13–54) to our original forward DFT expression Eq. (13–51). If we perform a forward DFT on the conjugate of the X(m) in Eq. (13–54), and divide the results by N, we get the conjugate of our desired time samples x(n).
Taking the conjugate of both sides of Eq. (13–54), we get a more straightforward expression for x(n):
Inverse FFT Method #2. The second inverse FFT calculation technique is implemented following the interesting data flow shown in Figure 13–15, below.
Figure 13–15. Processing for second inverse FFT calculation method.
In this clever inverse FFT scheme we don’t bother with conjugation. Instead, we merely swap the real and imaginary parts of sequences of complex data. To see why this process works, let’s look at the inverse DFT equation again while separating the input X(m) term into its real and imaginary parts and remembering that ejø = cos(ø) + jsin(ø).
Multiplying the complex terms in Eq. (13–56) gives us
Equation (13–57) is the general expression for the inverse DFT and we’ll now quickly show that the process in Figure 13–15 implements this equation. With X(m) = Xreal(m) + jXimag(m), then swapping these terms gives us
The forward DFT of our Xswap(m) is
Multiplying the complex terms in Eq. (13–59) gives us
Swapping the real and imaginary parts of the results of this forward DFT gives us what we’re after:
If we divided Eq. (13–61) by N, it would be exactly equal to the inverse DFT expression in Eq. (13–57), and that’s what we set out to show.
Used with the permission of the publisher, Prentice Hall, this on-going series of articles on Embedded.com is based on copyrighted material from "Understanding Digital Signal Processing, Second Edition" by Richard G. Lyons. The book can be purchased on line.
Richard Lyons is a consulting systems engineer and lecturer with Besser Associates. As a lecturer with Besser and an instructor for the University of California Santa Cruz Extension, Lyons has delivered digitasl signal processing seminars and training course at technical conferences as well at companies such as Motorola, Freescale, Lockheed Martin, Texas Instruments, Conexant, Northrop Grumman, Lucent, Nokia, Qualcomm, Honeywell, National Semiconductor, General Dynamics and Infinion.