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

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

Для оцінки алгоритму зазвичай використовують число необхідних добутків і додавань. Ці обчислювальні характеристики майже вичерпують складність пристрою на рівні алгоритму. В табл. 1.1 наведено порівняння деяких алгоритмів обрахунку двомірного перетворення Фур’є.

Історію швидких алгоритмів обробки сигналів прийнято відраховувати з 1965 р. коли Кулі та Тьюкі опублікували свій швидкий алгоритм обрахування і перетворення Фур’є (ШПФ-алгоритм), хоча насправді ця історія почалась набагато раніше. Сама рання ідея того, що ми називаємо швидкими алгоритмами, з’явилась задовго до появи ШПФ-алгоритмів. Алгоритм Левінсона був опублікований в 1947 р. як ефективний метод рішення деяких теплицевих систем рівнянь. Інший ШПФ-алгоритм, який сильно відрізнявся від алгоритму Кулі-Тьюкі, був розроблений раніше Гудом (1960) і Томасом (1963). Але публікація Гуда-Томаса пройшла майже непомітною. Згадана публікація Кулі і Тьюкі з’явилась якраз в потрібний час і послужила каталізатором застосування методу цифрової обробки сигналів в новому контексті. Незабаром Стогхем зауважив, що ШПФ-алгоритми можуть служити зручним способом обрахування згорток. Технологія цифрової обробки може безпосередньо використовувати ШПФ, і тому робота Кулі і Тьюкі стала широко відомою. Пізніше Виноград опублікував свій більш ефективний, хоча й більш складний метод, який до того ж дозволив глибше зрозуміти, що в дійсності означає процес обчислення дискретного перетворення Фур’є.

Таблиця 1.1.

Порівняння характеристик деяких двомірних алгоритмів перетворення Фур’є

Найменування алгоритму | Добутків на точку | Додавань на точку

Пряме обрахування дискретного перетворення Фур’є 1000х1000 | 8000 | 4000

ШПФ-алгоритм Кулі-Тьюкі 1024х1024 | 40 | 60

Гібридний ШПФ-алгоритм Кулі-Тьюкі/Винограда 1000х1000 | 40 | 72,8

ШПФ-алгоритм Винограда 1008х1008 | 6,2 | 91,6

ШПФ-алгоритм Нуссбаумера-Квендалла 1008х1008 | 4,1 | 79

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

Спектральний аналіз поєднує два важливих теоретичних підходи: статистичний аналіз часових рядів і методи аналізу Фур’є. Аналітичні методи, розвинуті Жаном Батістом Жозефом Фур’є (1768–1830), зіграли значну роль в розвитку прикладної математики. Розглянемо одне з найважливіших застосувань цих методів — для наближення неперіодичних функцій.

Нехай реалізація x(t) має кінцеву довжину Tr = Tp, рівну фундаментальному періоду. Припустиму, що вона складається з парної кількості N еквідистантних спостережень з інтервалом , вибраний таким чином, що частота Найквіста достатньо висока. Припустимо, що початковий момент реалізації дорівнює нулю і позначимо перетворену послідовність наступним чином:

, n = 1, 2, …, N. (1.1)

Для будь-якої точки (n = 1, 2, …, N), що належить інтервалу (0, Tp), де , ряд Фур’є, обрахований по всіх N значеннях реалізації, буде мати вигляд:

(1.2)

Коефіцієнти Aq і Bq будуть обраховуватись відповідно:

;

, (q = 1, 2, …, N/2 – 1); (1.3)

;

, (q = 1, 2, …, N/2 – 1).

Програма для розрахунку Aq і Bq має містити наступні операції:

визначення величини при фіксованих значеннях q і n;

обчислення і ;

обчислення і ;

обчислення суми для кожного з цих виразів при n = 1, 2, …, N;

збільшення аргументу q на одиницю і повторення всіх попередніх дій.

Такий спосіб обрахунків коефіцієнтів Aq і Bq потребує приблизно N2 операцій множення і додавання дійсних чисел і при великих N може виявитися непродуктивним і вимагати багато часу. Щоб суттєво знизити затрати машинного часу були розроблені і введені в практику інші способи обрахунків, які отримали назву «швидкого перетворення Фур’є» (ШПФ)

Перетворення Фур’є дійсної або комплексної функції x(t), заданої на інтервалі (0, T), являє собою величину:

(1.4)

або для дискретного випадку, n = 1, 2, …, N, коли для розрахунку функції X(t, T) беруться дискретні значення частоти

(1.5)

Перетворена послідовність дає на цих частотах складові Фур’є

, k = 0, 1, 2, …, N – 1. (1.6)

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

Швидке перетворення Фур’є ґрунтується на представленні величини N у вигляді ряду співмножників (відмінних від одиниці) і виконанні звичайного перетворення Фур’є для більш коротких послідовностей, число членів в яких визначається відповідними співмножниками. Якщо N може бути представлено у вигляді добутку p цілих і більших за одиницю чисел:

(1.7)

то, послідовність Xk може бути ітеративно знайдена шляхом розрахунку суми p доданків:

Nr1 — перетворень Фур’є, кожне з яких вимагає операцій з дійсними числами;

Nr2 — перетворень Фур’є, кожне з яких вимагає операцій з дійсними числами;

…

Nrp — перетворень Фур’є, кожне з яких вимагає операцій з дійсними числами;

Таким чином, загальне число операцій над дійсними числами складає

(1.8)

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

(1.9)

На рис. 1.1. за допомогою направленого графа подано послідовність