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

видом ПФ, это набор алгоритмов эффективного вычисления дискретного преобразования

Фурье

ДПФ =>

Кол-во операций:
N – перемножения комплексных чисел
(N-1) – сложения комплексных чисел
Для k точки спектра!

скорость 1 выч/нс, то
для ДПФ 10^9 будет найдено

за 32 года, а с
использованием ПБФ всего за 30 секунд

O(N^2) – скорость вычисления для ДПФ, где мы опускаем сложение
VS
O(N*Log2(N)) – скорость вычисления для
БПФ, и скоро мы увидим почему

N*log2(N)

N^2

вычленения повторяющихся поворачивающих множителей и будем использовать их свойства

для упрощения вычислений!

(основная идея БПФ)

отсчётов
 

 
N
N/2
ДПФ
N/2
ДПФ
Xe[0]
Xe[1]
Xe[2]
Xe[3]
Xo[0]
Xo[1]
Xo[2]
Xo[3]
O(L)=O(2(N/2)^2+N)=O(N^2/2+N)
N=8

N
 
Деление подобным образом в итоге уменьшило затраты вычислительной мощности.

Так почему бы не продолжить этот процесс?

(Учитывая умножения на 1/-1))

по времени)
 
Прореживание на 4 группы 2-х точечных ДПФ
Базовая операция

“бабочка” для прореживания по времени

 

 

Бит-ревёрсное прореживание

(Несёт малую вычислительную мощность, алгоритм Рейдера)

Итог

= ОБПФ
Обратное!

рекуррентной формулы
Предполагается хранение
поворачивающих множителей
в массиве данных.
Для использования этой

формулы для
разных этапов перемножения, достаточно предварительно вычислить и запомнить несколько пов. множ.

требует построение спецвычислителя (DSP – digital signal processor).

Окончательная экономия

времени вычисления различается для разных DSP, но алгоритм БПФ по основанию 4 может быть более чем вдвое быстрым, чем алгоритм по основанию 2 для DSP с оптимальной архитектурой.

Постоянно появляются новые концепции БПФ (УТ БПФ) которые имеют свои специфические выгоды, однако так или иначе они трудно реализуемы на сегодняшний день

преобразование






Широкие колебания
Мелкие колебания
t
t
t
t
Неопределённость:
Большая длина окна – выход из
интервала

гармоничности

Маленькая длина окна –
искажения области низких частот

Таки (J.W.Cooley и J.W.Tukey) в 1960- ых годах и

фактически являлось открытием заново идеи Рунге, Даниэльсона и Ланкоса (Runge (1903), Danielson и Lanczos (1942)).

Джеймс Кули был нанят в IBM Thomas J. Watson Research Center в Yorktown Heights, что в Нью-Йорке. Кули работал над своим собственным проектом, когда к нему обратился Ричард Гарвин (Richard Garwin) и показал некоторые заметки Джона Тьюки (John Tukey) об алгоритме, который теоретически способен вычислять быстрое преобразование Фурье.

Гарвин, в отличие от Кули, хорошо понимал всю важность этого алгоритма и его огромную практическую значимость, и поэтому настаивал на разработке этого алгоритма.

Гарвин был значительно более заинтересован в улучшении дистанционного сейсмического мониторинга ядерных взрывов; русские едва ли согласились бы на проведение инспекций на их территории. Гарвин так же видел необходимость в разработке методов раннего акустического обнаружения подводных лодок.

технологии их обработки” – Уолт Кестер; Лаборатория физических основ

и технологий беспроводной связи
(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, «Полиномы и быстрое преобразование Фурье»

Фурье?

Преимущества и недостатки БПФ

Алгоритм БПФ: прореживание по времени

и по частоте