автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Конвейерные процессы быстрых ортогональных преобразований с действительными фазовыми множителями

Міністерство освіти і науки України Національний університет “Львівська Політехніка”

о*

УДК 681.3

Ерметов Юрій Олегович

КОНВЕЄРНІ ПРОЦЕСОРИ ШВИДКИХ ОРТОГОНАЛЬНИХ [ЕРЕТВОРЕНЬ З ДІЙСНИМИ ФАЗОВИМИ МНОЖНИКАМИ

Спеціальність 05.13.13 - Обчислювальні машини, системи і мережі

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня кандидата технічних наук

Львів - 2000

Дисертацією є рукопис.

Робота виконана в Національному університеті “Львівська Політехніка Міністерства освіти і науки України.

Науковий керівник: доктор технічних наук, професор

Провідна установа: Національний технічний університет України “Київський

політехнічний інститут”, кафедра спеціалізован комп'ютерних систем, м. Київ

Захист відбудеться “23” групня 2000 р. об “11” год. на засідаї спеціалізованої вченої ради Д35.052.05 при Національному університ “Львівська Політехніка” в ауд. 226 головного корпусу за адресою 790 м. Львів-13, вул. С.Бандери, 12.

З дисертацією можна ознайомитися у науково-технічній бібліот Національного університету “Львівська Політехніка” за адресою: 790 м. Львів-13, вул. Професорська, 1.

Автореферат розісланий “22” листопада 2000 р.

Вчений секретар спеціалізованої вченої ради,

кандидат технічних наук, доцент С.П.Ткаченко

Мельник Анатолій Олексійович,

Національний університет “Львівська Політехніка”, завідувач кафедри електронних обчислювальних машин

Офіційні опоненти: доктор технічних наук, професор

Грицьків Зенон Дмитрович,

Національний університет “Львівська Політехніка”, завідувач кафедри радіотехнічних пристроїв, м. Львів;

кандидат технічних наук, доцент Дунець Роман Богданович Українська академія друкарства,

кафедра автоматизації і комп’ютерних технологій, м. Льві

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність темп.

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

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

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

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

Зв’язок роботи з науковими програмами, планами, темами. Вибраний апрямок досліджень пов’язаний з виконанням робіт в рамках пріоритетних аукових напрямків Міністерства освіти та науки України 07-“Перспективні ¡формаційні технології, прилади комплексної автоматизації, системи зв’язку” та 01-Охорона навколишнього природного середовища” по темах, які проводились та роводяться в даний час на кафедрі електронних обчислювальних машин та в ауково-дослідному конструкторському інституті НДКІ ЕЛВІТ Національного чіверситету “Львівська політехніка:

ДБ “СЕРГ”: “Розробка метрологічних основ та принципів побудови имірювально-обчисшовальних комплексів для забезпечення сертифікаційних ипробувань автотранспортних засобів” (1998-1999 рр.);

ДБ/17.ЕС: ’’Розробка нових принципів побудови вимірювально-обчислювальних ереж з елементами самоорганізації для екологічного моніторингу” (2000-2001 рр.).

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

У відповідності до поставленої мети в рамках дисертаційної робота розв'язуються наступні задачі:

- огляд та аналіз існуючих алгоритмів обчислення швидких ортогональнії) перетворень та конвеєрних процесорів для їх реалізації;

- вдосконалення існуючих та розробка нових алгоритмів обчислення ІПОП : дійсними фазовими множниками;

- розробка структур конвеєрних процесорів ШОП з дійсними фазовим) множниками та порівняння їх з конвеєрними процесорами ШОП за методо» Кулі-Тьюкі;

- розробка структур конвеєрних процесорів дискретного хвильовог перетворення (ДХП), а також структур багатофункціональних конвеєрни процесорів ШОП та ДХП;

- розробка паралельного конвеєрного процесора оберненого швидког косинусного перетворення та реалізація його на основі ПЛІС фірми Хіііпх. Методи досліджень. При виконанні поставлених задач використовувалис

апарат обчислювальної математики, методи та алгоритми цифрової обробк сигналів, теорія цифрових автоматів, теорія проектування комп’ютерів, теорі проектування НВІС, моделювання алгоритмів та апаратних засобів комп’ютер; експериментальні дослідження.

Наукова новизна роботи:

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

- розроблено нові паралельні алгоритми прямого та оберненого ШКП, я

характеризуються гранично високою швидкістю отримання результатів;

- розроблено нові структури одно-, дво-, багатоканальних та паралельні

