A fast algorithm for the cosine transform based on successive order reduction of the chebyshev polynomial

The discrete cosine transform (DCT) is one of the discrete orthogonal transformations, for which fast computation algorithms are known. It has the property that the transformed sequence has most of the energy in the lower‐order components, and is utilized widely in feature extraction and high‐efficiency coding. The following methods have been known as the fast‐cosine transform (FCT): (1) Computation is performed through the fast‐Fourier transform (FFT) with real sequence; (2) Computation is made by decomposing the matrix representing DCT into sparse factors. In those methods, approximately N log2N real multiplications and (3/2)N log2N real additions are required for computation of DCT for N = 2^v points. The FCT proposed in this paper differs from those methods in the following points. The DCT is represented by a finite series of Chebyshev polynomials. The order of the series is successively halved utilizing the successive factorization of Chebyshev polynomial, finally arriving at DCT values. By this method, (1/2) N log2N real multiplications and (3/2) N log2N real additions suffice to calculate the DCT for N points: the number of multiplications is halved, compared with the previous methods. The method is similar, in its structure, to FFT with radix 2, which leads to the feature that the programming is simple.