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

НАЦЮПАЛЬНА АКАДЕМЫ ПАУК УКРАЙШ 1НСТИТУТ ПРОБЛЕМ МОДЕЛЮВАННЯ В ЕНЕРГЕТИЦ1

| КонфденцШно

Екз.№

УДК 621.39:681.33

МОХОР Володимир Володимировнч

МЕТОДИ ДОСЛ1ДЖЕННЯ ВЕЛИКИХ КОМБ1НАЦ1ЙНИХ СХЕМ НА ОСНОВ1СПЕКТРАЛЬНИХ МОДЕЛЕЙ В БАЗИСАХ СКЛАДНИХ РОЗРЯДНИХ ФУНКЦ1Й

Спец1альшстьсв44Ш)2 - Математичне моделювання та обчислювалып методи

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

Кшв 1998

Дисерташсю е рукопис

Робота виконана в Гнституп проблем моделювання в енерге-тищ HAH УкраТни.

Науковий консультант - чпен-кореспондент HAH УкраТни, доктор техшчних наук, професор Евдокимов Виктор Федорович, 1нститут проблем моделювання в енергетиш, директор.

Офшшш опоненти:

доктор техшчних наук, професор Додонов Олександр Георгшович, 1нститут проблем реестрацп шформацп HAH УкраТни, заступник директора з науковоТ роботи;

доктор техт'чних наук, професор Бшецький Володимир Миколайович, 1нститут проблем моделювання в енергетищ HAH УкраТни, завщуючий вшнлом;

доктор техшчних наук Рогоза Валерш Сташславович, Нацюнальний техш'чний ушверситет УкраТни "КиТвський полпгехшчний ¡нститут", професор.

Провщна установа - Науковий центр таймерних обчислю-вальних систем 1нститугу кибернетики HAH УкраТни, м.КиТв.

Захист вибудеться "_"_199_року о_

годиш на засщанш спещашзованоТ вченоТ ради Д26.185.01 ШМЕ HAH УкраТни за адресою: 252680 МОД, Кшв-164, вул.Генерала Наумова, 15.

3 дисерташсю можна ознайомитись в б1бл10тец1 ШМЕ HAH УкраТни.

Автореферат розюланий_

Вчений секретар спешал13ованоТ вченоТ ради / _Семапна Е.П.

ЗАГАЛЫ1А ХАРАКТЕРИСТИКА РОБОТИ

Актуалыпсть теми

Математичне моделювання ) чисельне експериментування е одним з основних метод ¡в досл!дження процеав га явищ, натурне експериментування з якими в силу рЬних причин неможливе або недоцшь-не. В першу чергу це стосусться сошально-економ1чних систем, ор-гашзацшно-техшчних 1 глобалышх ресурсо-комужкацжних. Задач! цього класу були 1 е важливими в усьому свт (Дж.Нейман, К.Шеннон, Р.Беллман, Н.П.Бусленко, Г.СПоспслов, В.Л.Волкович, О.Г.Додонов, 1.1.Ляшко, В.С.Михалевич, М.В.Михапевич, А.А.Морозов).

Разом з тим, технолопчна револют'я останш'х ромв, яка торкнулась практично вах сфер людськоТ дшльносп, наочно довела, шо ви-робнич! ! сусгильш досягнеиня можлив! тьпькн за умов кошткого в1д-працювання вщповщноТ математично! модел! надежного р1вня адекватности В бшьшш мф! це притаманне складним об'ектам 1 системам, як! характеризуються значною кшыа'стю входов, виход!в \ наявшспо перехресних зв'язмв М1Ж ними. Критерий «складний об'ект», «значна ю'льмсть» завжди досить умовний 1 залежить вщ юлькосп ступешв свободи по кожному з ВХ0Д1В або виход!в, типу поставлено!' задачI та використовуваного алгоритму. Якщо обмежити клас вивчаемих об'ек-тт такими, для яких множина сташв об'екта повшстю визначаегься детермшованими бшарними функцЬши стан!в його вход!в ! не залежить в1д часу (прикладами таких об'оспв е цифров! комутатори ! пе-ретворювач! код|"в, включаючи функщ'оналып* перетворювач! та схе-ми м!кропрограмного управлшня, формою реатацн яких, зазвичай, е комбшацшш схеми), то пщ складним об'ектом (великою комбшацш-ною схемою) будемо вважати об'екти з такою юльюстю вход1в, що п обробка вимагае ресурсов, обсяг яких не е досяжним при розв'язаннг конкретно поставлено! задач!. Наприклад, при потужност! ЕОМ в 100 млрд. операцш за секунду ! китькост! вход!в 8 задача пошуку на мно-

жиж функцш стану комбжацжноТсхеми методом Ух перебору, що ш-дома, як загальна задача мнимпацп, вимагае ресурав часу обсягом 5 рокт. Тому комбшацшна схема в цьому випадку виступае складним об'ектом. В подальшому комбшацншу схему, яка виступае як склад-ний об'ект, будемо називати великою комбшацжною схемою (ВКС).

Слщ вщзначити, ьцо технолопчш досягнення останшх рок1в в облает! виробництва елементноГ бази цифровоУ техш'ки вже зараз дозво-ляють розлпщувати на одному кристап'1 бшьше шж мшьйон вентшпв 1 0Ч1куеться, що вподовж одного-двох роив це число збшьшиться в 3 -5 раз1в. Для такси емност« кристатв проблема м'пнмваци велико! ком-бшацшноУсхемн, що буде в ньому реализована, насьогодиI е актуальною практичною задачею.

Зазвичай, е два шляхи розв'язання проблема мш!м!зацн ВКС. Перший (лопчний синтез), полягае в мпттаци деякоУ булево! формула, записано'! в визначеному логичному базис! (В.М.Глушков, Л.А Ка-лужшн, О.А.Летичевський, Г.О.ЦеГшин, К.Л.Ющенко). В загальному випадку розв'язання ц5еТ задач1 на наш час невщоме, хоча для окремих лопчних базис!в ¡снують методи, достатш для побудови конструктив-них алгоритм1в м1н!м!зацп. Апе при цьому виникае шша проблема -проблема юнування в визначеному логичному базис! мш!м!зованоУ формули, виграш в складносп якоУ е достатшм для того, щоб розв'я-зання задач1 мшмваци мало сенс. Таким чином, ми повертаемось до проблеми м!шм!защУ в загальному випадку.

1нший шлях - шлях структурного синтезу - полягае в переход! з р!вня опису схеми в термшах функций лопчного стану до р!вня и опи-су в термшах задач! наближення (В.П.Боюн, В.Ф.евдокимов, Б.М.Ма-линовський, О.В.Палапн, К.Г.Самофалов). В основ! будь-яких мето-Д1в розв'язання задач! наближення завжди е припущення, щодо вибо-ру базису наближення. Ршшм базисним системам вщповщае р1зна структурна ¡нтерпретащя !, що найважлив!ше, р!зна практична реал!-

защя, тому що так-! техшчш характеристики, як точшсть, швидкод^я та апаратш вигратн прямо залежать в!д внкорнстаних СБФ I для вш-мшних систем е суттсво рвними. Вио1р базису виконусться, зазвичай, на множим повних, ортогональних систем лшшно незалежних функ-щи, яких в багатоииг.и'риому простор!* ¡снуе нескшчена бшьцясть. За цих обставин пошук найв1дпов1дшших з них являе собою значну ма-тематичпу 1 практичну проблему, яка в загальному випадку в наш час такожзалишаегься нерозв'язаною.

При розв'язанш зада41 структурного синтезу, зазвичай викори-стовуютъся дискрет) п' аналоги вщомих аналггичних базис ¡в (полшо-ш'альних, експоненц5альних , тригоиометричних та ¡п.), для яких ви-конаш всеб1чж математичш дослмження 1 обгрунтувапня, що своТм коршням сходять до Бериулли Даламбера, Лагранжа, Ейлера I Фур'е. Значним внеском наших чаав в галуз1 прикладних ас пекл'в р!зних аналтшшх базисов стало вщкритгя 1 розвиток для иих швидких об-числювальних алгоригопв (Дж.Ку.'п, Дж.Тьюм, С.Виноград, В.Д.Бай-ков, Г.М.Луцький, Г.€.Пухов).