конвеєрних процесорів ШКП та створено узагальнену методику побудої багатоканальних конвеєрних процесорів прямого та оберненого ШКП, я дозволяє отримувати структури процесорів з мінімальними затратар обладнання на їх реалізацію при забезпеченні заданої продуктивності;

- розроблено нові структури конвеєрних процесорів ШПФ та ШПХ з дійснш

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

- розроблено нові структури конвеєрних процесорів прямого та обернене

дискретного хвильового перетворення, що дозволило підвищити ШВИДКОЇ! обчислення ДХП, а також структуру багатофункціонального конвеєрне процесора ШПХ та ДХП, що дозволило зменшити затрати обладнання реалізацію цих перетворень.

Практичне значення одержаних результатів:

розроблені нові алгоритми паралельного обчислення прямого та оберненого ШКП дозволяють підвищити продуктивність обчислення цих перетворень в багатопроцесорних універсальних комп'ютерних системах та паралельних спеціалізованих комп'ютерних системах;

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

розроблений паралельний 8-канальний конвеєрний процесор одновимірного 8-точкового оберненого ШКП дозволяє будувати високопродуктивні системи стиснення аудіо та відео інформації, які базуються на стандартах JPEG, MPEG, Н.261 та інш.

Впровадження результатів роботи. Розроблені в дисертаційній роботі методи і алгоритми впроваджені; в НДКІ “ЕЛВІТ” (м. Львів, Україна) в науково-дослідній роботі ДБ "СЕРГ" при розробці апаратури вимірювання віброшвидкостей та віброприскорень у автотранспортних засобах;

в науково-дослідній роботі ДБ/17.ЕС, яка виконується на кафедрі ЕОМ ДУ"ЛП", при розробці спеціалізованих комп'ютерних засобів цифрової обробки сигналів та зображень;

в навчальному процесі кафедри ЕОМ Державного університету “Львівська політехніка” при проведені лекційних, практичних та лабораторних занять з предметів “Архітектура спеціалізованих комп'ютерних систем”, “Проектування комп’ютерних засобів обробки сигналів та зображень”.

Особистий внесок здобувача. Основний зміст роботи, всі теоретичні та рактичні розробки, висновки і рекомендації виконані автором особисто. В рукованих працях, опублікованих в співавторстві, :sдобувачу належать: [2] -□зробка та аналіз структур двоканальних конвеєрних процесора ШКП; [3] -ззробка структур конвеєрних процесорів ШПФ з дійсними фазовими множниками;

І] - розробка нового паралельного алгоритму ШКП та методики проектування агатоканальних конвеєрних процесорів ШКП; [5] - розробка принципів організації ібліотек стандартних елементів; [8] - розробка функціональної схеми паралельного ропесора двовимірного ІИКП.

Апробація результатів дисертації. Основні положення й результати исертаційної роботи доповідались й обговорювались на таких конференціях: іжнародна науково-технічна конференція “Сучасні проблеми засобів глекомунікацій, комп'ютерної інженерії та підготовки спеціалістів” TSCET’98, 1998 і.Сдавське, Україна); 5-та міжнародна науково-технічна конференція "Досвід эзробки і застосування приладо-технологічних САПР мікроелектроніки"

CADSM'99, 1999 (с.Славське, Україна); International Conference on Modern Problems of Telecommunications, Computer Science and Engineers Training TCSET’2000, 2000 (Lviv-Slavsko, Ukraine).

Публікації. Основний зміст дисертаційної роботи опублікований в 7 друкованих працях загальним обсягом 42 сторінки , з яких 1 - одноосібна, в тому числі 4 наукових статей (з яких 3-у фахових виданнях), 3 - матеріали і тєзї доповідей на конференціях.

Структура та обсяг поботи. Дисертаційна робота складається зі вступу і п'яті-розділів, висновку, списку літературних джерел з 132 найменувань і додатків. Зміст роботи викладено на 144 сторінках, включаючи 121 рисунок та 10 таблиць. додатках наведено тексти вихідних кодів розробленого програмного забезпечення т; роздрук машинного представлення результатів його роботи.

ЗМІСТ ДИСЕРТАЦІЇ

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

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

Алгоритм ШКП складається з матриці перетворень (МП) та матрш коригування (МК). Структура МП подібна до структури алгоритму ШШ Особливістю МК є ітераційний характер базових операції накопичуючого сумуванн проміжних результатів (НБО).

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

МП складається з log2N ярусів, на кожному з яких розташовано N/2 незалежна базових операцій (БО). Тому для паралельного обчислення МП достатні реалізувати відповідну кількість пристроїв БО (ПБО).

