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

- лшюгм^ний техн1чний ун1верситет укра1ни 1 * 0 "швський пол1ТЕХН1ЧНИй шститут"

-8 ОМ «96

На правах рукопису . удк 658.512.011.56:519.682.7

Б1ЛА Юр1й Миколайович

р03р0бка та д0сл1д1ення методiв трансэормацiк топологи друкованих плат в САПР

Спец1альн1сть 05.13.05 - Системи автоматизацП

проектування 8 техн1чних наук

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

КИ1В - 1996

Роботу виконано на кафедр! САПР НТУУ "КШ" та в НД1 "Вектор"

Науковий кер1вник:

доктор техн1чних наук,

професор

А. I.Петренко

0ф1ц1шп опоненти:

доктор техн1чних наук, професор

Ю.Ф.31ньковський

кандидат техн!чних наук,

професор

В.П.Гондюл

Ведуча орган1защя:

ВО "Електронмаш"

Захист в!дбудеться " 16 " вересня 1996 р. о /£год. в ауд. 412, корп. 12 на зас!данн1 спец1ал1зовано1 Ради Д.01.02.17 при Нац1ональному техн1чному ун1верситет1 Укращ: ("Ки1вський пол1техн1чний 1нститут") за адресою: 252056,1 м.Ки'1в-56, пр.Перемоги, 37, корпус 12.

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

3 дисертац!ею можна ознайомитися у б1бл!отец! ун1верситет

Автореферат роз1сланий "_"_1996 г.

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

спец1ал1зовано'1 Ради, кандидат техн!чних наук, професор

1. АНОТАЦШ

1.1. Мета роботи

Метою дисертац1йно1 роботи е роаробка та дослгдження метод1в трансформацП топологП друкованих ' плат (ДП) для покращення технолог1чних та електрнчних характеристик ДП, а також программа реал1зац1я гидспстеми трансформацП для ви-користання в САПР ДП.

1.2. Задач1, що виргшуються

Для досягнення поставлено! мети в. дисертащйн1й робот1 вир1шувалися так1 гадач1:

1. Находження подход/, який габезпечув виконання усього спектру необх1дних трансформац1й топологи ДП.

. 2,' Розробка рекурсивних алгоритм!в зсуву пров1дншав, усунення петхль, "д1агонал1зац15". топологи, зменшення к1ль-коот1 перех1дних отворив.

3. Розробка моделей "для виконання трзнп4г,рмац1Й тополог! 1 багатошарових друкованих.плат.

4. Розробка ' 1кструме1!тальних засобгв заданья трзнсфор-мащй.

5. Програмна ,реал1защя п1дсиотеьш трансформацП топологП для експлуатаци у склад1 САПР ДП на баз1 малих та персональних ЕОМ.

1.3. Положения, що захкщэться

Вир1шивши поставлен! в дисертащйтй робот1 задачу автор захищае:

1. Метод задания трансформаций топологи ДП за допомо-гою граматичних правил.

2. Структуру виконуючого механ1гму трансформаций - бу-дову адаптовано! машини. Тыор1нга.

3. Рекурсивн1 процедури зсуву пров1дник1в, . усунення '• пет1ль, -"диагонализацП" тополог!!, усунення зайвих пе-рвх1дних отворхв.

4. Принцип« .псбудови; 1нструментаи>них гасобхв та !х практичну реал1эац1и, а такс« реал^гацш виконуюча! системи трансформац!I.

2. ЗАГАЛЬНА ХАРАКТЕРИСТИКА ДИСЕРТАЦ1ЙН01 РОБОТИ

•2.1. Актуальн1сть роботи

В1домо, що. процес конструкторського проектування друко-ваних плат складаеться з к!лькох етатв. Головними етапами е: компоновка логiчних елемент1в у корпуси м!кросхем, розм!щення KopnyciB на поверхн1 ДП та трасировка з'еднань -синтез топологЯ ДП. В сучасних САПР ДП на завершальному етап1 синтезу тополог!'! застосовуються також i засоби ко-рекцП топологи, наприклад, у САПР ДП в!домих американських ф!рм Calay i Mentor Graphics.