Суб'ективно-практичною вадою анал^тичних базиЫв, характерною для нашого часу, е те, що шшдна методолоп'я Тх застосування спирасться на властивоеп Тх неперервноспт. Використання ж цифро-воТ дискретно!" форми Тх представления вносить первюну методичну погршшсть наближення наближуючоТ функци.

В значнш шр\ цей недолк долаеться в клаа систем так званих двшково-ортогоналышх функшй (типу функцш Волша). Область до-пустимих значень функцш цих систем обмежуегься множиною з двох елеменпв - (+1) и (-1), що з одного боку наближуе Тх до двшковоТ си-стеми, в яюй функцюнують цифров1 пристроТ, а з шшого боку збертае Тм ортогоналып властивост! \ вс5 т! переваги, як! з ними пов'язаш. Про-те, ¡снування протилежних у простор! дшсних чисел елеменпв (+1) 1 (-1) призводить до того, що при виконанш алгебра!чного додавання

виникае трели элемент — 0. Власне з uieT причини двшково-ортого-нальш системи, формально перебуваючи в клаЫ двшкових систем, при застосуванш в задачах наближення повинш розглядатись, як троУчш". За цих обставин виходить, що серед множили можливих СБФ так зва-Hi двшково-ортогональш системи в загальному випадку не можуть бути риднесеш Hi до класу аналггичних базист, ш до класу базиав, по-роджених функц1ями апгебри лопки, а результата, яю для них одержан!, не можуть бути безпосередньо застосоваш в биюрному npocTopi, в якому в наш час реально функцюнуе вся цифрова техшка. Таким чином Micue двшково-ортогональних (в {0,1}-розумшш) базист, важ-ливих для розв'язання задач наближення в дискретному npocropi, ли-шаеться вшьним.

Тому в математичному моделюванш е актуальною проблема ви-найдення класу дискретних базиав, як! б в найбшышй Mipi вщповЬа-ли потребам розв'язання задач наближення детермшованих npoueciß з бшарною лог!кою вхщних подш взагагн i задач синтезу комбшащйних схем спец1ал130ваних пристроТв обробки та перетворення ¡нформацп зокрема.

Зв'язок роботи з наукопими програмами, планами, темами.

Робота виконувалась в межах проведения досл!джень згщно Bi-домчого плану НДР HAH УкраТни (теми «Розряд», «Функщя», «Гра-шт», «Бар'ер», «Веер»), плану НДР та ДКР Секци прикладних проблем МЫстерства оборони УкраТни («Селен», «ВвавьУА»), вщом-чого плану НДР та ДКР Державно"/ служби УкраТни з питань техшч-ного захисту шформаци («Мережа-11»), вщомчого плану прикладних НДР та ДКР Державного комггету УкраТни з питань науки, технки i технологи («Криптон», «Старт»), вщомчого плану прикладних роб1т Национального агентства УкраТни з питань шформатизацй' («Крипто»), плану НДР та ДКР Мшмашпрому УкраТни вщповщно до комплексно! цшьовоТ программ по створенню прилад1в для нафтогазовоТ галуз1 та геологорозв!дки («Корунд»), вщомчого плану НДР Мшстерства Ук-

раши з надзвичайних ситуацш («Ммчорнобиль», «Пакет», «Сирена»), а також у зв'язку з виконанням ряду господарських угод з гп'дприемст-вами та установами.

Мета 1 зада-и доелмження

Основною метою дослщження е:

- розвиток теорп складних розрядних функцш, як математич-них моделей, якм в найбкпьш'й м[р! вщображують суть детер-мшованих процеЫв дискретних змш стану виход1в складних техшчних об'ектт без пам'ят! з 61 парною лопкою входных под1 й (на приклад! великих комбшацшних схем);

- розробка метод1"в формування спектральних моделей великих комбшацшних схем (ВКС) в базис! складних розрядних функцш з метою спростити розв'язання задач Ух анамзу та синтезу.

Для досягнення поставлено'!' мети необхщно розв'язати наступи! задач!:

1. Дослщити та теоретично обгрунтувати основш властивосп систем складних розрядних функцш, як1 забезпечують ефектившеть Ух використання для моделювання лопчних сташв ВКС.

2. Розробити методи побудови математичних моделей найкра-щого середньоквадратичного наближення дискретних детерм!'нованих процеемв змш лопчних сташв ВКС у вигляд1 многочленов по елемен-тах базису складних розрядних функцш(СРФ).

3. Розробити способи оцшки методично"1 похибки моделей вщ обмеження числа члешв в многочленах найкращого наближення та методи контролю в!рносп обчислень коефицатв многочлешв.

4. Визначити метод оцшки 1 критерш швидкосп зб1Жнося1 по-слщовностей наближуючих многочлешв в базиа СРФ.

5. Розробити методи \ алгоритми швидких спектральних пере-творень в базис! СРФ та пор!вняти \х ефектившеть.

6. Розробити методи анашзу та синтезу ВКС в базиЫ складних розрядних функцш.

Наукова новизна одержяних результатов.

Пщсумком розв'язання сформульованих вище задач дослщжен-ня е так1 нов! пауков! результата, що виносяться на захист:

1. Розвиток методологи математичного моделювання ВКС у ви-гляд! постановки задач! побудови найкращого средньоквадратичного наближення в простор"), базисом якого е впорядкована лшшно неза-лежна система детермшованих днскретних елеметтв, визначених на множиш {0, 1} за допомогою оператор1в булевоТ алгебри 1 таких, що описують змши в чаЫ лопчного стану виход1в ВКС в залежносп вщ змши стану Г» вход!в. Така постановка, на вщмшу вщ вщомих, дозволяв принципово виключити можливоть похибок, зумовлених методичною та приборного погршшстю дискретного представления ба-зисиих елемештв, а також зберегти можливють використання апарату булево» алгебри для Тх анал1тичного подання.

2. Вперше визначаи основа'! понятгя й властивост! систем склад-них розрядних функцш, як впорядкованоТ' множини лшшно незалеж-них двшкових елеменпв, народжених операторами булевоТ алгебри над функциями змши стану розрядш двшкового л^чильника, що доз-воляе обгрунтувати можливкть використання систем СРФ, як базис наближення. Системи СРФ б1пьш повно вщображують суть перетво-рень, як} здшснюються лопчними функцюнальними елементами електронних схем, шж будь-ям шип базиси, що використовуються в наш час, I добре пристосоваш для дискретного подання в будь-якому скшченому штервап! змши незалежноУ змшноТ при р1вномфному н квантуванш з частотою, що визначаеться теоремою Котельникова.

3. Стосовно систем СРФ визначеш понятгя бюртогонального доповнення, оператор ¡в сполученого перетворення, розрядного скалярного добутку, розрядноТ норми та розрядно! метрики. Одержан! результата забезаечують методолопчну основу застосування теорм ряд1в Фур'е при розв'язанш задач1 побудови математичноГ модел1 динамки лопчних станш ВКС у виглядг многочлену найкращого серед-

ньоквадратичного наближення в базис! складних розрядних функцш.

4. Стосовно систем СРФ розвинуто метод побудови математич-них моделей для заданого елемента простору у вигляд! многочлена найкраицого наближення з середкьоквадратичною нормою. Викори-стання м од иф1 кованого методу дозволяе сформуватп в обраному базис! СРФ дискретну слектральну модель динам!ки стану ВКС, р!вень методичноТ погршшосп функцюнування якоТ може бути визначено в загальному випадку оц!нкою залишкового члена.

