Chris@19: Chris@19: Chris@19: The Discrete Hartley Transform - FFTW 3.3.4 Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19:
Chris@19: Chris@19:

Chris@19: Previous: Real even/odd DFTs (cosine/sine transforms), Chris@19: Up: More DFTs of Real Data Chris@19:


Chris@19:
Chris@19: Chris@19:

2.5.3 The Discrete Hartley Transform

Chris@19: Chris@19:

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

The discrete Hartley transform (DHT) is an invertible linear transform Chris@19: closely related to the DFT. In the DFT, one multiplies each input by Chris@19: cos - i * sin (a complex exponential), whereas in the DHT each Chris@19: input is multiplied by simply cos + sin. Thus, the DHT Chris@19: transforms n real numbers to n real numbers, and has the Chris@19: convenient property of being its own inverse. In FFTW, a DHT (of any Chris@19: positive n) can be specified by an r2r kind of FFTW_DHT. Chris@19: Chris@19: Like the DFT, in FFTW the DHT is unnormalized, so computing a DHT of Chris@19: size n followed by another DHT of the same size will result in Chris@19: the original array multiplied by n. Chris@19: Chris@19: The DHT was originally proposed as a more efficient alternative to the Chris@19: DFT for real data, but it was subsequently shown that a specialized DFT Chris@19: (such as FFTW's r2hc or r2c transforms) could be just as fast. In FFTW, Chris@19: the DHT is actually computed by post-processing an r2hc transform, so Chris@19: there is ordinarily no reason to prefer it from a performance Chris@19: perspective.1 Chris@19: However, we have heard rumors that the DHT might be the most appropriate Chris@19: transform in its own right for certain applications, and we would be Chris@19: very interested to hear from anyone who finds it useful. Chris@19: Chris@19:

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

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

Chris@19:
Chris@19:

Footnotes

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

Chris@19: Chris@19:
Chris@19: Chris@19: Chris@19: