Discrete Hartley Transform - Properties

Properties

The transform can be interpreted as the multiplication of the vector (x₀, ...., x_N-1) by an N-by-N matrix; therefore, the discrete Hartley transform is a linear operator. The matrix is invertible; the inverse transformation, which allows one to recover the x_n from the H_k, is simply the DHT of H_k multiplied by 1/N. That is, the DHT is its own inverse (involutary), up to an overall scale factor.

The DHT can be used to compute the DFT, and vice versa. For real inputs x_n, the DFT output X_k has a real part (H_k + H_N-k)/2 and an imaginary part (H_N-k - H_k)/2. Conversely, the DHT is equivalent to computing the DFT of x_n multiplied by 1+i, then taking the real part of the result.

As with the DFT, a cyclic convolution z = x*y of two vectors x = (x_n) and y = (y_n) to produce a vector z = (z_n), all of length N, becomes a simple operation after the DHT. In particular, suppose that the vectors X, Y, and Z denote the DHT of x, y, and z respectively. Then the elements of Z are given by:

where we take all of the vectors to be periodic in N (X_N = X₀, etcetera). Thus, just as the DFT transforms a convolution into a pointwise multiplication of complex numbers (pairs of real and imaginary parts), the DHT transforms a convolution into a simple combination of pairs of real frequency components. The inverse DHT then yields the desired vector z. In this way, a fast algorithm for the DHT (see below) yields a fast algorithm for convolution. (Note that this is slightly more expensive than the corresponding procedure for the DFT, not including the costs of the transforms below, because the pairwise operation above requires 8 real-arithmetic operations compared to the 6 of a complex multiplication. This count doesn't include the division by 2, which can be absorbed e.g. into the 1/N normalization of the inverse DHT.)