5. Вперше з'ясовано ¡снування граничного значения розрядноУ норми зображаючого вектора аналп-ичноУ функцн в Ы-м!рному евюидовому простор!. 1снування граничного значения розрядноУ норми забезпечуе спрощення ош'нки погр!шност1" спектральних моделей в пор!внянн! з Тх оц!нкою по залишковому члену, а в сукупност! з оцшкою швидкосп зб!жно<П1 дае можлив'1сть алрюрного прийнятгя р!шення про доц!льн!сть прийняття або в!дхилення СРФ-моделей.

6. Стосовно систем СРФ розвинуто методику побудови алгорит-м!в швидких розрядних перетворень, ефективн!сть яких за числом операцш, як мш!мум, не прша н!ж ефектившсть алгоритм1в швидких перетворень Фур'е ! Волша та забезпечуе в пор!внянж з! звичайними розрядними перетвореннями збмьшення ефективносп в ступен!, про-поршйному розрядносг! модель

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

Практична щншсть роботи полягае в тому, то запропонований новий напрямок в досл!дженш та побудов! моделей великих комбша-ц!йних схем забезпечуе спрощення схемных р!шень 1 шдвищення тех-шчних характеристик спещал^зованих пристроУв для вир!шення задач обробки та перетворення дискретних сигнал1в.

Практичне значения мають так» результата:

- разроблено апгоритмн! програми розрахування послщовносп значень розрядних норм, як! дозволяють проводит« попередш дослщ-ження граничних характеристик фуккшональних оператор!в! створи-

та базу критерпв для прийняття рш1ень про доцшьшсть розв'язання задач 1 синтезу комбжацшноТ'схеми в базнЫ СРФ;

- розроблено методику анал!зу СРФ-спектр'т ВКС, яка дозволяв оцшити Т'х шструментальну погршшсть 1 виконати спектральку М1Н1М1зац1ю схеми у вщповщноат з припустимою методичною по-гршшстю;

- разроблено методику синтезу комбшацшних схем СБУ в базис] СРФ, яка забезпечуе поеднання простоти 1 однорщносп схемних ршень з можливютю оцшки Ух точносгп;

