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

Міністерство освіти і науки України

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

. о

УДК 621.372:681.3

Аль-Хамарші Кадрі Джамал /

УНІФІКОВАНІ ЗАСОБИ ВИКОНАННЯ ШВИДКИХ АЛГОРИТМІВ ЗСУНУТИХ КОСИНУСНИХ ТА СИНУСНИХ ПЕРЕТВОРЕНЬ

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

АВТОРЕФЕРАТ дисертації на здобуття наукового ступеня кандидата технічних наук

Львів - 2000

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

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

Науковий керівник: доктор технічних наук, старший науковий співробітник, Яцимірський Михайло Миколайович,

Національний університет “Львівська політехніка”, доцент

Офіційні опоненти: доктор технічних наук, професор Грицьків Зенон Дмитрович,

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

доктор технічних наук, старший науковий співробітник Воробель Роман Антонович,

Фізико - механічний інститут ім. Г.В. Карпенка НАН України, старший науковий співробітник відділу обчислювальних методів та систем перетворення інформації, м.Львів.

Провідна установа: Державний науково-дослідний інститут інформаційної інфраструктури Державного комітету зв’язку та інформатизації України і Національної академії наук України, м.Львів.

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

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

Автореферат розісланий “26” жовтня 2000 р.

Вчений секретар __

спеціалізованої вченої ради, .

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

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота тісно пов'язана з планами навчальної і наукової роботи Національного університету “Львівська політехніка” (тема ДБ “СЕРГ”, номер державної реєстрації 0198и002355 від 13.03.98), а також з тематикою міжвузівських програм на 1997-1999 роки (Міносвіти України від 3. XII. 1996 р., № 6/10-149). Зокрема, вона відноситься до проблеми №10 - розробка теорії, моделей і алгоритмів для створення інтелектуальних систем обробки інформації.

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

і потокових процесорів, а також програмного забезпечення сигнальних процесорів та універсальних ПЕОМ,

Для досягнення поставленої мети необхідно вирішити такі задачі:

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

2. Удосконалити методи синтезу швидких алгоритмів зсунутих ДКП і ДСП виділених видів з метою скорочення обчислювальних затрат і уніфікації засобів їх виконання.

3. Синтезувати уніфіковані швидкі алгоритми обчислення зсунутих косинусних і синусних перетворень всіх видів. Показати ефективність їх застосування при розробці уніфікованих програмованих, ітераційних, потокових і матричних процесорів виконання швидких алгоритмів ОТП.

4. Показати можливість ефективної реалізації типових процедур ЦОС (ортогональні перетворення, згортка, кореляція) на процесорах швидких зсунутих косинусних та синусних перетворень.

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

Наукова новизна отриманих результатів:

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

2) Синтезовано прямі швидкі алгоритми зсунутих косинусних та синусних перетворень четвертого виду з часовим та частотним прорідженням, а також отримано аналітичні оцінки їхніх обчислювальних витрат. Показано, що вони скорочують N/4 Іо%2 N додавань і N/4 log2N множень порівняно з відомими, аналогічними за призначенням, алгоритмами.

3) Запропоновано і обгрунтовано новий підхід до синтезу швидких побічних алгоритмів косинусних і синусних перетворень другого-четвертого видів, у котрому як базові використані відомі швидкі алгоритми косинусного та синусного перетворення першого виду. На його основі синтезовані швидкі побічні алгоритми перетворень другого - четвертого видів. Отримано

з

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

4) Показано, що запропоновані в роботі швидкі алгоритми косинусних та синусних перетворень дозволяють побудувати ефективні уніфіковані засоби виконання швидких алгоритмів ОТП у вигляді: ітераційних, матричних і

’ потокових процесорів, а також програмного забезпечення універсальних ПЕОМ і сигнального процесора TMS320C50.

5) Уперше зстановлено, що косинусне перетворення другого виду, його швидкі алгоритми і засоби їхнього виконання забезпечують реалізацію процедур фільтрації і кореляції сигналів за схемою:, пряме перетворення + добуток спектрів + обернене перетворення. Тому вони можуть бути використані як базові при побудові уніфікованих засобів ЦОС (на основі процесорів ШКП).

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

