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

Author

Tsung-Ching Lin ; Wen-Ku Su ; Pei-Yu Shih ; Trieu-Kien Truong

Author_Institution

Dept. of Inf. Eng., I-Shou Univ., Kaohsiung, Taiwan

fYear

2012

fDate

25-28 Aug. 2012

Firstpage

261

Lastpage

264

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.

Keywords

computational complexity; correlation methods; discrete cosine transforms; number theory; pipeline processing; DCT complexity reduction; Fermat prime-length; NTT; circular correlation; discrete cosine transform; fast algorithm; number theoretic transform; pipelines structure; Approximation algorithms; Correlation; Discrete cosine transforms; Educational institutions; Finite element methods; Signal processing algorithms; DCT/IDCT; Fermat prime number; circular correlation;

fLanguage

English

Publisher

ieee

Conference_Titel

Genetic and Evolutionary Computing (ICGEC), 2012 Sixth International Conference on

Conference_Location

Kitakushu

Print_ISBN

978-1-4673-2138-9

Type

conf

DOI

10.1109/ICGEC.2012.13

Filename

6457261