Direct methods for computing discrete sinusoidal transforms

Abstract

According to Wang, there are four different types of DCT (discrete cosine transform) and DST (discrete sine transform) and the computation of these sinusoidal transforms can be reduced to the computation of the type-IV DCT. As the algorithms involve different sizes of transforms at different stages they are not so regular in structure. Lee has developed a fast cosine transform (FCT) algorithm for DCT-III similar to the decimation-in-time (DIT) Cooley-Tukey fast Fourier transform (FFT) with a regular structure. A disadvantage of this algorithm is that it involves the division of the trigonometric coefficients and may be numerically unstable. Recently, Hou has developed an algorithm for DCT-II which is similar to a decimation-in-frequency (DIF) algorithm and is numerically stable. However, an index mapping is needed to transform the DCT to a phase-modulated discrete Fourier transform (DFT), which may not be performed in-place. In the paper, a variant of Hou's algorithm is presented which is both in-place and numerically stable. The method is then generalised to compute the entire class of discrete sinusoidal transforms. By making use of the DIT and DIF concepts and the orthogonal properties of the DCTs, it is shown that simple algebraic formulations of these algorithms can readily be obtained. The resulting algorithms are regular in structure and are more stable than and have fewer arithmetic operations than similar algorithms proposed by Yip and Rao. By means of the Kronecker matrix product representation, the 1-D algorithms introduced in the paper can readily be generalised to compute transforms of higher dimensions. These algorithms, which can be viewed as the vector-radix generalisation of the present algorithms, share the in-place and regular structure of their 1-D counterparts.