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