- розроблено алгоритмы I програми розрахунку параметр1в спектральних моделей, що дае можливють спростити розробку комбшацшних схем сиец'шшованих пристроТ'в обробки та перетворення дв(й-кових послшовностей, розширюе можливосп спектральних метод1в розв'язання ряду задач кодування повщомлень;

- розроблено методику контролю цшсност! спеетрт в базиа СРФ, засновану на властивосп виконання ртноеп Парсеваля, що дае можливють установити наявшсть помилок та збоТв в прийнятому по-вщомленш або в розрахованнх коефвдентах модели

- розроблено алгоритми швидких спектральних перетворень си-гнал'т, асимптотична оцшка ефективносп яких вщносно звичайних ал-горитм1в мае показниковий характер з основою, большою за одиницю;

- розроблено методику синтезу комбшацшних схем пристроТв, призначених для виконання швидкого перетворення в базис! СРФ, яка встановлюе однозначну вщповщшсть мок значениям (положеням) елеметтв матриц! каскаду перетворення та функцюнальним елемен-том (лшею зв'язку) схеми каскаду перетворення.

Теоретичш та прикладш результати реал13оваш в розробках, як! впроваджено в НПП «Пошук» (колишне КБ Швденного радиозаводу), ВАТ «Стек» (калишнш Чершвецький шститут автоматики), УкрНД1 ТБ, НЦ МО УкраТни, НП «Укрпейдж» при створенш спещал!30ваних

обчислювальних пристроУв, а також використовуються в учбовому процес1 КВ1УЗ та КМУЦА.

Особистий внесок здобувача.

В дисертаци використаж тшьки Т1 ¡деГ та результат», як( належать особисто автору. В спшьних роботах 5-11, 16-18 дисертанту належать постановки задач, основш ¡деТ Тх розв'язання, методи побудо-ви математичних моделей та методики '¿х використання в прикладних аспектах.

Апробащя результат»» роботи.

Основш' ¡деГта результата робота протягом 1983-1998 р.р. були внкладет на ряд\ загальносоюзних 1 республканських конферешнй та семшар!в, серед яких були: Республканська нарада-семшар з машинного проектування електронних схем (Льв1в, 1983), Загальносо-юзна школа-семшар "Розпаралелюваиня обробки ¡нформацГГ' (Львт, 1985, 1987), Загальносоюзний семшар "Питания оптимЬацн обчис-лень" (Кит, 1987, 1993), Загальносоюзна науково-техшчна конфе-ренщ'я "Проблеми пелнпнноТ електротехтки" (Кшв, 1988), Загальносоюзна науково-техшчна конференция "Проблеми комплексно! авто-матизацп функцюнальних випробувань в машинобудуванш" (Москва, 1988), Загальносоюзний симпоз1ум з проблеми наддостатносп в ¡н-формацшних системах (Лен'шград, 1989), Загальносоюзний семшар "Спец1'ал1зован1 процесори в САПР" (Москва, 1989), Республжанська науково-техшчна конферент'я "Функцюналы1о-ор1ентоваш обчислю-вальш системи" (Харюв, 1990), М1жнародна конференшя "Матема-тичне моделювання в електротехш'щ та електроенергетищ" (Льв1в, 1995).

Публтаци.

Список наукових праць автора нараховуе 60 найменувань. Онов-ш положения дисертгздУ викладеш у 38 роботах. Серед них монография (без сп1вавтор!в), 15 статей у фахових часописах 1 361'рниках (8 без сшвавтор1в), 4 авторських свшоцтва та 18 тез 1 матер'1ал1в доповщей

на конференциях i семшарах. Перел1'к найважливниих з них наведено в кшщ автореферату.

Структура днсссртаци-

Дисертац1Я складаегься з вступу, шести роздшв, buchobkíb, списку використаних джерел i двох додатшв. Текст роботи викладено на 263 сторшках, М1стить в соб? 58 рисункг'в, 5 таблиць, список використаних джерел нараховуе 109 найменувань.

ОСНОВНИЙ 3MICT

В перш ому роздкпи роботи вщзначено, що проблема розробки великоУ комбшацшноУ схеми е насамперед проблемою мнимпацм ло-пчноТ функцп и стану. Проблема m¡HÍMÍ3au¡í лопчних функшй взагал! мае значну вагу не тшьки в Teopii" цифрових автоматов, а й в практнц! розробки програмного забезпечення та створення спец1ал1зованих пристроУв обробки та перетворення шформаци. Зазвичай проблему míh¡m¡3aui'í виршують в KJiaci самих булевих функцш. Завдяки ckíh-ченост! множини р1зних булевих формул, складности не вище задано!, в принциш ¡снуе трив1альний алгоритм, який розв'язуе проблему m¡-шмЬацн шляхом поел¡довкого перебору. Але реал'юувати такий алгоритм можна тшьки за умов наявност! необмежених pecypcie. 3 цих причин в загальному вигляд! проблема мипмваци булевих функцШ в булев i й алгебр! лишасться нерозв'язаною по наш час.

За цих обставим користуються спешапьними методами та алгоритмами MÍHÍMÍ3au¡i, hk¡ розробляють для кожноУ окремоУ системи булевих функций. Найбшьш iiobho ui питания розроблеш для систем «И», «НЕ» та «ИЛИ», «НЕ». Але складшсгь цих алгоритм ¡в е показ-никовою функцкю числа зш'нних i починаючи з деякого р!вня перестае бути виршуваною.

В будь-якому випадку, m¡h¡MÍ3auii булевих формул передуе етап Ух формування, тобто запису формагнзованоУ залежност1 стану кожного розряду виходу схеми В1Д стану сукупноЫ и входов.. Складшсть

розв'язання ш'еУ задач! в загалыюму випадку також мае показннковий характер. Тому для ВКС проблемп з'являються вже на цьому еташ.

1ншим напрямком у виршешп проблеми мптшашУ е дослщжен-ня впливу змш лопчного стану на розрядному ртш на загальний (мак-ророзрядний) результат (В.В.Аристов, В.Ф.Бардачеико, О.Ф.Катков, Л.Г.Козлов, Ю.О.Плющ, В.П.Ромаицов, О.Й.Стасюк). Мшдшашя при цьому фактично досягаеться за рахунок замши системи булевих екшпалентпими (вЦносно одержуваних результатов), але небулевими математнчними моделями з подальшим урахуванням особливостей Ух апаратноУ реалпац'и.

Розвитком цього напрямку е нодалыиа формал^защя пщходу до мшмпацп булевих формул шляхом екя1 валентного Ух подання многочленами найкрашого наближення за системою функт'й, що сам! яв-ляють собою модедп динам1'ки лопчного стану.

Другий роздил присвячено розробт' основ теор!У розрядних функшй. Введено первинне понятгя простих розрядних функшй, ви-значено Ух основш властивост!, наведет' приклади практичного засто-сування. На основ! простих розрядних функт'й визначено склад}» розрядш функт'У (СРФ), доведено Ух властивосп. Виршено проблему ортогональност! систем СРФ.

Функцн, як1 визначаготься рекурентно, як 1к(т) = 11(2ыт), де т -незалежна змпша, а 1,(т) задаеться умовою

0 при те[0,~),

1 при те[^,1),

назван! простими розрядними функщ'ямм. Доведен! властивосп лшШ-ноУ незалежност'1, впорядкованост!, швар!антносгп щодо пщнесення в ступшь, ¡нверсност! щодо зворотнього аргументу та !нш!. Показано, що в лшйному д!йсному простор! система простих розрядних функ-цж не е повною.

Введению понять с клади их розрядних функцш передуе визна-чення ряду термшш, що е запозиченнями [ розвитком понять булевоТ алгебри, зокрема це стосусться понять параметричноТ булевоТ змшноТ Я(и, V, ..., \у) та параметричноТ булево» функци g [с]о(и, V,..., w), <][(и, V, ..., \у), ..., V, ..., №), Я 1м(и, V, №)]. Вщповадно 3 НИМИ ВИ-значеннями просп розрядш функци квал1ф1куються, як булев! змшш. Тод1 складною розрядною функщею «¡>(т) названо параметричну булеву функщю, для якоТ набором параметричних булевих змшних с множима простих розрядних функцШ: ф(т) = <р[ 10(т), 1,(т), 12(т),1„(т) Для породження конкретних систем скпадних розрядних функшй роз-глядаються оператори кон'юнкци, диз'юнкцп, ГПрса, Шеффера, сума за модулем 2, р1внозначшсть, шверс1я суми за модулем 2, ¡нверая р1в-нозначноеп. Впорядкування С РФ здшснюсться за системами Пел1, Адамара! Хармута.

Дня кожно'Т з означених систем СРФ запропоновано конструктив-ш методи визначення, оформлеш у вигляд! групових оператор1в над простими розрядними функцшми, доведено теореми мультишпкатив-ност1, двоТстосп, тотожност1, а також одержано рекурентш формули матричного вщображення систем СРФ.

Численними чисельннми експериментами з ортогонашзаци систем СРФ пщтверджена Тх лшшна незалежшсть 1 встановлена залежшсть результат ортогоналЬацн в1д способу впорядкування системи. Подо-лання Ц1'а залежносп забезпечуегься шляхом розробки методологи 5\-ортогонального доповнення. Показано, що результата бюртогоналпа-ци кожноТ з систем СРФ, впорядкованоТ р1зними способами, е однако-вими (з урахуванням впорядкування). Для кожноТ з систем СРФ винай-дено рекурентш формули матриць воображения бюртогональних до-повнень, встановлено структуры! властивосп таких матриць.

На основ! понятгя бюртогонального доповнення визначено по-

нятгя розрядноТ сполученост!. Оператор, за допомогою якого викону-сться перетворення розрядного сполучення, названо оператором роз-рядного перетворення. На основ!" рекурентних формул матриць воображения систем СРФ та Т'х бюртогональних доповнень винайдено ре-курентш формулн оператор'т розрядних перетворень в матричному вигляд! для кожно! з розглянутих систем.

В третьому роздин введен! понятгя розрядного скалярного добутку, розрядноТ норми та розрядноТ метрики. Визиачеш Тх основш власти воет!. На основ! розрядного скалярного добутку введено понят-тя розрядного простору, а також визначеш його основ1 властивост!.

Поняття розрядного скалярного добутку ^Х • У^ елемент!'в X та У вводиться, як окремий випадок загалыгого поняття скалярного добутку у лппйному векторному простор! за допомогою матриць розрядного перетворення П[а] таким чином, шо

{Х.у) = (хТ-П[а].у).

Математична коректн!сть цього визначення обумовлена тим, що матрищ" П[а] за побудовою с симетри'шими I позитивно визначеними, як це I вимагасться для скалярного добутку. В силу вщповщносп за-гальному визначенню, розрядний скалярний добуток мае вс! властивост! притаманш скалярним добуткам взагал!.

На основ! розрядного скалярного добутку можна визначити поняття ортогональности елементи X та У, як! не е нульовими або то-тожними, називаються ортогоналышми в розрядному розумшш тод!, коли для них виконуеться умова

(Х-¥}=(ХТ-П[а].у)=0.

У шдповщност! з цим визначенням вс! системи СРФ е ортого-нальними за побудовою.

Формальне поширення понятгя розрядного скалярного добутку на ниш, шдмшш вщ векторних види лшшних простор!в, можливе в ¡н-

тегральнш форм!:

(х(т),у(т))= |П(а,т)х(т)у(т)ск,

v

де П(а,т) - ядро вщповщного ¡нтегрального перетворення. Це визна-чення е в1рним для рвних вндш простор1в, але вимагае використову-вати ¡нше, аш'ж Р1манове, поняття ¡нтегралу.

Поняття розрядноТ норм и ((Щ елемента X вводиться на осно-bí поняття розрядного скалярного добутку насгупним чином:

Доведено, що для такого внзначення виконуються bcí умови та влас-тивост!, яю е необхщними i достатнши,

щоб ((х)) можна було визна-ти нормою в загальному розумшни Доведено також, що системи СРФ е нормованими вщносно розрядних норм.

Чисельними експериментами з разними обчислюваними функщ-ями на штервалах Ух визначення встановлено ¡снування границ1 роз-рядноУ норми при спрямувашй а в иескшчешсть. Цей факт дае мож-лив1сть в подальшому виконувати оцшку tohhoctí математичних моделей без обрахування оценки залишкового члену ряду.

а л

Спираючись на поняття розрядноУ норми для елеменпв X та Y введено функщю

p(X,Y)^(X-Y)},

стссовно якоТ доведено виконання основних умов i властивостей, нел л

обхщних i достатшх для того, щоб p(X,Y) можна було визнати метрикою в загальноматематичному розумшш цього термшу.

Вщповщно з ¡нтегральним поширенням поняття розрядного скалярного добутку виконусться ¡нтегральне розширення понять розрядноУ норми та розрядноУ метрики.

Визначення лонятгятермшу "розрядний прост1р" даеться наступ-т . .

ним чином. Нехай Ь2 е лпийний просп'р класт еквталентносн дшс-них функш'й з штегрованим на вщр1зку [0, Т] квадратом. Формально видшимо тдпроспр простору елементами якого е клас еквталент-носп' лининоТ оболонки иеск!нченовим|'рноТ системи СРФ. Цей шдпро-снр, який, вочевидь, е також лшшним простором, названо розрядним простором 9?

т

Норма, яка використовуеться для визначення Ь2 с класичною се-редньоквадратичною нормою, I може бути представлена, як окремий випадок елштичних норм з ядром перетворення, що тотожно дор1внюе одиницк Для ш'дкреслення цього факту використовуемо вщмшне означения Тод|" лнишшй просп'р клаа'в еквшалентносп дшсних фу-нкиш з ¡нтегрованим на вщр!зку [0, Т] квадратом ]' з елттичною нормою, ядро перетворення яко'1 П вщмшне в1ц единичного, означасться

1^2(П) • 3 цього боку розрядний просп'р повинен розглядатись, як про-

• т

спр з елттичною нормою 312(п) •

Виходячи з теореми про екв!валентн!'сть норм стверджуегься, що

т

збжисть послщовностей в простор! Ь2(Ц) еюивалентно виконусгься за будь-якою з обраних елштичних норм.

т

Перехщ вщ несюнченовим1'рного простору Ь2(п)Д° скшченови-м!рного векторного простору вщображаегься переходом вщ простору Я^п) до р^щ.

В четвертому роздал дисертацп викладеш результати, яш скла-дають теоретичне пщгрунтя спектральних моделей динамжи лопч-них сташв ВКС. Визначено, що розрядний проспр е нормованим простором, а тому метричним простором. Показано, що в розрядному простор! виконуються основш загальш властивосп норм, з чого ви-ходить можлив1*сть довести неперсрвт'сть розрядного скалярного до-бутку, що й виконано у вщповщнш теорем!. В свою чергу з неперер-

вноси розрядного скалярного добутку виходить, що ряди в розрядно-му простор! припускають почленне множення не тьпьки на сшл множники, але й на елементи простору. Доведено, що для ряд1в, як] мають скшчену границю \ зб1гаються до неТ, виконуеться влаепдасть зб|'жност1 скалярного добутку ряду I елемента простору до гранищ, яка визначасться скалярним добутком границ! ряду на той самий еле-мент розрядного простору.

Таким чином, е обгрунтованим використання для розрядного простору понять послщовносп, границ!, ряду, частковоУ суми ряду та шших, як! е неодмшними для коректноУ постановки задачГпобудови спектрально! математичноУ модел! в загальновизначеному розумшш цього понятгя.

Наведен! результат» також забезпечують можлив|'сть коректного використання в ¡дом их положень загальноУ теорГУ ряд ¡в Фур'е стосовно розрядного простору, а також постановку 1 розв'язання в ньому задач! найкращого наближення, що виглядае наступним чином.

Нехай р2(п)- розрядний проспр. Нехай також задана система СРФ з ш лшшно незалежних елемент ф,, ф2, ..., фш, а також еле-мент V е рцп). Потр!бно вщнайти лшшну комбшащю

с,ф, +- с2ф2 +... + Стфт,

яка забезпечуе найкраще наближення элемента У в простор! р$(п)> тобто забезпечуе мшшум виразу

({У-(С1ф1+С2ф2+-+Стфт))), або в розгорнутому ВИГЛЯД!

= (^-ХСкфк>П-С¥'-1Скфк) к=1 к=1 вщзмшнихС), С2,... Сге.

Осюльки система СРФ в розрядному простор'1 е ортогональною системою елементт, нетотожних нулю, тому

фк#0, .^к к~ 1,2, 3, ..., т.)

Тодп

Мннмум цього в и разу забезпечусгься при умов! с

Числа С\, виначет за шею формулою, мають назву коефвденлв Фур'е елемента V в розрядному простор! р™(П)-

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

со к=1

де Ск- коефвденти Фур'е, називаеться рядом Фур'е в розрядному про-

А

стор!, а найкраще наближення елемента У забезпечують часгков» суми

ш

Зш= ЕСкФк-к=1

Крш того, виконуегься умова р!вном!рност! наближення

N№4

яка дае можлив^сть теоретично1 оцшки точное« наближення.

1ншими результатами застосування загальноТ теорн ряд^в Фур'е до розрядних простор! в визнано наступне:

1. Коефвденти Фур'е елемента У в системах СРФ прямують до нуля при спрямувашп Тх номер!в в нескшчешсть.

л

2. Ряд Фур'е елемента У зб^гаеться до нього тод!! т!льки то-Д1, коли виконуеггься р!вшсть

яка е р!вн1стю Парсеваля в розрядному простор!. Р1вшсть Парсеваля може використовуватись, як контрольне сш'ввГдношення оцшки в^р-ност! обчислення коефщ1ент)с Фур'е.

3. Для того, щоб задана система СРФ була повною в розрядному простор!, необхщною 1 достатньою е умова виконання р!вкост1 Парсеваля для будь-якого елементу цього простору.

4. Якщо система СРФ розрядного простору повна, то еле-мент У цього простору, вс1 коефМенти Фур'е якого дор1внюють нулю, сам дор1вшое нулю. Для двох елементш розрядного простору з по-парноУ р|'вност! м1ж собою вшповшних коефадешчв Фур'е за повною системою СРФ виходить р'шшсть самих елементш. Тим самим забез-печуеться едишсть розкладання ел смени в розрядного простору в ряд Фур'е за системами СРФ.

В п'ятому роздм викладеш результате розробки алгоритм1в швидких спектральних перетворень для р1зних систем СРФ. Основ-ним недолком обчислення спектру безпосередньо за формулами дис-кретноТ' трансформацн Фур'е визнаеться значний обсяг обчислень, який ощнюеться, як Н2 (де N - розм1р виборки даних). Спираючись на вщом! результата в теорн побудовн швидких алгорнтмш та вщпо-вщно до прийнятоТ методики матрично-векторного викладення мате-р1алу констатовано, що швидга перетворення здшсненш в тих випад-ках, коли можливо здшснити факторизащю матриц! розрядного перетворення. Кшьюсть утворюваних при цьому матриць-ствмножниюв, визначаеться кшькгстю простих множншав, на яю розкладаеться число N. Чим бшьше таких множник1в, тим просгпша стуктура матриць-сшвмножниюв, 1, вщпошдно, тим проспшими е апгоритми перетворення. 3 цих М!-ркувань найпридатшшими е величини N = 2а. (Окрш того, в цьому випадку тополопчний граф мае високий стушнь регу-

лярносп, що надзвичайно важливо для апаратноТ реал1зац!У у пигляд1 ВКС.) В загальному випааку вщповщний граф алгоритму складаегься з а каскадов перетворения, кожен з яких мае 2" вушв, поеднаних м/ж собою плками. Кожен вузол графу виповщае оператору алгебраУчно-го додавання двох величин (у випадку, коли до вузла надходить дв! плки), або пустому оператору (коли до вузла надходить одна плка). Встановлено, що множники матриць розрядних перетворень, як5 е ре-гулярними, також мають регулярну структуру 1 можуть бути визначеш за рекурентними формулами. Визначено методику, за якою кожш'й матриш-мпожнику ставиться у вщповщшсть фаф каскаду алгоритму швидкого перетворення. Показано, що алгоритми прямого та оберне-ного перетворень в тополопчному план! е тотожними. Ух вщмшшсть полягас в конкретному гиги операцн алгебраУчного додавання (для прямого перетворення це в!д'емний тип, а для оберненого—додатнш).

Наведено приклади алгоритмов, як\ вщповщають р!зним способам факторизащУ матриць перетворення.

Для швидких алгоритлпв визначено абсолютну оцжку к1лькост1 виконуваних операцш алгебраУчного додавання МГж1= а-Ы/2. На приклад! кон'юнкгивноУ системи розглянуто методику вщносноУ оц!нки ефективност! (за кщьюспо операцш) швидких алгоритмов у сшвстав-ленн! з звичайними (нешвидкими) алгоритмами у базис! СРФ.

Визначено, що необхщна кщьк1сть операцш алгебраУчного додавання для прямого розрядного перетворення з безпосередшм викори-

Т -I

станням оберненоУ матриц! [ <3А [а] ] взагаш визначаеться величиною

М5,от=(За - 2"). Введено асимптотичну оцшку вщносноУ ефективност! атгоритм1в швидких перетворень, як границ! в¡дношения двох змш-их М5|ол, та М^, коли а спрямоване в нескшчешсть. Доведено, що ця оцшка мае характер показниковоУ функцн з основою, большою за оди-ницю, а саме:

•i* I

20

Mslwv _ ,r (3

«-.«о Mfaa ^

тобто, асимптотично ефектившсть швидких алгоритм1в несюнчено перевищуе ефектившсть звичайних алгоритмов розрядних перетво-рень. Осюльки в тополопчному план« алгоритми прямого та оберне-ного перетворень тотожш, оспльки все вищевикладене с Bipinra i для асимптотично"/ оценки ефективност1 швидких алгоритм!в обернених спектральних перетворень в базисах СРФ.

Onpi4 визначення ош'нки власноУ ефективностт алгоритмш швидких перетворень в базисах СРФ, виконано пор!вняльну оцшку ефек-тивност1 вщносно швидких алгоритмт спектральних перетворнь в ш-ших, шжсистеми СРФ, класах функцш, зокрема в oaci двшково-орто-гональних функцш Волша, як найближчому до класу СРФ за веши показниками, досить поширеному та достатньо вивченому, в тому чнел! i в пор^внянш з швидкими трансформац1ямн Фур'е. В'щомо, що ефектившсть швидких перетворень Волша за юльюстю операций ап-

гебраГчного додавання мае оцшку Mwo!= N-log2N. Показано, що

.. Mwo, _ lim ---2.

Таким чином, асимптотично, ощнка ефективносп швидких ал-горитм1в в базис! СРФ перевищуе оцшку ефективноеп швидких ал-горитм1в Волша в два рази. Аналопчний результат отримано вщнос-но алгоритм ¡в швидкоТ трансформацп Фур'е.

Шостий роздм присвячено розробщ метод1в анал1зу та синтезу ВКС спещатзованих пристро\'в автоматики та обчислювальноТ техш-ки. В ньому, по-перше, викладено ochobhI положения апаратноУ реаль зацн генераторш базисних функцш, тобто функцш систем СРФ. Подруге, викладено методику синтезу функцюнальних перетворювач^в i, по-трете, дослщжено особливост1 та розроблено метод синтезу при-строУв для виконання швидких перетворень в базиа СРФ.

Побудова генератор1в базисних функцш (ГБФ) базуеться на способах (засобах генераци просгнх розрядних функцш та реал!зацп ло-пчних операцш. Безпосередньо з визначення простих розрядних функцш виходить повне сшвпадання графшв змши в час! кожноТ к-01 просто» розрядноТ функцн 31 змшою в час1 стану одиничного виходу к-го розряду двшкового л1чильника. Таким чином, для генераци простих розрядних функцш можна використовувати звичайний посшдов-ний двшковий л1чильник на а розрядш. Щодо реашзацн в двшковш систем 1" лопчних. операций, як1 визначають конкретний вигляд СРФ, то це питания не викликае ускладнень, оскшьки ¡снуе достатня к!ль-шсть схем 1 техтчних пристроТв, як! реагизують щ операцн. Власне методика побудови ГБФ полягае в наступному:

- синтезуеться необхщна, або обираеться в ¡дом а схема двшкового л1чильника на а разряд!в;

- л1'чильний вхщ л1'чильника з'еднуеться з виходом генератора олорних !мпульс!в;

- синтезуеться необхшна, або обираеться вщома схема ре-ашацп лопчноТ операцн, яка визначае систему СРФ;

- синтезуеться необхадна, або обираеться вщома схема кому-тацп повного перебору вах можливих комбшацш виконання визна-ченоТ лопчноТ операц'п над_множнною з а вход!в;

- виконуегься з'еднання виход!в к-х розряд1'в двШкового Л1-чильника з вщповщними .¡-ми входами схеми комутацп;

- виходи схеми комутац!¥ с виходами генератора базисних функцш.

Д1'ев!сть методики шюстровано прикладами розроблених комбь нацшних схем генератор!в.

До переваг викладеноТ методики слщ взнести те,що при незмш-ному способ! упорядкування системи СРФ структура функционально!" схеми ГБФ е швар!антною до змши конкретного типу СРФ.

При розробщ методики синтезу схем функшональних перетворю-вач1в виходимо з того, що, по-перше, нелшшна залежшсть, яку нале-жить реал1зувати, може бути подана у вигляд1 частковоУ суми ряду за деякою базисного системою, якою обрано систему СРФ, по-друге, значения спектральних коефвденлв вважаються вщомими.

Тод1 методика синтезу перетворювача е по своУй суп' методикою реал1защ1 сталих коефЫенпв, як1 керовано подаються на вхщ сума-тора. Законом управлшня, який керуе дозволом/забороною пропуску значения З-го коефвдента, е вщпов'щна функщя системи СРФ. В залежност! вщ способу реалващУ значень коефвден^в, схема перетворювача може мати бйльший або менший ревень ушверсальносп. В тому випадку, коли значения коефвдеттв реал1зоваш апаратним шляхом, що е найбшьш природнш для комбшацшних схем, маемо суто розрядну схему, для пщтвердження характеристик якоТ в повнш М1р! застосовуються методи анализу, викладсш в попередшх роздшах роботи.

Наведено приклади розроблених схем перетворювач1в.

Дослщжено особливост! побудови схем пристроТв швидкого пе-ретворення в базис! СРФ. Осктьки алгоритми швидких перетворень належать до алгоритм ¡в конвейерного типу, для яких загальш питания побудови обчислювальних пристроУв розроблеш в достатшй для нашого випадку М]'р1, залишасться потр1бним визначити схему каскаду перетворення. Ця схема вщповщае деякш матрищ Гуда, що е одним з множниюв факторизованоУ матриц! розрядного перетворення. (МЬк шшим, на цш пщстав1 зроблено висновок, що найзручшшими для розв'язання задач! побудови пристрою швидкого спектрального перетворення в базис! СРФ е так! системи, для яких юнуе подання матриць перетворення у вигляд1 а-кратного ступеню матриц! Гуда). Власне схема каскаду реагпзуе скалярний добуток строки матриш Гуда на вектор значень попереднього перетворення. Виходячи з особли-востей матриць Гуда, визначено, що елементом схеми, який реагпзуе

обчислення значения ¡-го компонента вектора к-го каскаду перетво-рення можуть бути: 1) линя комутацн на лопчний нуль, 2) линя комутацн безпосередньо на один з виход1в попереднього каскаду перетво-рення, 3) лш|'я комутацн на один з виходш попереднього каскаду пе-ретворення через ¡нвертор, 4) лш!я комутацн, вхщ якоТ пщключено на вихщ багатовходового суматора, кожний з ВХОД1В якого, в свою чергу шдключено або безпосередньо на один з виход1в попереднього каскаду, або через ¡нвертор. На основ! виконаних дослщжень з'ясовано, що конкретний тип елемента схеми знаходиться у вщповадносп з\ значениям параметру, який е сумою модул!в слсмепп'в строки матриц! каскаду перетворення. Цей параметр прийнято за критерш вибору схемного елемеиту для вщповщноТ строки каскаду перетворення. Таким чином, за вщомими матрицями-сп!вмножниками факторизованоТ матриц! розрядного перетворення обраноТ системи СРФ досить формально визначасться структура, склад 1 тополог!я схеми пристрою швид-кого перетворення для обрахувння дискретного СРФ-спектру детер-АпнованоТ двшковоТ послщовносп".

