I was doing a bit of research on FFT and I came across this paper. According to it, computing the Fourier Transform using FHT is significantly faster than other methods, even for complex data. Yet, from what I gathered so far, the FHT method is rarely used. Why is that?

  • $\begingroup$ Paper is from 1997 - maybe there have been other developments in the 20 years since ? $\endgroup$
    – Paul R
    Jun 14 '17 at 16:11
  • $\begingroup$ "the DHT was originally proposed by R. N. Bracewell in 1983 as a more efficient computational tool in the common case where the data are purely real. It was subsequently argued, however, that specialized FFT algorithms for real inputs or outputs can ordinarily be found with slightly fewer operations than any corresponding algorithm for the DHT (see below)." $\endgroup$
    – endolith
    Jun 14 '17 at 18:11
  • $\begingroup$ Against FFTW or CUDA FFT would be a more topical comparison $\endgroup$
    – user28715
    Jun 14 '17 at 21:46

Basically, it isn't true. A Fourier transform making use of the symmetries of real-valued original data is just as computationally efficient. Also you can "pack" two independent sets of real data into one complex transform (one in the real part, one in the imaginary), then use symmetry relations to recover the respective two transforms.

The Hartley transform butterfly operation requires working with more input and output operands than the Fourier transform butterfly once the "twiddle factor" becomes smaller. Basically you have have two forward indexed data sets and two backward indexed data sets flowing into two butterflies in order to get two forward and two backward indexed data sets out in-place.

So all in all, the number of operations does not become less as soon as your algorithms make use of the "real input data" criterion, and the indexing logic is a lot less transparent. It's similar with the convolution theorem: applying it to Hartley transform data does not really save operations, you need to work with forward/backward address pairs and the algebraic operations are more tenuously related to the analytic relations of the Fourier transform than if you work with FFT right away (possibly including the Hermitian properties of a real-valued original transform pair).

The data representation is nicer if you want to work with only the non-redundant elements of a transform of purely real-valued original data (packing the real-valued $f_0$ and $f_{N/2}$ into one complex data element is ugly when storing non-redundant FFT data). Indeed, considering the Hartley transform as a dual storage representation of FFT (basically even for complex original data, $H(k) = \frac12 (F(k)+F^*(-k))$ if I remember correctly) at each stage of computation is one of the more straightforward ways to figure out a DHT step by step.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.