Швидке перетворення Фур'є

Знаходження спектральних складових дискретного комплексного сигналу безпосередньо по формулі ДПФ вимагає комплексних множень і комплексних додавань. Оскільки кількість обчислень, а отже, і час обчислень приблизно пропорційні , то при великих кількість арифметичних операцій дуже велика. Тому знаходження спектру в реальному часі навіть для сучасної обчислювальної техніки є складним завданням.

З цієї причини представляють значний інтерес обчислювальні процедури, які зменшують кількість множень і складань. Основний принцип усіх цих алгоритмів полягає в розкладанні операцій обчислення ДПФ сигналу довжини на обчислення перетворень Фур'є з меншим числом точок. Розділивши аналізований набір відліків на частини, обчислюють їх ДПФ і об'єднують результати. Такі процедури дістали назву алгоритмів швидкого перетворення Фур'є (ШПФ).

При реалізації ШПФ можливі декілька варіантів організації обчислень залежно від способу ділення послідовності відліків на частини (проріджування за часом або по частоті) і від того, на скільки фрагментів розбивається послідовність на кожному кроці (основа ШПФ). Найбільш простими і широко використовуваними є алгоритми ШПФ з основою 2, коли довжина послідовності є цілою мірою числа 2, тобто , де ціле число.

Проаналізуємо більш детально операції ДПФ на прикладі N =8. У цьому випадку, ввівши загальноприйняте в літературі позначення для дискретних експоненціальних функцій

, (7.17)

матимемо , тут і далі індекс N =8 опущено для простоти запису.

Користуючись матричним представленням вираз для обчислення ДПФ (вже без множника 1 /N)

, (7.18)

може бути представлений у вигляді добутку

 

, (7.19)

 

де матриця ДПФ прийме вигляд

, (7.20)

і вектор , - знак транспонування.

Проаналізуємо . Точки знаходяться на колі одиничного радіусу і являють собою періодичну послідовність. Тобто значення повністю визначають будь-яку степінь при (за умови N =8).

 

Рисунок 7.1 – Комплексна площина .

Показані числа = .

 

Суми виду (7.18) називають згортками. Згортки, які мають вказану властивість називають круговими.

Звернемо також увагу на те, що числа, які відповідають точкам розташованим діаметрально протилежно на колі відрізняються лише знаком. Тому , , , . Тобто будь-яка ціла степінь може бути представлена через 1, , , . З урахуванням цього матрицю ДПФ можна подати у вигляді

. (7.21)

В кожній строчці цієї матриці можна побачити або однакові або такі, що різняться за знаком члени. Ідея ШПФ застосовує описані вище властивості кругової згортки і, крім того, передбачає скорочення кількості операцій множення відповідно до тотожності

. (7.22)

Ліворуч у виразі (7.22) два множення, а праворуч лише одне. З урахуванням цього знайдемо складові дискретного спектру:

;

;

;

; (7.23)

;

;

;

.

Видно, що у круглих дужках маються лінійні комбінації елементів вектора . Кількість таких комбінацій дорівнює 8. В квадратних дужках вагові комбінації сум у круглих дужках (їх теж вісім). Останні операції передбачають утворення вагових сум з результатів у квадратних дужках.

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

 

, (7.24)

де

, (7.25)

 

, (7.26)

 

. (7.26)

Якщо обчислити добуток цих трьох матриць отримаємо матрицю . Розкладання матриць на прості множники виду (7.24) називають факторизацією.

Процедуру обчислення дискретного спектру зручно подати у вигляді графа (рис. 7.2), який пояснює послідовність дій, виконуваних факторизованою матрицею.

 

Рисунок 7.2 – Граф ШПФ. Кружком позначено підсумовування, а квадратом - множення на величину, що вказана в квадраті.

 

Промисловість серійно випускає інтегральні мікросхеми, які виконують чотирьохточкове ДПФ, яке є базовою операцією. Цю мікросхему називають «метеликом». Вона дозволяє виготовляти спеціалізовані процесори ШПФ для сигналів з довільним N.

Алгоритмічна схема «метелика» і її позначення наведені на рис. 7.3. Якщо на її вхід поступають комплексні числа і , тоді на на виході формуються числа згідно з виразами x ₁ + x ₂ w ⁿ і x ₁ - x ₂ w ⁿ. Оскільки комплексні величини являють собою пару чисел (реальні і мнимі частини), тому практично «метелик» має чотири входи і чотири виходи.

Рисунок 7.3 – Алгоритмічна схема і умовне позначення «метелика»

 

Як видно зі структурної схеми восьмиточечного спецпроцесора ШПФ реалізованого на «метеликах» (рис. 7.4), в ній реалізовані операції предписані факторизованою матрицею (7.24).

 

Рисунок 7.4 – Структурна схема спецпроцесора ШПФ на «метеликах»

 

Формально ШПФ здійснюється шляхом розбивання вихідної послідовності на парні і непарні підпослідовності. З ними далі подібним же чином. Ці процедури повторюються доти, поки не залишиться по одній парі чисел, які поступають на «метелики» першого етапу. Стосовно до восьми точкового ШПФ цими парами є , , , . На першому етапі операцій множення практично не проводиться (множення на ). Тут формуються суми і різниці отриманих пар.

Далі алгоритм обчислення відповідає рис. 7.4. Видно, що вся операція складається з трьох етапів. В загальному випадку для N -точкового ШПФ потрібно етапів. На кожному з них виконується N /2 операцій множення. Таким чином, алгоритм ШПФ потребує операцій множення. Загальний алгоритм ДПФ має операцій множення. Тому алгоритм ШПФ порівняно з алгоритмом ДПФ дає виграш по кількості операцій множення в разів.