🚀 go-pugleaf

steve+@andrew.cmu.edu (Stephen Webster) writes:

>*   The FHT uses a purely real kernel (sin + cos) instead of the FFT's
>imaginary kernel (sin + j cos).  (Yes, ``j'', dammit.  I'm an engineer.)
 ^^^^^^^^^         ^^^     ^^^

But... even engineers use (cos + i sin) as the kernel instead of
(sin + i cos), I hope!  :-) :-) :-)  And, don't forget the real part of
the complex kernel.

I.e., exp(0) = 1, not sqrt( -1 ).

Regards (from an engineer),

Kok Chen			kchen@apple.COM
Apple Computer, Inc.
-- 
----
Kok Chen			kchen@apple.COM
Apple Computer, Inc.

Let me straighten things out here. It has been proven in several research
papers that the FHT transform always ALWAYS require N-2 (N-1 if N is odd) more
additions, but the same number of multiplications as the comparable FFT
algorithms (i.e. if compare a radix-4 FHT to a radix-4 FFT, a prime-factor FHT
to a prime-factor FFT etc). There exist a hybrid FHT/FFT algorithm, which
computes only requires 2 more additions for computing the FHT spectrum (same
number of multiplications), but it actually achieve the improvement from the
FFT. This statement holds true irrespective or the input data being real or
complex (yes the FHT can handle complex data).
For people interested in checking:
  The best length-N radix-2 Hartley transform for real input data requires
      3/4 * N log(N) - 5/2 * N + 4 multiplications
      7/4 * N log(N) - 5/2 * N + 4 addittions
		
and the best length-N radix-2 FFT for real input data requires
      3/4 * N log(N) - 5/2 * N + 4 multiplications
      7/4 * N log(N) - 7/2 * N + 6 additions

Exactly a difference of N-2 additions. As a matter of fact given a FHT
program, by removing an addition in one butterfly (which is executed N-2
times) and changing the input and output to the butterflies around a little,
one ends up with a FFT. And similarly a FFT can ealisy be converted into a FHT.

The FHT has only advantage over the FFT as far as I can see: The forward and
inverse FHT transforms are alike (except for the 1/N scaling factor) which is
not the case for the FFT.

Henrik Sorensen, Univ. of PA

******************************************************************************
*   Henrik Sorensen               Department of Electrical Enginering        *
*   Internet: hvs@ee.upenn.edu    University of Pennsylvania                 *
******************************************************************************

What's all the fuss about?  Unless I'm much mistaken (and I don't
think I am :->), this property of the FT is well known.  If you take
the FT of purely real data, you get a transform that is Hermitian: the
real part of the transform is symmetrical about zero, and the
imaginary part is asymmetrical.  Thus, you need store only half of
each part of the transform, as the other half may be deduced using
symmetry.

This is exactly how the NAG library FFT routine for real input data
returns the result.  It sounds like Bracewell is patenting common
knowledge.

-- 
Hubert Matthews      ...helping make the world a quote-free zone...

hjm@cernvax.cern.ch   hjm@vxomeg.decnet.cern.ch    ...!mcvax!cernvax!hjm

In article <1115@cernvax.UUCP> hjm@cernvax.UUCP (Hubert Matthews) writes:

>  If you take
>the FT of purely real data, you get a transform that is Hermitian: the
>real part of the transform is symmetrical about zero, and the
>imaginary part is asymmetrical.
                   ^^^^^^^^^^^^
Antisymmetrical, actually (yeah, I know, it's a nitpick :->).

-Bryan George

The opinions expressed herein are the author's and
do not reflect those of his computer.

BTW, FYI, IMHO acronyms are a pain!

In article <1115@cernvax.UUCP> hjm@cernvax.UUCP (Hubert Matthews) writes:
>
>It sounds like Bracewell is patenting common knowledge.

I don't know if it is common knowledge that the Fourier Transform
of real data is Hermitian but Bracewell shows a pretty picture of that
fact in his 1965 book "The Fourier Transform...".  He has other pretty
pictures of symmetry properties on page 15.

I wonder if he knew that?

In article <11261@smoke.BRL.MIL> floyd@brl.arpa (Floyd C. Wofford) writes:
#I don't know if it is common knowledge that the Fourier Transform
#of real data is Hermitian but Bracewell shows a pretty picture of that
#fact in his 1965 book "The Fourier Transform...".  He has other pretty
#pictures of symmetry properties on page 15.
#
#I wonder if he knew that?

Considering the number of times he refers to it in the text, I would
say he was. The property of a FT of real data being Hermitian IS
pretty common knowledge.


-Greg Hennessy, University of Virginia
 USPS Mail:     Astronomy Department, Charlottesville, VA 22903-2475 USA
 Internet:      gsh7w@virginia.edu  
 UUCP:		...!uunet!virginia!gsh7w