On Sun, 19 Oct 2008 08:14:36 -0700 (PDT), "Steven G. Johnson"
<stevenj@[EMAIL PROTECTED]
> wrote:
>On Oct 19, 2:07 am, Eric Jacobsen <eric.jacob...@[EMAIL PROTECTED]
> wrote:
>> 'Substantial' is in the eye of the beholder, and the context matters,
>> as I've tried to repeatedly explain. I'm not interested in going
>> down a road that seems to me to be clearly headed to the usual
>> semantic nit-picking.
>
>In other words, you're not up to giving any actual evidence for your
>claim; it sounds like this thread is at an end, since you've resorted
>to innuendo and ad hominem attacks in place of rational arguments.
W T F?
What innuendo and ad hominem?
You seem to be taking this pretty personally. Why is it so im****tant
to you to make FHTs look inferior to FFTs? As I mentioned a couple
of times now, but which you have not addressed, unless you want to
claim that the FFT is always, in all cir***stances, superior to the
FHT (and I still don't know whether that's your position or not),
there really isn't any argument here.
I am absolutely not claiming that the FHT has any sort of general
"superiority" over the FFT and I've tried to be clear about that.
Since the transforms are different, and I hope you understand that
they are, those differences can be exploited in certain cir***stances
to provide a benefit. Again, as I've mentioned previously, that's to
be expected. Where there are differences one can exploit them to
one's advantage. That's what engineers do.
Assuming, of course, they're aware of the various tools and their
differences.
>> I will also say that I've given quite a few hints as to where one can
>> find certain advantages and under what conditions.
>
>The problem is that all your hints were demonstrably incorrect.
I disagree.
>You
>claimed that FHTs require half the size of the trig tables, which I
>explained is false.
Where did I claim that? I don't believe that to be true, so I
wouldn't have claimed it to be so. I did say,
"Another potential memory saving is in the twidlle factors, since the
FHT has a single reference function [cas()], instead of sin() and
cos(). Clearly it just depends on how you're trying to get it
implemented. These sorts of things only come into play if your'e
really tight on certain resources, but it can make a big difference in
the right cir***stances."
That does NOT imply that using cas() as a basis function takes half
the memory of cos() and sin(). I think even the least experienced
among us knows that if you have either of a sin() or cos() LUT, you
have the other as well. 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. How those memories are accessed in a
transform is different between the FFT and FHT, though, and that can
matter.
The last quoted sentence above should have made it clear that I'm not
claiming there's a large difference (certainly not a factor of two!),
and that it takes the "right cir***stances" to get a benefit. Do you
really think that there's never a difference? I'll try to illuminate
a bit more below, but the gist of what I was trying to say was that
there are certain architectures where the single real-valued basis
function of the HT can be exploited to reduce complexity.
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). 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. Here's one reference:
http://ieeexplore.ieee.org/Xplore/defdeny.jsp?url=/iel5/4061132/4061133/04061261.pdf?isnumber=4061133&prod=CNF&tp=x&arnumber=4061261&arSt=794&ared=795&arAuthor=P.+John+Paul%3B+P.N.+Girija&htry=16&code=21
For the constraints and optimizations in this case (and several are
actually shown), the author found using an FHT as the basis
advantageous.
That's really just a single example of the only small point I've had,
to which you seem to take extreme exception, that there do, in fact,
exist cases where the FHT can have an advantage. I've readily stated
that the advantage is usually small and only under certain
constraints, but there can be an advantage. Why you find that so
objectionable seems very curious.
> You claimed that FHTs have simpler or more
>regular memory access patterns, or that real-data FFTs require
>additional reorderings of the array, which was shown to be false 20
>years ago by Sorensen (he presented real-data FFT algorithms that have
>the same sort of memory access pattern as comparable FHT, and require
>the same number of p*****/reorderings).
I didn't claim that in the generic sense that you seem to be implying.
I think the problem here is that you don't understand my arguments. I
suspect your perspective is from the case of just performing
transforms in software via an HLL on a generalized computing platform,
and from my perspective that's the LEAST interesting case. So your
anxiety is perhaps from interpreting my statements from that
perspective, which could lead to some misconceptions since I'm looking
more broadly.
Since this seems to be a Big Thing to you, I'll try to help illuminate
it a bit better. Perhaps your horizons will be broadened, perhaps
not, so take it FWIW. But please do understand that sometimes people
try to do transforms via means other than a C or other HLL program
running on a processor somewhere. I tried previously to explain
that, but since it didn't seem to make it from here all the way to
there I'll try to be a bit more explicit.
There are a few scenarios that I think are relevant and exemplary:
1) An all-hardware implementation, i.e., just hooking gates and things
together to build a transformer. There'll likely be input and output
buffers, perhaps additional processing buffers, computation logic,
control logic, address generation logic, etc., etc. To generalize a
little bit this case can include silicon targets (i.e., to be fabbed
on a chip), or FPGA targets, or similar connections of primitive
building blocks.
2) A hybrid platform where various processing, memory and logic
elements are combined. This could be packaged memory with something
like an ALU and control logic. The main difference to case one could
be considered to be the granularity of the primitives, e.g., a
packaged memory rather than a more flexible block, an ALU rather than
parameterized adders and multipliers.
3) A small embedded processor, perhaps with some limited, but
inflexible, memory and limited computing ability.
4) An embedded DSP.
5) A generalized computing platform (e.g., a PC).
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? If your claim is that what works in case 5) should work in
all of the above cases then I think you're the one who needs to do
some pretty significant substantiating of claims. I don't even
necessarily buy the idea that the FFT is always superior in all
situations for case 5), especially when processing and/or interface
memory constraints may be involved, but I think the point there is way
too fine to argue either way.
I don't think it practical to fully analyze tradeoffss applicable to
all of the cases described, though (and that's been part of my point)
since the details of the constraints even in just case 1) alone may
lead to a very different approach just based on those details. The
availability of memory primitives can make a big difference; if, as
is often the case, one can get a dual ****t for the same resource and
cost utilization as a single ****t, that changes the game. If one
wants to optimize power consumption rather than area, that can change
the game. If one does not have multipliers available (as is still
the case in many FPGAs) then that can change the game.
Since the FHT does, in fact, have differences between it and the FFT,
such details may be significant to an implementer given certain
constraints that can exist. 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. Moving data in and out of limited memory efficiently can
be very different between the two, and how many instances can be
populated, how many ****ts, and how much hardware can be dedicated to
address generation can matter. If 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.
At a former employer back in ancient times when our FFT engines were
12"x12" circuit boards built with through-hole parts, the transform
algorithms that use only FIFO memories were attractive in order to
reduce the control and address generation hardware requirements. Those
sorts of tradeoffs change substantially every time the part library
changes.
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.
Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.ericjacobsen.org
Blog: http://www.dsprelated.com/blogs-1/hf/Eric_Jacobsen.php
|