Спочатку корекц!я тополог!í виконувалася т!льки з ц!ллю усунення так званих "вузьких Micub" - участюв порушень м!н!мально допустимого зазору м1ж елементами проводящего покриття ДП (площадками та пров!дниками). Така-корекц!я от-римала назву технолог!чних перетворень. Виконання технолог !чних перетворень дозволило спростити проектування за pá-хунок зниження вимог на етап! трасироьки, скоротити його строки та суттево здешевити виробництво ДП.завдяки зб!льшен-ню виходу придатних вироб1в.

Дал!, 1з зростанням iHTerpaui'i та зб1льшенням швидкодП компонент!в стало Тютр!бним виконувати коректировку тополо-ri'í, яка забезпечуе усунення прямих та гострих кут!в, л1кв!-дац1ю "т!ней", л1кв!дац1ю заивих перехШих отвор!в i яка скорочуе довжину з'еднань та к!льк!сть неоднор!дностей (стоньшень та деформац1й) i т.п. У цьому зв'язку виявилося актуальним находження тдходу для комплексного вир!шення пе-рел1чених задач, як! отримали.у дисертац1йн!й робот! загаль-ну формулiровку як задач! трансформацП тополог!!. 1снуюч! методи розв'язання задач! трансформацП тополог!i, як! основан! на евристичних алгоритмах, не забезпечують у багатьох випадках р!шення, як! задовольняють юнцевого користувача. Знаходження такого р1шення та застосування його в САПР скла-дае актуальну науково-техн!чну задачу.

2.2. Методи досл!дження

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

математики.

2.3. Наукова новизна

PiBHi модел! та методи трансформацп топологiï друкова-них плат розглянутг у роботах автор1в: Абрамова АЛ., Атаева Ю.Ю, EopofliHoï Е.В., Герасименко Е.П., Гринюса С. Л., Зйшяви-чюса В. А., Зюзз-на Ю.В., Каплана Л.М., Кота B.I., Миск1на В.В., Ойхмана Е.Г., Ф1нка Б.Л., Хомицького М.Г., Ясеницького .0.3. та imii. При розв'язанн! р1эних окремих задач трансформацп автори застосовують евристичн1 алгоритми, HKi не охоп-люються единим п1дходом.

Наукова новизна роботи полагав у сл1дуючому: . 1. Запропоновано синтаксичний (структурний) тдх1д для розв.'язання задач1 трансформацп топологП,'- який передбачав Bii6ip алфав1ту непох1дних элементов для зображення топологи та задания граматичних правил для виконання трансформащй;

2. Розроблено формализований опис виконуючого механ1зму трансформащй - адаптовано1 машини Тьюр1нга, яга призначена •до роботи, на р1зницю в1д клзсично! моделх, э двом1рними й багатошаровими зображеннями o6'sktîb. Також показано зв'язок Mix описоы роботи машини й описом трансформаций на piBHi граматичних правил.

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

2.4. Практична Щнн1сть та впровадження рззультат1в

Практична цГнн1сть дисертзвдйко! .роботи:

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

2. Розв'яэаЩ у рамках п1дсистеми частков1 задач! трансформацп топологп : л1чтпдацп зайвих перех1дних от-BopiB, усунення петт, "fliaroHaniaaiu'i" топологп, зсуву у вуэьких м1сцях пров1дник!Е в1д контактних площадок (КП) та перех1дних otbopîb (ПО) й "тдрззки" КП та ПО is завуженням пров1дника у мЮцях, де зсув проЕ1дника неможливий, та iHra;

3. Здобут! ршення Еикорисгат у пакет1 програм АРМ-ПЛАТ (комплекс ЛРМ2-01) та оистеьи САКТ-М (IEM PC), що

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

На цей час. программ засоби трансформац!! тополог! 1, як! були розроблен! в процес! виконання дисертац!йно! роботи, експлуатуються в 'Ки1вському об'еднанн! "Електронмаш", у Ки!в-ському державному КБ "Луч", ' !нститут! "АВТОМАТУГЛЕРОДПРОМ" (м.Конотоп), ПНИЭИ (м.Пенза), СКБ ВНИИМСО (м.бкатеринбург), та ряд! 1ниих орган!зац!й кра'1н СНД, як: використовують комплекс АРМ2-01 !з пакетом програм автоматизованого проектування друкованих плат АРМ-ПЛАТ або систему САКТ-М для 1ВМ РС..