ЗАГАЛЬШ ВИСНОВКИ ПО РОБОТ1

1. Актуальн!сть постановки i розв'язання задач! розробки методологи, метод!в 1 засоб1"в укрупненого (в пор1внянш з булевою алгеброю) математичного подання множини лопчних стан!в складних тех-шчних об'еютв взагал1 ! великих комбшащйних схем (ВКС) зокрема обумовлена потребами сучасно! техн!ки 1 технолога створення засо-б!в обробки ! перетворення шформацп. До класу великих в!днесено комбшацшш схеми, лопчн! стани яких описуються булевими функц!-ями такого р!вня складноси, для якого виршкмшя задач! мнпмнзаци нотребуе залучення ресурсов, що перевищують наявн!. Якщо прийня-ти до уваги, що проблема мнпьпзацн булевих функций в булевой алгебр! залишаеться нерозв'язаною в загальному вигляд! 1 не ¡снуе б!льш ефективного алгоритму н вир!шення, ашж алгоритм перебору,

2а

складшсть якого мае порядок 2 , де а - число незалежних змшних, то навггь для невеликих а межа використання допустимих можливо-стей досягасться досить швидко. Обгрунтовано постановку задач! формал1зацн опису динамки лопчних стан!в ВКС у вигляд1 задач'1 найкращого наближення по критер1ю мшшума середньоквадратично-го вщхилення.

