Оцінка обчислювальної складності алгоритму шпф.

Таким чином, N - точкове ШПФ2t буде складатися з log₂N етапів, на кожному з яких буде виконуватися N/2 БО. Тобто всього буде виконано log₂N*N/2 БО. Враховуючи, що для виконання одного «метелика» треба виконати 1 операцію комплексного множення то 2 операції комплексного додавання, оцінимо складність такого алгоритму.

;

Характеристики обчислювальної складності N – точкового алгоритму ШПФ2t:

Кількість операцій множення

Кількість операцій додавання

Порівнявши характеристики складності можна говорити, що побудований алгоритм є швидкий, оскільки він зменшує характеристики складності на порядок.

Реально, при N=1024 кількість операцій зменшується на два порядки:

ДПФ₁₀₂₄ = 2²⁰; ШПФ₁₀₂₄ = 2¹⁰ *10=5*2¹¹ ;

;

ШПФ за основою 2 та прорідженням за частотою (ШПФ2f).

Побудова даного алгоритму відрізняється від попереднього принципом поділу вхідних послідовностей, порядком виконання БО та самою БО. В алгоритмі ШПФ2f вхідні дані розділяються на першу та другу половини (від x(0) до x(N/2-1) та від x(N/2) до x(N-1) ), а етапи слідування будуть відповідати графу ШПФ2t, взятого справа наліво. При цьому вхідні відліки будуть слідувати в природному порядку, а вихідні – в біт – зворотньому порядку слідування номерів. Базова операція алгоритму ШПФ2f має вид:

Базова операція алгоритму ШПФ з частотним прорідженням.

Алгоритм 8- точкового ШПФ2f

Очевидно, що обчислювальна складність цього алгоритму така ж як і для ШПФ2t.

Крім ШПФ за основою 2, можна будувати ШПФ за основою 4, 8, при цьому довжини вхідних послідовностей мають бути степенями цих чисел. Наприклад, якщо N=16, то структура алгоритму ШПФ4t буде така:

Структура 16-точового ШПФ4t.

Як і в алгоритмах за основою 2, для одержання алгоритму з частотним прорідженням ШПФ4f достатньо розглянути наведену структуру у зворотньому порядку.

Алгоритми за більшою основою потребують менше операцій комплексного множення, але передбачають складнішу схему адресації та більше повертаючих множників.

Використання шпф в задачах обробки сигналів. Знаходження оберненого дпф за допомогою алгоритму шпф

Пряме ДПФ:

Обернене: ,

де:

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

,

(a+jb) спряжене (a-jb)

.

(* позначається операція комплексного спряження.)

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

Обчислення двовимірних перетворень.

Покажемо, що двовимірне точкове перетворення зводиться до системи одновимірних перетворень, оскільки ДПФ володіє властивістю сепарабельності.

Одновимірне перетворенням по рядках :

,

Тому можемо записати :

,

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