A novel approach to fast discrete Hartley transform

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(Nlog₂N/log₂log₂N) superior to O(Nlog ₂N) in the conventional FDT. The execution time of the systolic array is only O(Nlog₂N/log₂log₂N) 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