Реалізація результатів роботи. Отримані алгоритми використовувались при розробці структури і програмного забезпечення інформаційно-обчислювального комплексу системи забезпечення сертифікаційних випробовувань автотранспортних засобів (тема ДБ “СЕРГ”). Використання результатів роботи дозволило уніфікувати засоби ЦОС і скоротити час виконання процедур фільтрації і спектрального аналізу. Застосування уніфікованого підходу до побудови алгоритмів та засобів ЦОС при проведенні на кафедрі ЕОМ курсів “Обробка сигналів” і “Теоретичні основи і засоби медичної та технічної діагностики” дозволило в компактному виді подавати матеріал в частині методів і процедур ЦОС, що сприяло розширеному поданню та кращому засвоєнню особливостей їх, застосування. Застосування уніфікованих алгоритмів косинусних та синусних перетворень дозволило в 1.5-2.0 рази скоротити час розробки програмного забезпечення підсистеми попередньої фільтрації програмного комплексу обробки космічних зображень, ДКР “Нормалізація ”0кеан-0””, що розроблявся у науковому підприємстві СКБ ТВС (Львів). ,

Публікації. По темі дисертації опубліковано 12 наукових робіт [1-12], з них 8 статей у фахових науковий виданнях [1-8]. '"

Особистий внесок пошукувана. Всі теоретичні і практичні розробки, що виносяться на захист, виконані автором самостійно. В роботах, що опубліковані в співавторстві, пошукувачу належать: [1,5,10-11] - синтез одновимірних алгоритмів ШКП і ШСП; [1-12] - оцінка обчислювальних затрат одновимірних алгоритмів; [1-12] - розробка програм для перевірки ефективності

одновимірних алгоритмів; участь в удосконаленні методів синтезу алгоритмів та у формулюванні проблеми (задачі) в усіх наведених роботах.

Апробація роботи. Основні теоретичні й практичні результати дисертації доповідалися та обговорювалися на: 5-тій міжнародній науково-технічній конференції «Досвід розробки і застосування САПР в мікроелектроніці» (Львів, 1999); міжнародній науково-технічній конференції «Інформаційні системи та технології» (Львів, 1999); міжнародному симпозіумі «Питання оптимізації обчислень» (Київ, 1999); міжнародній конференції з автоматичного управління “Автоматика - 1999” (Харків, 1999); міжнародній конференції «Сучасні проблеми засобів телекомунікації, комп'ютерної інженерії та підготовки кадрів» (Львів-Славсько, 2000).

Структура роботи. Дисертація складається з вступу, п’ятьох розділів, списку літературних джерел з 145 найменувань, розміщеного на 9 сторінках, висновків і одного додатку, викладених на 6 сторінках. Зміст роботи викладений на 164 сторінках. Робота ілюструється 38 малюнками і 12 таблицями, викладеними на 19 сторінках.

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

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

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

д-і

У(к)=^Ф) Рх(п,к), >1-0

де х(п) - вхідна послідовність; у(к) - вихідна (спектральна) послідовність; рК(п,к) - квадратна N х /V-елементна матриця, яка задає коефіцієнти перетворення; п,/с = 0,1,2,...,ІУ-1 . Безпосереднє обчислення ДКП чи ДСП за виразом (1) має обчислювальну складність 0(М2) і тому актуальною є розробка швидких алгоритмів обчислення ДКП і ДСП. Для побудови швидких алгоритмів найчастіше використовують два методи. Прямий метод, що грунтується на властивостях матриці перетворення, і побічний (непрямий) метод, в котрому задіяні швидкі алгоритми інших перетворень - Фур’є, Хартлі тощо. Серед способів опису алгоритмів найбільшу практичну цінність має графічний, тому що він наочно відображає алгоритм і спрощує побудову засобів його виконання. Цей спосіб вибраний в роботі як основний.

