>The same savings can be obtained for an FFT algorithm specialized for
>real inputs.
>
>Yes, if you have an FFT subroutine that takes n complex inputs and
>returns n complex outputs, then you would need to take your real
>inputs and convert them into a complex array with zero imaginary
>parts, requiring twice the storage. However, it's been observed since
>(I think?) the late 1960's that this factor of 2 is not necessary.
>
>Instead, there are a number of FFT algorithms specialized for real
>data that take a real array as input, and return half of a complex
>array as output (requiring the same storage as the real array, and
>possibly operating in-place). The reason you can do this is that the
>discrete Fourier transform of real inputs is half redundant: the
>second half is the complex conjugate of the first half, in reverse
>order.
>
>(Probably the most well-known such technique, although not generally
>the most efficient, is a trick to express a real-input DFT of length n
>in terms of a complex-input FFT of length n/2 plus some post-
>processing. An alternative technique is to start with a complex-data
>FFT algorithm, and go through the algorithm and prune out the
>redundant operations...again, you can save a factor of 2 in memory and
>slightly more than a factor of 2 in computation compared to the
>complex-input algorithm.)
>
>The existence of these real-input FFT algorithms is why all claims of
>factor-of-two savings from FHT algorithms were (at best!) very
>misleading, as was pointed out shortly after FHTs was introduced.
>Inexplicably, this mythical factor of two has persisted for an
>amazingly long time in the imaginations of engineers (and some
>unfortunate authors).
>
>Regards,
>Steven G. Johnson
Thank-you for your verbose and interesting reply. Is it possible to tell
me
which would actually be the best (fastest, and free) real-FFT that I can
test myself? I'm using Intel CPUs.
Thanks again,
Dave
|
