FFT puzzle - convolution without an inverse FFT

This is a puzzle for those who know Fourier transform math.  Suppose you want to do a circular convolution of two complex-valued sequences A and B, each of length n.   It's well known that you can do it by:

  1. Use a forward FFT to transform A and B into sequences a and b respectively.
  2. Do elementwise multiplication of a and b.to generate a sequence c.
  3. Use a backward (inverse) FFT on c to get the product C=A*B

Now suppose you are stranded on a desert isle with a computer that does only forward FFTs.  Can you still do convolutions using a process similar to the above, without using a backward FFT?  How?

- Arch

For more complete information about compiler optimizations, see our Optimization Notice.

2 comments

Top
Arch D. Robison (Intel)'s picture

Yes, that is what I ended up doing. It reminded of a line from the song "Star Trekkin": "Only going forward 'cause we can't find reverse."

anonymous's picture

provided your computer can do lit'l more than FFT, you can do last step as follows:
IFFT(C) = 1/n * conjugate(FFT(conjugate(C)))

Add a Comment

Have a technical question? Visit our forums. Have site or software product issues? Contact support.