При оцінці ефективності використовують інтегральні характеристики: обчислювальні затрати (кількість множень цы (А) і додавань в ах'(А) в //-точковому алгоритмі А); похибка обчислень є; об’єм пам’яті даних Уп; об’єм пам’яті констант Ус; показник структурної складності. Похибка обчислень при розв’язуванні задачі (1) - це обчислювальна похибка, що виникає в результаті заокруглень. Показник У0 відображає скільки регістрів треба виділити для збереження вхідних, проміжних і вихідних даних в процесі роботи алгоритму. Віддають перевагу алгоритмам із заміщенням, у котрих проміжкові і вихідні дані зберігаються на місці вхідних. Показник Ус відображає кількість регістрів, необхідних для зберігання допоміжних констант, пов’язаних тільки з видом перетворення (а не з вхідним сигналом). Загальна тенденція полягає в тому, що при однакових фазових множниках зменшення обчислювальних затрат веде до зменшення є. Під структурною складністю розуміють кількість правил (формул розкладу), що використовується при побудові алгоритму.

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

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

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

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

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

CllN =уі2 /N[qk q„ cos( к(2п + 1 )k ) /(2N )], п, k = 0,1,2.N-І (2)

СІПд = JÎ7N[qkqn cos(mi(2k + \)/(2N)], n,k = 0,1,2,..(3)

CIVN =42ÏN[cuq„cos(ïï(2n + \)(2k + \)/(AN)J, «,* = 0,1.2.N-l, (4)

де q0 = 1, q„~ 1/V2 при пф 0. Аналогічні варіанти матриць синусних перетворень мають вигляд ..

SIIN =WN[qkq„sin(rr(2n + i)(k + \)/(2N)], n,k = 0,1,2,...,N-1, (S)

5///Л, = 'JlÏN[qkqn sirt(n(n + \)(2k + \)/(2N)], n,k = 0,1,2,...,N(6) SIVN = -J2/N[qkq„ sin(n(2n +1 )(2k + l)/(4N)J,n,k = 0,1,2,'...,JV- 1, (7)

де qN. 1 = 1 /V2 і q„ = l при n#N-\.

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

де 0(к) - //-точкове ДСПІІ вхідної послідовності х(п), п = 0,1,...,/V-1; А(к) і В(к) - N/2-точкові ДСПІІ підпослідовностей Ь(п)~х(п)-х(А’-І-п) і а(п)=(х(п) + хв^-\-п))2со5{л(2п + \)І(2М)), и=0Д,...,іУ/2-1 . Як і у відомих

алгоритмах ШКП другого виду (ШКПІІ), формула розкладу алгоритму ШСПІІ

підсумовування, на якому виконуються перетворення (8).

Побудовано графи цих алгоритмів і встановлено, що відомий алгоритм ШКПІІ і синтезований у роботі алгоритм ШСПІІ мають однакову структуру графів. їх відмінність полягає тільки в перекомутації виходів базової операції. Зокрема, на Рис. приведені базові операції алгоритмів ШКПІІ і ШСПІІ, де а і Ь

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

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

Q(2k + l) = (-1)*Л(к), * = 0,І,2-1; QW~2) = B{N І2-\)І2,

Q{2k) = В(к) - Q(2k + 2), к = ЛГ / 2 - 2,N / 2 -3,...,0

(8)

містить два етапи: основний, на якому обчислюються послідовності а(п) і Ь{п)\

------•а+Ь

б)

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

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

Ь%(0) = Ху(О)/ 2, ¿"Vк)=х!!(к)~ ¿"> - іл ■* = 1,2,...,ТУ -1, (9)

де ¿'¡¡(к)=ЩШ1У^{х(п)}, х{(п) = 2х(п)со5(л(2п + 1)/(4УУ),

Xу (%)=ДКПНМ ^х, (п)}. 3 метою подальшої уніфікації встановлено, що ДСПІУ можна без втрат у кількості операцій виконати на основі алгоритму 1І1КПП (а не ШСПІІ). Таким чином, встановлено, що перетворення ДКПІІ, ДСПІІ, ДКПІУ і ДСПІУ можна виконати за одним уніфікованим прямим швидким алгоритмом ШКПІІ, доповненим операцією множення вхідної послідовності на фазові множники і одним етапом підсумовування.

Отримано оцінки обчислювальних затрат синтезованих прямих алгоритмів ШКП і ШСП четвертого виду (ШКГПУ і ШСПІУ): // (г (ШКП - ШСП) = N / 2 (Іо8г N + 2 ;, а(ШКП - ШСП) = ЗУУ / 2 /о£, Л'. Встановлено, що у порівнянні з відомими аналогічними алгоритмами кількості операцій множення і додавання скорочено на Л'/Ч/о^іУ. На основі ізоморфної трансформації модифіковано графи алгоритмів ШКГІІУ і ШСПІУ. Показано, що на основних етапах вони повністю повторюють структуру графів алгоритмів І1ІПФ Кулі-Тьюкі за основою два і, таким чином, вдало поєднують уніфікованість і високу ефективність обчислень з простотою структури.

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

ШКП4Х і ШСП4Х. Основна увага тут приділялась синтезу нових алгоритмів четвертого виду.

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

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

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

аПV-1 -«) х(2п + \), (,ч = - і), п = 0,1..N /2 - І.

Крок 2. За допомогою операцій поворот вектора, обчислюємо допоміжну послідовність у2{п): у2(0) = а(0), y2(N/2) = a(N /2);

у2{п) = а(п)С^+а(И-п)8пм, . ■

у2{Ы - п) = а{п)Б'й - а(Л? - и)^, п = 1,2,..., ЛҐ / 2-1.

Крок 3. Виконуємо іУ -точкове ДПХ: У2(к) = ДПХЫ {у2(п)}.

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

1]Ц, {к)=У2(к)ЩК{1к + 1)+Г2(^-1 -к)Я^(2к +1),

