Fast radix-3 and radix-3/9 discrete Hartley transforms

An efficient radix-3/9 fast Hartley transform (FHT) algorithm is proposed. It shows a great improvement over the previous radix-3 FHT algorithm such that nearly 50% of the number of multiplications is saved. For the computation of real-valued DFTs (discrete Fourier transforms) with sequence lengths which are powers of 3, the proposed radix-3/9 algorithm gives an average of 16.2% reduction in the number of multiplications over the fastest radix-3/9 FFT (fast Fourier transform) algorithm. The improvement is mainly the result of the simplicity of the computing structure of the proposed algorithm and the use of fast length-3 and fast length-9 DHT modules