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

Загрузка...

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

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

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

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

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

Другий розділ присвячений розвитку методу синтезу прямих алгоритмів ШКП і ШСП другого-четвертого видів з косинусними фазовими множниками.

Для ДКП другого-четвертого видів у виразі (1) відповідно використовують матриці :


, (2)


, (3)


, (4)


де , при . Аналогічні варіанти матриць синусних перетворень мають вигляд


, (5)


, (6)


, (7)


де і при .

З цією метою доведено властивості періодичності елементів матриці (5) і ДСП другого виду (ДСПII). На їх основі синтезовані алгоритми ШСП другого та третього видів (ШСПII і ШСПIII). Зокрема, формула розкладу алгоритму ШСПII задається виразами

, ;

, (8)

де - точкове ДСПII вхідної послідовності , ; і - точкові ДСПII підпослідовностей і . Як і у відомих алгоритмах ШКП другого виду (ШКПII), формула розкладу алгоритму ШСПII містить два етапи: основний, на якому обчислюються послідовності і ; підсумовування, на якому виконуються перетворення (8).

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

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


Рис. Базові операції алгоритмів ШКП-ШСП другого виду:

а) ШКПII; б) ШСПII.


З цією метою встановлено, що між ДКПIV (ДСПIV) і ДКПII (ДСПII) існує зв’язок, подібний до етапу підсумовування у формулі розкладу алгоритму ШСПII (8),

, , , (9)

де , ,

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

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

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

Виходячи з наявності відомих засобів виконання алгоритмів ШПФ-ШПХ, як базове було вибране ДПХ і його швидкі алгоритми (ШПХ). Розглянуто два варіанти.

У першому з них для синтезу алгоритмів використаний алгоритм ШПХ за основою два (ШПХ2). Отримано алгоритми ШКП4Х і ШСП4Х, які (не залежно від способу прорідження) містять чотири основних кроки. Зокрема, при часовому проріджені алгоритм ШКП4Х – обчислення перетворення (1) послідовності , , з матрицею (4) – має вигляд.

Крок 1. Переставляємо елементи послідовності : , , , .

Крок 2. За допомогою операцій поворот вектора, обчислюємо допоміжну послідовність : , ;

,

, .

Крок 3. Виконуємо точкове ДПХ: .

Крок 4. За допомогою операцій поворот вектора переходимо до ДКП:

,

,

де , , , , .

Крок 5. Кінець алгоритму ШКП4Х.


Алгоритм ШСП4Х – обчислення перетворення (1) послідовності , , з матрицею (7) – при часовому проріджені збігається з алгоритмом ШКП4Х з точністю до параметра , що використовується на першому кроці, для ШСП4Х . В алгоритмах ШКП4Х і ШСП4Х з