Type-IV DCT, DST, and MDCT algorithms with reduced numbers of arithmetic operations

Xuancheng Shao, Steven G. Johnson

Research output: Contribution to journalArticlepeer-review

37 Scopus citations


We present algorithms for the type-IV discrete cosine transform (DCT-IV) and discrete sine transform (DST-IV), as well as for the modified discrete cosine transform (MDCT) and its inverse, 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, and the exact count is strictly lowered for all N ≥ 8. These results are derived by considering the DCT to be a special case of a DFT of length 8 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 DST-IV and MDCT follow immediately from the improved count for the DCT-IV.

Original languageEnglish
Pages (from-to)1313-1326
Number of pages14
JournalSignal Processing
Issue number6
StatePublished - Jun 2008


  • Arithmetic complexity
  • Discrete cosine transform
  • Fast Fourier transform
  • Lapped transform

ASJC Scopus subject areas

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


Dive into the research topics of 'Type-IV DCT, DST, and MDCT algorithms with reduced numbers of arithmetic operations'. Together they form a unique fingerprint.

Cite this