A new split-radix FHT algorithm for length-q*2mDHTs

摘要

In this paper, a new split-radix fast Hartley transform (FHT) algorithm is proposed for computing the discrete Hartley transform (DHT) of an arbitrary length N=q*2m, where q is an odd integer. The basic idea behind the proposed FHT algorithm is that a mixture of radix-2 and radix-8 index maps is used in the decomposition of the DHT. This idea and the use of an efficient indexing process lead to a new decomposition different from that of the existing split-radix FHT algorithms, since the existing ones are all based on the use of a mixture of radix-2 and radix-4 index maps. The proposed algorithm reduces substantially the operations such as data transfer, address generation, and twiddle factor evaluation or access to the lookup table, which contribute significantly to the execution time of FHT algorithms. It is shown that the arithmetic complexity (multiplications+additions) of the proposed algorithm is, in almost all cases, the same as that of the existing split-radix FHT algorithm for length- q*2m DHTs. Since the proposed algorithm is expressed in a simple matrix form, it facilitates an easy implementation of the algorithm, and allows for an extension to the multidimensional case.