Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms on the 2-D Hexagonal Spatial Lattice

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 n x n 2-D signal, focusing on the radix-2 x 2 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.