Cyclic convolution of real sequences: Hartley versus Fourier and new schemes
Recently, new fast transforms (such as the discrete Hartley transform in particular) have been proposed which are best suited for the computation of cyclic convolution of real sequences. Two approaches using Fourier or Hartley transforms are first compared, showing that the recently proposed FFT algorithms for real data present a lower arithmetic complexity than the corresponding DHT-based approach. Improvements are made to both types of algorithms, leading to different trade offs between arithmetic and structural complexity. We also present a new Hartley Transform algorithm with lower arithmetic complexity than any previously published one.