Fast fourier transform for hexagonal aggregates

Hexagonal aggregates are hierarchical arrangements of hexagonal cells. Thes e hexagonal cells may be efficiently addressed using a scheme known as gene ralized balanced ternary, for dimension 2, or GBT(2). The objects of intere st in this paper are digital images whose domains are hexagonal aggregates. We define a discrete Fourier transform (DFT) for such images. The main res ult of this paper is a radix-7, decimation-in-space fast Fourier transform (FFT) for images defined on hexagonal aggregates. The algorithm has complex ity N log(7) N. It is expressed in terms of the p-product, a generalization of matrix multiplication. Data reordering (also known as shuffle permutati ons) is generally associated with FFT algorithms. However, use of the p-pro duct makes data reordering unnecessary.