Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


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

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

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

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

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

Содержание

БПФ = быстрое ДПФБПФ – не является новым видом ПФ, это набор алгоритмов эффективного вычисления дискретного преобразования ФурьеДПФ => Кол-во операций: N – перемножения комплексных чисел(N-1) – сложения комплексных чиселДля k точки спектра!
Быстрое преобразование Фурье (БПФ)Володин Георгий Викторович БПФ = быстрое ДПФБПФ – не является новым видом ПФ, это набор Эффективность БПФ по сравнению с ДПФЕсли процессор имеет скорость 1 выч/нс, то Проблема поворачивающего множителя в ДПФ А давайте придумаем алгоритм вычленения повторяющихся поворачивающих множителей  БПФ с прореживанием по времени  N/2 ДПФ отсчётовN/2 ДПФ отсчётов  NN/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 точечного преобразования  Мало при большом N Деление подобным образом в Изображение алгоритма вычисления БПФ  для 8 отсчётов (прореживание по времени) Прореживание на Обратное БПФ ОДПФ(*) + умножение на N(*) + БПФ = ОБПФОбратное! Вариации БПФБПФ с прореживанием по частотеДПФДПФnnВычисление таблицы значенийИспользование рекуррентной формулыПредполагается хранение поворачивающих Математика закончиласьТеперь можно отдохнуть на моём кресле Минусы БПФ  Сверх быстрое БПФЭто теоретически это возможно, однако это требует построение спецвычислителя (DSP БПФ и теория обработки сигналовЭффект Гиббса+Эффект “перепада громкостей”Оконное преобразованиеШирокие колебанияМелкие колебанияttttНеопределённость:Большая длина История создания БПФДанное преобразование было предложено Кули и Таки (J.W.Cooley и J.W.Tukey) Список литературыЛекция №5 из курса “Теория Сигналов и технологии их обработки” – Вопросы к ЗачётуВ чём состоит идея быстрого преобразования Фурье? Преимущества и недостатки Внимание!Спасибо за внимание!
Слайды презентации

Слайд 2 БПФ = быстрое ДПФ
БПФ – не является новым

БПФ = быстрое ДПФБПФ – не является новым видом ПФ, это

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

Фурье

ДПФ =>

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

Слайд 3 Эффективность БПФ по сравнению с ДПФ
Если процессор имеет

Эффективность БПФ по сравнению с ДПФЕсли процессор имеет скорость 1 выч/нс,

скорость 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/2 ДПФ отсчётовN/2 ДПФ отсчётов  NN/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
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 точечного преобразования  Мало при большом N Деление подобным образом

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

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


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


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

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

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

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

 

 

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

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

Итог


Слайд 8 Обратное БПФ
 
ОДПФ
(*) + умножение на N
(*) + БПФ

Обратное БПФ ОДПФ(*) + умножение на N(*) + БПФ = ОБПФОбратное!

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


Слайд 9 Вариации БПФ
БПФ с прореживанием по частоте
ДПФ
ДПФ

n
n
Вычисление таблицы значений
Использование

Вариации БПФБПФ с прореживанием по частотеДПФДПФnnВычисление таблицы значенийИспользование рекуррентной формулыПредполагается хранение

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

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

Слайд 10 Математика закончилась
Теперь можно отдохнуть на моём кресле

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

Слайд 11 Минусы БПФ
 

Минусы БПФ 

Слайд 12 Сверх быстрое БПФ
Это теоретически это возможно, однако это

Сверх быстрое БПФЭто теоретически это возможно, однако это требует построение спецвычислителя

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

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

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

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



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

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

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

БПФ и теория обработки сигналовЭффект Гиббса+Эффект “перепада громкостей”Оконное преобразованиеШирокие колебанияМелкие колебанияttttНеопределённость:Большая

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






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

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

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



Слайд 14 История создания БПФ
Данное преобразование было предложено Кули и

История создания БПФДанное преобразование было предложено Кули и Таки (J.W.Cooley и

Таки (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 из курса “Теория Сигналов и

Список литературыЛекция №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 Вопросы к Зачёту
В чём состоит идея быстрого преобразования

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

Фурье?

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

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

и по частоте






  • Имя файла: bystroe-preobrazovanie-fure-bpf.pptx
  • Количество просмотров: 92
  • Количество скачиваний: 0