The fast Hartley transform

Abstract

A fast algorithm has been worked out for performing the Discrete Hartley Transform (DHT) of a data sequence of N elements in a time proportional to Nlog <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> N. The Fast Hartley Transform (FHT) is as fast as or faster than the Fast Fourier Transform (FFT) and serves for all the uses such as spectral analysis, digital processing, and convolution to which the FFT is at present applied. A new timing diagram (stripe diagram) is presented to illustrate the overall dependence of running time on the subroutines composing one implementation; this mode of presentation supplements the simple counting of multiplies and adds. One may view the Fast Hartley procedure as a sequence of matrix operations on the data and thus as constituting a new factorization of the DFT matrix operator; this factorization is presented. The FHT computes convolutions and power spectra distinctly faster than the FFT.