Chris@82: Previous: Real even/odd DFTs (cosine/sine transforms), Up: More DFTs of Real Data [Contents][Index]
Chris@82:If you are planning to use the DHT because you’ve heard that it is Chris@82: “faster” than the DFT (FFT), stop here. The DHT is not Chris@82: faster than the DFT. That story is an old but enduring misconception Chris@82: that was debunked in 1987. Chris@82:
Chris@82:The discrete Hartley transform (DHT) is an invertible linear transform
Chris@82: closely related to the DFT. In the DFT, one multiplies each input by
Chris@82: cos - i * sin (a complex exponential), whereas in the DHT each
Chris@82: input is multiplied by simply cos + sin. Thus, the DHT
Chris@82: transforms n real numbers to n real numbers, and has the
Chris@82: convenient property of being its own inverse. In FFTW, a DHT (of any
Chris@82: positive n) can be specified by an r2r kind of FFTW_DHT.
Chris@82:
Chris@82:
Chris@82:
Chris@82:
Like the DFT, in FFTW the DHT is unnormalized, so computing a DHT of
Chris@82: size n followed by another DHT of the same size will result in
Chris@82: the original array multiplied by n.
Chris@82:
Chris@82:
The DHT was originally proposed as a more efficient alternative to the Chris@82: DFT for real data, but it was subsequently shown that a specialized DFT Chris@82: (such as FFTW’s r2hc or r2c transforms) could be just as fast. In FFTW, Chris@82: the DHT is actually computed by post-processing an r2hc transform, so Chris@82: there is ordinarily no reason to prefer it from a performance Chris@82: perspective.5 Chris@82: However, we have heard rumors that the DHT might be the most appropriate Chris@82: transform in its own right for certain applications, and we would be Chris@82: very interested to hear from anyone who finds it useful. Chris@82:
Chris@82:If FFTW_DHT is specified for multiple dimensions of a
Chris@82: multi-dimensional transform, FFTW computes the separable product of 1d
Chris@82: DHTs along each dimension. Unfortunately, this is not quite the same
Chris@82: thing as a true multi-dimensional DHT; you can compute the latter, if
Chris@82: necessary, with at most rank-1 post-processing passes
Chris@82: [see e.g. H. Hao and R. N. Bracewell, Proc. IEEE 75, 264–266 (1987)].
Chris@82:
For the precise mathematical definition of the DHT as used by FFTW, see Chris@82: What FFTW Really Computes. Chris@82:
Chris@82:We provide the DHT mainly as a byproduct of some Chris@82: internal algorithms. FFTW computes a real input/output DFT of Chris@82: prime size by re-expressing it as a DHT plus post/pre-processing Chris@82: and then using Rader’s prime-DFT algorithm adapted to the DHT.
Chris@82:Chris@82: Previous: Real even/odd DFTs (cosine/sine transforms), Up: More DFTs of Real Data [Contents][Index]
Chris@82: