A MULTIDIMENSIONAL ANALOG OF THE COOLEY-TUKEY FFT ALGORITHM
- Autores: Starovoitov A.V.1
-
Afiliações:
- Siberian Federal University
- Edição: Volume 11, Nº 7 (2010)
- Páginas: 127-131
- Seção: Articles
- URL: https://journals.eco-vector.com/2712-8970/article/view/505816
- ID: 505816
Citar
Texto integral
Resumo
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.
Texto integral
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.×
Bibliografia
- Malozemov V. N., Macharskii S. M. Basises of diskrete harmonic analysis. S. 2. St. Petersburg : NIIMM. 2003.
- Dudgeon D. E., Mersereau R. M. Multidimensional Digital Signal Processing : Transl. from English. M. : Mir, 1988.
- Blahut R. Fast Algorithms for Digital Signal Processing : Transl. from English. М. : Mir, 1989.
- Oppenheim A. V., Schafer R. W. Digital Signal Processing : Transl. from English. М. : Sviaz, 1979.