An Algorithm for the Fast Hartley Transform
, by Ronald F. Ullmann
The fast Fourier transform algorithm uses two properties of the discrete Fourier transform to decrease the number of computations. The first property is that the kernel for the Fourier transform is periodic. The second property is the shift rule, The shift rule of the Fourier transform states that shifting a function in the time domain corresponds to multiplying the function in the frequency domain by a complex exponential factor. The Hartley transform has similar properties to the Fourier transform. The Hartley kernel is periodic, and shifting a function in the time domain corresponds to the two multiplications in the frequency domain. Due to the properties of the discrete Hartley transform, a fast Hartley transform algorithm can be based on the algorithm of the fast Fourier transform. Since the fast Hartley transform can work with only real numbers, the transform requires half of the multiplication of a similar FFT. The transform and other operations in Hartley space take less computing time than corresponding operations in Fourier space.
STANFORD