Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ncar!tank!eecae!netnews.upenn.edu!pender!hvs From: hvs@pender (H.V. Sorensen) Newsgroups: comp.dsp Subject: Re: Hartley xform Message-ID: <15129@netnews.upenn.edu> Date: 4 Oct 89 23:57:17 GMT References: Sender: news@netnews.upenn.edu Reply-To: hvs@pender (H.V. Sorensen) Organization: University of Pennsylvania Lines: 33 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 * ******************************************************************************