[comp.dsp] FFT space requirements

jgd@acl.lanl.gov (Jerry Glen Delapp) (03/16/90)

In article <3215@pur-phy> murphy@pur-phy (William J. Murphy) writes:

   Path: lanl!cmcl2!yale!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!cica!iuvax!noose.ecn.purdue.edu!mentor.cc.purdue.edu!pur-ee!pur-phy!murphy
   From: murphy@pur-phy (William J. Murphy)
   >Well perhaps.  But since there are *many* similar boards available for
   >a PC, I don't see why they would switch?
   >
   >JAV

   Let me give just one simple for instance why I would switch in a
   second (if I had the funds to buy a new system). Try doing an
   FFT on the PC that is 32K array of doubles.  Let's see that
   would be 256K for the signal and 256K twice for the returned
   arrays. (complex don't ya know) That makes 768K of data. Now
   consider what kind of crap you will have to use to program the
   EMS or EMM memory on the PC versus the simple act of mallocing
   on the Amiga and just doing the calculation?  That is enough
   reason for me.  I know, I have tried it on both, the Amiga
   worked without a hitch.  Now I am waiting to buy the 68030
   expansion card to make such a calculation feasible timewise.

If you don't mind a slightly strange format for storage, you can compute
the FFT in 256K for input and 256K for output, by performing a complex
FFT on the real data, followed by an unravel function. The trick is
that, in a real-to-complex FFT, the first and middle values of the
output both have zero imaginary component, and the second half is the
complex conjugate of the first half (in reverse order).  The method
described above doesn't store the second half since it's easily
generated from the first half, and uses the imaginary component of the
first value to store the real component of the middle value. I don't
remember the exact unravel calculation off the top of my head, but it
was no more complicated than a radix-2 FFT pass.

I think that this would allow you to wedge this calculation into memory
without resorting to EMS or EMM (until you wanted to unpack it). You can
still get the power spectrum from this format very easily.