МК складається з ]og2N-l ярусів, на кожному з яких здійсшоються ітерацій: обчислення НБО. Структура МК ефективно реалізується у випадку одно- : двоканальних конвеєрних процесорів (КП), проте апаратна реалізація паралельної алгоритму МК характеризується великою часовою затримкою або значни\ додатковими затратами обладнання.

Існує декілька структур МК алгоритму ШКП, які відрізняються методе перестановки даних. Початковій формулі розкладу алгоритму ШКП відповіді структура МК з проміжною перестановкою даних, в якій перестановка дані

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

іс.1. Структура направленого графа МК зі змішаною перестановкою даних для N=16

Часова затримка паралельного обчислення МК визначається кількістю БО у ійбільшій НБО:

Т^(М/2)Так. (2)

Велика затримка обчислення пояснюється послідовним обчисленням БО у ладі НБО. Для зменшення затримки в дисертаційній роботі запропоновано схему іралельного обчислення НБО на основі бінарних дерев, за допомогою яких [нтезовано нові структури паралельного обчислення МК. На рис.2 показано рукіуру паралельного обчислення МК з проміжною перестановкою даних.

ІДОі .

Рис.2. Структура направленого графа МК на основі бінарних дерев з проміжною перестановкою даних

Назвемо МК на основі бінарних дерев з проміжною перестановкою дани; бінарною МК на основі сортувальної пам‘яті (СП-МК), а з попередньон перестановкою даних - бінарною МК на основі пам‘яті типу FIFO (FIFO-MK).

Загальна кількість БО в бінарних МК дорівнює:

Ps = jVlog2 iV(log2 N-ї)/8, що в (log2 N) / 4 разів більше в порівнянні з послідовною МК.

Часова затримка обчислення МК

T = log2N(\og2N-\)l2TCLK,

що в N /(log2 N)2 разів менше в порівнянні з послідовною МК.

Таким чином, за рахунок збільшення обчислювальних зменшенім затримки паралельного обчислення МК.

З метою максимального зменшення часових затрат та затрат обладнання пр паралельних обчисленнях в дисертаційній роботі розроблено нові паралель] алгоритми обчислення МК прямого та оберненого ШКП, структуру яких показано і рис.З та рис.4.

(3)

(4)

затрат досягнут

№ ,

I'(S>

£40 Г (12) i'il) r,'m rwf

if (14)

¿'tu

L’C9) — /t

i'aj)

Рис.З. Структура направленого графа паралельної МК прямого ШКП

1(0) 1/ М

. Ь’й

Рис.4. Структура направленого графа паралельної МК оберненого ШКП

