A MULTIDIMENSIONAL ANALOG OF THE COOLEY-TUKEY FFT ALGORITHM

Abstract

In this article a recurring sequence of orthogonal basis in the n-dimensional case has been applied to derive formulas of n-dimensional fast Fourier transform algorithm, which uses Complex multiplication and nN n log 2 N complex addition; where N = 2 s – is a number of counts on one of the axes.

Full Text

Recurrent sequence of orthogonal bases in space of signals is well studied [1] and has numerous applications, including the derivation of Fourier’s formulas of fast transformation. In this article the recurrent sequence of orthogonal bases to a n-dimensional case is applied in order to derive formulas of a fast n-dimensional Fourier transformation variant, using 2 2 1 log 2 n n n N N − complex multiplication and 2 nNn log N complex addition, where N = 2s – is a number of counts on one of the axes (known in studies as in [2]). This variant n FFT contains a smaller number of complex multiplication operations than other algorithms, where the multidimensional Fourier transformation is carried out by repeated application of one-dimensional FFT (for example, see [3; 4]). Furthermore, we give definitions and basic statements from the theory of multidimensional signals, which are used in the article. To construct n-dimensional recurrent sequence of orthogonal bases we use the scheme of the statement, given in [1] for a one-dimensional case. Mathematics, mechanics, computer science 128 1. The space of periodic n-dimensional signals.