Быстрое преобразование Фурье. (Лекция 12)

Сентябрь 15, 2022

Главная
Физика
Быстрое преобразование Фурье. (Лекция 12)

Содержание

2. Быстрое преобразование Фурье Основной принцип всех этих алгоритмов заключается в разложении операций вычисления ДПФ сигнала длины
3. Быстрое преобразование Фурье Рассмотрим алгоритмы БПФ с основанием 2, когда длина последовательности , где целое число.
4. Быстрое преобразование Фурье Разобьем на две -точечные последовательности, состоящие из отсчетов с четными и нечетными номерами
5. Быстрое преобразование Фурье Так как , то предыдущее выражение можно записать в виде: (12.1) Каждая из
6. Быстрое преобразование Фурье Схема БПФ
7. Быстрое преобразование Фурье Далее можно вычислить каждое точечное ДПФ разбиением сумм на два точечных ДПФ. Таким
8. Быстрое преобразование Фурье Продолжим описанную процедуру разбиения исходной ДПФ на преобразования меньшей размерности, пока не останутся
9. Быстрое преобразование Фурье Число требуемых при этом пар операций «умножение – сложение» можно оценить как .
10. Быстрое преобразование Фурье Из рассмотренного алгоритма следует, что на каждой ступени вычислений происходит преобразование одного множества
12. Скачать презентацию

Слайд 2

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

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

Слайд 3

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

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

Слайд 4

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

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

Слайд 5

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

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

Слайд 6

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

Слайд 7

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

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

Слайд 8

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

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

Слайд 9

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

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

Слайд 10

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

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

Быстрое преобразование Фурье. (Лекция 12)

Содержание

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

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

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

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

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

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

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

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

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

Похожие презентации