Студопедия — Быстрое преобразование Фурье
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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






Рассмотрим дискретное прямое преобразование Фурье.

, (1)

= 0, 1,..., -1; k = 0, 1,..., -1; j -мнимая единица.

- отсчеты сигнала через интервал времени

- отсчеты спектральной плотности через интервал частоты

- число отсчетов.

Из (1) следует, что для определения одного спектрального коэффициента требуется умножений, вычислений экспонент и сложений, а на все коэффициентов требуется 2 умножений, сложений и вычислений экспонент. Алгоритм быстрого преобразования Фурье позволяет уменьшить число таких операций до

При = 210 = 1024 машинное время уменьшается в 100 раз.

Пусть = 2p (p - целое число). Разобьем последовательность (1) на сумму двух последовательностей, составленных из четных и нечетных номеров.

(2)

Однако вычисления по (2) можно ограничить номером , т. к. функции и являются периодическими с периодом из-за большего (в два раза) интервала отсчетов между ними. Итак, при будем иметь:

т.к.

Аналогично

. (3)

Теперь снова разобьем суммы и с четными и нечетными новыми номерами слагаемых:

;

= 0, 1,..., 2P-2-1.

Далее суммы снова можно разбить. Получим:

= 0, 1,..., 2P-3-1; для номеров +2P-3 знаки перед экспонентами заменяют на минус.

остальным членам соответствуют следующие отсчеты sk:

k=0,1,...2P-3-1.

Таким образом, мы имеем все время удваивающееся число сумм X,Y для одного, однако число членов в этих суммах все время в два раза уменьшается и, кроме того, в два раза уменьшается число номеров, так что общее число сумм остается тем же, но уменьшается число членов в каждой сумме.

Продолжая такое разбиение l раз, будем иметь:

;

(4)

.

где (5)

l = 1, 2,..., p; i = 1, 2,..., 2l-2 в (4) и i = 1, 2,..., 2l-1 в (5).

n = 0, 1,..., 2P-l-1. При l = p получим = 0, k = 0.

i = 1, 2,..., 2P-1.

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

Задано = 2P отсчетов сигнала , i = 0, 1, 2,..., -1, l = p, = 0

for i = 1 to N/2 , end.

* for n = 0 to n = 2P-l-1.

for i = 1 to i = 2l-2.

end, end.

l=l-1, if l>1 go to *, else for n=0 to .

, end.

 







Дата добавления: 2015-09-04; просмотров: 359. Нарушение авторских прав; Мы поможем в написании вашей работы!



Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...

Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

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

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

Деятельность сестер милосердия общин Красного Креста ярко проявилась в период Тритоны – интервалы, в которых содержится три тона. К тритонам относятся увеличенная кварта (ув.4) и уменьшенная квинта (ум.5). Их можно построить на ступенях натурального и гармонического мажора и минора.  ...

Ведение учета результатов боевой подготовки в роте и во взводе Содержание журнала учета боевой подготовки во взводе. Учет результатов боевой подготовки - есть отражение количественных и качественных показателей выполнения планов подготовки соединений...

Сравнительно-исторический метод в языкознании сравнительно-исторический метод в языкознании является одним из основных и представляет собой совокупность приёмов...

Концептуальные модели труда учителя В отечественной литературе существует несколько подходов к пониманию профессиональной деятельности учителя, которые, дополняя друг друга, расширяют психологическое представление об эффективности профессионального труда учителя...

Studopedia.info - Студопедия - 2014-2024 год . (0.008 сек.) русская версия | украинская версия