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 Cooley-Tukey 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: Cooley-Tukey 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 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.

• Yevgen Voronenko and Markus Püschel
  Algebraic Derivation of General Radix Cooley-Tukey 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 Cooley-Tukey 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 Cooley-Tukey 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. 1280-1316

  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
  Cooley-Tukey FFT like Algorithms for the DCT
  Proc. ICASSP, 2003

  The Cooley-Tukey 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 2-power 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