Type-II/III DCT/DST algorithms with reduced number of arithmetic operations

Xuancheng Shao, Steven G. Johnson

Research output: Contribution to journalArticlepeer-review

43 Scopus citations

Abstract

We present algorithms for the discrete cosine transform (DCT) and discrete sine transform (DST), of types II and III, that achieve a lower count of real multiplications and additions than previously published algorithms, without sacrificing numerical accuracy. Asymptotically, the operation count is reduced from 2 N log2 N + O (N) to frac(17, 9) N log2 N + O (N) for a power-of-two transform size N. Furthermore, we show that an additional N multiplications may be saved by a certain rescaling of the inputs or outputs, generalizing a well-known technique for N = 8 by Arai et al. These results are derived by considering the DCT to be a special case of a DFT of length 4 N, with certain symmetries, and then pruning redundant operations from a recent improved fast Fourier transform algorithm (based on a recursive rescaling of the conjugate-pair split-radix algorithm). The improved algorithms for the DCT-III, DST-II, and DST-III follow immediately from the improved count for the DCT-II.

Original languageEnglish
Pages (from-to)1553-1564
Number of pages12
JournalSignal Processing
Volume88
Issue number6
DOIs
StatePublished - Jun 2008

Bibliographical note

Funding Information:
This research was supported by DARPA and ARO under contract DAAG29-85-C-0028. The authors would like to thank Barry Cole for antireflection coating the samples, Robert Horning and Mary Hibbs-Brenner for the X-Ray measurements, Cynthia Kelley and Hai Ly for sample preparation and Tom Nohava for MBE growth.

Keywords

  • Arithmetic complexity
  • Discrete cosine transform
  • Fast Fourier transform

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Type-II/III DCT/DST algorithms with reduced number of arithmetic operations'. Together they form a unique fingerprint.

Cite this