What Are Discrete Hartley Transforms?

Discrete Hartley transforms (DHTs) are real-valued, invertible linear transforms that map a finite sequence of real numbers to another real sequence of the same length using the kernel cas(x) = cos(x) + sin(x). Ronald N. Bracewell introduced the discrete form in 1983 as a sampled counterpart to the continuous Hartley transform proposed by Ralph V. L. Hartley in 1942. For a length-N input, the forward transform is the sum over n of x(n) cas(2pin*k/N), and the inverse is the same expression scaled by 1/N. That symmetry is the transform's defining practical advantage: one routine and one set of coefficients serve in both directions, and no complex arithmetic is required at any stage.

The DHT sits in the same family of orthogonal discrete transforms as the discrete Fourier transform (DFT), the discrete cosine transform, and the Walsh-Hadamard transform. It is most often reached for when the input is real, which covers most sampled physical signals, because it avoids storing and multiplying the imaginary parts that a complex DFT carries through the computation even when half of them are redundant.

Relationship to the Discrete Fourier Transform

For a real input sequence, the DHT and the DFT carry exactly the same information, and either can be recovered from the other by simple index arithmetic. The real part of the DFT is the even part of the DHT, and the negated imaginary part of the DFT is its odd part, so the Fourier amplitude and phase spectra follow from a single Hartley pass. The power spectrum is even more direct: it is proportional to the sum of the squares of X(k) and X(N-k). The convolution theorem takes a modified form, since the DHT of a circular convolution is not simply the product of the two transforms but a combination of even and odd terms. When one of the sequences is even symmetric, that combination collapses back to a plain product.

Fast Hartley Transform Algorithms

Bracewell paired the transform with a radix-2 decimation-in-time fast Hartley transform (FHT), and the algorithmic literature quickly filled in the rest of the family. The 1985 IEEE Transactions on Acoustics, Speech, and Signal Processing paper On computing the discrete Hartley transform showed that decimation-in-frequency, radix-4, split-radix, prime-factor, and Winograd constructions all transfer to the DHT, so the design philosophies developed for the FFT apply essentially unchanged. Arithmetic complexity is O(N log N), and because all intermediate values are real, an in-place FHT uses about half the working memory of a complex FFT of the same length. Careful comparisons, including the radix-2 fast Hartley transform analysis on arXiv, find that specialized real-input FFT algorithms usually match or slightly beat the best FHT operation counts, so the case for the DHT rests more on code simplicity, memory locality, and hardware regularity than on raw multiply-add totals.

Implementation and Multidimensional Forms

Production libraries expose the DHT as a real-to-real transform kind, as in the FFTW documentation for the discrete Hartley transform, which also flags a subtlety that trips implementers: applying one-dimensional DHTs along each axis of an array yields the separable product of transforms, which is not identical to the true multidimensional Hartley transform built from a single cas kernel of the summed arguments. Fixed-point and systolic realizations exploit the real kernel to build regular, pipelined arrays suited to VLSI, and the same regularity makes the FHT attractive on digital signal processors with limited data memory.

Applications

Discrete Hartley transforms have applications in a range of fields, including:

• Spectral analysis of real-valued sensor and instrumentation data
• Fast convolution and correlation in digital filtering
• Image coding, watermarking, and texture analysis
• Multicarrier communication, including Hartley-based OFDM variants
• Optical and interferometric signal processing
• Biomedical signal analysis, such as electrocardiogram feature extraction