On Mon, 13 Oct 2008 15:53:19 +0100, "VelociChicken" <bob@[EMAIL PROTECTED]
>
wrote:
>
>"Richard Owlett" <rowlett@[EMAIL PROTECTED]
> wrote in message
>news:jcqdnanT_obeLHLVnZ2dnUVZ_qTinZ2d@[EMAIL PROTECTED]
>> Eric Jacobsen wrote:
>>> On Fri, 10 Oct 2008 13:37:42 -0400, Randy Yates <yates@[EMAIL PROTECTED]
>
>>> wrote:
>>>
>>>
>>>>Eric Jacobsen <eric.jacobsen@[EMAIL PROTECTED]
> writes:
>>>>
>>>>
>>>>>On Fri, 10 Oct 2008 11:54:52 -0500, Richard Owlett
>>>>><rowlett@[EMAIL PROTECTED]
> wrote:
>>>>>
>>>>>
>>>>>>julius wrote:
>>>>>>
>>>>>>>On Oct 9, 9:02 pm, Richard Owlett <rowl...@[EMAIL PROTECTED]
> wrote:
>>>>>>>
>>>>>>>
>>>>>>>>I'm interested in Magnitude vs Frequency.
>>>>>>>>I have a strictly Real input sequence.
>>>>>>>>There's Fast Hartley transform code available for my preferred
>>>>>>>>language.
>>>>>>>>Relative speed is not an issue as I'm working on stored data.
>>>>>>>>
>>>>>>>>What gotcha's should I watch out for?
>>>>>>>>Is the a good comparison on the web of their practical
differences?
>>>>>>>>
>>>>>>>>TIA
>>>>>>>
>>>>>>>
>>>>>>>Richard, maybe it's better if you tell us what your intended
>>>>>>>application
>>>>>>>is. Right now it sounds a bit like asking whether you should buy a
>>>>>>>sedan
>>>>>>>or a hatchback :-P. There will be lots of opinions, but they are
>>>>>>>worthless
>>>>>>>depending on your situation and application.
>>>>>>
>>>>>>Well, my app is about as simple as it gets.
>>>>>>I have a time sequence f(t) and I want a measure of abs(f(omega))
>>>>>>Signal so far has been audio, but don't think that bears on
question.
>>>>>>I'm not going to filter/process/... the transformed data, just plot
it.
>>>>>>I have been using an FFT so far.
>>>>>>I wish to change hardware/OS/etc.
>>>>>>There is existing FHT code that I can cut and paste.
>>>>>>Wikipedia article seemed to imply FHT lost favor to FFT when faster
FFT
>>>>>>algorithms were developed.
>>>>>
>>>>>Back when processing power and memory were hard to come by I used to
>>>>>use FHTs a lot. As you mention, they're very good when the input is
>>>>>real-valued, and if you only need the magnitude output for a plot
>>>>>it'll be pretty efficient.
>>>>>
>>>>>Since processing power and memory are cheap these days everybody just
>>>>>plugs in FFTs. When computing or memory resources are hard to come
>>>>>by, though, the FHT can have some real advantages.
>>>>
>>>>I thought that, when using the trick of an N-point FFT to get the
>>>>transform of 2 N-point real sequences, the FHT has no computational
>>>>advantage whatsoever over the FFT? But to answer Richard's question,
>>>>there's nothing wrong or disadvantageous in using it.
>>>
>>>
>>> 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.
>>>
>>> The output of the FHT can be problematic if you don't optimise for it,
>>> but, again, if you just want a magnitude spectrum or something it's
>>> pretty easy to pull it out of the native output vector, especially if
>>> a dual-****t is used for the output buffer.
>>>
>>> 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. Since memory is seldom a
>>> constraint these days it's pretty moot.
>>>
>>> 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.
>>>
>>> I'm not surprised that the FHT (and other things like it) are largely
>>> unknown since canned FFTs and the like are pretty easy to plug in.
>>>
>>
>> Canned is key feature. It's there for cut and pasting. There is a
canned
>> FFT, but it attempts to be all things to all people and the particular
FHT
>> was written when resources were scarcer.
>>
>> Thanks folks.
>>
>>
>>>
>>> Eric Jacobsen
>>> Minister of Algorithms
>>> Abineau Communications
>>> http://www.ericjacobsen.org
>
>Resources are always scarce, and of course the faster you do something,
the
>more of it you can do! Give your software the edge, especially in audio
DSP.
>People should stop thinking like Micro$oft - the "computers are faster,
so
>we'll make Windoze slower" mentality! ; )
>
>Despite the arguments on theory, I found FHT to be 50% faster than any
FFT
>code on the internet, so I use it. It's probably the cos/sin
approximations
>and that it uses half the memory, which helps the data cache and prep
time.
>
>Cheers,
>Dave
Yup, if you're careful about how you do things you can get some real
advantages. Some of my FHT experience was on my Amiga in grad school
when I was processing audio sensor data (i.e., real-valued), and coded
the whole thing in 68k assembly with LUTs for the cas() function. I
also had a hand-coded 68k-assembly FFT with LUT twiddles, and just
the buffer handling alone, with extra car paid to handling the input
buffer and forming the ouput magnitude vector provided a substantial
advantage with the FHT.
Operation count alone doesn't tell the whole story, but it's often the
only metric considered.
Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.ericjacobsen.org
Blog: http://www.dsprelated.com/blogs-1/hf/Eric_Jacobsen.php
|
