О модификации быстрого одномерного преобразования Фурье по алгоритму Кули-Тьюки

О модификации быстрого одномерного преобразования Фурье по алгоритму Кули-Тьюки

Автор: Сидорова Т.В., Зыкова Т.В., Сафонов К.В.

Журнал: Сибирский аэрокосмический журнал @vestnik-sibsau

Рубрика: Математика, механика, информатика

Статья в выпуске: 2 т.16, 2015 года.

Бесплатный доступ

Рассматривается один из методов нахождения дискретного преобразования Фурье, позволяющий уменьшить затраты машинного времени на вычисления по сравнению с классическим алгоритмом. Быстрые алгоритмы вычисления преобразования Фурье очень востребованы и актуальны, они имеют множество приложений в задачах цифровой обработки одномерных и многомерных сигналов, обработки различных изображений, например космоснимков. Общепринятый алгоритм представляет собой последовательное вычисление одномерного дискретного преобразования Фурье по строкам и столбцам. Существуют различные методы ускорения данного алгоритма, один из которых и реализован в данной статье. Представлена программная реализация модифицированного алгоритма по аналогу Кули-Тьюки дискретного преобразования Фурье для одномерного сигнала с числом отсчетов p · 2 s, p, s N. Для данного алгоритма была разработана программа в системе компьютерной математики MATLAB. Она протестирована на наборе, состоящем из 16384 отсчетов одномерного сигнала. При выполнении программы производится также сравнение времени ее выполнения со временем, затрачиваемым встроенным алгоритмом вычисления быстрого преобразования Фурье. В результате, среднее время выполнения программы по модифицированному алгоритму дает выигрыш около 20 % по времени. Кроме того, приводится общее описание алгоритма дискретного преобразования Фурье, обозначены возможности для увеличения скорости выполнения вычислений, рассматривается модифицированный алгоритм по аналогу Кули-Тьюки быстрого преобразования Фурье для одномерных и многомерных сигналов.

Еще

Преобразование фурье, быстрое преобразование фурье (бпф), алгоритм бпф кули-тьюки, программируемая логическая интегральная схема (плис)

Короткий адрес: https://sciup.org/148177426

IDR: 148177426

Список литературы О модификации быстрого одномерного преобразования Фурье по алгоритму Кули-Тьюки

  • Даджион Д., Мерсеро Р. Цифровая обработка многомерных сигналов. М.: Мир, 1988. 488 c.
  • Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир, 1989. 448 c.
  • Оппенгейм А. В., Шафер Р. В. Цифровая обработка сигналов. М.: Связь, 1979. 416 с.
  • Гонсалес Р., Вудс Р. Цифровая обработка изображений. М.: Техносфера, 2005. 1072 с.
  • 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.
  • Rudnick P. Note on the calculation of fourier series//Math. Comp. 1966. Vol. 20, No. 3. P. 429-430.
  • 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-380.
  • 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.
  • 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.
  • Старовойтов А. В. О многомерном аналоге алгоритма Кули-Тьюки//Вестник СибГАУ. 2010. Т. 27, № 1. С. 69-73.
  • Киселев О. И., Кольцова И. В., Тутатчиков В. С. Схема параллельного вычисления одномерного быстрого преобразования Фурье//Наука и образование в XXI веке: материалы Междунар. науч.-практ. конф. (30 сент. 2013, г. Тамбов): в 8 ч./Институт повышения квалификации. Тамбов, 2013. С. 140-141.
  • 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.
  • 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.
  • Малоземов В. П., Машарский С. М. Основы дискретного гармонического анализа. СПб.: НИИММ, 2003.304 c.
  • Программа для вычисления одномерного быстрого преобразования Фурье на основе модифицированного алгоритма Кули-Тьюки: свидетельство о гос. регистрации программы для ЭВМ/Т. В. Сидорова, Т. В. Зыкова; Роспатент. № 2014661701 РФ; заявл. 19.09.2014 (заявка № 2014619428); зарег. 11.11.2014.
  • Dadzhion D., Mersero R. Tsifrovaya obrabotka mnogomernykh signalov . Moscow, Mir Publ., 1988, 488 p.
  • Bleynut R. Bystrye algoritmy tsifrovoi obrabotki signalov . Moscow, Mir Publ., 1989, 448 p.
  • Oppengeym A. V., Shafer R. V. Tsifrovaya obrabotka signalov . Moscow, Svyaz Publ., 1979, 416 p.
  • Gonsalez R., Woods R. Tsifrovaya obrabotka izobrazhenii . Moscow, Tehnosfera Publ., 2005, 1072 p.
  • 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.
  • Rudnick P. Note on the calculation of fourier series. Math. Comp. 1966, Vol. 20, No. 3, P. 429-430.
  • 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.
  • 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.
  • 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.
  • Starovoitov A. V. . Vestnik SibGAU. 2010, No. 1 (27), P. 69-73 (In Russ.).
  • Kiselev O. I., Kolthova I. V., Tutatchikov V. S. . Мaterialy XV Mezhdunar. nauch. konf.
  • “Nauka i obrazovanie v XXI veke” . Tambov, 2013, P. 140-141 (In Russ.).
  • 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.
  • 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.
  • Malozemov V. P., Masharsky S. M. Osnovy diskretnogo garmonicheskogo analiza . St. Peterburg, NIIMM Publ., 2003, 304 p.
  • Sidorova T. V., Zykova T. V. Programma dlya vychisleniya odnomernogo bystrogo preobrazovaniya Fur'e na osnove modifitsirovannogo algoritma Kuli-T'yuki . 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.
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp