Modification of a Two-Dimensional Fast Fourier Transform Algorithm by the Analog of the Cooley-Tukey Algorithm for a Rectangular Signal

摘要

One-dimensional fast Fourier transform (FFT) is the most popular tool for computing the two-dimensional Fourier transform. As a rule, a standard method of combination of one-dimensional FFTs-the so-called algorithm "by rows and columns" [1]-is used in the literature. In [2, 3], the authors showed how to compute the FFT for a signal with the number of samples 2|~s × 2~s with the use of an analog of the Cooley- Tukey algorithm. In the present paper, a two-dimensional analog of the Cooley-Tukey algorithm is constructed for a rectangular signal with the number of samples 2~s × 2~s + 9. The number of operations in this algorithm is much less than that in the successive application of a one dimensional FFT by rows and columns. The testing of the algorithm on image-type signals shows that the speed of computation of the FFT by the algorithm proposed is about 1.7 times higher than that of the algorithm by rows and columns.