Для паралельного обчислення МК на основі нових алгоритмів ШКП необхідна ількість двовходових БО визначається з формули (1) і дорівнює кількості БО ослідовної МК. Відповідно ця кількість в (log j А') / 4 разів менша кількості БО інарних МК. '

Часова затримка обчислення визначається кількістю ярусів:

T = (bg2N~\)TCLK, (5)

ю в N /(2 log 2 N) разів менше в порівняти з алгоритмом з послідовною схемою бчислень НБО і в (log 2 N)/2 разів менше в порівнянні з бінарними алгоритмами з аралельною схемою обчислень НБО.

Нові алгоритми обчислення МК дозволяють без додаткових обчислювальних їтрат максимально скоротити затримку паралельного обчислення МК.

У другому розділі на основі існуючих та нових алгоритмів обчислення ШКП нйснгосться розробка одно-, дво-, багатоканальних та паралельних конвеєрних роцесорів ШКП. На основі проведених досліджень розробляється узагальнена ;етодика побудови багатоканальних конвеєрних процесорів прямого та оберненого ЖП, яка дозволяє отримувати структури процесорів з мінімальними затратами бладнання на їх реалізацію при забезпеченні заданої продуктивності.

Згідно існуючої методики проектування спеціалізованих комп'ютерних засобів ля побудови КП алгоритму ПЖП кожному ярусу МП відповідає сортувальна ам‘ять (СП), пристрій базової операції (ПБО) та пристрій управління. Внаслідок одібності структури МП до структури алгоритму ШПФ питання побудови одно- та воканальних КП МП алгоритму ШКП є достатньо дослідженим. В дисертаційній оботі з врахуванням особливостей алгоритмів перестановки даних в структурах ЩШ1, ШКП2 та ШКПЗ розроблено нові багатоканальні структури СП, оптимізовані а затратами обладнання за рахунок спрощення m-входових комутаторів та меншення кількості адресних мультиплексорів.

Окрім існуючою!" структури конвеєрного процесора МК (КПМК) на основі СП в исертаційній роботі розроблено три нових підходи до побудови конвеєрних роцесорів МК: 1) на основі пам'яті FIFO; 2) на основі СП та пам'яті FIFO; 3) на снові паралельного алгоритму.

Існуючу структуру КПМК на основі СП, яка базується на реалізації структури 1К з проміжною перестановкою даних, показано на рис.5а. На основі реалізації груктури МК з попередньою перестановкою даних в дисертаційній роботі интезовано нову структуру КПМК на основі пам'яті FIFO (рис.5б), в якій в орівнянні зі структурою КПМК на основі СП досягнуто скорочення затрат бладнання на релізацію пам'яті на 25%. Оскільки затрати обладнання на реалізацію акопичуючого пристрою БО (НПБО) та пам'яті мають відповідно логарифмічну та інійну залежність від розміру перетворення N, то із збільшенням розміру ерстворення затрати обладнання на реалізацію пам'яті вносять визначальний вклад загальні затрати обладнання на реалізацію КП.

1-й

НПБО

СІЇ 2-й НІГБО - СІЇ log,»-« ІІПБО СП

(4) (8) <ю

I

U*

t'Q-'O

iw-?>

ІІПБО.

2-t

FIFO

(N'S)

HEbO

iiSJU

а б

Рис.5. Структури КПМК: а - на основі СП; б - на основі пам'яті FIFO

Оскільки в КПМК па основі СП зі збільшенням номера яруса розмір пам‘ят зростає, а в КПМК на основі пам‘яті FIFO зменшується, то оптимальним з точю зору затрат обладнання на реалізацію пам'яті буде КПМК, в якому СП об'єму > буде розміщено на ярусі і = log2 N12-І. Синтез нової структури оптимізованогі КПМК на основі СП та пам'яті FIFO базується на реалізації нової структури МК з змішаною перестановкою даних (рис.1). В КПМК на основі СП та пам'яті FIFC (рис.б) досягнуто скорочення затрат обладнання на реалізацію пам'яті в 2 рази порівнянні з КПМК на основі СП і в 1,5 рази в порівнянні з КПМК на основі яам'яі FIFO.

Т

¡ШВО

6

гн

:п :п

ІІПБО ШВО

(4> lcgW . Гн ■48 N

2 л

№

FEFO

'JN/2) *

ІПБО -

og, /V

2

JFIFO

0)

ШБС

logw-i

І

Рис.б. Структура оптимізованого КПМК на основі СП та пам'яті FIFO

На рис.7 показано структуру КПМК на основі нового паралельного алгорита ШКП, затрати обладнання на реалізацію якої при невеликій кількості канал дорівнюють затратам обладнання на реалізацію структури КПМК на основі СП.

FIFO t-

сп

(N)

г

LIFOO LITOI

(D ПБОО 1* <3) ПЕОЇ г* (JW-l) ПБО

-і- Ье«2

Рис.7 Структура К1ІМК на основі паралельного алгоритму

При побудові паралельних КП з кількістю каналів N на основі різних алгоритм обчислення МК кількість ПБО визначається обчислювальними затратами відповіді: МК і дорівнює кількості БО у цій МК, а кількість конвеєрних регістрів пропорційною часовій затримці обчислення МК, тобто кількості ярусів відповіді МК. При паралельному обчисленні МК всі перестановки даних здійснюють відповідними з'єднаннями входів та виходів сусідніх ярусів і, відповідно, зник потреба у СП. Відповідно найменшими затратами обладнати характеризують паралельні КП, побудовані на основі нового паралельного алгоритма ШКП.

На основі існуючих та нових структур КПМК в дисертаційній роботі нтезовано методику побудови оптимальних за затратами обладнання структур гатоканальних КП (БКП) МК.

Для великих розмірів перетворення та відносно невеликої кількості каналів т, м яких затрати обладнання на реалізацію ярусів і = log2 N - log2 m,...,log2 TV - 2 y FO-MK менші в порівнянні з паралельною МК, можна застосувати метод [тимізації по аналогії з одноканальними КП. Якщо в бінарній FIFO-МК двійково-версну СП об'ємом N розмістити на ярусі і = log2 т-1, то зліва від СП отримаємо уси зі структурою бінарної СП-МК, а справа - яруси зі струкгурою бінарної FIFO-К. Реалізувавши яруси зі структурою бінарної СП-МК на основі паралельної МК, римуємо оптимальну за затратами обладнання структуру БКП МК. Крім того, що існують яруси зі струкгурою бінарної FIFO-МК, затрати обладнання на іалізаццо яких для БКП на основі паралельної МК менші в порівнянні з БКП на ;нові бінарної FIFO-МК, то двійково-інверсну СП об'єму N необхідно перемістити і відповідний ярус другої групи. При цьому перед ярусами першої групи необхідно «містити двійково-інверсну СП об'ємом 2І+2, затрати на яку повинні бути іншими в порівнянні з отриманим виграшем у затратах обладнання від :реміщення основної СП об'ємом N. При збільшенні розміру перетворення іачення затрат обладнання оптимального БКП становить 50% в порівнянні з БКП і основі паралельної МК і 67% в порівнянні з БКП на основі бінарної FIFO-MK.

При невеликих розмірів перетворення, для яких найменшими затратами эладнання характеризуються БКП на основі паралельної МК, структуру тгамального БКП необхідно будувати на основі паралельної МК. При зростанні лькості каналів m для N ~ от2, для яких найменшими затратами обладнання ірактеризуються БКП на основі бінарної СП-МК, структуру оптимального БКП гобхідно будувати на основі бінарної СП-МК. Для т > -J2N, для яких айменшими затрати обладнання характеризуються БКП на основі паралельної МК, груктуру оптимального БКП необхідно будувати на основі паралельної МК.

Запропонована методика дозволяє отримувати структури багатоканальних КП К з мінімальними затратами обладнання на їх реалізацію.

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

Питання побудови КП алгоритмів ІІІПФ за методом Кулі-Тьюкі (ШПФКТ) остатньо широко освітлене в існуючій літературі.

Направлений граф оптимізованого в дисертаційній роботі алгоритму ШПФ з ійсними фазовими множниками (ШПФДФМ), показано на рис. 8.

т,----------------------------------------,-----------------------------------------------------—-----------------------------------------------------------------------------------------------Х'[0)

а

Рис.8. Структура направленого графа алгоритму ШПФДФМ для N=16: а - матриця коригування; б - матрия перетворень

Алгоритм складається з МК та МП. МП має подібну до алгоритму ШПФІ структуру за винятком дійсних замість комплексних фазових множників та Б позначених на рис.7б чорним кольором, в яких використовуються коригук коефіцієнти q. В алгоритмі ІППФДФМ дійсна структура фазових множиш дозволяє в 2 рази скоротити кількість перемножувачів та в 1,5 рази - кількіс суматорів для реалізації МП, проте з'явилась необхідність побудови КП д реалізації МК.

Окрім трьох суматорів структура ПБО МК вимагає використання пам'яті РП для обчислення коригуючих коефіцієнтів q. Передача коефіцієнтів q здійсшоєтьс; загальному потоці даних на місці елементів послідовності, що дорівіпоють нулю.

На рис.9 показано синтезовану структуру КП МП. Вона ідентична структурі КП алгоритму ШПФКТ за винятком тракту передачі значень q. На цьому тракті пам‘яіь ТГО створює затримку, яка дорівнює затримці основного тракту.

Рис.9. Структура КП МП алгоритму ШПФДФМ

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

Аналіз затрат обладнання на реалізацію структур КП алгоритмів ШПФ та ШПХ юказав, що при невеликих та середніх розмірах перетворення найбільший внесок у ¡агальні затрати обладнання вносять перемножувачі, тому в цьому випадку менші іпаратні затрати матимуть КП алгоритмів ПФ та ШПХ з дійсними фазовими шожниками, при чому діапазон цих розмірів перетворень для швидкого іеретвореіпія Хартлі є більшим. Із збільшенням розміру перетворення зростає іитома вага затрат обладнання на реалізацію пам'яті, що обумовлює великі затрати )бладнаітя на реалізацію МК в алгоритмах ШПФ та ШПХ з дійсними фазовими ■шожниками. Тому при великих розмірах перетворена доцільно за затратами )бладнання використовувати алгоритми ШПФ та ШПХ за методом Кулі-Тьюкі.

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

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

В результаті аналіза структур КП алгоритму ШПХ з дійсними фазовими шожниками показано, що на основі КП МК можна реалізувати пряме ДХП, а на існові КП МП - обернене ДХП. В дисертаційній роботі розроблено структуру КП, гка дозволяє здійснювати обчислення алгоритмів ШПХ з дійсними фазовими шожниками та прямого і оберненого ДХП без значних додаткових затрат )бладнання. Дослідження показали, що при великих розмірах перетворення затрати ібладпаиня КП ШПХ-ДПХ прямують до значення однакового із затратами >бладнання КП ШПХРБ і в 2 рази меншого від суми затрат обладнання КП ІППХРБ ■а прямого та оберненого ДХП.

У п'ятому розділі з метою апробації та експериментального підтвердження результатів теоретичних досліджень попередніх розділів на основі нового паралельного алгоритма оберненого ШКП (ОШКП) розроблено паралельний 8-канальний конвеєрний процесор алгоритму 8-точкового ОШКП. Для реалізації множень на константи розроблено спеціалізовані перемножувачі, що дозволило скоротити затрати обладнання в порівнянні з універсальними перемножувачами в 4 рази. Створено VHDL-модель паралельного процесора, на основі якої паралельний процесор реалізовано на основі ПЛІС фірми Хіііпх з використанням пакету автоматизованого проектування Xilinx Foundation 2.1. Засобами цього пакету виконано симуляцію роботи паралельного процесора та перевірку точності обчислень на основі тестових послідовностей. За точністними параметрами паралельний процесор відповідає стандартам JPEG, MPEG та Н.261 стиску сигналів та зображень. Отримані в результаті проектування ПЛІС значення затрат обладнання та швидкодії є найкращими серед існуючих паралельних процесорів ОШКП. Розроблений процесор може бути основою для розробки 8-канальногс конвеєрного процесора алгоритму двовимірного ШКП.

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

У запропонованій дисертаційній роботі отримано наступні результати:

1) вдосконалено існуючі алгоритми прямого та оберненого швидкогс косинусного перетворення, швидкого перетворення Фур‘с та швидкогс перетворення Хартлі з дійсними фазовими множниками, що дозволяє зменшиті затратами обладнання при реалізації цих перетворень на основі конвеєршс процесорів;

2) розроблено нові паралельні алгоритми прямого та оберненого швидкоп косинусного перетворення, в яких при однаковій кількості в порівнянні з існуючим! алгоритмами всі базові операції є незалежними і можуть обчислюватись паралельно Нові алгоритми можуть бути використані для паралельного обчислення алгоритмі ІІЖП як в багатопроцесорних універсальїшх комп'ютерних системах, так і прі проектуванні паралельних процесорів ШКІІ, що дозволяє значно підвиіциті швидкодію процесорів без надлишкових затрат обладнання;

