Copyrights to these papers may be held by the publishers. The download files are preprints. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Markus Püschel and Martin Rötteler (Applicable Algebra in Engineering, Communication and Computing, special issue on "The memory of Thomas Beth", Vol. 19, No. 3, pp. 259-292, 2008)
Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms on the 2-D Spatial Hexagonal Lattice
Preprint (277 KB)
Bibtex
Recently, we introduced the framework for signal processing on a nonseparable 2-D hexagonal spatial lattice including the associated notion of Fourier transform called discrete triangle transform (DTT). Spatial means that the lattice is undirected in contrast to earlier work by Mersereau introducing hexagonal discrete Fourier transforms. In this paper we derive a general-radix algorithm for the DTT of an nxn 2-D signal, focusing on the radix-2x2 case. The runtime of the algorithm is O(n^2 log(n)), which is the same as for commonly used separable 2-D transforms. The DTT algorithm derivation is based on the algebraic signal processing theory. This means that instead of manipulating transform coefficients, the algorithm is derived through a stepwise decomposition of its underlying polynomial algebra based on a general theorem that we introduce. The theorem shows that the obtained DTT algorithm is the precise equivalent of the well-known Cooley-Tukey fast Fourier transform, which motivates the title of this paper.
Keywords: Algebraic signal processing theory: Current status, Theory of transform algorithms, Nonseparable transforms and latticesMore information: