An efficient split-radix FHT algorithm

In this paper, a new efficient split-radix FHT algorithm is proposed for computing a length-2^m DHT by using a mixture of radix-2 and radix-8 index maps in the decomposition of the DHT. An efficient indexing process and a technique for grouping the twiddle factors are incorporated. Introduction of these three features in the proposed algorithm results in significant savings in terms of the data transfer, address generation, and twiddle factor evaluation or access to the lookup table, which contribute significantly to the execution time of the FHT algorithms. These savings are achieved with the arithmetic complexity (multiplications+additions) being no more than that of the existing split-radix FHT algorithms.