On Oct 20, 9:34=A0am, "VelociChicken" <b...@[EMAIL PROTECTED]
> wrote:
> >> Can you elaborate a little on this mysterious factor of two memory
use=
?
>
> There's no 'complex' array to be set up.
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
|
