A Fast Algorithm of the Discrete Cosine Transform for the Fermat Prime-length

Abstract

A fast algorithm is developed to evaluate the discrete cosine transform (DCT) when the number of data sample is a Fermat prime. It is based on the ideas of decomposing the length DCT into two circular correlations which can be implemented by a use of the number theoretic transform (NTT). This fact leads to result a reduction of computing the DCT complexity when compared with more conventional methods. In addition, this fast DCT provides a regular and simple structure based on circular correlations. Therefore, it can also be implemented by the use of a modification of Kung\'s pipelines structure.