dg@lakart.UUCP (David Goodenough) (09/28/89)
Not too surprisingly, we're already talking about FFT, which logically has to be used in DSP. But does anyone know anything of FHT - the Fast Hartley Transform, which is supposed to do the same job as the FFT, but in about 1/2 the time. I have a reference to it _SOMEWHERE_ at home, but I'm curious to know what the general opinion of FHT is. -- dg@lakart.UUCP - David Goodenough +---+ IHS | +-+-+ ....... !harvard!xait!lakart!dg +-+-+ | AKA: dg%lakart.uucp@xait.xerox.com +---+
poser@csli.Stanford.EDU (Bill Poser) (09/29/89)
The Fast Hartley Transform is described in great detail in Ronald Bracewell's recent book _The Hartley Transform_. Mathematically, the Hartley transform is like the Fourier Transform but has a real kernel, that is, cos + sin instead of cos + i sin. It is therefore not the same as the Fourier Transform. However, the MAGNITUDE of the Hartley Transform is the same as that of the Fourier Transform. In the many cases in which one only cares about the magnitude, not the phase, the Fourier Transform may be replaced by the Hartley transform.
mhorne@ka7axd.wv.tek.com (Michael T.Horne) (09/29/89)
In a recent article by David Goodenough: > ...But does anyone know anything of FHT - the Fast Hartley Transform, which > is supposed to do the same job as the FFT, but in about 1/2 the time? The FHT is an interesting transform, saving you computation time by reducing the time to compute the DFT kernel (by avoiding a complex multiply/sum). However, there are techniques available for reducing the computation time for a normal FFT down to that of the FHT, such as (for real data sets) transforming two data sets of size N using a single N-point FFT, transforming a data set of size N using an N/2-point FFT, etc. In short, FFT techniques are available that minimize the purported computation-time advantage of the FHT. Mike
ted@nmsu.edu (Ted Dunning) (09/30/89)
In article <4755@orca.WV.TEK.COM> mhorne@ka7axd.wv.tek.com (Michael T.Horne) writes:
...
However, there are techniques available for reducing the
computation time for a normal FFT down to that of the FHT, such as
(for real data sets) transforming two data sets of size N using a
single N-point FFT, transforming a data set of size N using an
N/2-point FFT, etc. In short, FFT techniques are available that
minimize the purported computation-time advantage of the FHT.
see knuth. (as in all things).
--
ted@nmsu.edu
remember, when extensions and subsets are outlawed,
only outlaws will have extensions or subsetsbrianw@microsoft.UUCP (Brian Willoughby) (10/02/89)
In article <10471@csli.Stanford.EDU> poser@csli.stanford.edu (Bill Poser) writes: >The Fast Hartley Transform is described in great detail in >Ronald Bracewell's recent book _The Hartley Transform_. Mathematically, >the Hartley transform is like the Fourier Transform but has a real >kernel, that is, cos + sin instead of cos + i sin. It is therefore not >the same as the Fourier Transform. However, the MAGNITUDE of the >Hartley Transform is the same as that of the Fourier Transform. In the >many cases in which one only cares about the magnitude, not the phase, >the Fourier Transform may be replaced by the Hartley transform. For use in a one-way transform - perhaps to display frequency spectrum content of audio data - the FHT might be the choice. But, since HiFi audio is often discussed in this group, I wanted to point out that the phase information is necessary to accurately reconstruct the original signal. If the goal is to process the frequency domain data obtained from a Fourier Transform and then reconstruct a modified version of the original time domain data, it follows that a great deal of information would be lost without the phase of each frequency component. Brian Willoughby UUCP: ...!{tikal, sun, uunet, elwood}!microsoft!brianw InterNet: microsoft!brianw@uunet.UU.NET or: microsoft!brianw@Sun.COM Bitnet brianw@microsoft.UUCP
ingoldsb@ctycal.COM (Terry Ingoldsby) (10/03/89)
In article <698@lakart.UUCP>, dg@lakart.UUCP (David Goodenough) writes: > Not too surprisingly, we're already talking about FFT, which logically > has to be used in DSP. But does anyone know anything of FHT - the Fast > Hartley Transform, which is supposed to do the same job as the FFT, but There was a short article on the FHT in BYTE about 6 months ago (I can find it if you are interested). The following month a number of readers sent letters to the editor lambasting the article. As I recall the discussion the FHT is faster than the FFT for REAL (vs complex) data. There are well known techniques for doing the same thing with an FFT and getting a similar speed-up. -- Terry Ingoldsby ctycal!ingoldsb@calgary.UUCP Land Information Systems or The City of Calgary ...{alberta,ubc-cs,utai}!calgary!ctycal!ingoldsb
geoff@desint.UUCP (Geoff Kuenning) (10/04/89)
In article <TED.89Sep29150837@kythera.nmsu.edu> ted@nmsu.edu (Ted Dunning) writes: > see knuth. (as in all things). I wasn't aware of a discussion of FFT's in Knuth. It certainly isn't in my copies of Volumes 1 or 3. I don't have a copy of volume 2, because (despite its title) it is devoted primarily to random number generators. But I've read it (long ago) and don't recall FFT's there, either. Am I misremembering? -- Geoff Kuenning geoff@ITcorp.com uunet!desint!geoff
ted@nmsu.edu (Ted Dunning) (10/04/89)
In article <178@desint.UUCP> geoff@desint.UUCP (Geoff Kuenning) writes: In article <TED.89Sep29150837@kythera.nmsu.edu> ted@nmsu.edu (Ted Dunning) writes: > see knuth. (as in all things). I wasn't aware of a discussion of FFT's in Knuth. It certainly isn't in my copies of Volumes 1 or 3. I don't have a copy of volume 2, because (despite its title) it is devoted primarily to random number generators. But I've read it (long ago) and don't recall FFT's there, either. Am I misremembering? only slightly. actually volume 2 covers a great deal more than just random number generators and their evaluation. unfortunately i was misremembering, too. fft's are mentioned obliquely in several places in volume 2 in the context of multiplication. i don't think that any of the references are really very good introductions to the fft. ooooops. -- ted@nmsu.edu remember, when extensions and subsets are outlawed, only outlaws will have extensions or subsets