
DCT/DST Algorithms
We have developed an algebraic framework to concisely derive almost all of the existing fast algorithms for the 16 types of discrete cosine and sine transforms (DCTs and DSTs). Further, we have derived new algorithms for all 16 DCTs and DSTs. These algorithms are, in structure and in a strict mathematical sense, the analogue of the CooleyTukey FFT. The approach we use to discover, derive, and classify algorithms, is a part of the algebraic signal processing theory.
Papers
 Markus Püschel and José Moura
Algebraic Signal Processing Theory: CooleyTukey Type Algorithms for DCTs and DSTs
submitted for publication
This paper presents a systematic methodology based on the algebraic signal processing theory 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 wellknown CooleyTukey 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.
 Yevgen Voronenko and Markus Püschel
Algebraic Derivation of General Radix CooleyTukey Algorithms for the Real Discrete Fourier Transform
submitted for publication
We show that the real version of the discrete Fourier transform
(called RDFT) can be characterized in the framework of polynomial
algebras just as the DFT and the discrete cosine and sine
transforms. Then, we use this connection to algebraically derive a
general radix CooleyTukey type algorithm for the RDFT. The algorithm
has a similar structure as its complex counterpart, but there are also
important difference, which are exhibited by our Kronecker product
style presentation. In particular, the RDFT is decomposed in smaller
RDFTs but also other auxiliary transforms, which we then decompose by
their own CooleyTukey type algorithms to obtain a full recursive
algorithm for the RDFT.
 Markus Püschel and José Moura
The Algebraic Approach to the Discrete Cosine and Sine Transforms and their Fast Algorithms
SIAM Journal of Computing 2003, Vol. 32, No. 5, pp. 12801316
It is known that the discrete Fourier transform (DFT) used in digital signal processing can be characterized in the framework of representation theory of algebras, namely as the decomposition matrix for the regular module C[Z_n] = C[x]/(x^n  1). This characterization provides deep insight on the DFT and can be used to derive and understand the structure of its fast algorithms. In this paper we present an algebraic characterization of the important class of discrete cosine and sine transforms as decomposition matrices of certain regular modules associated to four series of Chebyshev polynomials. Then we derive most of their known algorithms by pure algebraic means. We identify the mathematical principle behind each algorithm and give insight into its structure. Our results show that the connection between algebra and digital signal processing is stronger than previously understood.
dttalgo.pdf (335 KB)
 Markus Püschel
CooleyTukey FFT like Algorithms for the DCT
Proc. ICASSP, 2003
The CooleyTukey FFT algorithm decomposes a discrete Fourier transform (DFT) of size n = km into smaller DFTs of size k and m. In this paper we present a theorem that decomposes a polynomial transform into smaller polynomial transforms, and show that the FFT is obtained as a special case. Then we use this theorem to derive a new class of recursive algorithms for the discrete cosine transforms (DCTs) of type II and type III. In contrast to other approaches, we manipulate polynomial algebras instead of transform matrix entries, which makes the derivation transparent, concise, and gives insight into the algorithms' structure. The derived algorithms have a regular structure and, for 2power size, minimal arithmetic cost (among known DCT algorithms).
ctdct.pdf (73 KB)
 Markus Püschel and José Moura
The Discrete Trigonometric Transforms and Their Fast Algorithms: An Algebraic Symmetry Approach
Proc. 10th Digital Signal Processing Workshop, 2002