£"'(*-1 - к)=ї2(к)Е^,(2к + 1)~ ¥г(Ы-\ - Л)Л^(2* +1), де к = 0,1, ..„ЛГ/2-1, Щ,(к) = (С^,-8ки,)/2, Л8^; = ґС^+‘0/2,

СГК = соз(2ж/К), Б'к - 5іп(2пг /К).

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

Алгоритм ШСП4Х - обчислення перетворення (1) послідовності х(п), /1 = 0,1,...,^-!, з матрицею (7) - при часовому проріджені збігається з алгоритмом ШКП4Х з точністю до параметра л’, що використовується на першому кроці, для ШСП4Х 5 = 1. В алгоритмах ШКП4Х і І1ІСП4Х з частотним прорідженням кроки один-чотири виконуються в зворотному порядку, а в алгоритмах ШКП2Х, ШСП2Х, ШКПЗХ, ШСПЗХ відсутній другий крок поворотів вектора.

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

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

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

Таблиця.

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

№ п/п Метод Множення (/¿у ) Додавання (а д- )

1 Прямий аЦ -а1Ц = 2тЛ (Зт-2)+\

2 Побічний =//"'= 2 тЛт ■ а“ =а“‘ =2ті(Зт-2)+2

3 Прямий //'!' =2'"-' (« + 2) «у =3 2т~1 т + 4

4 Побічний (ШПХ24) /^'=2"-’ (т + 2) се" =3 2т~{ т + 4

5 Побічний (ШПХ2) Мк = 2"’-' (т + 3)-2 а^=2т_1 (Зт + 1) + 2

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

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

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

у, = х, ■ С + х2 ■ 5; у2 = хі • Б - х2 • С,

де X] і х2 - входи операції; уі і у2 - виходи операції; С і 5 - фазові множники, що містяться в пам’яті констант. При цьому додатково треба забезпечити перекомутацію входів-виходів, тобто подавати їх прямо чи навхрест. Показано,

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

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

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

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

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

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

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

2) Розвинуто метод побудови швидких побічних алгоритмів обчислення

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

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

Показано, що при реалізації на процесорі ТМ8320С50 побічні алгоритми косинусного і синусного перетворень мають перевагу в часі виконання порівняно з прямими алгоритмами. Перші алгоритми скорочують час виконання на 18% і їх доцільно використовувати як базові при реалізації на сигнальних процесорах. .

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

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

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

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

1. Мороз І., Хамарші К., ІІцимірський М. Реалізація одно- та двовимірних алгоритмів ортогональних тригонометричних перетворень на процесорах цифрової обробки сигналів серії ТМБ320// Вісник Державного

університету "Львівська політехніка". Радіоелектроніка та телекомунікації. -Львів. -1999. -№ 3 87. - С. 292-297.

2. Хамарши К. Д., Яцимирский М. Н. Быстрое, вычисление симметричных косинусного и синусного преобразований // Збірник наукових праць. Інституту проблем моделювання в енергетиці. -Киев. -1998. -вып. 4. -С. 169-174.

3. Хамарші К., Яцимірський М. Швидкі алгоритми прямого та оберненого дискретного синусного перетворення // Технічні вісті. -1999. -№ 1(8), 2(9).-С. 37-40.