2.5. Алробац1я роботи та публ1каи11

Головн! положения дисертац!йно! роботи допов!далися: на республ1канськ1й конференцП "Автоматизированные рабочие места и системы проектирования и контроля средств вычислительной техники", м. КиГв, жовтень 1985 р.; на щор!чн!й нау-ково-техн1чн1й конференцП "Автоматизация проектирования РЭА и ЭВА", м. Пенза, 1990, 1991 и 1992 рр.

Матер!али дисертац!йно1 роботи в!дбито в 7-ми друкованих працях.■

2.6. Структура та розм!р роботи

Дисертац!йна робота складаеться з вступу, трьох глав та висновку, як! викладен! на 145 стор1нках машинописного тексту та 1люстрован1 19 малюнками та 8 таблицями, списку л!-тератури й двох додатк!в.

У перш1й глав! дисертацшно! роботи дана розгорнута постановка задач!, виконаний анал1з застосованих метод!в трансформац!1 та виконана класиф!кац1я задач! трансформац!1 тополог!!, яка дозволяв в^днести П до класу задач розп1зна-вання образ!в ! застосувати новий (синтаксичний) п!дх!д для 11 розв'язання.

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

розв'язуються OKpeMi задач! трансформацП тополог!'!.- зсув групи пров1дник!в, усунення пет!ль, "д!агонал1зац1я" топологП, усунення зайвих ГО. Також у глав! наводиться формаль-ний опис структури виконуючого механ1зму трансформац1й - ма-шини Тьюр1нга, i наводиться процедура одержання опису функц1онування машини на основ! -гадания граматичних правил, як! описують трансформац!ю.

Третя глава присвячена программ 1й реал!зацП засоб1в задания та виконання трансформац!й.■ У Н1й розглянута структура п1дсистеми трансформацП тополог i'i САПР ДП, даний опис !нструментальних 3aco0iB задания трансформац!й та опис вико-нуючо! системи трансформацш. Описан! програмн! засоби були розроблен! в ход! виконання дисертац!йно! роботи для експлу-атацг1 в склад! САПР ДП на 6a3i малих (СМ 1420) i персональ-них (IBM PC) ЕОМ.

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

Додатки включають текста програм на !нструментальному язику задания трансформащй Матрикс i документа, як! Шдтверджують впровадження розроблених програмних засобгв на промислових п1дприемствах.

3. ГОЛОВНИЙ 3MICT РОБОТИ

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

. У запропонованих. paitiute Шдходах розглядалися, як правило, лиш OKpeMi випадк:г розв'язання зсдач! трансформацП топологП, наприклад, ■ виконання технолог!чних коректувань (технолог!чн! п^ретворення). . Алё i п цих випадках р!шення

мали обмежений характер: коректуванню п!длягали т!льки найб1льш прост1 конф1гурац11 друкованих елемент1в (КДЕ), як! складалися з невелико! кхлькост! елемент1в. Головн! труднощ! викликають виконання шукання 1 правильна трансформац!я конф!гурац!й, як! враховують усю фактичну р!зноман!тн1сть конф!гурац!к. Головним недолгом запропонованих ран!ше п!дход!в, на думку автора; е те , що в них не анал!зувалася структура з'еднань тополога! ДП. У дисертац!йн1й робот! для розв'язання поставлено! задач! був запропоноваиий синтаксич-ний (структурний) п!дх!д, який основуеться. на анал!э1 струк-тури образ!в ! базуеться на математичн!й теорП формальних граматик та вир!шуючих автомат!в. Даний п!дх!д дозволив правильно виконувати трансформацП КДЕ любо! складност!.

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

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

Кожна елементарна трансформац1я може бути записана у вигляд! правила постановки одн1е"! композицП елементарних п!добраз1в на м1сце друго!. 'Об'еднання сличенного алфав!ту елементарних п1добраэ1в. та ск1нченно1 к!лькост! правил • постановки, по суй, складае граматику, котра задае воображения множини вихОних образ1в у множину результуючих

Таким чином, застосування синтаксичиого лОходу для

-7- . ' ' .

