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

Загрузка...

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

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

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

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

Для взаємно обернених дискретних синусних перетворень (ДСП) другого та третього видів матриці в (1) відповідно задаються виразами

,


,


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

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


,


,


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

Базові операції цих алгоритмів показано на рис.1, де , . При і відповідно отримуємо алгоритми ШКП4 і ШСП4. У -точкових алгоритмах маємо етапів простих базових операцій типу (рис. 1,а) і етапів поворотів вектора, на котрих виконуються операції типу (1,б). Встановлено, що структури алгоритмів ШКП2 і ШКП4 є подібними. По-перше, вони мають однакові базові операції. По-друге, загальна кількість етапів у цих алгоритмах збігається і рівна . При цьому в алгоритмі ШКП4 є на два більше етапів повороту вектора. На основі методу інвертування графів синтезовано алгоритми ШКП4 і ШСП4, в котрих першим каскадом є етапи поворотів вектора. Їх направлений граф показаний відповідно при і на рис.2 у напрямку справа наліво.

Для побудови двокаскадних алгоритмів ШПФ дійсної послідовності (ШПФд), ШПФ ермітової послідовності (ШПФе) і швидкого перетворення Хартлі (ШПХ) використано непрямий метод, в котрому відповідні перетворення обчислюються на основі алгоритмів ШКП2 чи ШКП3 за допомогою введення двох додаткових етапів. На одному з них виконуються перестановки елементів перетворюваної послідовності за законом


, (2)


де послідовність, отримана в результаті перестановки. На іншому виконується етап поворотів вектора. Показано, що останній етап поворотів вектора алгоритму ШКП2 і вказаний додатковий етап поворотів вектора можна об’єднати в один етап повороту вектора типу (рис.1,б) зі зміненими фазовими множниками. Це дозволяє скоротити один етап поворотів вектора, тобто зменшити на кількість множень і на кількість додавань у двокаскадних алгоритмах ШПФ-ШПХ (на 5-7% при ). При , і отримуємо двокаскадний алгоритм ШПХ, а при , і маємо двокаскадний алгоритм ШПФд.

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


(3)


Аналіз етапів першого каскаду алгоритмів ШКП2 і ШСП2 показав, що цей каскад відповідає точковому алгоритму швидкого перетворення Уолша-Адамара (ШАУА) з упорядкуванням елементів за Уолшем. Таким чином, отримані двокаскадні алгоритми ШКП2, ШСП2, ШПФд і ШПХ можна розглядати як непрямі алгоритми обчислення тригонометричних перетворень на основі алгоритму ШАУА.

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

Показано, що двокаскадні алгоритми ШКП2, ШСП2, ШПХ і ШПФд можна подати у вигляді алгоритму УША1, узагальнена схема котрого приведена на рис. 3.

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

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

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

Алгоритм УША2 побудований на основі інвертування графу алгоритму УША1. Алгоритми УША1 і УША2 взяті за основу і при побудові алгоритмів УША3 та УША4. Оскільки алгоритми ШКП2, ШСП2 і ШКП4-ШСП4 відрізняються схемами з’єднання базових операцій другого каскаду, то для приведення їх до універсальної структури (алгоритму ШКП2) у алгоритмах ШСП2 і ШКП4-ШСП4 введені додаткові перестановки елементів вихідної послідовностей, котрі відповідно описуються рекурентними виразами


, (4)

, (5)

де - вхідна точкова послідовність, а і - вихідні точкові послідовності.

За правилами (4) чи (5) послідовності меншої довжини ( і ) розбиваються аж до отримання чотириточкових. Ці ж перестановки використовуємо і для перевпорядкування фазових множників