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

DOI10.1016/J.SIGPRO.2007.11.024zbMATH Open1186.94305arXiv0708.4399OpenAlexW1976370567WikidataQ61657827 ScholiaQ61657827MaRDI QIDQ971394FDOQ971394

Authors: Xuancheng Shao, Steven G. Johnson 

Publication date: 19 May 2010

Published in: Signal Processing (Search for Journal in Brave)

Abstract: 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 ~2NlogN to ~(17/9)NlogN for a power-of-two transform size N, and the exact count is strictly lowered for all N > 4. These results are derived by considering the DCT to be a special case of a DFT of length 8N, 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.

Full work available at URL: https://arxiv.org/abs/0708.4399

Recommendations

• Type-II/III DCT/DST algorithms with reduced number of arithmetic operations
• The fast DCT-IV/DST-IV computation via the MDCT
• Simple FFT and DCT algorithms with reduced number of operations.
• Fast Computation of MD-DCT-IV/MD-DST-IV by MD-DWT or MD-DCT-II
• Fast discrete sine transform algorithms

zbMATH Keywords

fast Fourier transformdiscrete cosine transformarithmetic complexitylapped transform

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (11)

• New algorithm for multidimensional type-III DCT
• Fast Computation of MD-DCT-IV/MD-DST-IV by MD-DWT or MD-DCT-II
• New universal rotation-based fast computational structures for an efficient implementation of the DCT-IV/DST-IV and analysis/synthesis MDCT/MDST filter banks
• Fast computational structures for an efficient implementation of the complete TDAC analysis/synthesis MDCT/MDST filter banks
• A wavelet OFDM receiver for baseband power line communications
• Improved and extended mixed-radix decimation in frequency fast MDCT algorithm
• The fast DCT-IV/DST-IV computation via the MDCT
• Linear filtering in DCT IV/DST IV and MDCT/MDST domain
• A new look at DCT-type transforms
• Complexity reduction, self/completely recursive, radix-2 DCT I/IV algorithms
• Type-II/III DCT/DST algorithms with reduced number of arithmetic operations

Uses Software

• FFTW

This page was built for publication: Type-IV DCT, DST, and MDCT algorithms with reduced numbers of arithmetic operations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q971394)