4. Хамарши К. Д., Яцимирский М. Н. Быстрые алгоритмы косвенного вычисления косинусных и синусных преобразований (ДКП-І1 и ДСП-11) // Вісник Державного університету "Львівська політехніка". Комп'ютерна інженерія та інформаційні технології. -Львів. -1999; -№ 370 -С. 111-116.

5. Хамарши К.Д, Яцимирский М. Н. Быстрые алгоритмы одномерных косинусных и синусных преобразований // Вестник Харьковского государственного политехнического университета. Системный анализ, управление и информационные технологии. - 2000. - № 97. - С.100-105.

6. Яцимірський М.М, Хамарші К.Д. Синтез алгоритмів швидкого синусного перетворення/УВісник Державного університету "Львівська політехніка". Комп'ютерні системи та мережі. -Львів. -1998. -№ 350. - С. 90-93.

7. Яцимірський М. М., Хамарші К. Д. Швидкі алгоритми обчислення косинусно-синусного перетворень для систолічних структур // Інформаційні технології і системи. -1998. -№ 1/2. -С. 190- 194.

8. Яцимірський М., Мороз 1., Хамарші К. Синтез швидких алгоритмів двосторонньо зсунутих одно та двовимірних косинусних та синусних перетворень // Вісник Державного університету "Львівська політехніка ". Комп'ютерна інженерія та інформаційні технології. -Львів. -1999. -№ 380 -С. 130-136.

9. Хамарши К., Яцимирский М. Фильтрация и корреляция сигналов на

основе быстрых алгоритмов косинусного преобразования // Технічні вісті. -2000.-№ 1(10), 2(11).-С.92-96. ‘

10. Яцимірський М.М., Мороз І.В., Хамарші К.Д. Синтез швидких алгоритмів одно- і двовимірних косинусних та синусних перетворень // “Теорія обчислень”: 36. наук, праць. НАН України, Ін-т кібернетики ім.В.М.Глушкова, Наук, рада НАН України з проблеми “Кібернетика”; Редкол.: І.В.Сергієнко (відп. ред.) та ін. - Київ, 1999. - С. З96-400.

11. Moroz I., Hamarsheh Q., Yatsymirskyy М. The implementation of the fast one/two-dimensional orthogonal trigonometric transform algorithms with the TMS320 family digital signal processor II Proceeding of international conference on modern problems of telecommunications, computer science and engineers training. -Lviv-Slavsko, Ukraine. - 2000. - P. 116-117.

12. Яцимирский М., Хамарши К. Синтез алгоритмов быстрого вычисления дискретных симметричных косинусного и синусного преобразований // 5-та міжнародна науково-технічна конференція «Досвід розробки і застосування САПР в мікроелектроніці. -Львів. - 1999. - С. 147-148.

АНОТАЦІЯ

. ! ■ ' 1 '

Аль-Хамарші Кадрі Джамал. Уніфіковані засоби виконання швидких

алгоритмів зсунутих косинусних і синусних перетворень. - Рукопис.

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

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

Ключові слова: ЦОС, уніфікація, швидкі алгоритми, ортогональні перетворення, спеціалізовані процесори.

АННОТАЦИЯ

Аль-Хамарши Кадри Джамал. Унифицированные средства выполнения быстрых алгоритмов сдвинутых косинусных и синусных преобразований. - Рукопись. .

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

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

В работе усовершенствованно прямые и косвенные методы синтеза быстрых алгоритмов сдвинутых косинусных и синусных преобразований второго - четвертого видов. Раскрыта взаимная связь между преобразованиями второго и четвертого видов, на основе которой синтезированы прямые быстрые алгоритмы косинусного и синусного преобразований четвертого вида. Показано, что они сокращают на 10-20% вычислительные затраты по сравнению с известными аналогичными алгоритмами и выгодно отличаются от последних простотой структуры - имеют простой граф, подобный алгоритму БПФ Кули-Тьюки по основанию два, и упрощенную базовую операцию, состоящую из одного умножения и двух сложений. Полученные быстрые алгоритмы косинусного и синусного преобразований четвертого вида отличаются от известных прямых алгоритмов быстрого косинусного преобразования второго вида тем, что содержат два дополнительных шага -умножения преобразуемой последовательности на' фазовые множители и суммирования спектральной последовательности. При этом последний шаг имеет структуру, совпадающую с этапом суммирования алгоритмов второго вида, что обеспечивает простоту построения унифицированных средств выполнения сдвинутых преобразований.