3) проаналізовано існуючі та розроблено ряд нових структур одно-, дію-багатоканальних та паралельних конвеєрних процесорів прямого та оберненог швидкого косинусного перетворення. На їх основі розроблено методик проектування багатоканальних конвеєрних процесорів швидкого косинусног перетворення, яка дозволяє отримувати структури конвеєрних процесорів мінімальними затратами обладнання;

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

5) розроблено нові структури конвеєрних процесорів прямого та оберненого скретного хвильового перетворення, багатофункціональних процесорів для конання прямого та оберненого дискретного хвильового перетворення, а також атофункці опальних конвеєрних процесорів для виконаннпя швидкого ретворення Хартлі та прямого та оберненого дискретного хвильового ретворення, що дозволяє здійснювати проектування спеціалізованих мп'ютерних засобів для реалізації цих перетворень з мінімальними затратами ладнання,

6) розроблено 8-канальний паралельний конвеєрний процесор 8-точкового

ерненого швидкого косинусного перетворення. Розроблено VHDL-модель оцесора, на основі якої процесор промодельовано та відтестовано. Розроблений оцесор реалізовано на ПЛІС фірми Хіііпх засобами пакету автоматизованого оектування Xilinx Foundation 2.1. Отримані в результаті проектування ПЛІС ічення затрат обладнання та швидкодії є найкращими серед існуючих паралельних оцесорів ОІШСП. .

