ABSTRACT
Trigonometric transforms have a central role as signal processing tools. In particular, the discrete Fourier transform (DFT), the discrete Hartley transform (DHT), and the discrete cosine transform (DCT) are the most employed transformations in both theoretical and practical contexts [36]. Computed according to their definitions, these transforms exhibit quadratic complexity, which is enough to prevent their application in several contexts. Nevertheless, fast algorithms are capable of computing them with a computational complexity in O(N logN), where N is the transform blocklength. Considering the design of fast algorithms for discrete transforms, it is a well-known fact that the number of multiplications is an important figure of merit that significantly affects the overall computational complexity of a given algorithm. Thus, as a rule of thumb, fast algorithm designers often aim at the minimization of the multiplicative complexity.
