LibRar.Org.Ua — Бібліотека українських авторефератів

Загрузка...

Головна Електроніка. Обчислювальна техніка → Уніфіковані засоби виконання швидких алгоритмів зсунутих косинусних та синусних перетворень

частотним прорідженням кроки один-чотири виконуються в зворотному порядку, а в алгоритмах ШКП2Х, ШСП2Х, ШКП3Х, ШСП3Х відсутній другий крок поворотів вектора.

Таким чином, уніфіковані засоби виконання ШКП-ШСП повинні забезпечувати реалізацію трьох незалежних процедур: перестановки даних; виконання етапу поворотів вектора; виконання алгоритму ШПХ (за довільною основою). Оскільки ШПХ без втрат в кількості операцій може бути виконане за допомогою відомих швидких ДКП і ДСП першого виду (ШКПФ і ШСПФ), то фактично отримані уніфіковані швидкі алгоритми обчислення косинусних і синусних перетворень першого-четвертого видів.

У другому варіанті синтез алгоритмів ШКП-ШСП здійснюється за допомогою формул розкладу алгоритмів ШПХ за розщепленою основою два-чотири (ШПХ24). В цьому випадку ДКПIV (ДСПIV) зводиться до двох точкових ДПХ, містить перший і четвертий крок алгоритму ШКП4Х. При цьому другий крок суттєво ускладнюється – має структуру алгоритмів ШПХ24. Тому другий варіант доцільно використовувати тільки при наявності арифметичних пристроїв виконання алгоритмів ШПФ-ШПХ за розщепленою основою два-чотири та при побудові матричних процесорів, тому що скорочуються обчислювальні затрати, див. таблицю, де . Таким чином, встановлено, що прямий та побічний метод синтезу швидких алгоритмів ДКП-ДСП другого-четвертого видів дозволяють отримувати алгоритми з однаковими обчислювальними затратами.

Четвертий розділ присвячений розробці ефективних алгоритмів фільтрації і кореляції сигналів на основі алгоритмів ШКПII (ШКП2Х). Використовуючи формули зв’язку між ДКПII і ДПФ, синтезовано алгоритм фільтрації-кореляції сигналів через ШКПII. Як і у випадку перетворень Фур’є-Хартлі, тут зберігається класична схема: пряме перетворення + модифіковане множення косинусних спектрів + обернене перетворення. При цьому модифіковане множення спектрів, зводиться до двох кроків поворотів вектора (на один крок менше у порівнянні з використанням відомих алгоритмів обчислення ШПФ через ШКП ).


Таблиця.

Обчислювальні затрати алгоритмів ШКП-ШСП

п/п

Метод

Множення ( )

Додавання ( )

1

Прямий

2

Побічний

3

Прямий

4

Побічний (ШПХ24)

5

Побічний (ШПХ2)


Таким чином, уніфіковані засоби виконання алгоритмів ШКП-ШСП можуть бути використані і при виконанні типових операцій цифрової обробки – фільтрації та кореляційному аналізі сигналів.

У п’ятому розділі розглянуті питання реалізації синтезованих алгоритмів ШКП-ШСП. Розроблено програми для сигнального процесора TMS320C50. Встановлено, що побічні алгоритми мають перевагу в часі виконання на 18% порівняно з прямими алгоритмами. Це пояснюється тим, що операції повороту вектора добре узгоджуються з особливостями архітектури сигнальних процесорів, де додавання і множення можна виконувати паралельно.

З метою визначення узагальненої базової операції ітераційних процесорів проведений аналіз отриманих побічних алгоритмів ШКП-ШСП. Встановлено, що їх можна реалізувати за допомогою операції повороту вектора

; ,

де і - входи операції; і - виходи операції; і - фазові множники, що містяться в пам’яті констант. При цьому додатково треба забезпечити перекомутацію входів-виходів, тобто подавати їх прямо чи навхрест. Показано, що для забезпечення виконання швидких побічних алгоритмів зсунутих ДКП-ДСП достатньо в операційний пристрій відомого ітераційного процесора виконання алгоритмів ШПФ-ШПХ дійсних послідовностей, що містить чотири перемножувачі дійсних чисел і два суматори, добавити два двохканальні комутатори і сигнали управління ними. Подальший аналіз засвідчив, що при виборі базової операції за розщепленою основою два-чотири, добавлення в операційний пристрій ітераційного процесора одного чотирьохканального комутатора і сигналу управління ним, дозволяє виконувати на його основі й алгоритми ШКП-ШСП другого-четвертого видів.

При розробці уніфікованих матричних процесорів виконання швидких алгоритмів зсунутих ДКП-ДСП достатньо мати в наявності матричні процесори виконання ШПХ, повороту вектора і перестановки даних. Аналогічним чином, використовуючи ряд відомих методик прискорення обчислювального процесу, сучасні технології програмування дозволяють розробити уніфіковані програми швидкого обчислення ОТП для універсальних ПЕОМ, котрі за часом виконання перетворення будуть практично рівноцінними з спеціалізованими програмами.

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

В додатку А наведено акти про впровадження результатів роботи.


ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ ТА ВИСНОВКИ


1) Розвинуто метод синтезу прямих алгоритмів ШКП і ШСП другого і третього видів з косинусними фазовими множниками. Синтезовані нові алгоритми ШСП другого і третього видів, котрі дозволяють виконувати ДКП чи ДСП тільки за рахунок перекомутації виходів базової операції.

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

2) Розвинуто метод побудови швидких побічних алгоритмів обчислення косинусних і синусних перетворень другого - четвертого видів. На основі формул розкладу відомих алгоритмів косинусних і синусних перетворень першого виду отримано побічні уніфіковані алгоритми ШКП і ШСП другого-четвертого видів з найменшими обчислювальними затратами серед відомих алгоритмів даного класу. Таким чином, розроблений уніфікований підхід до побудови алгоритмів ШКП і ШСП всіх чотирьох видів.

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