Talk About Network

Google





Electronic Equipment > Digital Signal Processing (DSP) > Re: "Discrete H...
Latest [ Topics | Posts ] Archive Post A New Topic Post a Reply
<< Topic < Post Post 43 of 44 Topic 14030 of 14426
Post > Topic >>

Re: "Discrete Hartley transform" vs " Discrete Fouuier transform"

by "VelociChicken" <bob@[EMAIL PROTECTED] > Oct 21, 2008 at 01:46 PM

"VelociChicken" <bob@[EMAIL PROTECTED]
> wrote in message 
news:Nf5Lk.160694$ix.59555@[EMAIL PROTECTED]
> >The same savings can be obtained for an FFT algorithm specialized for
>>real inputs.
>>
>>Yes, if you have an FFT subroutine that takes n complex inputs and
>>returns n complex outputs, then you would need to take your real
>>inputs and convert them into a complex array with zero imaginary
>>parts, requiring twice the storage.  However, it's been observed since
>>(I think?) the late 1960's that this factor of 2 is not necessary.
>>
>>Instead, there are a number of FFT algorithms specialized for real
>>data that take a real array as input, and return half of a complex
>>array as output (requiring the same storage as the real array, and
>>possibly operating in-place).  The reason you can do this is that the
>>discrete Fourier transform of real inputs is half redundant: the
>>second half is the complex conjugate of the first half, in reverse
>>order.
>>
>>(Probably the most well-known such technique, although not generally
>>the most efficient, is a trick to express a real-input DFT of length n
>>in terms of a complex-input FFT of length n/2 plus some post-
>>processing.   An alternative technique is to start with a complex-data
>>FFT algorithm, and go through the algorithm and prune out the
>>redundant operations...again, you can save a factor of 2 in memory and
>>slightly more than a factor of 2 in computation compared to the
>>complex-input algorithm.)
>>
>>The existence of these real-input FFT algorithms is why all claims of
>>factor-of-two savings from FHT algorithms were (at best!) very
>>misleading, as was pointed out shortly after FHTs was introduced.
>>Inexplicably, this mythical factor of two has persisted for an
>>amazingly long time in the imaginations of engineers (and some
>>unfortunate authors).
>>
>>Regards,
>>Steven G. Johnson
>
> Thank-you for your verbose and interesting reply. Is it possible to tell

> me which would actually be the best (fastest, and free) real-FFT that I 
> can test myself? I'm using Intel CPUs.
> Thanks again,
> Dave

These graphs appear to show FHT in good favour:

http://www.geocities.com/ResearchTriangle/8869/fft_summary.html

Does anybody agree? I'm guessing the trig table and accuracy tradeoffs
have 
a big part to play in the results.
 




 44 Posts in Topic:
"Discrete Hartley transform" vs " Discrete Fouuier transform"
Richard Owlett <rowlet  2008-10-09 20:02:59 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
julius <juliusk@[EMAIL  2008-10-10 09:12:59 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
Richard Owlett <rowlet  2008-10-10 11:54:52 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
Eric Jacobsen <eric.ja  2008-10-10 10:15:02 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"Steven G. Johnson&q  2008-10-18 12:24:22 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
Eric Jacobsen <eric.ja  2008-10-18 23:07:56 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"Steven G. Johnson&q  2008-10-21 16:11:32 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
Eric Jacobsen <eric.ja  2008-10-21 16:54:37 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
Randy Yates <yates@[EM  2008-10-10 13:37:42 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
Eric Jacobsen <eric.ja  2008-10-10 12:42:23 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
Richard Owlett <rowlet  2008-10-10 14:48:45 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"VelociChicken"  2008-10-13 15:53:19 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
Eric Jacobsen <eric.ja  2008-10-13 15:08:36 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"Steven G. Johnson&q  2008-10-16 10:07:01 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"VelociChicken"  2008-10-19 15:41:35 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"Steven G. Johnson&q  2008-10-16 10:12:18 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
Eric Jacobsen <eric.ja  2008-10-16 13:19:36 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
Andrew Reilly <andrew-  2008-10-21 00:04:49 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
Eric Jacobsen <eric.ja  2008-10-20 18:48:06 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"Steven G. Johnson&q  2008-10-19 08:03:01 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"Steven G. Johnson&q  2008-10-19 08:14:36 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
Eric Jacobsen <eric.ja  2008-10-20 14:21:09 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"Steven G. Johnson&q  2008-10-16 10:17:13 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
clay@[EMAIL PROTECTED]   2008-10-16 14:07:55 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"Steven G. Johnson&q  2008-10-16 16:48:44 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
Eric Jacobsen <eric.ja  2008-10-17 11:41:23 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"Steven G. Johnson&q  2008-10-20 18:10:49 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
Eric Jacobsen <eric.ja  2008-10-21 00:32:58 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"Steven G. Johnson&q  2008-10-17 16:18:20 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"VelociChicken"  2008-10-18 00:46:48 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
Eric Jacobsen <eric.ja  2008-10-17 17:21:33 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"Steven G. Johnson&q  2008-10-21 11:30:46 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
Eric Jacobsen <eric.ja  2008-10-21 13:46:01 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"Steven G. Johnson&q  2008-10-18 12:03:16 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"VelociChicken"  2008-10-18 22:49:18 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"Steven G. Johnson&q  2008-10-18 16:15:55 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"Steven G. Johnson&q  2008-10-19 08:02:28 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
Andrew Reilly <andrew-  2008-10-19 22:05:34 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
Jerry Avins <jya@[EMAI  2008-10-19 18:19:41 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"VelociChicken"  2008-10-20 14:34:10 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"Steven G. Johnson&q  2008-10-20 11:46:09 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"VelociChicken"  2008-10-20 20:47:54 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"VelociChicken"  2008-10-21 13:46:55 
Re: "Discrete Hartley transform" vs " Discrete Fouuier transform
"Steven G. Johnson&q  2008-10-21 12:05:01 

Post A Reply:
  Go here to Signup

AddThis Feed Button


About - Advertising - Contact - Frequently Asked Questions - Privacy Policy - Terms of Use - Signup

Contact
localhost-V2008-12-19 Thu Jan 8 18:32:28 PST 2009.