2. Розроблеш основы! теоретичш положения апарату складних розрядних функцш: введен! поняття простих розрядних функцш, що являють собою дв1йков! функц!У змши стану единичного виходу в1д-повщного розряду двшкового л!чнльника 1 е природними для опису змши стану дискретних об'екп'в взагал1"; визначено основш власти-вост! таких функц!й; розглянуто можлив1Сть побудови математичноТ модел1 детермшованого процесу у вигляд! лшшного многочлена за простими розрядними функщями; з'ясовано, що система простих розрядних функцш не е повною в липйкому простор!, а тому, в загально-му випадку, не е достатньою для побудови лшшноТ модель яка може забезпечити заданий р!вень точност! наближення; для розв'язання шеУ проблеми запропоновано системи складних розрядних функцш (СРФ), як1 е похцшими вщ застосування визначених оператор!в буле-воУ алгебри над множиною простих розрядних функцш. Системи СРФ б!льшою м1рою вщображають динам1ку змш лопчних стан!в ВКС шж будь-як! !нш! базиси, як! зараз вщом!, 1 добре пщходять для дискрети-зац!'1 на довшьному скшченому ¡нтервал! змши незалежного аргумента, якщо крок його квантування е р!вном!рним, а частота квантування визначаегься теоремою Котельникова. За цих умов визначен! основш операторы властивост! СРФ. Показано, що системи СРФ е лЫйно незалежними та впорядкованими, а в!дтак можугь слугувати базисом наближення.

