ON COMPUTING THE DISCRETE HARTLEY TRANSFORM

The discrete Hartley transform (DHT) is a real-valued transform closely related to the DFT of a real-valued sequence. R. N. Bracewell (1984, 1985) has recently demonstrated a radix-2 decimation-in-time fast Hartley transform (FHT) algorithm. A complete set of fast algorithms for computing the discrete Hartley transform (DHT) is developed, including decimation-in-frequency, radix-4, split radix, prime factor, and Winograd transform algorithms. The philosophies of all common fast Fourier transform (FFT) algorithms are shown to be equally applicable to the computation of the DHT, and the fast Hartley transform (FHT) algorithms closely resemble their FFT counterparts. The operation counts for the FHT algorithms are determined and compared to the counts for corresponding real-valued FFT algorithms. The FHT algorithms are shown always to require the same number of multiplications, the same storage, and a few more additions than the real-valued FFT algorithms. Even though computation of the FHT takes more operations, in some situations the inherently real-valued nature of the DHT may justify this extra cost.