FAST ALGORITHMS FOR COMPUTING THE DISCRETE COSINE TRANSFORM

In this paper, efficient methods for mapping odd-length type-II, type-III, and type-IV DCT's to a real-valued DFT are presented. It is found that odd-length type-II and type-III DCT's can be transformed, by means of an index mapping, to a real-valued DFT of the same length using permutations and sign changes only. The real-valued DFT can then be computed by efficient real-valued FFT algorithms such as the prime factor algorithm. Similar mapping is introduced to convert a type-IV DCT to a real-valued DFT up to a scaling factor and some additions. Methods for computing DCT's with even lengths are also discussed.