СПИСОК ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

Ерметов Ю.О. "Синтез конвеєрних пристроїв для реалізації матриці коригування в горитмі швидкого косинусного перетворення", Вісник Державного університету іьвівська Політехніка” "Комп'ютерні системи проектування. Теорія і практика", 373, 1999, с.128-136.

Мельник А.О., Ерметов Ю.О. “Розробка двоканальних конвеєрних пристроїв для алізації матриці коригування в алгоритмі швидкого косинусного перетворення”, сник Державного університету “Львівська Політехніка” “Комп'ютерна інженерія інформаційні технології”, №370, 1999, с.28-34.

Ерметов Ю.О., Мороз І.В. Конвеєрні пристрої швидкого перетворення Фур'є за :тодом Рейдера-Бреннера. Вісник Державного університету “Львівська штехніка” “Комп’ютерна інженерія та інформаційні технології”, № 386, 1999, [1-18.

Мельник А.О., Ерметов Ю.О. “Багатоканальна конвеєрна реалізація матриці ригування в алгоритмі швидкого косинусного перетворення”, збірник наукових іаць симпозіуму “Сучасні проблеми в комп'ютерних науках” (CCLP2000), 2000, .89-100 (с.Славське, Україна).

Мельник А.О., Ерметов Ю.О. “Засоби проектування спеціалізованих НВІС від горитмічного опису задачі до рівня міжрегістрових передач”. Тези доп. на жнародній НТК "Сучасні проблеми засобів телекомунікації', комп'ютерної якенерії та підготовки спеціалістів" TCSET'98, 1998, с. 108 (с.Славське, Україна). Ерметов Ю.О. Синтез конвейєрних пристроїв для реалізації матриці коригування в горитмі швидкого косинусного перетворення. Тези доп. на 5-й міжнародні і і НТК [освід розробки та застосування приладо-технологічних САПР мікроелектроніки", 99, с.149-151, (с.Славське, Україна).

