14.2 Швидке перетворення Фурьє.
Швидке перетворення Фур'є [32] засновується на властивостях кругової діаграми і, крім того, використовує скорочення кількості операцій множення відповідно з формулою
ab ac=a(b c).
Зліва у цьому рівнянні дві операції множення, а праворуч лише одна. З урахуванням цих посилань знайдемо компоненти дискретного спектра (частотної характеристики) згідно з матрицею (8.50)
w0=[(k0+k4)+(k2+k6)]+[(k1+k5)+(k3+k7)]; w1=[(k0-k4)+(k2-k6)m2]+[(k1-k5)+(k3-k7)m2]m; w2=[(k0+k4)-(k2+k6)]+[(k1+k5)-(k3+k7)]m2; w3=[(k0-k4)-(k2-k6)m2]+[(k1-k5)-(k3-k7)m2]m3; w4=[(k0+k4)+(k2+k6)]-[(k1+k5)+(k3+k7)]; w5=[(k0-k4)+(k2-k6)m2]-[(k1-k5)+(k3-k7)m2]m; w6=[(k0+k4)-(k2+k6)]-[(k1+k5)-(k3+k7)]m2; w7=[(k0-k4)-(k2-k6)m2]-[(k1-k5)-(k3-k7)m2]m3. |
(8.5) |
Iз (8.51) видно, що в круглих дужках є лінійні комбінації елементів вектора K (імпульсної характеристики системи). Таких комбінацій вісім. У квадратних дужках маємо комбінації круглих дужок (їх теж вісім). Останні операції утворюють зважені суми із квадратних дужок.
Ці послідовні операції можуть бути представлені у вигляді множини трьох порівняно простих матриць (справа наліво). Тоді матриця ЦПФ приймає вид:
M=M3M2M1, |
(8.52) |
,
,
Порожні клітини матриць M1, M2, M3 заповнюються нолями. Розклад матриці М на три матриці M1, M2, M3 називають факторизацією. Процедура розрахунків (8.51) дискретного спектру (частотної характеристики) може бути ілюстрована спеціальним графом. Такий граф може пояснити послідовність обчислень, що предписуються факторізованою матрицею.
В алгоритм обчислення вводяться відліки функції K(t), а праворуч, на виході алгоритма ШПФ маємо відліки частотної характеристики.
Формально ШПФ реалізується шляхом розподілу початкової послідовності на парні (k0,k2,k4,k6,...) і непарні (k1,k3,k5,k7,...) послідовності. З ними далі поступають аналогічно. Ці процедури повторюють до тих пір поки незостанеться по одній парі чисел, які поступають на схеми першого етапу. Оскільки ці схеми нагадують бабочку, то їх i іменують "бабочками". Відносно восьмиточкового ШПФ цими парами є k0k4, k2k6, k1k5, k3k7. На першому етапі операції множення не виконуються (множиться на 1). Тут формуються суми та різниці отриманих пар. Алгоритм обчислення зручно представляти у вигляді схеми спецпроцесора ШПФ на "бабочках", що показано на рис.8.4.
Весь алгоритм складається із трьох етапів. У загальному випадку для N-точкового ШПФ необхідно log2N етапів. На кожному із них виконуються (1/2)N операцій множення. Таким чином, алгоритм ШПФ має всього (N/2)log2N операцій множення. Загальний алгоритм ЦПФ має N 2 операцій множення. Тому ШПФ порівняно з ЦПФ має перевагу по операціях множення в 2N(log2N)-1 разів. Розглянутий алгоритм дозволяє обчислювати частотні характеристики систем з одним входом та одним виходом. Але багаторазове звернення до цього алгоритма забезпечить знаходження частотних характеристик по всіх необхідних входах та виходах.