A novel approach to fast discrete Hartley transform

Abstract

The Discrete Hartley transform (DHT) is an important tool in digital signal processing. We propose a novel approach to perform DHT. We transform DHT into a form expressed in discrete moments via a modular mapping and truncating Taylor series expansion and present a completely new formula for computing DHT. We extend the use of our systolic array for fast computation of moments without any multiplications, to one that computes DHT with only a few multiplications and without any evaluations of triangular functions. The multiplication number used in our method is O(Nlog2N/log2log2N) superior to O(Nlog 2N) in the conventional FDT. The execution time of the systolic array is only O(Nlog2N/log2log2N) for 1-D DHT and O(N k) for k-D DHT (k⩾2). The systolic array consists of very simple processing elements and hence it implies an easy and potential hardware/VLSI implementation. The approach is also applicable to DHT inverses.