The computation of unitary transforms is a complicated and time-consuming task. However, it would not be possible to use orthogonal transforms in signal and image processing applications without effective algorithms to calculate them. Note that both complexity issues-efficient software and circuit implementations-are the heart of the most applications. An important question in many applications is how to achieve the highest computation efficiency of the discrete orthogonal transforms (DOTs). The suitability of unitary transforms in each of the above applications depends on the properties of their basis functions as well as on the existence of fast algorithms, including parallel ones. A fast DOT is an efficient algorithm for computing the DOT and its inverse with an essentially smaller number of operations than direct matrix multiplication. The problem of computing a transform has been extensively studied.
Historically, the first efficient DFT algorithm, for length 2M, was described by Gauss in 1805 and developed by Cooley and Tukey in 1965. Since the introduction of the fast Fourier transform (FFT), Fourier analysis has become one of the most frequently used tools in signal/image processing and communication systems; other discrete transforms and different fast algorithms for computing transforms have been introduced as well. In the past decade, fast DOTs have been widely used in many areas such as data compression, pattern recognition and image reconstruction, interpolation, linear filtering, spectral analysis, watermarking, cryptography, and communication systems. The HTs, such as the WHT and Walsh-Paley transform, are important members of the class of DOTs. These matrices are known as nonsinusoidal orthogonal transform matrices and have found applications in digital signal processing and communication systems because they do not require any multiplication operations in their computation. A survey of the literature of fast HTs (FHTs) and their hardware implementations is found in Refs. 2, 4, 14-22, and 66-74. There are many other practical problems where one needs to have an N-point FHT algorithm, where N is an arbitrary 4t integer. We have seen that despite the efforts of several mathematicians, the Hadamard conjecture remains unproved even though it is widely believed to be true.