Fast Hartley Transform Pruning

The discrete Hartley transform (DHT) is becoming increasingly popular as a tool for the processing of real signals. Fast Hartley transform (FHT) algorithms exist which compute the DHT in a time proportional to N log2N. In many applications, such as interpolation and convolution of signals, a significant number of zeros is padded to the nonzero valued samples before the transform is computed. It is shown that for such situations, significant saving in the number of additions and multiplications can be obtained by pruning the FHT algorithm. The modifications in the FHT algorithm as a result of pruning are developed and implemented in an FHT subroutine. The amount of saving in the operation count is also determined. © 1991 IEEE.