"Two-Dimensional 8x8 Discrete Cosine Transform Parallel Processor". Proceedings of temational Conference on Modem Problems of Telecommunications, Computer Science d Engineers Training TCSET’2000, 2000, p. 101 (Lviv-Slavsko, Ukraine).

АНОТАЦІЯ

Ерметов Ю.О. Конвеєрні процесори швидких ортогональних перетворень дійсними фазовими множниками. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук з спеціальністю 05.13.13 - Обчислювальні машини, системи та мережі. Національний університет “Львівська Політехніка”, Львів, 2000.

Дисертація присвячена питанням розробки нових та удосконалення існуючи алгоритмів обчислення швидких ортогональних перетворень з дійсними фазовим множниками та розробки на їх основі спеціалізованих конвеєрних процесорів да реалізації цих перетворень. В дисертації розроблено нові паралельні алгоритм прямого та оберненого швидкого косинусного перетворення, які дозволяют здійснювати паралельне обчислення цих перетворень без надлишкових затр; обладнання. Розроблено методику проектування одно-, дво-, багатоканальних ' паралельних конвеєрних процесорів швидкого косинусного перетворення мінімальними затратами обладнання. Вдосконалено існуючі алгоритми обчислені швидких перетворень Фур‘с та Хартлі з дійсними фазовими множниками і на основі розроблено структури конвеєрних процесорів для реалізації цих перетворен Показано, що при невеликих та середніх розмірах перетворень використані швидких ортогональних перетворень з дійсними фазовими множниками ефективнішим в порівнянні з перетвореннями за методом Кулі-Тьюкі. Розроблеї структури конвеєрних процесорів для реалізації прямого та оберненого дискретно хвильового перетворення, а також запропоновано структуру багатофункціонально конвеєрного процесора для спільного виконанння дискретного хвильово перетворення та швидкого перетворення Хартлі з дійсними фазовими множникам що дозволило значно скоротити затрати обладнання на реалізацію цих перетвореї На основі нового паралелельного алгоритма швидкого косинусного перетворен розроблено 'УТЮЬ-модель 8-канального конвеєрного процесора 8-точково оберненого швидкого косинусного перетворення, яку реалізовано на основі ПЛ фірми Хіііпх. Затрати обладнання та швидкодія розроблненого процесора найкращими серед існуючих паралельних процесорів оберненого швидке косинусного перетворення. Основні результати дисертації впроваджені в НДР , “СЕРГ” та ДБ/17.ЕС, які проводилися в Державному університеті “Львівсі політехніка”, а також в навчальному процесі кафедри ЕОМ Державного університс “Львівська політехніка”.

АННОТАЦИЯ

Эрметов Ю.О. Конвейерные процессоры быстрых ортогональн преобразований с действительными фазовыми множителями. - Рукопись.

Диссертация на соискание учёной степени кандидата технических наук специальности 05.13.13 - Вычислительные машины, системы и сети. Национальный университет “Львовская политехника”, Львов, 2000.

Диссертация посвящена вопросам разработки новых и усовершенствоваг существующих алгоритмов вычисления быстрых ортогональн преобразований с действительными фазовыми множителями и разработки на

