On Mon, 20 Oct 2008 14:21:09 -0700, Eric Jacobsen wrote:
> I can go on and on, but I hope you're starting to get the drift. For
> people who actually have to build things, being constrained by the
> availability and details of the building blocks makes one look much
> further than just academic papers and software library comparisons. All
> that being said, I don't think I've personally plugged in an FHT
> anywhere serious in at least fifteen years. As I said in my very
> first post in this thread, memory and processing is cheap enough these
> days that saving development time by plugging in a canned FFT is almost
> always the way to go. Evidently the difference between you and me is
> that I recognize that there are still those odd corner cases once in a
> while where the tradeoffs can go the other way.
I'm afraid that you still haven't made the case, at least to me. In
fact, a couple of your comments, specifically about wasted space,
irregularity of access pattern (i.e., address generator complexity) and
the bit about no multiplications in the first two p***** makes me think
that you haven't looked at an FFT algorithm in about as long as your FHT
experience. I'm not in Steven's league, but none of the FFT code that
I've written in the last several years has had much other than linear
memory addressing, and hasn't used multiplies in the first two p*****.
The first FFT machine that I encountered was indeed a VLSI device (the
Austek A41102.) It achieved it's good performance for the day by
streaming data in and out of DRAM chips with sequences of column-access
cycles. That was pretty quickly overtaken by Motorola DSP chips, though.
I suspect that a paraphrase of Steven's point (and, indeed my own
interest) is not to say that there's anything *necessarily* worse about
the FHT than the FFT (apart from the point that I make below), but that
in any given instance, it would seem likely that a technique that makes
the FHT faster could *also* be used to make the FFT faster. That's why
he's keen to find particular examples and insights of such corner cases.
Why are we computing a transform in the first place? Do we want to
analyse the power spectrum, or do we want to perform convolution
filtering, or some other purpose? It's been a while since I looked, but
my memory of the FHT has it requiring a bunch of additional sum/
difference operations on X_k and X_{N-k}, in order to perform either of
those operations. That's not a particularly attractive addressing
sequence, and a bunch of additional memory operations, to my eye.
Cheers,
--
Andrew
|
