Modification of a two-dimensional fast Fourier transform algorithm by the analog of the Cooley-Tukey algorithm for a rectangular signal

Описание

Тип публикации: статья из журнала

Год издания: 2015

Идентификатор DOI: 10.1134/S1054661815010137

Ключевые слова: Cooley-Tukey FFT, parallel FFT algorithm, two-dimensional fast Fourier transform, Algorithms, Photonic crystals, Cooley-Tukey, FFT algorithm, Number of samples, Rectangular signals, Two dimensional fast Fourier transforms, Two dimensional Fourier transforms, Fast Fourier transforms

Аннотация: 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 2s ? 2s 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 2s ? 2s + ?. 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. © 2015, Pleiades Publishing, Ltd.

Ссылки на полный текст

Издание

Журнал: Pattern Recognition and Image Analysis

Выпуск журнала: Vol. 25, Is. 1

Номера страниц: 81-83

Персоны

  • Noskov Michael V. (Institute of Space and Information Technology, Siberian Federal University, Kirenskogo street 26, Krasnoyarsk, Russian Federation)
  • Tutatchikov V.S. (Institute of Space and Information Technology, Siberian Federal University, Kirenskogo street 26, Krasnoyarsk, Russian Federation)

Вхождение в базы данных