фективне обчислення вихідний послідовності у (ПТ) ЦФ. З цією метою слід визначити ДПФ H (k) і X (k) в N + M-1 точках для послідовностей h (ПТ) і х (ПТ), потім визначити ДПФ Y (k) = H (k) X (k) вихідний послідовності у (ПТ). Обчислення у (ПТ) по ОДПФ Y (k) виконується, наприклад, по алгоритму (5.3). Для обчислення ДПФ і ОДПФ використовуються алгоритми ШПФ. Відзначимо, що якщо довжина М послідовності х (ПТ) велика, то реалізація згаданого вище алгоритму обчислення у (ПТ) пов'язана зі значною тимчасовою затримкою (для накопичення всіх М вибірок х (ПТ) ) . З метою зменшення цієї затримки можна вхідну послідовність х (ПТ) розбити на відрізки x i (ПТ) кожен довжиною L і обробляти кожен з них незалежно від інших. Уявімо
(6.2)
Тоді можна (6.1) записати у вигляді
(6.3)
Де приватна згортка
(6.4)
В
Таким чином можна починати розрахунок методами БПФ приватних згорток і формувати у (ПТ) шляхом відповідного підсумовування елементів приватних згорток [2].
7. ІНШІ ШВИДКА АЛГОРИТМИ ОБЧИСЛЕННЯ дискретного перетворення Фур'є
7.1 Узагальнений алгоритм Кулі-Тьюки з довільним підставою з множниками повороту
Крім розглянутих вище класичних алгоритмів ШПФ відомих як алгоритми Кулі-Тьюки по підставі 2, відомо безліч інших. Деякі з них дозволяють істотно підвищити ефективність обчислення дискретного перетворення Фур'є. Так, алгоритми Винограду при рівному числі складення вимагають приблизно в 5 разів менше множень, ніж алгоритми Кулі-Тьюки.
В основі всіх відомих алгоритмів лежить принцип розбитті вихідного ДПФ на сукупність мало точкових. Різниця полягає в способах обчислення мало точкових алгоритмів і подальшого об'єднання часткових результатів. При цьому розмір перетворення не обов'язково дорівнює ступеню двох, тобто стає можливим БПФ довільної довжини, що дуже важливо для ряду практичних завдань. Так, в техніці зв'язку при цифровому перетворенні багатоканальних сигналів розмір БПФ визначається числом поєднуваних каналів.
Коротко розглянемо тільки деякі, найбільш важливі алгоритми, на основі яких згодом виникло безліч різних ефективних модифікацій. Це: 1) узагальнений алгоритм Кулі-Тьюки з довільним підставою з множниками повороту; 2) алгоритм простих множників Гуда-Винограду, 3) алгоритм Винограду. p> Для простоти викладу скрізь будемо вважати N = N 1 N 2 , де N - довжина перетворення. Очевидно, наведені нижче положення легко можуть бути перенесені на більш загальний випадок, коли
Узагальнений алгоритм Кулі-Тьюки з довільним підставою з множниками повороту. Отже, нехай N = N 1 N 2 , де N 1 і N 2 - цілі позитивні. Покажемо, що в цьому випадку обчислення вихідного N-точкового ДПФ можна звести до обчислення N 1 N 2 -точкових і N 2 N 1 -точкових ДПФ і N помноженої на множники повороту. Для цього у вирази для ДПФ (1.1)
(7.1)
де, необхідно зробити підстановку:
В
k = k 1 + k 2 N 2, k 1 = 0, ...., N 2 -1; k 2 = 0, ...., N 1 -1; (7.2)
n = n 1 + n 2 N 2, n 1 = 0, ...., N 2 -1; n 2 = 0, ...., N 2 -1. (7.3)
В
Малюнок 6 - Сигнальний граф алгоритму
Тоді ДПФ (7.1) перетвориться до виду
(7.4)
Таким чином, отриманий алгоритм включає в себе дві основні щаблі: на першій ступені переставлені відповідно до (7.3) вхідні вибірки піддаються N 2 -точкового перетворенню Фур'є. На другий щаблі виробляється обчислення N 1 -точкових ДПФ. Між першою і другий ступенями здійснюється операція повороту шляхом множення на повертають множники. Отримана послідовність на виході ДПФ повинна бути переставлені відповідно до (7.2). p> Приклад 4. Нехай N = 6, N 1 = 3, N 2 = 2. Покладемо k = k 1 + k 2 * 2; n = n 1 + + n 2 * 3; n 1 k 2 = 0,1,2; n 2 k 1 = 0, 1.
Тоді
Відповідний сигнальний граф алгоритму зображено на рис.6. p> Розглянутий підхід може бути покладений в основу синтезу алгоритмів ШПФ Кулі-Тьюки з довільним постійним підставою. Найбільшу популярність отримали алгоритми з підставами 4 і 8, що дозволяють підвищити ефективність обчислення...
