On Thu, 16 Oct 2008 10:12:18 -0700 (PDT), "Steven G. Johnson"
<stevenj@[EMAIL PROTECTED]
> wrote:
>On Oct 10, 3:42 pm, Eric Jacobsen <eric.jacob...@[EMAIL PROTECTED]
> wrote:
>> I think it depends on the details of the resource issues. The FHT is
>> nice from a memory perspective if the input is real-valued since you
>> don't have to do any buffer manipulation, whereas with an N/2-pt FFT
>> you may need to fiddle with the appropriate buffering/addressing to
>> arrange the input properly. Similar issue with the output.
>
>Nope, there is no intrinsic implementation advantage of an FHT that
>I'm aware of; we looked carefully at this issue when working on FFTW.
>(Sorensen in 1987 showed that there are real-valued FFT algorithms
>that have a very similar structure to FHT algorithms. Of course, all
>of this is a bit moot because highly optimized FFT codes these days
>look a lot different from the 1960s-1980s radix-2 and split-radix
>algorithms.)
>
>> In my experience the real advantage of the FHT was the memory
>> requirement, which can be substantially smaller than an FFT depending
>> on the constraints and what you're doing.
>
>Not true. FHTs and real-input FFTs have essentially the same memory
>requirements (obviously depending upon the implementation, but there
>is no intrinsic advantage one way or the other).
>
>> Another potential memory saving is in the twidlle factors, since the
>> FHT has a single reference function [cas()], instead of sin() and
>> cos().
>
>Nope, there's no savings here either, because if you count carefully
>you'll discover that you need half as many (sin,cos) pairs as cas
>functions, so the number of constants balances out.
>
>Steven
Nice. Misses the point, though.
Again, it's a bit more complicated than just counting how much memory
is needed. How it's used can make a big difference, too. Since
the FHT can directly take the real-valued input buffer in the time
order in which it is presented, there can be an advantage depending
(again) on the implementation and what you're trying to do. The same
is true on the output, the same is true in the way that the twiddle
tables are used.
Things like incrementing a pointer into a memory is easier (and
typically faster) than manipulating an address via a computation. That
can make a significant difference and isn't reflected by just
analyzing memory sizes.
It's the usual thing of trying to optimize the tradeoff spaces for
anything...the details may matter. It's no surprise that in some
cases one way or the other (FFT of FHT) may come out ahead compared to
other cases. It's already been acknowledged multiple times in this
thread that the differences are likely to be small, but there are
differences and (surprise) depending on the application one may turn
out to be better than the other.
And optimizing transforms for computation on a CPU is only relevant to
comparisons on that CPU. I'm looking at it far more generically, as
the sorts of applications where the difference may matter may not be
run on a CPU or DSP at all.
Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.ericjacobsen.org
Blog: http://www.dsprelated.com/blogs-1/hf/Eric_Jacobsen.php
|
