РЕФЕРАТ
по дисципліни В«Аналіз часових рядівВ»
на тему:
В«Алгоритм фільтрації, приклад на основі ШПФВ»
ЗМІСТ
Введення
1. Основи алгоритмів ШПФ
2. Алгоритм ШПФ із проріджуванням за часом
3. Програма і приклад реалізації алгоритму ШПФ з проріджуванням по часу
4. Алгоритм ШПФ із проріджуванням по частоті
5. Застосування методу ШПФ для обчислення зворотного ДПФ (ОДПФ)
6. Застосування БПФ для обчислення реакції ЦФ
7. Інші швидкі алгоритми обчислення дискретного перетворення Фур'є
7.1 Узагальнений алгоритм Кулі-Тьюки з довільним підставою з множниками повороту
7.2 Алгоритм простих множників
7.3 Алгоритм винограду
8. Аналіз точності реалізації алгоритмів ШПФ
Висновок
Список використаних джерел
ВСТУП
В основі перетворення Фур'є <# "1.files/image001.gif">
Рисунок 1 - Дослідження лінійного фільтра
Хід вирішення цього завдання залежить від того, яку позицію ми віддамо перевагу. Виберемо тимчасової шлях вирішення (верхня половина рис. 2) - доведеться вхідний сигнал записати як функцію часу S BX ( t ) і використовувати імпульсну характеристику фільтра h ( t ), тобто математичну запис його роботи в часі. Вирушимо по частотному шляху (Нижня половина рис. 2) - потрібно буде оперувати вже не з самим вхідним сигналом, а з його спектром g bx (П‰). О”а і алгоритм роботи нашого фільтра буде потрібно представити в частотній області - у вигляді частотної характеристики K (П‰). О”ля цього скористаємося допомогою В«магічного склаВ» ПФ.
В
Рисунок 2 - Швидке перетворення Фур'є
Отже, два шляхи - який з них обрати? Мабуть, той, який простіше. У всякому разі, в більшості практичних завдань перевага віддається частотному напрямку.
Якщо виконувати ДПФ вхідний послідовності, прямую - строго за вихідній формулі, то буде потрібно багато часу (особливо якщо кількість вхідних відліків велике). Конструктивніше використовувати принцип В«розділяй і володарюй В», що лежить в основі алгоритму ШПФ. Згідно з ним вхідна послідовність ділиться на групи (наприклад, парні і непарні відліки), і для кожної з них виконується ДПФ, а потім отримані результати об'єднуються. У підсумку виходить ДПФ вхідний послідовності - і істотна економія часу. Тому описаний алгоритм так і назвали - швидке перетворення Фур'є. p> У даному рефераті розглянемо більш докладно швидке перетворення Фур'є. br clear=all>
1. ОСНОВИ АЛГОРИТМІВ ШПФ
Дискретне перетворення Фур'є (ДПФ) X (k) кінцевої последовател'ності х (ПТ), п = О, 1, ..., N-1 визначається згідно (1.1), (1.2):
(1.1)
В
(1.2)
причому є періодичною послідовністю з періодом N, так як т = О, 1, 2 ... Безпосереднє обчислення ДПФ (5.1) при комплексних значеннях х (ПТ) вимагає для кожного значення k (N - 1) множень і (N - 1) складань комплексних чисел або 4 (N -1) множень і (2N - 2) складань дійсних чисел, а для всіх N значень k = 0, 1, ..., N -1 потрібно приблизно N 2 множень і N 2 складань комплексних чисел. Таким чином, для великих значень N (порядку декількох сотень або тисяч) пряме обчислення ДПФ (1.1) вимагає виконання вельми великого числа арифметичних операцій множення і додавання, що ускладнює реалізацію обчислення в реальному масштабі часу процесів і спектрів.
Швидким перетворенням Фур'є називають набір алгоритмів, реалізація яких призводить до суттєвого зменшення обчислювальної складності ДПФ (1.1). Вихідна ідея цих алгоритмів полягає в тому, що N-точкове послідовність розбивається, на дві коротші, наприклад на дві (N/2) точкові послідовності, обчислюються ДПФ для цих більш коротких послідовностей і з цих ДПФ конструюється ДПФ вихідної послідовності. Для двох (N/2)-точкових послідовностей потрібно приблизно множень комплексних чисел, тобто число множень (а також складань) зменшується приблизно в 2 рази. Аналогічно замість обчислення ДПФ (Н/2)-точковою послідовності можна обчислити ДПФ для двох (Н/4)-точкових послідовностей і таким чином знову зменшити необхідне число множень і складань. Якщо N = 2 v , v> O і ціле, то процес зменшення розміру ДПФ може бути продовжений до тих пір, поки не залишаться тільки 2-точкові ДПФ. При цьому загальне число етапів обчислення ДПФ дорівнюватиме v = log 2 N, а число необхідних арифметичних операцій для обчислення N-точкового ДПФ буде порядку N v , тобто зменшується приблизно в N/log 2 N...
