Hartley Transform

An Integral Transform which shares some features with the Fourier Transform, but which (in the discrete case), multiplies the Kernel by

$\begin{displaymath} \cos\left({2\pi kn\over N}\right)-\sin\left({2\pi kn\over N}\right) \end{displaymath}$

(1)

instead of

$\begin{displaymath} e^{-2\pi ikn/N}=\cos\left({2\pi kn\over N}\right)-i\sin\left({2\pi kn\over N}\right). \end{displaymath}$

(2)

The Hartley transform produces Real output for a Real input, and is its own inverse. It therefore can have computational advantages over the Discrete Fourier Transform, although analytic expressions are usually more complicated for the Hartley transform.

The discrete version of the Hartley transform can be written explicitly as

$\displaystyle {\mathcal H}[a]$	$\textstyle \equiv$	$\displaystyle {1\over\sqrt{N}} \sum_{n=0}^{N-1} a_n\left[{\cos\left({2\pi kn\over N}\right)-\sin\left({2\pi kn\over N}\right)}\right]$	(3)
	$\textstyle =$	$\displaystyle \Re {\mathcal F}[a]-\Im {\mathcal F}[a],$	(4)

where ${\mathcal F}$ denotes the Fourier Transform. The Hartley transform obeys the Convolution property

$\begin{displaymath} {\mathcal H}[a*b]_k={\textstyle{1\over 2}}(A_kB_k-\bar A_k\bar B_k+A_k\bar B_k+\bar A_k B_k), \end{displaymath}$

(5)

where

$\displaystyle \bar a_0$	$\textstyle \equiv$	$\displaystyle a_0$	(6)
$\displaystyle \bar a_{n/2}$	$\textstyle \equiv$	$\displaystyle a_{n/2}$	(7)
$\displaystyle \bar a_k$	$\textstyle \equiv$	$\displaystyle a_{n-k}$	(8)

(Arndt). Like the Fast Fourier Transform, there is a ``fast'' version of the Hartley transform. A decimation in time algorithm makes use of

$\displaystyle {\mathcal H}_n^{\rm left}[a]$	$\textstyle =$	$\displaystyle {\mathcal H}_{n/2}[a^{\rm even}]+{\mathcal X}{\mathcal H}_{n/2}[a^{\rm odd}]$	(9)
$\displaystyle {\mathcal H}_n^{\rm right}[a]$	$\textstyle =$	$\displaystyle {\mathcal H}_{n/2}[a^{\rm even}]-{\mathcal X}{\mathcal H}_{n/2}[a^{\rm odd}],$	(10)

where ${\mathcal X}$ denotes the sequence with elements

$\begin{displaymath} a_n\cos\left({\pi n\over N}\right)-\bar a_n\sin\left({\pi n\over N}\right). \end{displaymath}$

(11)

A decimation in frequency algorithm makes use of

$\displaystyle {\mathcal H}_n^{\rm even}[a]$	$\textstyle =$	$\displaystyle {\mathcal H}_{n/2}[a^{\rm left}+a^{\rm right}],$	(12)
$\displaystyle {\mathcal H}_n^{\rm odd}[a]$	$\textstyle =$	$\displaystyle {\mathcal H}_{n/2}[{\mathcal X}(a^{\rm left}-a^{\rm right})].$	(13)

The Discrete Fourier Transform

$\begin{displaymath} A_k\equiv {\mathcal F}[a]=\sum_{n=0}^{N-1} e^{-2\pi ikn/N} a_n \end{displaymath}$

(14)

can be written

$\displaystyle \left[\begin{array}{c}A_k\\ A_{-k}\end{array}\right]$	$\textstyle =$	$\displaystyle \sum_{n=0}^{N-1} \underbrace{\left[\begin{array}{cc}e^{-2\pi ikn/... ..._{{\hbox{\sf F}}}\left[\begin{array}{c}a_n\\ a_n\end{array}\right]\hfill\eqnum$	(15)
	$\textstyle =$	$\displaystyle \sum_{n=0}^{N-1} \underbrace{{1\over 2}\left[\begin{array}{cc}1-i... ...ay}\right]}_{{\hbox{\sf T}}}\left[\begin{array}{c}a_n\\ a_n\end{array}\right],$	(16)

$\begin{displaymath} {\hbox{\sf F}}={\hbox{\sf T}}^{-1}{\hbox{\sf H}}{\hbox{\sf T}}. \end{displaymath}$

(17)

References

Arndt, J. ``The Hartley Transform (HT).'' Ch. 2 in ``Remarks on FFT Algorithms.'' http://www.jjj.de/fxt/.

Bracewell, R. N. The Fourier Transform and Its Applications. New York: McGraw-Hill, 1965.

Bracewell, R. N. The Hartley Transform. New York: Oxford University Press, 1986.