On Oct 20, 5:21=A0pm, Eric Jacobsen <eric.jacob...@[EMAIL PROTECTED]
> wrote:
> Why is it so im****tant to you to make FHTs look inferior to FFTs? =A0
Straw man.
I never said FHTs were inferior. I said that the two are nearly
identical in every measurable respect, so far as is currently known---
no one has demonstrated any significant intrinsic advantage one way or
the other in terms of performance or memory utilization.
You, on the other hand, claimed "substantial" benefits in
"computational resources" for the FHT in some cir***stances for
unexplained reasons, including "substantial" memory savings.
> have the other as well. =A0 And either sin() or cos() can be folded so
> that much less than a full wave needs to be stored, and you can do
> that with cas() as well. =A0
No you can't do it with cas as well. That was my point: if you look
at the trig table of sin and cos values, they have twice as much
redundancy as a table of cas values (which has less symmetry), and
because of that the number of trigonometric constants is essentially
the same for an FHT or FFT.
>=A0Do you really think that there's never a difference?
I think that no one has demonstrated any substantial difference; the
only clear differences that have been demonstrated slightly favor FFTs
(but only slightly....a few flops saved is irrelevant in practice).
You were claiming "substantial" benefits in performance in memory, and
I was pointing out that, over the last 20 years, despite strenuous
efforts, there is zero evidence to sup****t your claim in any known
cir***stances, and plenty of evidence that the intrinsic differences
between the algorithms are negligible (and swamped by differences in
skill of implementors).
> FWIW, I've found several (recent) references where people are
> currently building generalized transform hardware based on FHT engines
> (kind of like Mayer did with his software). =A0 Since a generalized
> compression engine may need to do FFTs, FCTs, and FSTs, there are
> evidently advantages to just building a single FHT to do all of those
> tasks. =A0 Here's one reference:
>
>
http://ieeexplore.ieee.org/Xplore/defdeny.jsp?url=3D/iel5/4061132/40611..=
..
(You can do all of those functions using a real-data FFT, too.)
That paper doesn't actually try doing a real-data FFT and comparing it
to an FHT. In fact, the papers it cites as explanation for why they
chose to do an FHT are actually papers explaining just the opposite,
that real-data FFTs are just as efficient as FHTs and have similar
structure.
DHTs certainly have conceptual attractions. And the fact that the
same routine is its own inverse is sometimes convenient (the one
concrete reason cited by the paper authors for their choice).
If you had said, "I find the DHT conceptually nicer, and the fact that
it is its own inverse leads to some savings of code/gates in some
applications," I wouldn't have any objection. What bothered me is
your claiming "substantial" benefits in performance and that the
"memory requirement is substantially smaller", both of which claims
are contradicted by 20 years of work.
> For the constraints and optimizations in this case (and several are
> actually shown), the author found using an FHT as the basis
> advantageous.
None are shown; are we reading the same 2-page conference paper? The
timing numbers they re****t for FFT etc are worse than those for FHT,
but that's because they implemented the other transforms using an FHT
(hence with additional overhead). They didn't actually try comparing
to any intrinsic real-data FFT algorithm, so that paper really isn't
evidence one way or the other.
> 1) An all-hardware implementation, i.e., just hooking gates and things
> together to build a transformer. =A0
And what, precisely, do you see as the substantial "performance" and
"memory" advantages of an FHT in this cir***stance?
> 2) A hybrid platform where various processing, memory and logic
> elements are combined. =A0
And what, precisely, do you see as the substantial "performance" and
"memory" advantages of an FHT in this cir***stance?
> 3) A small embedded processor, perhaps with some limited, but
> inflexible, memory and limited computing ability.
And what, precisely, do you see as the substantial "performance" and
"memory" advantages of an FHT in this cir***stance?
> 4) An embedded DSP.
And what, precisely, do you see as the substantial "performance" and
"memory" advantages of an FHT in this cir***stance?
> 5) A generalized computing platform (e.g., a PC).
And what, precisely, do you see as the substantial "performance" and
"memory" advantages of an FHT in this cir***stance?
> Can you begin to see that each of these cases is quite different and
> optimized solutions for each might look quite different from each
> other? =A0
Of course they are different, but you still have yet to (correctly)
explain a clear concrete advantage for FHTs in performance or memory
in *any* cir***stance.
> If memory is tight and only chunks of
> certain sizes are available (and one is limited in how much area can
> be used for memory), then damn straight tootin' an FHT can have an
> advantage.
Why do you think that an FHT requires smaller chunks of data than a
real-data FFT?
> address generation can matter. =A0If pipelining is required for repeated
> transforms and multipliers are at a premium, then an FHT may have an
> advantage since the first two stages don't require any multiplication.
Clearly false. Real-data FFTs have been proven to require no more
multiplications than FHTs, and fewer additions (at least, for all
currently known algorithms).
> I can go on and on, but I hope you're starting to get the drift.
Nope, sorry, I'd like to see a concrete advantage explained in terms
of the differences between the transforms that you claim are so
significant. Not vague handwaving that "well, the two transforms
aren't EXACTLY identical, so there must be SOME cir***stance where
there is a substantial advantage for one or the other."
> almost always the way to go. =A0 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 merely think one should have clear evidence before blithely
contradicting 20 years of study in a field. An awareness of past work
is also good to have.
Regards,
Steven G. Johnson
|
