2
$\begingroup$

Can you explain to me in what way Hartley Transform differs from Fourier Transform? Is it even used today or is it some mostly forgotten, obsolete archaic thing?

Please don't use equations - I dont understand them, but I understand Fourier Transform.

$\endgroup$
4
  • 2
    $\begingroup$ " I dont understand them, but I understand Fourier Transform." no, you don't. The Fourier transform is an integral transform that you can only understand if you've handled the equations. If you're somehow confronted with multiple transforms, I'm 100% sure you'll need to be able to understand the equations behind both transforms. $\endgroup$ – Marcus Müller Oct 8 '16 at 18:15
  • 5
    $\begingroup$ I'm voting to close this question as off-topic because it's pretty much impossible to explain the difference between two closely-related integral transforms without using equations. Even without that restriction, the question is too broad and doesn't show research effort. $\endgroup$ – Marcus Müller Oct 8 '16 at 18:18
  • $\begingroup$ SE.DSP wishes you a happy new year, with a reminder that your question and its answers may require some action (votes, acceptance, etc.) $\endgroup$ – Laurent Duval Dec 31 '16 at 16:22
  • $\begingroup$ @MarcusMüller this is math and you have to understand math. However, the greater battle is not between those who can handle equations - this is mostly by rote and there is no way to know that a mind understands that handling. Rather, the understanding is shown by those who don't just handle and teach math, but who implement it. The author may well have implemented FT and I would urge some respect for this, because only implementing gets your BS tested. $\endgroup$ – Henrik Erlandsson Jan 8 at 21:30
6
$\begingroup$

You are probably interested in the real discrete transforms. Here are the basis functions for a transform of length 6. The inverse transforms are weighted sums of these basis functions, and the forward transform figures out the weights given the time domain sequence. A reconstruction of the time domain sequence by the inverse transform is exact. The discrete transforms don't actually involve the continuous functions shown below but rather their samples at integer time indices (here 0, 1, 2, 3, 4, 5).

As a service to those who prefer to see equations, the discrete Hartley transform $H_k$ and discrete Fourier transform $X_k$ of $x_k$, where $k = 0, \dots, N-1$ are defined by:

$$H_k = \sum_{n=0}^{N-1} x_n \left[ \cos \left( \frac{2 \pi}{N} n k \right) + \sin \left( \frac{2 \pi}{N} n k \right) \right]\\ X_k = \sum_{n=0}^{N-1} x_n \left[ \cos \left( \frac{2 \pi}{N} n k \right) - i \sin \left( \frac{2 \pi}{N} n k \right) \right],$$

where $i$ is the imaginary unit.

Hartley

Hartley basis functions
Figure 1. Hartley transform basis functions are harmonic sinusoids. Each basis function is a sum of sine and cosine.

Being harmonic means that the frequency of each is an integer multiple of the lowest non-zero frequency. Some of the sinusoids have frequency greater than the Nyquist frequency.

Or as discrete sequences: [1, 1, 1, 1, 1, 1] (yellow), [1, 1.366, 0.366, -1, -1.366, -0.366] (black), [1, 0.366, -1.366, 1, 0.366, -1.366] (green), and so on.

Hartley basis functions, aliased
Figure 2. Hartley basis functions, constructed from the discrete basis functions by perfect bandlimited interpolation assuming that the sequences repeat forever. The discrete Hartley transform could alternatively be expressed directly with these functions, colored the same as in Fig 1.

Except for the special cases of frequency 0 and π, the aliased Hartley basis functions come in pairs of harmonic equal frequency sinusoids that are 90 degree apart, just like in the real discrete Fourier transform below. Except for scaling and phase shifts (with one scaling constant and one phase shift constant for each pair), the basis functions are identical to those of the real discrete Fourier transform.

Fourier

Real Fourier basis functions
Figure 3. Real discrete Fourier transform basis functions are harmonic cosines and sines, here colored the same as the equivalent scaled and phase-shifted Hartley basis functions in Fig. 2.

For frequencies 0 and π there are no sine basis functions because their samples would be zero-valued and would never contribute to the weighted sum in the inverse tramsform. Unlike with the Fig. 1 formulation of Hartley transform, the discrete Fourier transform basis functions stay within the Nyquist frequency limit.

Popularity of Hartley

The fast Hartley transform algorithm came out in 1984, but there has been no significant increase in its popularity since.

Google Ngram of Hartley transform
Figure 4. Google Ngram of Hartley transform counts the relative frequency of the word pair in literature as it developed over the years.

