🚀 go-pugleaf

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.

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

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 subsets

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

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

brianw@microsoft.UUCP (Brian Willoughby) writes:

>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_. ...

>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.

I would like to point out that the FFT transform may be derived quite
simply from the FHT transform. Since you wanted all the phase info
contained in the FFT, you now have it. However, since FHT is computed
over real numbers and not imaginary numbers, the computation effort is
much less. To compute (in C) the FFT from the FHT is:

    for ( i =0 ; i < N/2; i++ )
    {
	FFT[ i ].real = FFT[ N-i ].real = (FHT[ I ] + FHT[ N-i ])/2.0 ;
	FFT[ i ].imag =
	    -( FFT[ N-i ].imag = (FHT[ I ] - FHT[ N-i ])/2.0 ) ;
    }

In a similar fashion, the FHT can be derived from the FFT so that the
inverse transform can be found:

    for ( i =0 ; i < N; i++ )
    {
	FHT[ i ] = FFT[ i ].real - FFT[ i ].imag ;
    }

And since the FHT is faster than the FFT, it is often faster to use
the FHT and convert than to actually compute the FFT of a data set.

-Allan G. Schrum

P.S. I tried to be acurate with the above equations, but if I made a
typo or other small error, please adjust flames to an appropriate
level :-)

-- 
Allan G. Schrum                 | Sign it? Without reading the fine print?
Digital Design, Inc.            |-----------------------------------------
3060 Business Park Drive        | (404) 447-0274
Norcross, GA 30071              | ...!gatech!rebel!didsgn!allan