Abstract In this paper the Cooley-Tukey fast Fourier transform (FFT) algorithm is generalized to the multi-dimensional case in a natural way that incorporates the standard row-column and vector-radix algorithms as special cases. It can be used for the evaluation of discrete Fourier transforms of rectangularly or hexagonally sampled signals or signals which are arbitrarily sampled in either the spatial or Fourier domain. These fast Fourier transform algorithms are shown to result from the factorization of an integer matrix; different algorithms correspond to different factorizations. This paper will first derive a generalized discrete Fourier transform, then derive the general Cooley-Tukey algorithm, and conclude by interpreting existing multi-dimensional FFT algorithms in terms of the generalized one.
Generalized cooley-tukey algorithms for evaluation of multi-dimensional discrete fourier transforms
1980-01-01
19 pages
Article/Chapter (Book)
Electronic Resource
English
British Library Online Contents | 2017
|British Library Online Contents | 2015
|Fast Algorithms of Discrete Fourier and Cosine Transforms in Mixed Formats
British Library Conference Proceedings | 2003
|