🗊Презентация Быстрое преобразование Фурье (БПФ)

Быстрое преобразование Фурье (БПФ) Володин Георгий Викторович

БПФ = быстрое ДПФ БПФ – не является новым видом ПФ, это набор алгоритмов эффективного вычисления дискретного преобразования Фурье ДПФ => Кол-во операций: N – перемножения комплексных чисел (N-1) – сложения комплексных чисел Для k точки спектра!

Эффективность БПФ по сравнению с ДПФ

Проблема поворачивающего множителя в ДПФ - поворачивающий множитель Свойства: Периодичность: Симметрия:

 БПФ с прореживанием по времени

Построение алгоритма …

Изображение алгоритма вычисления БПФ для 8 отсчётов (прореживание по времени)

Обратное БПФ

Вариации БПФ

Математика закончилась

Минусы БПФ Необходимо отсчётов (можно добавить необходимое количество нулевых отсчётов – “закидывание нулями”). БПФ вычисляет либо все точки спектра либо ни одного! Поэтому для расчёта не полного спектра быстрее будет ДПФ.

Сверх быстрое БПФ Это теоретически это возможно, однако это требует построение спецвычислителя (DSP – digital signal processor). Окончательная экономия времени вычисления различается для разных DSP, но алгоритм БПФ по основанию 4 может быть более чем вдвое быстрым, чем алгоритм по основанию 2 для DSP с оптимальной архитектурой. Постоянно появляются новые концепции БПФ (УТ БПФ) которые имеют свои специфические выгоды, однако так или иначе они трудно реализуемы на сегодняшний день

БПФ и теория обработки сигналов

История создания БПФ Данное преобразование было предложено Кули и Таки (J.W.Cooley и J.W.Tukey) в 1960- ых годах и фактически являлось открытием заново идеи Рунге, Даниэльсона и Ланкоса (Runge (1903), Danielson и Lanczos (1942)). Джеймс Кули был нанят в IBM Thomas J. Watson Research Center в Yorktown Heights, что в Нью-Йорке. Кули работал над своим собственным проектом, когда к нему обратился Ричард Гарвин (Richard Garwin) и показал некоторые заметки Джона Тьюки (John Tukey) об алгоритме, который теоретически способен вычислять быстрое преобразование Фурье. Гарвин, в отличие от Кули, хорошо понимал всю важность этого алгоритма и его огромную практическую значимость, и поэтому настаивал на разработке этого алгоритма. Гарвин был значительно более заинтересован в улучшении дистанционного сейсмического мониторинга ядерных взрывов; русские едва ли согласились бы на проведение инспекций на их территории. Гарвин так же видел необходимость в разработке методов раннего акустического обнаружения подводных лодок.

Список литературы Лекция №5 из курса “Теория Сигналов и технологии их обработки” – Уолт Кестер; Лаборатория физических основ и технологий беспроводной связи (http://ip-5-125.unn.ru/ftp/public/analog/5.pdf) Лекция №12 из курса “Проектирование микропроцессорныx систем управления” – Денисов К.М.; Институт ЭТИПЭМС, кафедра электротехники и прецизионных электромеханических систем (http://ets.ifmo.ru/denisov/dsp/lec12.htm) Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.. Алгоритмы: построение и анализ, 2-е издание, М.:Вильямс, 2005, стр. 926-953, глава 30, «Полиномы и быстрое преобразование Фурье»

Вопросы к Зачёту В чём состоит идея быстрого преобразования Фурье? Преимущества и недостатки БПФ Алгоритм БПФ: прореживание по времени и по частоте

Внимание!