Усовершенствован метод построения быстрых косвенных алгоритмов вычисления косинусных и синусных преобразований второго - четвертого видов. На основе формул разложения известных алгоритмов косинусных и синусных преобразований первого вида получены косвенные унифицированные алгоритмы сдвинутых косинусных и синусных преобразований с наименьшими вычислительными затратами среди известных алгоритмов данного класса. Показано, что алгоритмы, БПФ, быстрого преобразования Хартли (БПХ) и быстрые косвенные алгоритмы косинусных синусных преобразований состоят из трех обобщенных шагов: перестановки данных, выполнения БПХ и выполнения операций поворотов вектора. При этом БПХ без потерь в количестве операций можно заменить парой быстрых алгоритмов косинусного-синусного преобразования первого вида. Таким образом, разработаны унифицированные быстрые алгоритмы выполнения БПФ, БПХ, а также БКП и БСП всех четырех видов.

С целью унификации средств ЦОС при выборе, БКП как базового преобразования показано, что оно обеспечивает эффективное выполнение процедур фильтрации и корреляции сигналов по классической схеме: прямое БКП + модифицированное умножение спектров + обратное БКП.

Рассмотрены вопросы построения унифицированных средств выполнения ОТП. Установлено, что для расширения функциональных возможностей итерационного процессора БПФ-БПХ в направлении обеспечения возможности

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

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

Показано, что при реализации на сигнальном процессоре. TMS3£0C50 косвенные быстрые алгоритмы косинусного и синусного преобразований имеют преимущество во времени выполнения по сравнению с прямыми алгоритмами. Они, алгоритмы, сокращают время выполнения на 18% и их целесообразно использовать в качестве основных при реализации на сигнальных процессорах. Время выполнения преобразований на универсальных ПЭОМ с помощью универсальной программы, разработанной на основе полученных в работе алгоритмов, практически совпадает с временем выполнения специализированной программы.

Ключевые слова: ЦОС, унификация, быстрые алгоритмы, ортогональные преобразования, специализированные процессоры.

ABSTRACT

Al-Hamarsheh Qadri Jamal. Unified means of fulfillment of fast algorithms of shifted cosine and sine transformations. - Manuscript.

Thesis on competition of a scientific degree of the candidate of engineering science on a speciality 05.13.13 - computers, system and web. - State university “ Lviv polytechnic ”, Lviv, 2000.

The thesis deals with development of unified means of fulfillment of fast algorithms of orthogonal angular transformations, including cosine and sine transformations shifted in temporary and frequent areas.

Direct and indirect methods of synthesis of.fast algorithms of shifted cosine and sine transformations (DCT and DST) of second - fourth kinds for unified means of digital signal processing are improved. On their basis the number of fast algorithms is synthesized . These favourably differ from known algorithms by structural complexity and reduced computing costs. Particularly, the new fast DCT and DST algorithms of the fourth kind are obtained which have a simple structure and

compared to known algorithms reduce NI A\og2 N of additions and A741og2 N Multiplication for given of N - point transformation.

It is detected, that DCT of the second kind and it’s fast algorithms allow to calculate a convolution and correlation under the scheme: direct transformation + multiplication of spectra + inverse transformation. Therefore they can be used as base in DSP means' construction.

It is shown, that the synthesized algorithms allow to develop unified iterative, matrix and data-flow processors for fulfillment of orthogonal angular transformations

- Fourier, Hartley, shifted cosine and sine - without essential increase of amount of the equipment and losses in productivity compared to one-transform oriented processors. Particularly, the extension of functionalities of iterative processors for fast Fourier-Hartley algorithms is attained at the expense of additional introduction one or two switches into it's base operational device (depending on the algorithm basis).

Key words: DSP, unification, fast algorithms, orthogonal transformations, specialized processors.

Підписано до друку 23.10.2000 р.

Формат 60x84 1/16. Папір офсетний.

Друк на різографі. Умови, друк. арк. 1,4. Обл.-видав. арк. 0,9. Тираж 100 прим. Зам. 440.

Поліграфічний центр Видавництва Національного університету “Львівська політехніка” вул. Ф.Колесси, 2, 79000, Львів