3. Побудова многочлена найкращого наближення по критерию м1-ш'мума середньоквадратичного в!дхилення спираеться на припущен-

ня про ортогоналыпсть базису наближення. Системи СРФ не е почат-ково ортогональними. Показано, що Ух ортогоналпаш'я методом Гра-ма-Шмщта призводить в загальному випадку до порушення елемен-тами системи обмеження на область допустимих значень у вигляд! множини {0, 1}. Кр1м того, результата ортогонащзацГУ суттево зале-жать в]д способу впорядкування системи СРФ 1 для знаходження мо-жливо ¡снуючоУ прийнятноУ ортогонально! системи необхщно багато-разово виконувати процедуру ортогонащзацп для кожного N (де N -значения размгрност1 системи СРФ). При реалышх значениях N кшь-юсть варшпв ортогонал!зацп, з яких треба зробити вибф, неприпус-тимо велика (N1). За викладених причин ортогонал1зашя систем СРФ не е прийнятною для побудови базису наближення в нашому випадку.

4. За альтернативу ортогонал!зацн пропонусться визначення 1 методика побудови системи, що е б'юртогонапьним доповненням до системи СРФ. Елементи такоУ системи мають властившть бюртогональ-ност1 у вщношенш до елемешчв системи СРФ 1 навпаки. Показано, що в евклщовому простор! побудова бюртогонапьного доповнення в загальному випадку зводиться до розв'язання задач! обернення тран-спонованоУ матриц! елемештв системи СРФ. Для конкретних систем СРФ (кон'юнкгивних, диз'юнктивних, адитивних 1 т.п.) визначено, що правило впорядкування вихщноУ системи СРФ впливае тшьки на упо-рядкування елемент1В бюртогоналыюго доповнення систем СРФ, але на вплвае на Ух вигляд. При цьому власне система СРФ залишаеться незмшною. Тим самим доласться основний недол1К безпосередньоУ ортогонал^зашУ.

5. Розвинуте поняття оператора розрядного перетворення в не-скшченовимфному I скщченовимфному просторах. Винайдеш залеж-ност'|, яю пов'язують матричш оператори розрядного перетворення з магрицями систем СРФ та Ух бюртогонапьних доповнень. Встановле-но, що матриц! розрядного перетворення мають рекуррентну струк-

туру 1 можуть бути побудован! явним чином по рекурентним формулам, як1 визначет для кожноТ системи СРФ. Показано, що матриц! розрядного перетворення е симетричними 1 позитивно визначеними, що дае можливють на Ух основ! ввести розрядний скалярний добуток, для якого виконуються вс1 загальш властивост1 скалярного добутку. За допомогою введеного розрядного скалярного добутку формально визначено розрядну норму 1 розрядну метрику, для яких виконуються вс! вщповщш загальн1* властивостт та сш'ввщношення. На цьому ш'д-грунт1 коректним е використання результата, вщомих !з загальноУ теор1У рядт Фур'е, при розв'язанш задач! побудови математичноУ мо-дел! динамки лопчних стан ¡в ВКС в базис! СРФ.

6. Показано, що дискретна спектральна модель динамки лопчних стан ¡в БКС в евюн'довому простор! з розрядним скалярным до-бутком визначаеться у вигляд! узагапьненого перетворення Фур'е ¡, вщповщно, для неУ виконуються загальн! властивост! ряд!в Фур'е та Ух часткових сум. Показано, що ¡снують класи задач, для яких побу-дова спектрально'! модел! динам!ки стан!в ВКС автоматично виконуе и мшшвацно, незалежно вщ складносп' задач!. Для моделей, як! вщ-повщають аналггичним функц!ональним операторам, встановлено !с-нування граничних значень розрядних норм, що спрощуе оцшку по-гривносп спектрапьних моделей вщносно ошнки за залишковим членом, а разом з оцшкою швидкост! зб|гання дае можливють априорного прийнятгя ршення про доцшьшсгь прнйнятгя або вшхиленкя СРФ-моделей.

7. Для обчислення значень коеф!циент!в спектральних моделей розроблено методи ! алгоритми швидких перетворень. Зокрема показано, що процедура факторизаци транспонованоУ матриц! бюртого-нального доповнення дае можлив1Сть побудувати швидю алгоритми, для яких асимптотична оцшка виграшу по к!лькост1 операц!й у сшв-ставленн! 31 звичайними алгоритмами мае вигляд показниковоУ за-

лежност'1 з основою, бшьшою в'|д одинищ. Пор1вняння по числу опе-раш'й з алгоритмами швидких перетворень Фур'е та Волша показуе дворазову перевагу систем СРФ.

8. На ochobí виконаних теоретичных дослщжень розроблено:

- алгоритм« та програми розрахування последobhoctí значень розрядних норм, я к i дають можлив1сть проводити попередне визна-чення граничних характеристик функцюнальних оператор!в i створи-ти на IX ochobí базу критернв для прийняття ранения про доцшьшсть розв'язання задач*1 синтезу комбЫацшноУ схеми в базис» СРФ;

