разів. Так, при N = 1000 для прямого обчислення ДПФ згідно (1.1) потрібно приблизно N 2 = 10 6 операцій комплексних множень і складань, а при використанні алгоритмів ШПФ таких операцій потрібно всього порядку 10 4 , тобто обсяг обчислень скорочується приблизно на два порядку.
Розглянемо два алгоритми ШПФ: з проріджуванням за часом (в яких потрібно перестановка відліків вхідний послідовності х (ПТ)) і з проріджуванням по частоті (в яких потрібно перестановка відліків вихідний послідовності Х (k) ).
2. АЛГОРИТМ БПФ З проріджування ПО ЧАСУ
Нехай потрібно обчислити ДПФ (1.1) при N = 2 v , де v> O. де v> O ціле (якщо N 2V, то можна послідовність х (ПТ) доповнити в кінці нульовими елементами так, щоб довжина результуючої послідовності була ступенем 2).
Розіб'ємо вихідну N-точкову послідовність х (ПТ) = х v (П), де v = log 2 N. п = О.. ​​ .., N -1 , на дві (N/2)-точкові послідовності Х v-1, 0 (п) і Х v-1, 1 (п), складаються відповідно з парних і непарних членів х (ПТ), т. е.
(2.1)
При цьому N-точкове ДПФ (1.1) можна записати у вигляді
(2.2)
Враховуючи, що отримуємо
(2.3)
Де і - (N/2)-точкові ДПФ відповідно послідовностей і:
;.
В
Так як X v (k) повинно бути визначено для N точок (k = 0, 1, ..., N-1) , а Х v-1, 0 (k) і Х v-1, 1 (k) визначаються толькo для N/2 точок (k = 0, 1, ..., N/2-1), Довизначивши (2.3) для значень k = N/2, N/2 +1, ..., N-1; враховуючи, що Х v-1, 0 (k) і Х v-1, 1 (k) періодичні функції з періодом Н/2, можна записати
В
X v (k + N/2) = Х v-1, 0 (k + N/2) + Х v-1, 1 (K + N/2) = Х v-1, 0 (k) - Х v-1, 1 (K),
(2.4)
Так як == -1.
Формули (2.3) і (3.4) дають алгоритм обчислення N-точкового ДПФ через (N/2)-точкових ДПФ. Цей алгоритм можна представити спрямованим графом, що має вигляд В«метеликаВ»
В
Рисунок 3 - граф має вигляд В«МетеликиВ»
(рис.3, а), в якому вихідні числа с і d виходять з вхідних чисел а і b по правилам
(2.5)
Як приклад граф на рис.3, б представляє операції (2.3) і (2.4). Аналогічно можна тепер виразити (N/2)-точкові ДПФ Х v-1, 0 (k) і Х v-1, 1 (k) через (N/4)-точкові ДПФ:
(2.6а)
І
(2.7б)
де Х v-2, 0 (k) і Х v-2, 1 (k ) - відповідно (N/4)-точкові ДПФ парних Х v-2, 0 (n) і непарних Х v-2, 1 (п)
членів послідовності Х v-1, 0 (п), а Х v-2, 2 (k) і Х v-2, 3 (k)-відповідно (N/4)-точкові ДПФ парних Х v-2, 2 (П) і непарних Х v-2, 3 (п) членів послідовності Х v-1, 1 (п).
Процес зменшення розміру ДПФ від М до M/2, де М дорівнює ступеня 2, продовжується до тих пір, поки на v-му кроці (v = log 2 N, де N-початковий розмір ДПФ) не опиняться тільки 2-точкові ДПФ Ф (k), k = 0,1, для двоточкових послідовностей (п), п = 0,1, що визначаються з співвідношень
(2.8)
Останні обчислюються без операції множення.
Приклад 1. Побудуємо алгоритм ШПФ із проріджуванням за часом для N = 8 = 2 3 , v = 3, тобто для послідовності х (ПТ), п = 0, 1,2, З, 4.5,6,7. Розіб'ємо згідно (2.1) вихідну послідовність х (ПТ) = х 3 (п) на дві послідовності: x 2,0 (п) і х 2,1 (n), - складаються відповідно з парних і непарних членів х 3 (п):
В
(2.9)
В
Рисунок 4 - Алгоритм 8-точкового ШПФ
Тепер знову розіб'ємо послідовності (2.9) на послідовності з непарних та парних членів послідовностей (2.9):
(2.10)
Послідовності (2.10) є вже двоточковими.
Тепер, використовуючи алгоритм, представлений графом В«метеликВ» (див. рис.3, а), будуємо алгоритм 8-точкового ШПФ (рис. 4). Спочатку побудуємо вихідний масив. Як видно з (2.10), він з елементів послідовності х (n) = х (nТ), n = 0,1 ... 7, причому на входах першого графа В«метеликВ» першого ст...
