FFTW 3.3.5: The Discrete Hartley Transform

If you are planning to use the DHT because you’ve heard that it is cannam@127: “faster” than the DFT (FFT), stop here. The DHT is not cannam@127: faster than the DFT. That story is an old but enduring misconception cannam@127: that was debunked in 1987. cannam@127:

The discrete Hartley transform (DHT) is an invertible linear transform cannam@127: closely related to the DFT. In the DFT, one multiplies each input by cannam@127: cos - i * sin (a complex exponential), whereas in the DHT each cannam@127: input is multiplied by simply cos + sin. Thus, the DHT cannam@127: transforms n real numbers to n real numbers, and has the cannam@127: convenient property of being its own inverse. In FFTW, a DHT (of any cannam@127: positive n) can be specified by an r2r kind of FFTW_DHT. cannam@127: cannam@127: cannam@127: cannam@127:

Like the DFT, in FFTW the DHT is unnormalized, so computing a DHT of cannam@127: size n followed by another DHT of the same size will result in cannam@127: the original array multiplied by n. cannam@127: cannam@127:

The DHT was originally proposed as a more efficient alternative to the cannam@127: DFT for real data, but it was subsequently shown that a specialized DFT cannam@127: (such as FFTW’s r2hc or r2c transforms) could be just as fast. In FFTW, cannam@127: the DHT is actually computed by post-processing an r2hc transform, so cannam@127: there is ordinarily no reason to prefer it from a performance cannam@127: perspective.⁵ cannam@127: However, we have heard rumors that the DHT might be the most appropriate cannam@127: transform in its own right for certain applications, and we would be cannam@127: very interested to hear from anyone who finds it useful. cannam@127:

If FFTW_DHT is specified for multiple dimensions of a cannam@127: multi-dimensional transform, FFTW computes the separable product of 1d cannam@127: DHTs along each dimension. Unfortunately, this is not quite the same cannam@127: thing as a true multi-dimensional DHT; you can compute the latter, if cannam@127: necessary, with at most rank-1 post-processing passes cannam@127: [see e.g. H. Hao and R. N. Bracewell, Proc. IEEE 75, 264–266 (1987)]. cannam@127:

For the precise mathematical definition of the DHT as used by FFTW, see cannam@127: What FFTW Really Computes. cannam@127:

cannam@127:

Footnotes

cannam@127: cannam@127:

(5)

cannam@127:

We provide the DHT mainly as a byproduct of some cannam@127: internal algorithms. FFTW computes a real input/output DFT of cannam@127: prime size by re-expressing it as a DHT plus post/pre-processing cannam@127: and then using Rader’s prime-DFT algorithm adapted to the DHT.

cannam@127:

2.5.3 The Discrete Hartley Transform

Footnotes

(5)