тове специализированных конвейерных процессоров для реализации этих еобразований. В диссертации разработаны новые параллельные алгоритмы ямого и обратного быстрого косинусного преобразования, которые зволяют осуществлять параллельные вычисления этих преобразований без эыточиых затрат оборудования. Разработана методика проектирования но-, дво-, многоканальных и параллельных конвейерных процессоров ¡строго косинусного преобразования с минимальными затратами орудования. Усовершенствованы существующие алгоритмы вычисления [стрых преобразований Фурье и Хартли с действительными фазовыми ожнтелями и на их основе разработаны структуры конвейерных процессоров я реализации этих преобразований. Показано, что при небольших и средних змерах преобразований использование быстрых ортогональных еобразований с действительными фазовыми множителями является более фективным по сравнению с преобразованиями на основе метода Кули-Тьюки. зработаны структуры конвейерных процессоров для реализации прямого и ратного дискретного волнового преобразования, а также предложена эуктура многофункционального конвейерного процессора для выполненния скретного волнового преобразования и быстрого преобразования Хартли с йствительными фазовыми множителями, что позволило значительно кратить затраты оборудования на реализацию стих преобразований. На нове нового ларалелельного алгоритма быстрого косинусного еобразования разработана VHDL-модель 8-канального конвейерного оцессора 8-точкового обратного быстрого косинусного преобразования, торая реализована на основе ПЛИС фирмы Xilinx. Затраты оборудования и (стродействие разработанного процессора являются лучшими среди ществующих параллельных процессоров обратного быстрого косинусного еобразования. Основные результаты диссертации внедрены в НИР ДБ 'ЕРГ” и ДБ/17.ЕС, которые проводились в Национальном университете [ьвовская политехника”, а также в учебном процессе кафедры ЭВМ щионального университета “Львовская политехника”.

ABSTRACT

Ermetov Y.O. Pipeline processors of the real-factor fast orthogonal transforms . -jnuscript.

Thesis for the Degree of Doctor of Philosophy in Computer Science in speciality .13.13 - Computing machines, systems and networks. - National Lviv Polytechnic liversity, Lviv, 2000.

The thesis deals with development of the new algorithms of the real-factor fast hogonal transforms (FOT) and engineering of the pipeline processors for their plementation. Instead of popular Cooley-Tukey FOT (CTFOT) real-factor FOT (RFFOT) jposed by Rader and Brenner features simpler basic operations but requires additional ding operations.

Among all of the RFFOT the fast cosine transform (FCT) is the most representative. It nsists of two parts: transforming matrix (TM) and correcting matrix (CM). The structure TM is similar to the structure of Cooley-Tukey FFT algorithm. Thus pipeline plementation of the TM has been researched enough whereas implementation of the CM

is practically unknown. The main peculiarity of CM is recursive structure of the bas adding operations. Sequential nature of these operations is convenient for one-chann iterative and pipeline implementations but results in large timing latency or requin significant additional hardware in multichannel cases. With the purpose to reduce hardwa and timing penalties a new algorithm for parallel CM computation had been develope featuring the same number of independent parallel basic operations (BO) instead sequential BOs of the usual FCT algorithm. The new parallel algorithm had been al: developed for the inverse FCT with the same results of reducing hardware and timh penalties.

In the thesis development of the one-, two-, multichannel and parallel pipeli; processors for the FCT implementation is considered. As processors with a few charuu for TM implementation are investigated enough so development of the multichannel T processors is considered. For TM implementation optimised structures of the multichanr sorting memories are developed. For CM implementation four basic structures of pipeli processors are considered. They are based on existing FCT algorithms and new paral FCT algorithm developed in this thesis. Considering advantages and drawbacks of structures the generalized methodics of multichannel pipeline CM processors engineering developed which allows to design processors with minimum hardware expenditures

Fast Fourier transform (FFT) algorithm with real-factor coefficients has simp significantly basic operation structure comparing to Cooley-Tukey FFT algorithm w complex coefficients but similar to FCT algorithm requires additional CM unit. Althou usual fast Hartley transform (FHT) deals with real coefficients but real-factor FI algorithms simplifies basic operation structure significantly although also requires CM uj The pipeline processors for the real-factor FFT and FHT algorithms implementation , developed in the thesis and compared to the Cooley-Tukey algorithms pipel implementations. Investigations testifies that for small and average sizes of these transfer the real-factor algorithms allows to obtain minimum hardware expenditures.

The discrete wavelet transform (DWT) is widely used in the tasks of signal and im; compression. Its high computational requirements stipulates development of speciali: processors for its implementation. Pipeline processors for DWT implementation developed in the thesis. Comparing to existing implementations they feature generali: structure not depending on transform size and filter length. Investigations shows resemblance of the RFFOT and DWT pipeline processors that allowed with the aim reduce hardware expenditures to develop pipeline processor for implementation of the Hartley transform and discrete wavelet transform.

New parallel FCT algorithm was used to develop VHDL-model of the parallel channel pipeline processor for 8-point inverse FCT algorithm implementation. Develo processor was implemented using FPGA of Xilinx, Inc. Simulation with Xilinx Founda: software showed the best timing and hardware parameters of this processor comparing existing 8-channel processors.

The main scientific results of this thesis were introduced in scientific-research proj< conducted by Lviv Polytechnic University and in educational process of the Departmen Computer Engineering of National Lviv Polytechnic University as the part of lecturing laboratory methodical papers.