8. АЛГОРИТМИ ШВИДКОГО ПЕРЕТВОРЕННЯ ФУР’Є
8.1. ВИЗНАЧЕННЯ І КЛАСИФІКАЦІЯ АЛГОРИТМІВ БПФ
Алгоритми швидкого перетворення Фур'є (БПФ) – це способи швидкого обчислення ДПФ, що усувають властиву ДПФ обчислювальну надмірність. Вони були вперше запропоновані в 1965 році американцями Кулі і Тьюкі і належать до базових алгоритмів ЦГЗ у частотній області. Алгоритми ґрунтуються на властивостях комплексної
та періодичності W kn
періодом, рівним довжині оброблюваної реалізації сигналу N (числу точок БПФ). З урахуванням останньої властивості експонент W N pkn = W N kn / p
відповідає період N/p , де p – цілі числа, куди ділиться N . Використання даних властивостей в алгоритмах БПФ виключає велику кількість операцій, що повторюються при обчисленні ДПФ.
Загальний принцип БПФ полягає в розбитті ДПФ вихідної послідовності на ДПФ підпослідовностей меншої довжини, аж до мінімально можливої (рівній підставі БПФ), через які обчислюється ДПФ вихідної послідовності.
Розбиття означає проріджування послідовностей у часовій або частотній області. У зв'язку з цим розрізняють БПФ з проріджуванням за часом і БПФ з проріджуванням за частотою.
На відміну від ДПФ, БПФ може обчислюватися тільки за певною кількістю точок N , що відповідає цілого ступеня його заснування m : N = m L , де L – це число етапів проріджування : L = log m N . До найбільш використовуваних відносяться БПФ на підставах т = 2, 4, 8, але найчастіше застосовують БПФ на підставі 2 .
Як показано в [40], главі 5, за допомогою БПФ обчислюється також зворотне ДПФ (ОДПФ).
8.2. АЛГОРИТМ БПФ З ПРОРІЖУВАННЯМ ЗА ЧАСОМ З ОСНОВАННЯ 2
Нехай задано послідовність x(n) N кінцевої довжини N, n = 0, 1,.N – 1.
Потрібно знайти її ДПФ: X (jk) = ∑ x (n) W N kn для k = 0, 1. N- 1 (номери n = 0
бінів ДПФ) з мінімальним обсягом обчислень.
Вирішення цієї задачі в даному алгоритмі БПФ знаходиться наступним чином.
Вихідну послідовність x(n) завдовжки N розіб'ємо на 2 підпослідовності завдовжки N/2 – парну (що включає відліки x(n) з
парними індексами n : x 1 (n) = x (2n) і непарну : x 2 (n) = x (2n + 1), n = 0,
1. (N/2) – 1. Це відповідає першому прорідження сигналу за часом
0 1 2 3 4 5 6 7 8 9 10 N – 1
Мал. 8.1. Ілюстрація проріджування сигналу за часом
Позначимо їх ДПФ як X 1 (jk) N/2 та X 2 (jk) N/2 . Виразимо ДПФ вихідної послідовності x(n) N через ДПФ підпослідовностей x 1 (n) N/2 , x 2 (n) N/2 :
N k = X 1 (jk +) W N K X 2 (jk), (8.1)
Це перші N/2 частотних вибірок ДПФ.
Другу половину частотних вибірок X(jk) для k = (N/2), … (N – 1) знайдемо з урахуванням властивості періодичності:
Вирази (8.1), (8.2) визначає базову операцію БПФ (операцію
множник W N k , рівний за модулем одиниці, називають
повертають. Обчислення відповідно до (8.3) включають одне комплексне множення та пару
Базову операцію представляють графічно за допомогою сигнального графа (метелика ШПФ), рис. 8.2.
Мал. 8.2. Сигнальний граф базової операції БПФ
додавання (верхній вихід) та
відповідає множенню на
множник, що повертає W N k .
Сигнальний граф алгоритму БПФ виходить як сукупність графів базових операцій. Для першого етапу проріджування він показаний на рис. 8.3 випадку N = 8.
Мал. 8.3. Сигнальний граф БПФ для першого етапу проріджування
Оцінимо необхідний обсяг обчислень відповідно до даного графа за кількістю операцій множення:
для ДПФ K розумн.ДПФ = N 2; для БПФ K розумн. БПФ = 2 (N / 2) 2 + N / 2 = N 2 / 2 + N / 2.
Як бачимо, в результаті одноразового проріджування обсяг обчислень зменшився приблизно у 2 рази.
Далі кожну з послідовностей x 1 (n) і x 2 (n) можна розбити ще на дві підпослідовності вдвічі меншої довжини: x 11 (n), x 12 (n) та x 21 (n), x 22 (n) (парну) і непарну) і повторити наведені вище операції об'єднання їх ДПФ за допомогою базових операцій. Таке проріджування
виконуємо L разів до отримання N/2 двоточкових послідовностей x l (0), x l (1) , ДПФ яких обчислюється тривіально: X l (j0) = x l (0) + W 2 0 x l (1), X l (j1) = x l (0) − W 2 0 x l (1). В результаті отримуємо повний граф БПФ, показаний на рис. 8.4 для N=8.
x p(1) = x(4) x p(2) = x(2)
x p (4) = x (1) x p (5) = x (5) x p (6) = x (3) x p (7) = x (7)
Мал. 8.4. Повний граф БПФ для N = 8
Відповідно до графа на кожному з L етапів ДПФ виконуються N/2 базових операцій, а загальний обсяг обчислень для комплексних операцій множення та складання – віднімання складає:
log 2 N, K склад. БПФ = NL = N log 2 N.
Число операцій з речовими числами в 4 рази більше для множення і в 2 рази більше для Виграш БПФ щодо ДПФ за кількістю операцій множення K умн.ДПФ /K умн.БПФ = 2N/log 2 N. Так, при
N = 2 10 = 1024 K умнБПФ = 5120, K умнДПФ ≈ 10 6 , виграш дорівнює 204,8.
Виділені на рис. 8.4 вузлові точки графа відповідають осередкам оперативної сигнальної пам'яті. Так як обчислення виконуються поетапно, то можливе заміщення осередків пам'яті, що визначає загальну необхідну сигнальну пам'ять в об'ємі, що дорівнює 2N осередків для N
комплексних чисел (їх реальної та уявної частини). При цьому використовувані осередки пам'яті на вході графаз N відліками вхідного сигналу x(n) (загалом комплексного) заміщаються зрештою N комплексними частотними вибірками БПФ X(jk) .
Особливістю алгоритму БПФ з проріджуванням за часом є неприродний порядок відліків вхідного сигналу , що їм потрібний ,
обумовлений його багаторазовими розбиттями на парні та непарні (n = 0, 4, 2, 6, 1, 5, 3, 7 для N = 8). Це призводить до необхідності попередньої перестановки відліків вихідної послідовності до початку обчислень. Для цього природні номери відліків послідовності x(n) представляються в подвійному коді, ці коди прочитуються в зворотному порядку, тобто праворуч наліво і перетворюються
потім знову десяткову форму, відповідну номеру відліку переставленої послідовності x(p) .
Наприклад, для графа рис. 8.4 відліку n (10) = 4 вихідної послідовності x(n) у десятковій системі відповідають двійковий код
n (2) = 100, (перевернутий) код n дв. = 001 та десятковий номер p = 1 відліку переставленої послідовності x(p) .
8.3. АЛГОРИТМА ПРОГРАМНОЇ РЕАЛІЗАЦІЇ БПФ
З ПРОРІЖУВАННЯМ ЗА ЧАСОМ З ПІДСТАВИ 2
Етапи ДПФ відповідно до сигнального графа рис. 8.4 слідують у порядку, зворотному етапах проріджування сигналу, що виконуються при виведенні алгоритму БПФ. На першому етапі обчислюються N/2 двоточкових ДПФ, кожному з яких відповідає одна базова операція БПФ, на другому шляхом їхнього попарного об'єднання за допомогою двох
базових операцій обчислюються N/4
чотириточкових ДПФ і т. д., на
за допомогою N/2 базових операцій
об'єднуються у ДПФ вихідної послідовності. З урахуванням зазначеної закономірності процес програмного обчислення БПФ можна розбити на три вкладені цикли(У порядку їх вкладення):
за номером етапу обчислення - об'єднання ДПФ i = 1, 2, ... (зовнішній);
за номером обчислюваного ДПФ на етапі l = 1, 2, …2 L – i;
за номером базової операції обчислюваного ДПФ m = 1, 2, …2 i – 1 . Значення повертають множників для базової операції на етапі
визначаються узагальненим виразом
L − i, k = 0, 1, . ( N / (2 L - i + 1 ) )
Опис змінних: X(n), W, T, P1, P2, P3, i, l, m та ін.
Введення масиву X(n), n = 0, 1, …N – 1
Перестановки: X(р) = X(n) n = p (дв. інв), p = 0, 1, … N - 1
множника, що повертає: P1 = ( m – 1) + (l – 1)2 i