On Oct 16, 4:19=A0pm, Eric Jacobsen <eric.jacob...@[EMAIL PROTECTED]
> wrote:
> On Thu, 16 Oct 2008 10:12:18 -0700 (PDT), "Steven G. Johnson"
>
>
>
>
>
> <stev...@[EMAIL PROTECTED]
> wrote:
> >On Oct 10, 3:42=A0pm, Eric Jacobsen <eric.jacob...@[EMAIL PROTECTED]
> wrote:
> >> I think it depends on the details of the resource issues. =A0 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. =A0 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. =A0Of 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. =A0
>
> >Not true. =A0FHTs 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. =A0Misses the point, though.
>
> Again, it's a bit more complicated than just counting how much memory
> is needed. =A0 How it's used can make a big difference, too. =A0
=A0Since
> 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. =A0 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. =A0 It's no surprise that in some
> cases one way or the other (FFT of FHT) may come out ahead compared to
> other cases. =A0 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. =A0 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 Communicationshttp://www.ericjacobsen.org
>
> Blog:http://www.dsprelated.com/blogs-1/hf/Eric_Jacobsen.php-
Hide quoted
=
text -
>
> - Show quoted text -
Hey Eric,
I recall Mot with the 56k series actually implemented a bit reversed
order mode for incrementing pointers, so the data can be read in and
out of the FFT's space directly. Pretty cool!! I used that feature and
it was quite nice.
Clay
|
