Fast Fourier Transform for Hexagonal Aggregates

Hexagonal aggregates are hierarchical arrangements of hexagonal cells. These hexagonal cells may be efficiently addressed using a scheme known as generalized balanced ternary for dimension 2, or GBT₂. The objects of interest in this paper are digital images whose domains are hexagonal aggregates. We define a discrete Fourier transform (DFT) for such images. The main result of this paper is a radix-7, decimation-in-space fast Fourier transform (FFT) for images defined on hexagonal aggregates. The algorithm has complexity N log₇ N. It is expressed in terms of the p-product, a generalization of matrix multiplication. Data reordering (also known as shuffle permutations) is generally associated with FFT algorithms. However, use of the p-product makes data reordering unnecessary.