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

Загрузка...

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

на етапах перетворення. Таким чином, щоби на основі алгоритму УША1 побудувати алгоритм УША3 достатньо в першому внести такі зміни: замінити останній етап простих базових операцій етапом поворотів вектора; забезпечити вибір фазових множників на всіх етапах операцій поворот вектора; ввести два додаткових варіанти перестановки вихідних даних. Алгоритм УША4 будується як інвертування графу алгоритму УША3. При цьому перестановки (4) і (5) заміняються оберненими до них перестановками


, (6)


. (7)


Недоліком розглянутих алгоритмів УША1-УША4 є потреба одночасної розробки засобів реалізації хоча би двох алгоритмів: УША1-УША2 чи УША3-УША4. Вона обумовлена тим, що у більшості випадків застосувань ЦОС необхідно виконувати і пряме, і обернене перетворення. Для його усунення розроблений алгоритм УША5. Із структури алгоритмів УША1-УША4 випливає, що їх можна подати у вигляді двократного звернення до одного етапного універсального блоку поворотів вектора, графічно показаного для на рис.6.

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

Виконання кожного із вищенаведених ДОП перетворень здійснюється за наведеною на рис. 7 схемою, де - вхідна точкова послідовність, УБN – універсальний точковий блок, - вихідна послідовність, що є результатом прямого чи оберненого перетворення Фур’є, дискретного перетворення Хартлі, дискретного перетворення Уолша-Адамара, косинусного чи синусного перетворення другого-четвертого видів.

Побудовано швидкі алгоритми (з скороченням кількості операцій переміщення даних) виконання перестановок (2)-(7). Показано, що вони мають структуру, близьку до перестановки даних за законом двійкової інверсії адрес алгоритму ШПФ за основою два. Встановлено і експериментально підтверджено, що перестановки (2)-(7) можуть бути реалізовані надшвидко – за допомогою операцій переміщення даних.

У четвертому розділі розглянуто алгоритмічний підхід до побудови ШНМ фільтрації сигналів. На вхід мережі поступає сигнал , , а її виходом є сигнал , . Мережа містить нейронів , кожний з котрих має входів та один вихід. Виходом нейрону є величина , що обчислюється за виразами

, , , (8)

де ваги нейронів, деяка функція. Для лінійних нейронів має місце тотожність. З цього випливає, що лінійна ШНМ описує лінійний оператор перетворення сигналів. Зокрема, рівняння (8) при виборі відповідних ваг описує ДПФ, ДПХ, ДКП чи ДСП різних видів.

Суть алгоритмічного підходу до побудови нейронних мереж полягає у використанні швидких (а не безпосередніх) алгоритмів при реалізації перетворень виду (8). На основі універсального блоку (див. рис.6) побудовано ШНМ реалізації швидких алгоритмів ортогональних перетворень. При цьому двоточкова операція повороту вектора замінена двома нейронами з двома входами і одним виходом (E1 і Е2), див. рис. 8.

Тут , , а і , і - відповідно ваги першого та другого нейронів. Оскільки ваги нейронів можуть набувати довільних значень з інтервалу , то така нейронна мережа охоплює всі вищевказані ортогональні перетворення. На її основі побудована ШНМ фільтрації сигналів у частотній області.

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

У п’ятому розділі розглянуто основні, практично важливі варіанти реалізації отриманих у роботі універсальних швидких алгоритмів ДОП. Відзначено, що використання базової операції повороту вектора – складової операції алгоритму ШПФ за основою два - дозволяє організовувати паралельне виконання обчислень на програмованих процесорах ЦОС. Для універсальних алгоритмів УША1-УША4 і універсального блоку не відомі варіанти з високою основою. Але на основі відомого підходу декомпозиції алгоритму ШПФ за основою два у вигляді набору блоків (малоточкових перетворень) можна реалізувати їх паралельне виконання за схемою з високою основою, де операційний пристрій паралельно виконує вибрану кількість взаємопов’язаних базових операцій (а не одну).

Розглянуто структури потокових універсального НВІС-процесора швидких ортогональних перетворень і НВІС-процесора реалізації універсального блоку алгоритмів швидких ортогональних перетворень, а також отримано оцінки основних затрат обладнання на їх реалізацію. Встановлено, що порівняно з однотипним за структурою потоковим НВІС-процесором, що реалізує алгоритм ШПФ за основою два, затрати обладнання скорочуються у 1.1-1.6 раз при одночасному забезпеченні універсальності стосовно видів перетворень. При великих розмірностях універсальний блок скорочує в 1.2 раз затрати обладнання порівняно з універсальними алгоритмами.

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

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


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


У дисертаційній роботі розвинуто методи синтезу швидких алгоритмів дискретних ортогональних перетворень. При цьому отримано такі основні результати:

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

2) Розроблено нові двокаскадні швидкі алгоритми обчислення дискретного перетворення Хартлі (з часовим та частотним прорідженнями), дискретного перетворення Фур’є дійсної чи ермітової послідовностей. Порівняно з