$\endgroup$
1
  • $\begingroup$ Google (and most search engines) doesn't use word pairs, or exact searches, deplorably. However, on equal terms here's the Ngram for Fourier Transform. books.google.com/ngrams/… $\endgroup$ – Henrik Erlandsson Jan 8 at 22:24
4
$\begingroup$

You are lucky if you do understand the Fourier transform; I still don't (caveat emptor).

Assuming a certain classical sign convention (i.e. a $e^{-ift}$ vs a $e^{ift}$ kernel, a change of convention won't change the properties), for a real signal, the discrete Hartley transform (DHT) is the sum of the real and the imaginary part of the discrete Fourier transform (DFT). In other words, it corresponds to the function: $a+ib \mapsto a+b$.

It is purely real, it is an involution, so it is its own inverse. It seems to still be in use for some coding, encryption or watermarking applications, where the use of real transforms can be simpler, while keeping some of the DFT nice properties (with respect to convolution for instance).

While in general it has been found to be no faster than FFT (see Fast Hartley Transform Implementation in MATLAB), it can be embedded into the same parametric family (New Parametric Discrete Fourier and Hartley Transforms, and Algorithms for Fast Computation, 2011). For some specific hardware, data or data size, it may still be found beneficial. Looking back, it has been used for the Fast computation of discrete cosine transform through fast Hartley transform by Henrique (Rico) Malvar. I suspect that the Hartley transform may have shed some insights into the development of the Lapped Orthogonal Transform (LOT).

Although quite forgotten, it may rise again some day.

$\endgroup$
2
  • 2
    $\begingroup$ "I still don't" <- same here. If I happen to end up with too much spare time on my hands, I might do some functional analysis, ~ theory and group theory... and knowing that those people that took matching courses during their math studies have less of a practical understanding of the FT ("huh, you use that for what? What's frequency? It was just one of the examples on one of our exam sheets for the less interesting class of linear integral transforms..."), I probably still won't understand it, just more of its structural foundation... $\endgroup$ – Marcus Müller Oct 9 '16 at 4:24
  • 1
    $\begingroup$ I am glad not being alone in such a gross coming-out. Without the appropriate level in maths, I am becoming semi-Platonist. Some tools might be unreasonably efficient because of intricate relationships pertaining to analysis, algebra or topology. If I have a lot of free time, I will dive into category theory, to take a step above the landscape, and see what emerges $\endgroup$ – Laurent Duval Oct 9 '16 at 8:17
3
$\begingroup$

You're right, it isn't very common. There are many Fourier-related transforms, most of which have a niche application.

It has the advantage that there are no imaginary numbers, and the forward and inverse transforms are the same. But the disadvantage is that for practical problems (such as modulation), you will have additional terms being summed that make it more cumbersome.

Here is a relatively non-mathy article describing the history of both transforms, written by the author of a fast Hartley transform algorithm. Perhaps this will help shed some light on this for you!

$\endgroup$
0
1
$\begingroup$

You are asking to understand this in the context of an implementation for signal processing, which requires an explanation based on programming. Ever the two worlds. Math has to work on paper and in reading minds, programmed implementations has to work in the world.

Because I read the 1988 Byte article, I searched just now and found [an article that mentioned it][1], and compared FHT to FFT (as did the Byte article). Fast Fourier Transform is used widely today, but the Fast Hartley Transform offered benefits in implementation (speed), and likely still does, on the proviso that chips aren't manufactured to accelerate 1 of the transforms.

In signal processing, speed vs. quality is vital. Both are implementations applied to the field. There are numerous transforms available, and you can implement your own. In doing so, something beyond your mind verifies what in your mind is applicable to the world.

Mathematicians have no use for the concept of speed of computation, and so they seem strangely unfit for implementing algorithms, despite that programming is simpler, more concrete, and heavily based on math including symbolization.

Programmers test formulas in mathematicians' minds. Don't hesitate to ask as you do, especially here. If you implemented a Fourier Transform, you understand it in a way a mathematician could not prove beyond on paper. (Cue [Principia][2]).

Apart from programming and speed of implementation, a third factor as mentioned is hardware acceleration. Depending on the system you're writing the implementation on, there may or may not be hardware acceleration favoring the most famous transform over all the other ones or one that you invent.

This factor would have to be removed today, to compare the two transforms rationally. [1]: https://m.eet.com/media/1175816/f-scott.pdf [2]: https://en.wikipedia.org/wiki/Principia_Mathematica

$\endgroup$

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.