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

г~гДШОНЩШЙ ТЕХН1ЧНИЙ УН1ВЕРСИТЕТ УКРАГНИ "КйШСЬКИЙ ПОЛ1ТЕХН1ЧНИЙ 1НСТИТУТ"

- 8 0И1 «В

На правах рукопису

УДК 658.512,011.56:519.682.7

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

РОЭРОБКА ТА Д0СЛ1ДЖЕННЯ МЕТОДIВ ТРАНСФОРМАЦII ТОПОЛОГИ ДРУКОВАНИХ ПЛАТ В САПР

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

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

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

КШв - 1996

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

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

доктор техн!чних наук, професор А.¡.Петренко

Оф1ц1йн1 опоненти:

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

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

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

професор

В.П.Гондюл

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

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

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

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

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

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

Вчений секретар /О/ Писаренко

спец1ал1зовано'! Ради, (\JlJi Леон1д Дмитровиц

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

1. АНОТАЩЯ

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

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

1.2. Задач!, що Еиршуються

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

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

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

3. Роэробка моделей .'для виконання трано>}:;рмзц1й топологи багатошарових друкованих.плат.

4. Роэробка ' пютрументальних засоб1в задании трансформащй.

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

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

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

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

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

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

4. Принципи . псбудови; 1нструментальних засоб1в та ¿х практичну реал!гац!ю, а такс« реал1гацш виконуючо'1 системи трансформащ\.

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

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

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

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

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

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

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

-з- ■ •

математики. •

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

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

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

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

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

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

Практична uiHHiCTb дисертзщйноЧ .роботи:

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

2. Розв*язан1 у рамках П1дсистеми частков1 задач1 трансформацп тополог iï : л1:св1даци зайвих перех1дних от-BopiB, усунення neTijn., "fliaroHanisaiiiï" топологi'i, зсуву у вузьких мюцях пров!дник!в sis контактних площадок (КП) та перех1дних отвор1в (ПО) й "ni.upi зки" КП та ПО is заауженням пров1дника у Micipx, до зсув пров1дника неможливий, тз iкш;

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

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

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

2.5. Апробац!я роботи та публ!кацП

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

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

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

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

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

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

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

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

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

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

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

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

. У запропонованих. paiiime пхдходах розглядалися, як правило, лиш окром! вкпэдк;- розв'язання задач! трансформацГ! тополог!!, наприклад, • виконання технолог1'чиих коректуваиь (технолоПч)п перетворення). Алё i n цих випадках р!шення

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

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

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

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

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

. - 7 -

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

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

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

Формальна граматика О визначаеться як четв!рка 6 = (Уу,Уы, Р, в) . де Ут та ^ - основний та допом1жний словники (алфав1ти) граматики (? в1дпов!дно. Символ Р поз-начае ск!нченну множину правил виводу або правил постановки, як! позначаються аС ~*- ^ , де 1 Р> - ланцшки (ком-позицП) символ!в 1з V = Ути\/>1. Вказанним• правилом вико-■ нуеться зам1на ланцюжка </. -на ланцюжок £ . Символ 5 £ 1/м початковий символ.

Основний-словник "V? е словником непох1дних елемент1в (терм!нальних символ1в, елементарних п1добраз!в), з котрих будуються речения (образи) язйку, який породжений граматикою С- Речення. будуються у вигляд! лачцюжкхв (або !нших компо-зиц!й)-елементарних п1доСраз!в, Допом1жний словник У» е словником допом1жних символ1в, котр1 використовуються у прочее! виводу ланцюжка поряд з терм1пальними символами, однак в!дсутн1 у ланцожках, я.к1 е речениями язику. Язик образ!в, який породжений граматикою С , позначаеться ¿(0).

Ш-Лх/в^х, х*ут*}.

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

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

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

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

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

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

л

- а -

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

Що стосуеться граматики типу О, то для використання цей клас враховуеться надто широким. Еудь-якЛ можлив: образи, у тому числ1 й образи КДЕ,• породжуються граматиками 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 граматики.

У дисертацшнхй ' робот! доводиться наступна теорема: будь-який язик типу 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в в!д контактно! площадки. Зсув виконуеться з метою зб!лыпення 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домо, що граматикам типу 0 в1дпов!дають машини Тыор1нга.

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

Магааинна пам'ять адаптовано1 машини Тыор!нга д!литься на дв! д1лянки: л!ву та праву. На Л1В1Й д1лянц1 запиоуються нетерм!нальн! символи, а на прав1й д!лянц! - композицП терм1нальних символ!в. До ус1х символ1в та композиций, як! пом!щуються у пам'ять машини, . додаються зазначення позицИ на площин! та номера шару. Винягок складають два спец!альн1 символи: символ продовжування режиму та символ переключения режиму. Вони вастосовуються для узгодження двох режшав робота машини: режиму трансформацП та режиму в!дновлення. Щ символи заноситься у л!вий магазин разом 1з значениям верши-ни правого магазину, яке дор!внюе числу зайнятих осередк!в магазину.

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

