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

Презентация на тему Презентация на тему Быстрое преобразование Фурье (БПФ), предмет презентации: Математика. Этот материал содержит 17 слайдов. Красочные слайды и илюстрации помогут Вам заинтересовать свою аудиторию. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций ThePresentation.ru в закладки!

Слайды и текст этой презентации

Слайд 1
Текст слайда:

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

Володин Георгий Викторович


Слайд 2
Текст слайда:

БПФ = быстрое ДПФ

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

ДПФ =>

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


Слайд 3
Текст слайда:

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

Если процессор имеет скорость 1 выч/нс, то
для ДПФ 10^9 будет найдено за 32 года, а с
использованием ПБФ всего за 30 секунд

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

N*log2(N)

N^2


Слайд 4
Текст слайда:

Проблема поворачивающего множителя в ДПФ

 

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

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



Слайд 5
Текст слайда:




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

 

 



N/2 ДПФ отсчётов

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


Слайд 6
Текст слайда:

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

 

 


 

Итоговая формула
для N точечного
преобразования

 

 


Мало при большом N

 

Деление подобным образом в итоге уменьшило затраты вычислительной мощности. Так почему бы не продолжить этот процесс?


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


Слайд 7
Текст слайда:

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

 

Прореживание на 4 группы 2-х точечных ДПФ

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

 

 

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

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

Итог


Слайд 8
Текст слайда:

Обратное БПФ

 

ОДПФ

(*) + умножение на N

(*) + БПФ = ОБПФ

Обратное!


Слайд 9
Текст слайда:

Вариации БПФ

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

ДПФ

ДПФ


n

n

Вычисление таблицы значений

Использование рекуррентной формулы

Предполагается хранение
поворачивающих множителей
в массиве данных.

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


Слайд 10
Текст слайда:

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

Теперь можно отдохнуть на моём кресле


Слайд 11
Текст слайда:

Минусы БПФ

 


Слайд 12
Текст слайда:

Сверх быстрое БПФ

Это теоретически это возможно, однако это требует построение спецвычислителя (DSP – digital signal processor).

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

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



Слайд 13
Текст слайда:

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


Эффект Гиббса

+


Эффект
“перепада громкостей”

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







Широкие колебания

Мелкие колебания

t

t

t

t

Неопределённость:

Большая длина окна – выход из
интервала гармоничности

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



Слайд 14
Текст слайда:

История создания БПФ

Данное преобразование было предложено Кули и Таки (J.W.Cooley и J.W.Tukey) в 1960- ых годах и фактически являлось открытием заново идеи Рунге, Даниэльсона и Ланкоса (Runge (1903), Danielson и Lanczos (1942)).

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

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

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


Слайд 15
Текст слайда:

Список литературы

Лекция №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, «Полиномы и быстрое преобразование Фурье»


Слайд 16
Текст слайда:

Вопросы к Зачёту

В чём состоит идея быстрого преобразования Фурье?

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

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






Слайд 17
Текст слайда:

Внимание!

Спасибо за внимание!


Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика