Научная электронная библиотека ULRICH'S Periodicals Directory

Сибирский государственный университет
науки и технологий имени академика М.Ф. Решетнева

Сибирский аэрокосмический журнал
ISSN 2712-8970 (Print) ISSN 2782-5760 (on-line)

Сведения об образовательной организации

UDK 519.677
ABOUT MODIFICATION OF ONE-DIMENSIONAL FAST FOURIER TRANSFORM ON ALGORITHM OF COOLEY-TUKEY
T. V. Sidorova [1], T. V. Zykova [1]*, K. V. Safonov [2]
[1] Siberian Federal University, Institute of space and informatics technologies 26, Kirenskogo Str., Krasnoyarsk, 660079, Russian Federation [2] Reshetnev Siberian State Aerospace University 31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation *E-mail: zykovatv@mail.ru
In the present paper we give the description a method of finding the discrete Fourier Transform, which allows to reduce the cost of computer time to calculate compared to the classical algorithm. Fast algorithms for calculating the Fourier transform are very relevant and actual, they have many applications in problems of digital processing of one-dimensional and multi-dimensional signal and processing of different images, for example, satellite images. A common algorithm is a sequential calculation of the one-dimensional Discrete Fourier Transform by rows and columns. There are various methods of acceleration of the algorithm, one of which is implemented in this article. It is presented the software implementation of the modified algorithm of Cooley–Tukey analog for the Discrete Fourier Transform for the one-dimensional signal with the number of counts p · 2s, p, s N. For this algorithm, we developed a program in the computer algebra system MATLAB. It has been tested on a set consisting of a 16384 counts of one-dimensional signal. The time of calculations for the classical algorithm and for modified algorithm of Fast Fourier Transform is carried out. As a result, the average computer time for the modified algorithm gives about 20 % time reduction. In addition, in the article it is provided a general description of the Discrete Fourier Transform algorithm and indicated opportunities for increasing of the speed of computing. Also, it is considered a modified algorithm of Cooley–Tukey analog for the Fast Fourier Transform of one-dimensional and multidimensional signals.
Fourier Transform, Fast Fourier Transform (FFT), Cooley–Tukey FFT algorithm, MATLAB, programmable logic device (PLD).
References
  1. Dadzhion D., Mersero R. Tsifrovaya obrabotka mnogomernykh signalov [Digital processing of multidimensional signals]. Moscow, Mir Publ., 1988, 488 p.
  2. Bleynut R. Bystrye algoritmy tsifrovoi obrabotki signalov [Fast algorithms of digital processing of signals]. Moscow, Mir Publ., 1989, 448 p.
  3. Oppengeym A. V., Shafer R. V. Tsifrovaya obrabotka signalov [Digital processing of signals]. Moscow, Svyaz Publ., 1979, 416 p.
  4. Gonsalez R., Woods R. Tsifrovaya obrabotka izobrazhenii [Digital processing of images]. Moscow, Tehnosfera Publ., 2005, 1072 p.
  5. Cooley J. W., Tukey J. An algorithm for the machine calculation of complex Fourier series. Math. Comput. 1965, Vol. 19, No. 90, P. 297–301.
  6. Rudnick P. Note on the calculation of fourier series. Math. Comp. 1966, Vol. 20, No. 3, P. 429–430.
  7. Danielson G. C., Lanczos C. Some improvements in practical fourier analysis and their application to x-ray scattering from liquids. J. Franklin Inst. 1942, Vol. 233, No. 4, P. 365–80.
  8. Heideman M. T., Johnson D. H., Burrus C. S. Gauss and the history of the fast fourier transform. The ASSP Magazine. 1984, Vol. 1, No. 4, P. 14–21.
  9. Cooley J. W., Lewis P. A., Welch P. D. An algorithm for the machine calculation of complex fourier series. IEEE Trans. Audio Electroacoustics. 1967, Vol. 15, No. 2, P. 76–79.
  10. Starovoitov A. V. [About multidimensional analog of algorithm of Cooley–Tukey]. Vestnik SibGAU. 2010, No. 1 (27), P. 69–73 (In Russ.).
  11. Kiselev O. I., Kolthova I. V., Tutatchikov V. S. [Scheme of parallel calculation of one-dimensional fast fourier transformation]. Мaterialy XV Mezhdunar. nauch. konf. “Nauka i obrazovanie v XXI veke” [Materials Intern. Scientific. Conf “Science and education in the XXI century”]. Tambov, 2013, P. 140–141 (In Russ.).
  12. Tutatchikov V. S., Kiselev O. I., Noskov M. V. Calculating the n-Dimensional Fast Fourier Transform. Pattern Recognition and Image Analysis. 2013, Vol. 23, No. 3, P. 429–433.
  13. Noskov M. V., Tutatchikov V. S. Modification of a two-dimensional fast fourier transform algorithm for a rectangle signal. Pattern Recognition and Image Analysis. 2015, Vol. 25, No. 1, P. 81–83.
  14. Malozemov V. P., Masharsky S. M. Osnovy diskretnogo garmonicheskogo analiza [Bases of the discrete harmonious analysis]. St. Peterburg, NIIMM Publ., 2003, 304 p.
  15. Sidorova T. V., Zykova T. V. Programma dlya vychisleniya odnomernogo bystrogo preobrazovaniya Fur'e na osnove modifitsirovannogo algoritma Kuli-T'yuki [The program for calculation of one-dimensional fast Fourier transformation on the basis of the modified algorithm of Cooley-Tukey]. Certificate on the state registration of the computer program No. 2014661701 of the Russian Federation, dem. 19.09.2014 (demand No. 2014619428), registration 11.11.2014 Rospatent.

Sidorova Tatyana Valerevna – Cand. Sc., Docent, Department of Applied Mathematics and Computer Security, Institute of space and informatics technologies, Siberian Federal University. E-mail: stany6@yandex.ru

Zykova Tatyana Viktorovna – Cand. Sc., Docent, Department of Applied Mathematics and Computer Security, Institute of space and informatics technologies, Siberian Federal University. E-mail: zykovatv@mail.ru

Safonov Konstantin Vladimirovich – Dr. Sc., Head of Department of Applied Mathematics, Reshetnev Siberian State Aerospace University. E-mail: safonovkv@ rambler.ru