steve+@andrew.cmu.edu (Stephen Webster) (10/04/89)
I believe the major distinguishing features between the FHT and the FFT are: * 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.) * Since you're only handling real data, you cut the number of multiplies in half; that is, you don't have to carry around a real and an imaginary part for each datum in the calculation. * What you actually get from the FHT is an asymmetric combination of the magnitude & phase of your input time waveform. Intuitively, one can see that the symmetry of the FFT in magnitude & phase means that you're doing "extra" calculations that you don't have to; the FHT exploits this. * This all means that the FHT is just great for finding power spectra (wherein you don't care about mag & phase separately). You _can_ convert the FHT output to magnitude & phase data, but the total number of calculations required is the same, or greater, than a good FFT. * FHT algorithms for finding power spectra are (generally) shorter than their FFT-based counterparts, while FHT algorithms for finding mag & phase are (generally) longer. * I think R.N. Bracewell has actually gone and patented the FHT, while the FFT is as public as the Pythagorean Theorem. I wish him the best of luck in enforcing that patent. -steve webster ITC/EE, CMU
kchen@Apple.COM (Kok Chen) (10/05/89)
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.
hvs@pender (H.V. Sorensen) (10/05/89)
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 *
******************************************************************************hjm@cernvax.UUCP (Hubert Matthews) (10/11/89)
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
george@gt-mach2.eedsp.gatech.edu (B. George) (10/11/89)
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!
floyd@smoke.BRL.MIL (Floyd C. Wofford) (10/12/89)
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?
gsh7w@astsun.astro.Virginia.EDU (Greg S. Hennessy) (10/12/89)
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