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

DOI10.1016/J.SIGPRO.2008.01.004MaRDI QIDQ971426zbMATH OpenOpenAlexWikidataFDO

Authors Xuancheng Shao, Steven G. Johnson

Publication date 19 May 2010

Published in Signal Processing (Search for Journal in Brave)

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

zbMATH Keywords

arithmetic complexitydiscrete cosine transformfast Fourier transform

Mathematics Subject Classification ID

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

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 ~ 2N log_2 N to ~ (17/9) N log_2 N for a power-of-two transform size N. Furthermore, we show that a further 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 4N, 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 DCT-III, DST-II, and DST-III follow immediately from the improved count for the DCT-II.

Recommendations

• Type-IV DCT, DST, and MDCT algorithms with reduced numbers of arithmetic operations
• Simple FFT and DCT algorithms with reduced number of operations.
• Fast discrete sine transform algorithms
• scientific article; zbMATH DE number 24367
• Fast algorithms for computing the discrete cosine transform

Cited in

(15)

• Cosine manifestations of the Gelfand transform
• Fast discrete sine transform algorithms
• New algorithm for multidimensional type-III DCT
• A new look at DCT-type transforms
• scientific article; zbMATH DE number 621949 (Why is no real title available?)
• scientific article; zbMATH DE number 1737498 (Why is no real title available?)
• Lowest complexity self-recursive radix-2 DCT II/III algorithms
• Recursive calculation of discrete cosine transform for low resolution signal processing
• Simple FFT and DCT algorithms with reduced number of operations.
• Low-Complexity Scaling Methodsfor DCT-II Approximations
• Improved DCT-DST prime factor algorithms.
• DCT-former: efficient self-attention with discrete cosine transform
• A faster multipole Legendre-Chebyshev transform
• Improvement of the discrete cosine transform calculation by means of a recursive method
• Type-IV DCT, DST, and MDCT algorithms with reduced numbers of arithmetic operations

Describes a project that uses

Uses Software

• DCT-III
• FFTW

This page was built for publication: Type-II/III DCT/DST algorithms with reduced number of arithmetic operations

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