Габлиия I.

А Ш

Л

ш.

•к

ПФ

__ __ К V АпВпиСпяК

ш

I у ВпнЬ

ЙГ^

и

N

й

в и ш

___Д1я_

Зсув групи пров!дник1в в1д кп.

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

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

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

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

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

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

Б ^ Ап ^ АпяБипнСяйвК«^ КлпяВпппиСпладКтВляиСтлКп1* ЬлпянСтлтКлябммСпкКл3

0

О

Кпп 8плиСптКп ** ВгтптЬлгмСтвКп ^ ЬпягчиИ.тгкСятКл ^

©

©

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

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

У режим1 вхдновлення вгдбуваеться ,зворотн1й процес: зчитування з правого магазину записаних paHinie композищй та вапис ix у в1дшв1дн1 погицп на плотен! на вгдповодному mapi. Пой процес продовжу'еться до тих nip, поки вершина правого ь—ааину не энизиться до значения, яке було вказане э ocTaHHiM зчитаним з aiBoro магазина спещальним символом (не ■ важливо яким). Також у режим! вцщовлення машина TbiopiHra зд1йснюб читання магазинних символ1в з л1вого магазину, yci магаэитй символи, за винятком спецхальних символ1в, при ць-ому пропускаться. У випадку, якадэ був зчитаний спеадальний символ продовжування режиму,, режим роботи машини не зм1нюеться. Якщр ж був зчитаний символ переключения режиму, машина Тыор1нг%а"поновлюе, роботу у режим! трансформацп.

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

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

Машина TbiopiHra е ciMKa Т=(1,£),Г. К,8, у.&ХУР), Де:

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

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

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

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

. • - 13 -

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

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

X - символ продовжування режиму; У - символ переключения режиму; Р - множина заключних стан!в;

<5 - в1дображення Q * (Кч{А}) * Г* (Ki/{A}) у множину Q*(KuM)*(((MXtY})*tf*L)u(XM*!t(l(»lfih-. Де Д " пустий ланцюжок (композиц1я), а ¿ = {/1, П,В,Н) , L -■ к!льк!сть шар!в тополог!! ДП.

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

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

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

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

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

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

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

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

' Виконуюча система трансформащй будуеться у в1дпов1д-ност! до принципiв функщонування адаптовано'1 машини Ть-юр1нга, алгоритм роботи котро! визначавться нзйором ПФ. При цьому можлив1 два вар1анти побудови виконуючо! системи: у вигляд! ун1версально'1 машини Тьюргнга та у виглядх машини Тыор1нга i3 незм1нним набором команд. У першому BapiaHTi множину команд отримують шляхом трансляци вшидного опису трансформаций, який готуеться на спец1ал1зованому язику. При другому BapiaHTi множину команд формують засобами звичайних яаик1в програмування. Перший вариант Сув застосований при розробц! п1дсистеми трансформаци тополог i 'i для експлуатаци на ЕОМ СМ 1420, та б бШш ун1версальним, але й бхльш склад-ним у реад1зацП. У ход1 його реалхааци . було розроблено 1нструментальний язик задания трансформац!й Матрикс. Другий вар1ант був застосований при розробц1 Шдсистеми трансформаци топологи для експлуатаци на ПЕОМ. Перевагою другого вар1анту е те, wp bih дозволяв вводити додатковг параметри настроювання окремих'процедур трансформаци й цим роэширити IX експлуатац!Йн1 можливости

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

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

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

- "fliaroHaiiBaui'i" топологП;

- эсуву пров1дник1в Е1Д контактних площадок;

- сгладжування. пров1дник1в;

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

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

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

4. ГОЛОВНI РЕЗУЛЬТАТИ РОЁОТИ

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

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

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

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

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

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

' . 5. МАТЕР1АЛИ ДИСЕРТАДII 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бна граматика типу 0. Останне означав, що трансформац1я образ1в на модел1 тополог!1 може виконува-тися т1льки за допомогою машини Тьюринга.

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

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

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

- 1? -

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

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

Bila Y.N/ Eleboration and research of methods for transformation cf 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 (PCE) 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 слова: виргшуючий .автомзт, машина Tbropinra, технологхчн1 перетворення, тополог1я друковано! плати, трансформзщйна грзматика, язик.

П1дп. до друкyjf.ce.tc. Формат 60х84'/|«.

Пашр друк. № / . Способ друку офсетний. Умов», друк. арк. с, и . Умовн. фарбо вЫб. . Обл.-»ид. арк./,£? . Тираж го .Зам.

Ф1рма «В1ПОЛ» 252151, Ки7в, пул. Волинська, $0.