- алгоритмы i програми сбрахування параметр1в спектраль-них моделей, hk¡ спрощують проектування комбшацшних схем при-строГв обробки та перетворення двШкових поондовностей (сигнаш'в);

- методику анагизу СРФ-спектр1*в ВКС, яка дае можлив1'сть оцшити Тх шструментальну погршшсть i виключити несуттев1 спектрально складов1, здшснюючи, там самим, спектральну мш1м»защю ВКС;

- методику синтезу комбшацшних схем в базис» СРФ, яка за-безпечуе простоту i однорщшсть схемных рпнень, можлив1'сть вико-нання оцшки i'x tomhoctí за доступними критер1*ями; ряд конкретних схемних pimeub спещал^зованих пристроТв обробки i перетворення ¡нформацн.

OCHOBHI РОБОТИ, ОПУБЛ1КОВАН1 ПО TEMI ДИСЕРТАЩ!

(наведен! мовою орипналу)

1.Moxop В.В. Основы теории синтеза вычислительных устройств в базисе разрядных функций. - К.: Наук.думка, 1997.-192 с.

2.Мохор В.В. Применение Т-преобразования к разрядно-анапо-говому моделированию функций II Электронное моделирование. -1982,- №6. -С. 94-95.

3.Мохор В.В. Построение разрядных математических моделей

нелинейных зависимостей методом обратного разрядного отображения// Моделирование электрофизических и электроэнергетических систем и устройств. - К.: Наук.думка. - 1983. - с. 162-169.

4.Мохор В.В. Приближенная оценка числа разрядных дискрет при решении динамических задач в области РД-преобразований // Гибридные вычислительные машины и комплексы. - К.: Наук, думка, 1986. - Вып 9. - с. 6-9.

5.Мохор В.В., Литвиненко В.В., Труш А.И. Два критерия сходимости разрядных моделей // Гибридные вычислительные машины и комплексы. - К.: Наук, думка, 1988. - Вып 11.-е. 84-86.

6.Мохор В.В., Давыденко А.Н. Формирование линейных разрядных моделей поданным полнофакторных экспериментов // Электронное моделирование. - 1989.- № 1. - с. 88-91.

7.Мохор В.В., Корхмазов Г.С. Разрядный метод решения нелинейных уравнений// Гибридные вычислительные машины и комплексы; - К. Наук, думка, 1989. - Вып. 12.- с. 11-13.

8.Мохор В.В., Труш А.И. Зависимость качества разрядных моделей от значения используемых систем счисления // Математическое и электронное моделирование в информационном обеспечении технических систем. - К.: Изд-во КНИГА. 1989. с. 28-34.

9.Мохор В.В., Оленич К.И. Построение минимизированных раз-рядно-дифференциальных математических моделей // Математическое и электронное моделирование в информационном обеспечении технических систем. - К.: Изд-во КНИГА. 1989. с. 39-44.

Ю.Мохор В.В., Давыденко А.Н., Кравец С.Ю. Свойства систем базисных функций, построенных на основе простых разрядных функций// Известия ВУЗов. Сер. Радиоэлектроника. - 1995.- № 11-12. - с. 58-62.

П.Мохор В.В., Давыденко А.Н., Кравец С.Ю. Об особенностях использования различных логических базисов при построении мате-

матических моделей нелинейных объектов на основе сложных разрядных функций // Электронное моделирование. - 1995.- № 2. - с. 75-79.

12.Мохор В.В. Простые разрядные функции, их свойства и приложения в задачах аппроксимации// Збфник наукових праць 1нститу-ту проблем моделювання в енергетицк - Льв1в: "Свгг". 1998. Вип.4.-с. 118-126.

13. Мохор В.В. Основные положения теории синтеза цифровых устройств в базисах сложних разрядных функций// Зб1*рник наукових праць 1нституту проблем моделювання в енергетиць - Львт: "Свгг". 1998. Вип.4.-с. 132-137.

14. Мохор В.В. Асимтотическая оценка эффективности алгоритмов быстрых преобразований в базисе конъюнктивных сложных разрядных функций// Збфник наукових праць 1нституту проблем моделювання в енергетищ. - Черкаси: Вид-во 1нст. управл. бпнес. 1998. Вип.5.- с. 19-21.

15. . Мохор В.В. Построение цифровых функциональных преобразователей в базисе сложных разрядных функций// Зб1рник наукових праць 1нсти-туту проблем моделювання в енергетищ. - Черкаси: Вид-во Гнет, управл. б1знес. 1998. Вип.5.- с. 13-18.

16. A.c. № 1564618 СССР, MKHG 06 F 7/556. Устройство для вычисления логарифмов/ А.Н.Давыденко, В.В.Литвиненко, В.В.Мохор, К.И.Оленич, К.И.Рогозин. - № 4402248; Заявлено 04.04.88; Опубл. 15.05.90. Бюл. № 18.

17.А.С. № 1674113 СССР, МКИ G 06 F 7/556. Устройство для вычисления функции у=ех, у=хга/ А.Н.Давыденко, В.В.Литвиненко, В.В.Мохор, К.И.Оленич, А.И.Труш. - № 4682924; Заявлено 30.03.89; Опубл. 30.08.91. Бюл. № 32.

18. A.c. № 1735845 СССР, МКИ G 06 F 7/548. Устройство для вычисления гиперболических функций y=sh(x) и y=ch(x)/ А.Н.Давыден-ко, В.ВЛитвиненко, В.В.Мохор, К.И.Оленич, А.И.Труш. - №4848087; Заявлено 09.07.90; Опубл. 23.05.92. Бюл. № 19

30

АНОТАЦ11

Мохор В.В. Методи дослщження великих комбшацшних схем на основ! спектральних моделей в базисах складних розрядных функ-ц!й. - Рукопис.

Дисерташя на здобутгя вченого ступеня доктора техн!чних наук по спещальносп 01.05.02 - математичне моделювання та обчислю-вальш методы.

Дисерташя присвячена питаниям проектування складних техшч-них пристроУв (на приклад! комб!нац!йних схем великого розм!ру). В робой розвинуто новий науковий напрямок в математичному моде-люванш', побудований на концепцГГ спектрального опису детермшо-ваних процеав зм!ни лопчного стану об'екта. Встановлено, що введения класу складних розрядних функщй дозволяв реал!зувати ефек-тивний процес комп'ютерного досл!дження та проектування техшч-них об'ект!в з багатьма входами, виходами 1 перехресними зв'язками. Запропонован! чиселын" методи синтезу макромоделей таких пристроУв та Ух спектрального анал!зу, висока ефектившстъ яких обгрунтова-на теоретично I шдтверджена на практищ. Основн! результата знайшли промислове застосування в проектуванш нових тип!в спеща-лЬованих пристроУв перетворення шформаци з покращеними техшч-ними характеристиками. ~

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

Мохор В.В. Методы исследования больших комбинационных схем на основе спектральных моделей в базисах сложных разрядных функций. - Рукопись.

Диссертация на соискание ученой степени доктора технических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы.

Дисертация посвящена вопросам проектирования сложных тех-

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

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

Mokhor V.V. Methods for large combinatory logic scheme investigation on the base of spectral models in basis of complex digit functions. -Manuscript.

Thesis for a doctor's degree by spesiality 01.05.02 - mathematical simulation and numerical methods. - The Institute of Simulation Problems in Pover of National Academi of Sciense of Ukraine, Kyiv, 1998.

The dissertation is developed to problem of complex engeneereng equipment design (by the example of a large combinatory logic schemes). New line of investigation in mathematical simulation is developed, which based on the conseption of enlarge spectral description for deterministic processes of logical unit status variation. It is obtained that introducing class, comlex digit function makes possible to realise effective computer-aided investigation and design of engeneereng units with multiple inputs,

outputs and criss-cross links. Numerical methods for macromodel synthsis and spectral analysis of those units are proposed. The high efficiency of these methods is theoretically justified and practically supported.

The main dissertation results have industrial application in esign of new kind of specific devices with improved technical characteristics for information transforms.

Key words: mathematical simulation, combinatory logic scheme, spectral analysis, synthesis, digit function, numerical methods.

Подписано до друку 26.11.98. Формат 60x84/1б.Патр друкарський. Офсетний друк. Ум.фарбовщб.9. Ум.друк.арк. 1.86. 0бл.-вид.арк.2,0 Тираж 100 прим. Замовлення № И ДСП. Вид № 45/IV

Видавншдво КМУЦА.

252058. КиТв-58, проспект Космонавта Комарова, 1.