розв'язання задач! трансформацы топологП ДП з позиц!й ма-тематично! теорп буде полягати у виконашЦ апдуючих двух етаШр: .

- !дентиф!кацп на топологи ДП непсшдних елеменИв !з попередньо обраного алфав!ту непох1дних елемент1в !. складан-ня опису тополог!!, тобто побудов! в!дпов!дно1 модел1 топо-логП;

- задания . в!дпов1дних граматик для знаходження та .трансформацп на модел1 необх!дних множин конф!гурац!й дру-кованих елемент!в.

Формальна граматика С визначаеться як четв!рка 6 = (Ут,Ун, Р, в) , Де Ут та - основний та допом!жний словники (алфав!ти) граматики б в!дпов!дно. Символ Р позначен ск!нченну множину правил виводу або правил постановки, як! позначаються Р , де с£ 1 $ - ланцожки (ком-позицП) символ!в !з У = Д/ти\/ц. Вказанним-правилом вико-•' нуеться зам!на ланцюжка Л -на ланцюжок р . Символ 3 ¿ЛГи початковий символ.

Основний словник 14 е словником непох1дних елемент!в (терм!нальних символ!в, елементарних п!добраз!в), з котрих будуються речення (образи) язйку, який породжений граматикою (? • Речення будуються у вигляд! ланцкшйв (або !нших компо-зицЩ-елементарних п1добраз!в, Допом1жний словник Уы е словником допом!жних символ1в, котр1 використовуються у про-цес! виводу ланцюжка поряд з терм!нальними символами, однак в!дсутн1 у ланцожках, як! е речениями язику. Язик образ!в, який породжений граматикою С , позначаеться Ь (&).

Правило пОстановга, яке мЮтить у л!в!й частин! почат-' ковий символ 2 , в!дкривае процес виводу. Завершения виводу. в!дбуваеться у результат! застосування к!лькох правил постановки до отримання ланцожка, у котрого ус1 допом!жн1 символи е зам!нен1 основними, терм1нальними символами.

Всього вид!ляють чотири типи граматик (!ерарх!я Хомсь-' кого):

- тип О:' необмежена граматика; " •

- тип 1: граматика безпосередньо складових;

- тип 2: безконтекстна граматика;

- тип 3: регулярна граматика.

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

л *

«*»

граматик, сп1вв1дносяться яч с с Ь с Ь. , де ¿г - семейство, яке повднув ус\ язики типу 1-0-3. Отже, виб1р гра-матики типу 1 для задания образ1в покривав можливост1 задания образ1в за допомогою граматик типгв 2 13.

Що стосувться граматики типу 0, то для використання цей клас враховуеться надто широким. Будь-як1 можлив1 образи, у тому числ1 й образи КДЕ, - породжуються граматиками Типу 1. Необмежен1 граматики не породжугать образ1в з новими ' власти-востями. Однак в1дсутн1сть обмежень на вид правил постановки дозволяв задавати правила, як1 передбачають перестановку терм1нальних символов та усунення ствол!в.. Ця особливасть дозволяв х'арактеризувати подЮн1 правила виводу як трансформации!, тобто правила виводу, як! дозволягать зм1нювати (трансформувати) образи.

У теори формальних граматик. процес породження лан-цкшив розг'лядаеться як процес "розвитку" початкового симво-. лу 5 < який оточений пустими символами. Якщо. розглядати ви-падок, коли в оточений непустими символами, можна збудувати процес зканення контексту символа Б , тобто процес трансфор-мацп множини вшидних ланцгашв у множину результуючих. Формальн1 граматики, як1 вир1шують задачу зм1нення образ1в, звуться трансформацшними.

Вюадним язиком трансформащйно! граматики буде язик:

= У, '*}.

Породжений язик:

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

У дисертащйшй ' робот1 доводиться наступна теорема: будь-який язик типу О може бути породжений граматиксяо, у яко1 ус1 правила постановки мають у л1в1й частин1 по одному

допстжному символу.

Дя теорема дозволила розробити синтаксичну конструкцию правил постановки трансформащйних граматик стосовно до тополог! I ДП. Така конструкц!я отримала наэву породжуючо! фор-мули (ПФ). Синтаксис ПФ викладемо у форм! нотац1й Бекуса-На-ура (БНФ). Для цього використаемо розширення ЕНФ, у якому ЦК означав повторения ланцюжка о£ в!д т до п раз1в. По умовчанню т-о, п=о°.

Структура породжуючо! формули:

< породжуюча формула>: :-<лдва частина> -*■ < права частина>

<допом1жний символ>

<л1ва частина>: :-

{скомпозищя основних символ!в>>* <права частина>; :М<композ.символ!в>{ \/<композ.сгмвол!в>)-};

■Ккомпозшця допом1ж.символ!в>}'

< композ.символ1в>:: ■

{скомпоэтця основних символ!в>}<

скомпозищя допомДж.символ!в>:: ■

г

«номер тару>}' I

<допом1жнии символ>

{<напрямок>}' JJ

де <допом1жнкй символ> --одна з великих букв латинського алфавиту; <номер шару> - додэтне число; <напрямок> комбДнавдя букв П,Л,В,Н, яка задае величину ! напрямок змЩення; <композиция основних символ!в> - деякий п!добраэ, який складено з непох1дних елементДв. У випадках, коли ц1 композит 1 в обох частиках ПФ сп1впадають, розум!ЕТЬся, що постановка допомхжних символ!в виконуеться у контекст!. Гнакше, рахувться, що виконуеться постановка !з. змОенням контексту, тобто - трансформащя.

Приклад. Зсув групи друкованих провгдниклв в!д контактно! площадки. Зсув виконуеться з метою эб!льшення ! золюючбго зазору м1ж КП i проводником. У таблиц! 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домо, що граматикам типу 0 в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ляшЦ - композшШ терм!нальних символ!в. До ус!х символ1в та композищй, як1 пом!щуються у пам'ять машини, . додаються зазначення позицП на площин1 та номера шару. Виняток складають два спец1альн1 символи: символ продовжування режиму та символ переключения режиму. Вони вастосовуються для узгодження двох режим1в роботи машини: режиму трансформацП та режиму 'в1дновлення. Ш символи заноситься у л!вий -магазин разом 1з значениям верши-ни правого магазину, яке дор!внюе числу зайнятих осередк!в магазину.

• Машина Тьюр1нга починае свою роботу у режим! трансфор-мацП. В момент початку роботи основна головка машини Ть-юр1нга знаходиться у дёяк!й вих!дн1й позицП, в1дносно яко! надал1 визначаеться П положения на площин!. Головка пам'ят1 у початковий момент зчитуе вм1ст першого осередку левого магазину. У режим1 трансформацП основна головка машини Ть-юр1нга зд1йснюе перем1щення на площии з одн1е! позицП у другу, зчитуваиня, 1дентифжацш та -запис композита

Таб^идя 1.

ПФ

Д1я

А Ш

Ал

К уАпВпнСпвК

ш

ь у ЪпнЬ

а

л. ш.

■к

и

N

йт

в ш ш

V Спа N

Зсув групи ПР0В1ДНИК1В В1Д

кп.

Зсув групи, яка починаеться з прямого проводника.

Зсув групи, яка починаеться з пров1дника 1з зламом П1д 45 градус1в.

Зсув групи, яка починаеться з пров1дника 1з зламом п1д 45 градус1в при зеркальному в1дображенн1.

Зсув одиночного прямого проводника.

Зсув одиночного пров!дника 1з зламом п1д 45 градус1в.

Зсув одиночного проводника 1з зламом п1д 45 градус!в при зеркальному в1дображенн1

3 ^ АяпВттСтК»^ КяпаВшиСпмнКтВпвиСптКп**' ЬппгтСштКтВяачСпшКп3

0

©

МлпмКплВпппСптК/г ^ ВплшЬппкСтлКв ^ ЬляпняЬшпСппКп ^ Кп ^

0

Мал. 1. Зсув групи пров!дник1в в!д КП.

4

- 12 - • ■ терШнадьних символiB. Кожне эчитування композицП супровод-жуеться эаписом зчитано! композицП у вглыЦ осередки пам'яП правого магазину. .Також машина Тьюр1нга виконуе эчитування та запис магазинних символ1в у zisouy магазин!. При зчитуваннг спещального символу продовжування режиму машина Тьюрхнга продовжуе роботу в режт.и трансформации При зчиту-ванн1 спещального символу переключения режиму- машина Ть-юр!нга припиняб виконання трансформацш, а тхльки виконуе послДдовне зчитування символов а л1вого магазину. Це продов-жуеться до .тих nip, поки не в1дбудеться зчитування символу продовжування режиму. Шсля цього виконання трансформащй поновлюбться. Якщо на якомусь кроц1 машина Тьюронга не змог-ла ДдентифДкувати зчитану на площинi композицш, вона переходить у режим в1дновлення.

У режим! в1дновлення в1дбуваеться звороиий процес: зчитування з правого магазину записаних ран1ше композицш та запис 'ix у В1ДП0В1ДН1 позицП на площинi на в1дпов1дному mapi. Hqjj процео продовжу'вться до тих nip, поки вершина правого разину не знизиться до значения, яке було в казане з останнДм зчитаним з л1вого магазина спевдальним символом (не важливо яким). Також у режим! в1дновлення машина Тыоршга afliftcaoB читання магазинних символов э л1вого магазину, Yci магазинш символи, за винятком спещальних символ1в, при ць-ому пропускаться. У випадку, якщо був зчитаний спещальний символ продовжування режиму,, режим роботи машини не эмИшбться. Якщо ж був зчитаний символ переключения режиму, машина Тыор^нг.а'понавлюе; роботу у режим1 трансформац! i.

Машина Тьюр1нга завершув свою- роботу при спустошешп л1вого магазину. .Результатом И роботи на топологи, завдяки режиму в1дновлення, завжди буде являтися або повнютю транс-формована конф1гуращя - результуюча КДЕ, або конф1гурац1я без будь-яких 3MiH - вюидна КДЕ.

Дамо формальний опис адаптовано! машини Тьюршга.

Машина Тьюршга б ciMKa Т=(1,#,Г, K,S, Де>

Z - ск!нченна множина термшальних символ1в топологП ДП;

Q - скученна множина стан1в;

Г - скДнченна множина магазинних символ1в л1вого магазину;

К - скхнченна множина композитй терм1нальних символ1в, HKi сприймэються основною головкою машини TbiopiHra,

- початковий стан;

2,- початковий символ, який перший з'являеться у мага-зинн!й пам'ят!;

X - символ продовжування режиму;

У - символ переключения режиму;

Р - множина заключних стан1в;

5 - в!дображення Q * (К^Ш) * Г* (Ки{А}) у множину 0*(К1>Ш)*(((Г-{Х,У})хй**Ь)и{ХЖ*(К"№1 Де Д - пустий ланцюжок (композиц!я), а ¿ = {/1,П,В, Н} . L - к1льк!сть шар1в топологii ДП.

У дисертац1йн1й робот! показано, ш,о для будь-яко! трансформац!йно! граматики, яка задана за допомогою множини ПФ, може бути збудована детерм1нована адалтована машина Тыор!нга, яка виконуе- на модел! топологi'i задан! трансфор-мац!!.

Дал! у дисертац!йн1й робот! розглядаеться проблема ви-бору алфав!ту непох1дних елемент!в для тополог!I ДП. При ць-ому' стараються виконати слгдугоч! дв! вимоги: .

1. Непох!дн! елементи повинн! служити основними элементами образ!в та вабезпечувати адекватний й стислий опис вих!дних даних.

2. 0ск1льки структурна !нформац!я в непох!дних елемен-тах не важлива, i вони рахуються простими й компактними образами, !х вид!лення та розп!знав&ння повинн! легко зд!йсню-ватися !снуючими несинтаксичними методами.

В якост1 можливих вар!ант!в алфав!т!в у дисертац!йн!й робот!-анал!зуються векторний, позиц!йний та растровий ал-фав1ти.

Незважаючи на обмежене застосування (т!льки для регулярно! топологП), для реал!зацП п1дходу у середовищ! ОС РВ (комплекс АРМ2-01) був обраний другий вар1ант алфав!ту, як той, що дов!в свою ефектйвн1сть при розв'язаян! задач! синтезу тополог!!. Даний виб!р дозволив .експериментально пе-реМрити отриман1 теоретичн! результата й зд1йснити розробку п1дсистеми трансформац!'i тополог ii для експлуатац! ! на малих ЕОМ в1тчизняного виробнйцтва. Для реал!зац1! п!дходу у сере-довиц! MS DOS (IBM PC), був обраний векторний алфав1т, що дозволило здхйснювати трансформац!» й нерегулярно! топологП ДП.

Розв'ягання 'задач! трансформац!! топологП ДП в САПР

эдшснюеться шляхом включения до САПР гпдсистеми трансфор-мацп топологИ, яка складаеться з трьох головних частин: виконуючо! системи трансформацш, б1блютеки трансформацгй та 1нструментальних васобгв настроювання й- управлшня. Шдсистема призначена для застосування на завершальному етап! проектування топологи для внесения зм1н, якх забезпе-чують покращения технологхчних та електричних характеристик ДП, а також спрошують сам' процес проектування.

' Виконуюча система трансформацш будуеться у В1ДП0В1Д-HocTi до принцип1в функцгонування адаптовано! машини Ть-npiHra, алгоритм роботи котро! визначаеться набором ПФ. При цьому можливi два вар!анти побудови виконуючо"! системи: у вигляд1 ун1версально! машини Тьюр1нга та у вигляд! машини Тьюр1нга 1з незманним набором команд. У першому BapiaHTi множину команд отримують шляхом трансляци вшидного опису трансформацш, який готуетьоя на спещагизованому язику. При другому BapiaHTi множину команд формують засобами звичайних язик1в програмування. Перший вар1ант був застосований при розробщ п1дсистеми трансформаци топологП для вксплуатаци на ША СМ 1420, та е б1льш унхвероальним, але й б1льи склад-ним у peaaisaiU'i. У xofli його реал1заци . було розроблено 1нструментапьний язик задания трансформащй Матрикс. Другий BapiaHT був застосований при розробщ пгдсистеми трансформаци тополог!! для експлуатаци на ПЕОМ. Перевагою другого вар1анту в те, що BiH дозволяв вводити додатков: параметри настроювання окремих-процедур трансформаци й цим розширити "ix експлуатац^йн1 можливост1.

До б1бл1отеки трансформац1й, яка була розроблена nifl час виконання дисертащйно! роботи, ув!йшли так1 головн! процедури трансформаци:

- зменшення к1лькост1 перех!дних oTBppiB;

- усунення пет1ль;

- "д! агонал1заци" тополог!!;

- зсуву пр0В1Дник1В В1Д контактних площадок;

- сгладжування. прстдншив;

- "niflpiBKii" КП i ПО та стоньшення проваднишв.

Шдсистема трансформац1! топологi! була реал1зована у

середовищ1 операщйннх систем ОС РВ та MS DOS для експлуатаци на малих та персональних ЕОМ у склад1 пакету програм-АРМ-ПЛАТ та системи САКТ-М.

4. ГОЛОВЫI РЕЗУЛЬТАТИ РОБОТИ

1. Виконана постановка задач 1 трансформацп тополог И ДП та проведений анал1з 1снуючих метод1в та элгортшв II розв'язання;

2. Запропонований синтаксичний (структурний) Шдх1д для розв'язання задач! трансформащI тополог!!, у рамках якого розроблек! рекурсивно процедури зсуву проЕ1дник!в, усунення пет1ль, "д1агоналозац!1" топологи та зменшення к1лькост! перех1дних отвор!в;

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

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

5. Зд!йснена розробка моделей для виконання трансформацп! топологИ багатошаровнх друкованих плат на р!зних об-числювальних платформах: поэтапно! модел! для ЕОМ СМ 1420 та впорядковано! векторно! модел! для ПЕОМ.

6. Виконана програмна . реалозавдя подсистем трансформацп топологИ для експлуатацП у склад! САПР ДП АРМ-ПЛАТ та САКТ-М на баз! малих та персональних ЕОМ.

' . 5. "МАТЕР IАЛИ ДИСЕРТАЦ11 0ПУБЛ1 КОВАН I У СЛ1ДУШИХ ДРУКОВАНИХ РОБОТАХ

1. Автоматизированное редактирование топологии плат печатного монтажа / Г.Ю.Вепринский, Е.Ш.Райз, Ю.Н.Била // ЭВМ в проектировании и производстве. -.Л.: Машиностроение,. Ленингр. отд-ние, 1987. - Вып.З. - С.366-372.

Автором виконана експериментальна перев!рка можливосИ використання синтаксичного (структурного) подходу для виконання технолог!чних перетворень зз допомогою позшцйно! модел! топологоо ДП.

2. Тетельбаум А.Я., Била Ю.Н. Повышение технологичности печатного монтажа в САПР // Автоматизация проектирования в электронике: Респ.межвед.науч.-техн.сб. -1988. - Рып.38. - С.95-103.'

- 16 -

Автором виконаний анализ основних п1дход1в до роев'яэання задач! технолоПчних перетворень та запропонова-но виконувати перетворення на позицпиий мод ел 1 топологи за допомогою механДзму пар матриць та набору ор1бнтованих граф1в заотооування матриць. що поклало основи розробц! спещального язику задания трансформаций Матрикса.

3. Била . Ю.Н. Трансформация топологии плат печатного монтажа // Управляющие системы и машины. - 1992.. - N3/4. -С. 47-52.

4. Тетельбаум А.Я., Била Ю.Н. Синтаксический подход к трансформации топологии печатных плат // Автоматизация проектирования в электронике: Респ.межвед.науч.-техн.сб. 1993. - Вып.47. - С.41-50.

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

5. Тетельбаум А.Я., Била Ю.Н. Трансформация топологии

' печатных плат // Автоматизация.проектирования РЭА. и ЗВА: сб. тезисов докладов к зональной конференции, г.Пенза. - .1990. -С.53-54.

Автором виконана постановка задач1 трансформацП топологи ДП та запропонований. синтаксичний Шдх1д до П розв'язання.

6. Била ф.Н. Лингвистический подход к синтезу топологии Ш // Автоматизация проектирования РЭА и, ЭВА: сб. тезисов докладов к зональной конференции; г¿Пенза. - 1991. -С. 61-63. •

- 17 -

Била Ю.Н. Разработка и исследование методов трансформации топологии печатных плат в САПР. Рукопись. Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - системы автоматизации проектирования по технически),! наукам. Национальный технический университет Украины', Киев, 1996 г.

Защищается В научных работ, которые содержат результаты разработки и,исследования методов трансформации топологии . печатных плат (ПП) для улучшения технологических и электрических характеристик ПП, а также информацию о программной реализации подсистемы трансформации топологии для использования в САПР Щ. При решении поставленной задачи в диссертационной работе применяется синтаксический- (структурный) подход, базирующийся на теории формальных грамматик и решающих автоматов. В частности, пршенены трансформационные грамматики для задания трансформаций и предложена структура адаптированной машины Тьюринга для их выполнения на модели топологии ПП. Осуществлено промышленное внедрение разработанных программных средств на предприятиях стран СНГ. '

Bila Y.N. Eleboration and research of methods for transformation of printed circuit board topology in CAD. Manuscript. Dissertation for a candidates degree in technical science on speciality 05.13.05 - computer aided designe in technical science. National Technical University of the Ukraine, Kiev, 1996. ■ *

It is defended 6 scientific works which Include the resalts of eleboration and research of methods for transformation of printed circuit board (PCB) topology for impruvment of technological - and electrical characteristics of PCB, the information about program realization of subsystem for transformation of PCB topology in CAD is included too. The solution of the task was achieved by use of syntactic (structural) approach which is based on a theory of formal grammar and automaton. Particularly, there was used a transformational grammar and propoused structure of adapted Turing machine for making the transformations • on the model of PCB topology. The introduction of designed program applications is"made on .the enterprises of the CIS. .

Ключов1 слова: вир1шуючий .автомат, машина TbiopiHra, технолоНчн1 перетворення, тополо^я друковано! плати, траноформавдйна граматика, язик.

Il Un. до друку 1106. AT. Форма! 60X847,6.

flaiiip друк. Jû 1 . Cnoci6 друку офсетний. Умовн. друк. арк. с,Ц . Умовн. фарбо-В|'дб. . Обл.-вид. арк. ffo ■.

Тираж to .Зам. 3bg-j}Yj .

ф|рма « В) ПОЛ» 252I5I, Ки7в, вул. Волниста, 60.