Перевод названия: ABOUT MODIFICATION OF ONE-DIMENSIONAL FAST FOURIER TRANSFORM ON ALGORITHM OF COOLEY-TUKEY
Тип публикации: статья из журнала
Год издания: 2015
Ключевые слова: matlab, Fourier transform, Fast Fourier Transform (FFT), Cooley-Tukey FFT algorithm, Programmable logic device (PLD), преобразование Фурье, быстрое преобразование Фурье (БПФ), алгоритм БПФ Кули-Тьюки, программируемая логическая интегральная схема (ПЛИС)
Аннотация: Рассматривается один из методов нахождения дискретного преобразования Фурье, позволяющий уменьшить затраты машинного времени на вычисления по сравнению с классическим алгоритмом. Быстрые алгоритмы вычисления преобразования Фурье очень востребованы и актуальны, они имеют множество приложений в задачах цифровой обработки одномерных иПоказать полностьюмногомерных сигналов, обработки различных изображений, например космоснимков. Общепринятый алгоритм представляет собой последовательное вычисление одномерного дискретного преобразования Фурье по строкам и столбцам. Существуют различные методы ускорения данного алгоритма, один из которых и реализован в данной статье. Представлена программная реализация модифицированного алгоритма по аналогу Кули-Тьюки дискретного преобразования Фурье для одномерного сигнала с числом отсчетов p · 2 s, p, s N. Для данного алгоритма была разработана программа в системе компьютерной математики MATLAB. Она протестирована на наборе, состоящем из 16384 отсчетов одномерного сигнала. При выполнении программы производится также сравнение времени ее выполнения со временем, затрачиваемым встроенным алгоритмом вычисления быстрого преобразования Фурье. В результате, среднее время выполнения программы по модифицированному алгоритму дает выигрыш около 20 % по времени. Кроме того, приводится общее описание алгоритма дискретного преобразования Фурье, обозначены возможности для увеличения скорости выполнения вычислений, рассматривается модифицированный алгоритм по аналогу Кули-Тьюки быстрого преобразования Фурье для одномерных и многомерных сигналов. 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 · 2 s, 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.
Журнал: Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева
Выпуск журнала: Т. 16, № 2
Номера страниц: 360-363
ISSN журнала: 18169724
Место издания: Красноярск
Издатель: Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева