Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for DCTs and DSTs

Abstract

This paper presents a systematic methodology based on the algebraic theory of signal processing to classify and derive fast algorithms for linear transforms. Instead of manipulating the entries of transform matrices, our approach derives the algorithms by stepwise decomposition of the associated signal models, or polynomial algebras. This decomposition is based on two generic methods or algebraic principles that generalize the well-known Cooley-Tukey FFT and make the algorithms' derivations concise and transparent. Application to the 16 discrete cosine and sine transforms yields a large class of fast algorithms, many of which have not been found before.

31 pages, more information at http://www.ece.cmu.edu/~smart

References in corpus (2)

• Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for DCTs and DSTs
• Type-II/III DCT/DST algorithms with reduced number of arithmetic operations

Cited by in corpus (9)

• Discrete Signal Processing on Graphs
• Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for DCTs and DSTs
• Spectral Domain Sampling of Graph Signals
• Spectral Projector-Based Graph Fourier Transforms
• Lightweight Hardware Transform Design for the Versatile Video Coding 4K ASIC Decoders
• Low-complexity Scaling Methods for DCT-II Approximations
• Fast cosine transform for FCC lattices
• Implementing the sine transform of fermionic modes as a tensor network
• FFT and orthogonal discrete transform on weight lattices of semi-simple Lie groups