Info Catalog fftw3: Real even/odd DFTs (cosine/sine transforms) fftw3: More DFTs of Real Data

fftw3: The Discrete Hartley Transform

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

Info Catalog fftw3: Real even/odd DFTs (cosine/sine transforms) fftw3: More DFTs of Real Data