Инфоурок Другое ПрезентацииБыстрое преобразование Фурье

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

Скачать материал
Скачать материал "Быстрое преобразование Фурье"

Получите профессию

Методист-разработчик онлайн-курсов

за 6 месяцев

Пройти курс

Рабочие листы
к вашим урокам

Скачать

Методические разработки к Вашему уроку:

Получите новую специальность за 2 месяца

Директор десткого сада

Описание презентации по отдельным слайдам:

  • Лекция № 12 Быстрое преобразование ФурьеНахождение спектральных составляющих...

    1 слайд

    Лекция № 12
    Быстрое преобразование Фурье
    Нахождение спектральных составляющих дискретного комплексного сигнала непосредственно по формуле ДПФ требует комплексных умножений и комплексных сложений. Так как количество вычислений, а следовательно, и время вычислений приблизительно пропорциональны , то при больших количество арифметических операций весьма велико. Поэтому нахождение спектра в реальном времени даже для современной вычислительной техники представляет сложную задачу.
    По этой причине представляет значительный интерес вычислительные процедуры, уменьшающие количество умножений и сложений.

  • Быстрое преобразование ФурьеОсновной принцип всех этих алгоритмов заключается...

    2 слайд

    Быстрое преобразование Фурье
    Основной принцип всех этих алгоритмов заключается в разложении операций вычисления ДПФ сигнала длины на вычисление преобразований Фурье с меньшим числом точек. Разделив анализируемый набор отсчетов на части, вычисляют их ДПФ и объединяют результаты. Такие процедуры получили название алгоритмов быстрого преобразования Фурье БПФ.
    При реализации БПФ возможно несколько вариантов организации вычислений в зависимости от способа деления последовательности отсчетов на части (прореживание по времени или по частоте) и от того, на сколько фрагментов производится разбиение последовательности на каждом шаге (основание БПФ).

  • Быстрое преобразование Фурье     Рассмотрим алгоритмы БПФ с основанием 2, ког...

    3 слайд

    Быстрое преобразование Фурье
    Рассмотрим алгоритмы БПФ с основанием 2, когда длина последовательности , где целое число.
    БПФ с прореживанием по времени. Рассмотрим идею БПФ с прореживанием по времени на примере деления набора отсчетов пополам. Введя общепринятое в литературе обозначение для дискретных экспоненциальных функций:


    Запишем ДПФ сигнала в виде:




  • Быстрое преобразование ФурьеРазобьем            на две           -точечные по...

    4 слайд

    Быстрое преобразование Фурье
    Разобьем на две -точечные последовательности, состоящие из отсчетов с четными и нечетными номерами соответственно. В результате получим:



    Заменяя индексы суммирования на при четном и на
    при нечетном , придем к выражению:

  • Быстрое преобразование ФурьеТак как                  , то предыдущее выражени...

    5 слайд

    Быстрое преобразование Фурье
    Так как , то предыдущее выражение можно записать в виде:



    (12.1)

    Каждая из сумм (12.1) является точечным ДПФ: первая – для четных отсчетов исходной последовательности, а вторая – для нечетных. Несмотря на то, что индекс в формуле (12.1) распространяется на значений , каждая из сумм требует вычислений только для , так как и
    периодичны по с периодом . Объединение же этих сумм приводит к точечному ДПФ .






  • Быстрое преобразование ФурьеСхема БПФN|2
ДПФN|2
ДПФРис.12.1

    6 слайд

    Быстрое преобразование Фурье
    Схема БПФ
    N|2
    ДПФ
    N|2
    ДПФ
    Рис.12.1

  • Быстрое преобразование ФурьеДалее можно вычислить каждое           точечное Д...

    7 слайд

    Быстрое преобразование Фурье
    Далее можно вычислить каждое точечное ДПФ разбиением сумм на два точечных ДПФ. Таким образом, и могут быть вычислены в виде:

  • Быстрое преобразование ФурьеПродолжим описанную процедуру разбиения исходной...

    8 слайд

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

  • Быстрое преобразование ФурьеЧисло требуемых при этом пар операций «умножение...

    9 слайд

    Быстрое преобразование Фурье
    Число требуемых при этом пар операций «умножение – сложение» можно оценить как . Таким образом, вычислительные затраты по сравнению с непосредственным использованием формулы ДПФ уменьшается в раз. При больших это отношение становится весьма велико. Например, при
    достигается более чем 100-кратное ускорение, но и это еще не предел. Количество комплексных умножений в алгоритме БПФ с прореживанием по времени может быть сокращено вдвое.

  • Быстрое преобразование ФурьеИз рассмотренного алгоритма следует, что на каждо...

    10 слайд

    Быстрое преобразование Фурье
    Из рассмотренного алгоритма следует, что на каждой ступени вычислений происходит преобразование одного множества из комплексных чисел в другое множество из комплексных чисел.
    Будем считать входным массивом на ступени вычисления , а – выходным массивом на ступени вычислений.
    С учетом введенных обозначений имеем:

  • Быстрое преобразование ФурьеВышеприведенные соотношения подсказывают метод со...

    11 слайд

    Быстрое преобразование Фурье
    Вышеприведенные соотношения подсказывают метод сокращения числа комплексных умножений вдвое. Так как , эти соотношения можно записать в виде:



    Так как на каждую ступень разбиения имеется
    таких операций, а общее число ступеней равно , то общее число пар операций «умножение-сложение» сокращается до .


Получите профессию

Экскурсовод (гид)

за 6 месяцев

Пройти курс

Рабочие листы
к вашим урокам

Скачать

Скачать материал

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 626 501 материал в базе

Скачать материал

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

  • Скачать материал
    • 22.09.2020 452
    • PPTX 251 кбайт
    • Оцените материал:
  • Настоящий материал опубликован пользователем Колесова Наталия Анатольевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт

    Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

    Удалить материал
  • Автор материала

    Колесова Наталия Анатольевна
    Колесова Наталия Анатольевна
    • На сайте: 3 года и 3 месяца
    • Подписчики: 0
    • Всего просмотров: 79262
    • Всего материалов: 238

Ваша скидка на курсы

40%
Скидка для нового слушателя. Войдите на сайт, чтобы применить скидку к любому курсу
Курсы со скидкой

Курс профессиональной переподготовки

Менеджер по туризму

Менеджер по туризму

500/1000 ч.

Подать заявку О курсе

Курс повышения квалификации

Специалист в области охраны труда

72/180 ч.

от 1750 руб. от 1050 руб.
Подать заявку О курсе
  • Сейчас обучается 42 человека из 21 региона

Курс профессиональной переподготовки

Организация деятельности библиотекаря в профессиональном образовании

Библиотекарь

300/600 ч.

от 7900 руб. от 3950 руб.
Подать заявку О курсе
  • Сейчас обучается 281 человек из 66 регионов

Курс профессиональной переподготовки

Руководство электронной службой архивов, библиотек и информационно-библиотечных центров

Начальник отдела (заведующий отделом) архива

600 ч.

9840 руб. 5900 руб.
Подать заявку О курсе

Мини-курс

Развитие детей: сенсорика, самостоятельность и моторика

3 ч.

780 руб. 390 руб.
Подать заявку О курсе

Мини-курс

Продвинутые техники нарративного подхода в психологии

5 ч.

780 руб. 390 руб.
Подать заявку О курсе
  • Сейчас обучается 20 человек из 14 регионов

Мини-курс

Основы политической науки

4 ч.

780 руб. 390 руб.
Подать заявку О курсе