Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
О
Факультет:
ТГВ
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2005
Тип роботи:
Інші
Предмет:
Автоматичне проектування
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет “Львівська політехніка”
кафедра САПР
Р О З Р А Х У Н К О В О - Г Р А Ф І Ч Н А Р О Б О Т А
з курсу: “Основи автоматичного проектування об’єктів”
Виконали: ст.гр. КН-43
Годиш Т.В.
Данків Н.Г.
Прийняв: Матвійків О.М.
Львів - 2005
Індивідуальне завдання
Дати характеристику комп’ютерних систем проектування для радіоелектронних пристроїв (на прикладі OrCAD, pCAD, тощо).
Провести аналіз ОП, отриманого в індивідуальному завданні, особливості та вихідні дані на його проектування.
Сформувати технічне завдання на проектування радіоелектронного пристрою.
Дати характеристику методів опису електричних схем. Застосовуючи ці методи, побудувати модель об’єкта проектування (ОП) :
У вигляді графа
У матричному вигляді
Дати коротку характеристику процедур проектування радіоелектронних пристроїв на прикладі друкованих плат:
Методи та алгоритми компоновки елементів
Методи та алгоритми розміщення елементів на платі
Методи та алгоритми трасування звязків між елементами
Розмістити елементи РЕП на друкованій платі:за допомогою системи OrCAD;
Провести траси на друкованій платі:за допомогою системи OrCAD;
Пояснити роботу алгоритму трасування Лі на прикладі псевдо-плати:
Зобразити плату з 4-5 елементів, побудувати монтажно-комутаційне поле, вибрати 2-ві точки для трасування та провести трасу за допомогою хвильового алгоритму Лі –
За критерієм мінімуму згинів;
За критерієм мінімуму перетинів.
Описати отримані результати.
Розрахувати геометричні розміри, розробити методи кріплення деталей, метод подачі живлення, зовнішній вигляд спроектованого РТП в корпусі (оформити як ескізне проектування).
Проаналізувати вплив температурних, електричних та механічних полів на спроектований пристрій.
Виконати ескізне проектування “лицевої” панелі для даного радіотехнічного пристрою.
Оформити пояснювальну записку і захистити звіт по роботі.
Аналіз об’єкту проектування
Дуже часто в охоронних системах використовуються безконтактні сенсори для контролю ближньої зони. Це – простір біля дверей, частина коридору, сходів, стіл, сейф і т.д. Зазвичай такі задачі вирішують засобами високочастотної технології. Сенсором може бути LC – генератор, що розстроюється при наближенні сторонніх об’єктів, втрачаючий баланс високочастотний міст та інші. На схемі зображений пристрій, що формує короткі інфрачервоні імпульси і приймає їх відображення від об’єкту, що з’явився неподалік.
Тут ВІ – інфрачервоний діод, що періодично збуджується імпульсами струму, амплітуда яких в декілька разів перевищувати допустиме значення. Тривалість таких імпульсів tімп = 0,7R3C2 ( 10мкc, а період слідування Т = 1,4R2C1 ( 0,2c.
Відбитий інфрачервоний імпульс попадає на фото діод BL1. Після підсилення і обмеження мікросхемою DA1 він поступає на один з входів елемента DD 2.1 (вивід 13). Якщо відбитий імпульс співпадає з випроміненим (імпульс, що збуджується інфрачервоним діодом поступає на вивід 12 DD 2.1), то на виході DD 2.1виникає короткий імпульс низького рівня, який запускає одновібратор (DD 2.2, DD 2.3). На виході одновібратору виникає імпульс тривалістю Тзв = 0,7R8C7 ( 0,1c. Він поступає на вхід звукового генератора (DD2.4, DD1.6) динамічна головка НА1 створює короткий звуковий сигнал біля 1400Гц.
Таким чином пристрій „озвучує” відбиті інфрачервоні імпульси. Серія таких імпульсів буде трансформуватися ним в тривожно озвучену послідовність, що йде з частотою інфрачервоних імпульсів.
Технічне завдання
1. Вступ
Темою контрольної роботи з курсу “Основи автоматизованого проектування складних об’єктів і систем” є розробка конструкції інфрачервоного датчика присутності (ІДП). Пристрій призначений для охорони приміщення: тривожний сигнал звучить в тому випадку, коли в приміщенні, що охороняється, буде знайдений рухомий чи нерухомий об’єкт, який був відсутній в момент включення пристрою.
2. Підстави для розробки
Пристрій розробляється на підставі замовлення НУ “Львівська політехніка”, завдання кафедри САПР.
3. Призначення розробки
Пристрій призначений для виявлення присутності небажаних об’єктів і входить до складу охоронних систем. Вхідними даними на проектування є схема електрична принципова, а вихідними – конструктивно завершений пристрій.
4. Мета розробки
Метою розробки даного пристрою є покращення вже існуючих охоронних систем для забезпечення швидкого реагування на небажані об’єкти. Розробка пристрою ведеться з врахуванням критеріїв максимальної надійності і мінімальних витрат.
5. Вимоги до об’єкта проектування
Клас використання ІДП – наземна електронна апаратура.
Група використання ІДП – професійна РЕА.
5.1. Вимоги до функціональних характеристик:
- пристрій має забезпечити надійне виявлення небажаних об’єктів;
- пристрій повинен забезпечувати швидку подачу інформації (звукового сигналу) при виявлення небажаного об’єкту.
5.2. Вимоги до складу і параметрів технічних засобів:
- пристрій має складатись з поширених елементів для підвищення ремонтопридатності пристрою;
- пристрій має мати легкий доступ до основних його елементів для підвищення ремонтопридатності.
5.3. Вимоги до кліматичної та механічної стійкості:
Види кліматичного виконання приладу - УХЛ 4.1 і 4.2 по ГОСТ 15150, вологість по ГОСТ 20790. Кліматичне виконання УХЛ (для районів з помірним холодним кліматом) категорія розміщення РЕА на об’єкті експлуатації 4.1 (апаратура стаціонарна, що працює в опалюваних наземних і підземних приміщеннях) характеризуються розміщенням ІДП в опалюваних приміщеннях з параметрами:
а) вплив температури :
- робочі температури +1…+35 (С
- середні температури +20 (С
- граничні температури +1…+40 (С
б) вплив вологи:
- 98% при температурі 25 (С
В якості нормальних кліматичних умов приймаємо:
- температура оточуючого середовища (15…35) (С;
- відносна вологість повітря (45…75)%;
- атмосферний тиск (86…104) кПа;
5.4. Вимоги механічної стійкості.
Оскільки апаратура стаціонарна, то спеціальні вимоги щодо міцності не висуваються.
5.5. Вимоги по надійності:
- середній строк служби, не менше 6 років;
- середній час безвідмовної роботи – не менше 10000 год;
- пристрій повинен забезпечувати безперервну роботу на протязі 16 годин.
5.6. Параметри мережі живлення:
- напруга (220 ( 22) В;
- частота (50 ( 1) Гц;
- коефіцієнт гармонік напруги – 5%
5.7. Вимоги електробезпеки для класу професійної РЕА:
- конструкція ІДП повинна задовольняти вимогам щодо електробезпеки.
5.8. Конструкція повинна відповідати вимогам технологічності, ергономіки та технічної естетики.
5.9. Маркування приладу повинно відповідати вимогам ГОСТ 20790.
6. Стадії і етапи розробки
Згідно ЕСКД процес проектування виглядає наступним чином
ТТВ – тактико-технічні вимоги;
НДР – науково-дослідна розробка;
ТЗ – технічне завдання;
ПТ – пропозиція технічна;
ЕП – ескізний проект;
ТП – технічний проект;
РД ДВ – робоча документація дослідного взірця;
РД УС – робоча документація установочної серії;
РД СВ – робоча документація серійного виробництва;
В – виробництво.
Але в нашому випадку стадії РД УС і В не виконуюються, оскільки запускати даний пристрій у серійне виробництво не планується, а також стадія ПТ не проходиться в проектуванні даного пристрою. Всі решта пристрої будуть пройдені.
7. Порядок контролю і приймання
Буде проведено ряд випробувань:
попередні. Ці випробування проводяться власними силами (силами розробника і виконавця), під час яких вносяться зміни до розробки.
приймально-здавальні випробування. Ці випробування будуть проведені спеціальною комісією. до складу комісії входять: представники замовника, виконавця, потенційного підприємства – виробника, окрім того, сторонні незалежні особи. Комісія проводить випробування і здійснює повний контроль всієї документації. В результаті випробувань комісія приймає остаточний висновок: прийняти виріб, прийняти з деякими зайваженнями або відхилити його.
Процедури проектування
При конструкторському проектуванні РЕА (радіоелектронних апаратур) вирішуються завдання, пов'язані з пошуком найкращого варіанта конструкції, що задовольняє вимогам технічного завдання й максимально враховуючої можливості технологічної бази виробництва. Тісний взаємозв'язок завдань і більша розмірність кожної з них звичайно не дозволяє запропонувати метод пошуку оптимального конструктивного рішення в єдиному циклі у зв'язку із труднощами створення загальної математичної моделі, що комплексно враховує особливості конструкторсько-технологічної бази виробництва. Тому розробка й реалізація алгоритмів і методів рішення окремих завдань етапу конструкторського проектування: компонування, розміщення й трасування,- дотепер залишаються актуальними проблемами, рішення яких невід'ємне пов'язане з розвитком систем автоматизації проектування.
Алгоритми компоновки
На етапі конструкторського проектування вирішуються питання, пов'язані з компонуванням елементів логічної схеми в модулі, модулів в осередки, осередків у панелі й т.д. Ці завдання в загальному випадку тісно зв'язані між собою, і їхнє рішення дозволяє значно скоротити витрати й трудомісткість зазначеного етапу в САПР. Звичайно завдання компонування розглядаються як процес прийняття рішень у певних або невизначених умовах, у результаті виконання якого частини логічної схеми розташовуються в конструктивних елементах i-го рівня, а ці елементи розміщаються в конструктивних елементах (i+1) -го рівня й т.д., причому розташування виконується з оптимізацією за обраним критерієм.
Компоновкою електричної схеми РЕА на конструктивно закінчені частини називається процес розподілу елементів нижчого конструктивного рівня у вищий відповідно до обраного критерію. Основним для компонування є критерій электромагнітотеплової сумісності елементів нижчого рівня. Даний критерій визначає область припустимих розбивок схеми, на якій формулюються інші критерії. Такими критеріями можуть бути: мінімум типів конструктивно закінчених частин, щільність компонування, мінімум з'єднань між пристроями, простота діагностування й ін. Очевидно, що зовнішні з'єднання між частинами схем є одним з найважливіших факторів, що визначають надійність РЕА. Тому найпоширенішим критерієм є критерій мінімуму числа зовнішніх зв'язків. Виконання цього критерію забезпечує мінімізацію взаємних наведень, спрощення конструкції, підвищення надійності й т.д.
Для побудови формальної математичної моделі компоновочних завдань зручно використати теорію графів. При цьому електричну схему інтерпретують ненаправленим мультиграфом, у якому кожному конструктивному елементу (модулю) ставлять у відповідність вершину мультиграфа, а електричним зв'язкам схеми - його ребра. Тоді завдання компонування формулюється в такий спосіб, Заданий мультиграф G(X,U). Потрібно “розрізати” його на окремі шматки G1(X1,U1), G2(X2,U2),..., Gk(Xk,Uk) так, щоб число ребер, що з'єднують ці шматки, було мінімальним, тобто
мінімізувати i≠j
при i,j = 1,2,…,k,
де Uij - безліч ребер, що з'єднують шматки Gi(Xi,Ui) і Gj(Xj,Uj).
Іншими словами розбивками частин сукупності G на графи вважаються, якщо будь-яка частина із цієї сукупності не порожня; для будь-яких двох частин перетинання безлічі ребер може бути не порожнім; об'єднання всіх частин у точності дорівнює графові G.
Відомі алгоритми компонування можна умовно розбити на п'ять груп:
1. алгоритми, що використають методи цілочисельного програмування.
2. послідовні алгоритми
3. ітераційні алгоритми
4. змішані алгоритми
Алгоритми першої групи хоча й дозволяють одержати точне рішення завдання, однак для пристрою реальної складності фактично не реалізовані на ЕОМ. Останнім часом найбільше поширення одержали наближені алгоритми компонування (послідовні, ітераційні, змішані). При використанні послідовних алгоритмів спочатку за певним правилом вибирають вершину графа, потім здійснюють послідовний вибір вершин (із числа нерозподілених) і приєднання їх до формованого шматка графа. Після утворення першого шматка переходять до другого й т.д. до одержання бажаного розрізування вихідного графа. В ітераційних алгоритмах початкове розрізування графа на шматки виконують довільним образом; оптимізація компонування досягається парними або груповими перестановками вершин графа з різних шматків. Процес перерозподілу вершин закінчують при одержанні локального екстремума цільовій функції, що задовольняють вимогам розроблювача. У змішаних алгоритмах компонування для одержання початкового варіанта “розрізування” використається алгоритм послідовного формування шматків; подальша оптимізація рішення здійснюється перерозподілом вершин між окремими шматками графа.
Послідовні алгоритми компоновки
У послідовних алгоритмах компонування «розрізування» вихідного графа G(X,U) на шматки G1(X1,U1), G2(X2,U2),…, Gk(Xk,Uk) зводиться до наступного. У графі G(X,U) знаходять вершину xi X з мінімальним локальним ступенем .
Якщо таких вершин трохи, то перевагу віддають вершині з максимальним числом кратних ребер. З безлічі вершин, суміжних з вершинами формованого шматка графа G1(X1,U1), вибирають ту, котра забезпечує мінімальне збільшення зв'язків шматка із ще нерозподіленими вершинами. Дану вершину xi X X1 включають в G1(X1,U1), якщо не відбувається порушення обмеження по числу зовнішніх зв'язків шматка, тобто
,
де αjε – елемент матриці суміжності вхідного графа G(X,U); δ(xg) – відносна вага вершини xg, , дорівнює збільшенню числа зовнішніх ребер шматка G1(X1,U1) при включенні вершини xg у безліч X1; E – безліч індексів вершин, включених у формований шматок графа на попередніх кроках алгоритму; m – максимально припустиме число зовнішніх зв'язків окремо взятого шматка з усіма що залишилися.
Зазначений процес триває доти, поки безліч X1 не буде містити n елементів або приєднання чергової нерозподіленої вершини xj до шматка G1(X1,U1) не приведе до порушення обмеження по числу зовнішніх з'єднань шматка, рівному
Слід зазначити, що величина не є монотонною функцією |X1|, тому, для того щоб переконається в неможливості подальшого формування шматка внаслідок порушення останнього обмеження, необхідно перевірити його нездійсненність на наступних кроках збільшення безлічі X1 аж до n. Як остаточний варіант вибирають шматок G10(X10,U10), що містить максимально можливе число вершин графа G(X,U), для якого виконуються обмеження на число зовнішніх зв'язків і вхідних у нього вершин (nmin-nmax).
Після перетворення шматка G10(X10,U10) процес повторюють для формування другого, третього й т.д. шматків вихідного графа з тією лише різницею, що розгляду підлягають вершини, що не ввійшли в попередні шматки.
Сформулюємо алгоритм послідовного компонування конструктивних елементів.
1) t:0
2) Xf = Xt = Ø; t=t+1; Θ=1; ?=nmax,
Де t, ? - порядкові номери формованого шматка й приєднує верли, що; ? - обмеження на число вершин у шматку.
3) По матриці суміжності вихідного графа | αhp|Nx, де N – число вершин вихідного графа (при великому значенні N для скорочення обсягу оперативної пам'яті ЕОМ використаємо не саму матрицю суміжності, а її кодову реалізацію), визначаємо локальні ступені вершин .
4) З безлічі нерозподілених вершин X вибираємо вершину xj з ρ(xj) = . Переходимо до п.6. Якщо таких вершин трохи, то переходимо до п.5
5) З підмножини вершин Xl з однаковим локальним ступенем вибирають вершину xj з максимальним числом кратних ребер (мінімальним числом суміжних вершин), тобто |Гxj| = .
6) Запам'ятовуємо вихідну вершину формованого шматка графа . Переходимо до п.10
7) По матриці суміжності будуємо безліч Xs = і визначаємо відносні ваги вершин :
.
8) З безлічі XS вибираємо вершину . Переходимо до п. 10. Якщо таких вершин трохи, то переходимо до п.9.
9) З підмножини вершин Xv з однаковою відносною вагою вибираємо вершину xj з максимальним локальним ступенем, тобто .
10) .
11) Якщо >m , те переходимо до п.13.
12) Розглянуті вершини включаємо у формований шматок Xf = Xt .
13) ? = ? + 1.
14) Якщо ?> ?, те переходимо до п.15, а противному випадку - до п.7.
15) Якщо |Xf|<nmin, де nmin - мінімально припустиме число вершин у шматку, то переходимо до п.21.
16) Вибираємо остаточний варіант сформованого шматка графа:
Xt = Xf ; X = X Xt ; ? = nmax .
17) Якщо |X|> nmax , те переходимо до п.20.
18) Якщо |X|< nmin , те переходимо до п. 21.
19) Визначаємо число зовнішніх зв'язків останнього шматка графа:
,
де F – безліч індексів вершин, що входять в X. Якщо , то переходимо до п. 21, у противному випадку – до п. 24.
20) Якщо t<k – 1 , де k - число шматків розрізування графа, то переходимо до п. 2, у противному випадку – до п. 23.
21) Попередній цикл «розрізування» уважаємо недійсним. Якщо t>1, тобто є як мінімум один раніше сформований шматок, то переходимо до п. 22. у противному випадку - до п.23.
22) Шукаємо інший припустимий варіант формування попереднього шматка з меншим числом вершин: t = t – 1; .
Переходимо до п.7.
23) Завдання при заданих обмеженнях не має рішення.
24) Кінець роботи алгоритму.
Розглянутий алгоритм простий, легко реалізується на ЕОМ і дозволяє одержати рішення завдання компонування. Також серед достоїнств даної групу алгоритмів виступає висока швидкодія їх при рішенні завдань компонування.
Основним недоліком послідовного алгоритму є нездатність знаходити глобальний мінімум кількості зовнішніх зв'язків (не аналізуються можливі ситуації). Найбільша ефективність методу послідовної розбивки графа має місце, коли число вершин графа G значно більше вершин у будь-якій частині розбивки.
Ітераційні алгоритми компонування
Сутність даної групи алгоритмів полягає у виборі деякого початкового «розрізування» вихідного графа на шматки (вручну або за допомогою послідовного методу компонування) і наступного його поліпшення за допомогою ітераційного парного або групового обміну вершин з різних шматків. При цьому для кожної ітерації здійснюється перестановка тих вершин, що забезпечує максимальне зменшення числа зв'язків між шматками графа або максимальне поліпшення іншого обраного показника якості з урахуванням використовуваних обмежень (наприклад, на максимальне число зовнішніх ребер будь-якого окремо взятого шматка).
Розглянемо основну ідею ітераційного алгоритму розбивки графа G, заданого матрицею суміжності, з мінімізацією числа сполучних ребер. Розбивка графа G = (X,U) на l підграфів G1 = (X1,U1), G2 = (X2,U2),…,Gl= (Xl,Ul) зведемо до розбивки на два підграфа. Із цією метою в матриці суміжності R виділимо по головній діагоналі дві підматриці R1 й R2. При цьому порядок підматриці R1 дорівнює числу вершин, які повинні перебуває в G1, а порядок підматриці R2 – числу всіх вершин, що залишилися, графа. Необхідно так переставити рядки й стовпці матриці R, щоб число ребер між G1 і частиною, що залишилася, графа G було мінімальним. Після цього підматрицю R1 з матриці R виключаємо, викресливши з R рядки й стовпці, що відповідають елементам R1. Далі підматрицю R1’ розбиваємо знову на дві підматрицю R2 й R2’, причому порядок R2 відповідає числу вершин другого виділюваного подграфа, а порядок R2 – числу вершин, що залишилися, графа. Переставляємо рядки й стовпці R1' з метою мінімізації числа сполучних ребер. Після цього підматриця R2' виключається й процес повторюється доти, поки не буде виконана розбивка графа G на l підграфів.
Основна ідея алгоритму полягає у виборі таких рядків і стовпців, перестановка яких приводить до зосередження в діагональних клітках матриці R максимального числа елементів. Побудуємо прямокутну матрицю W = ||wi,j||nix(n-ni), у якій рядки визначаються вершинами з безлічі I, а стовпці – з безлічі V, . На перетинанні k рядка ( і q стовпця перебуває елемент
,
де rk,q - елемент матриці суміжності R.
Елемент wk,q матриці W характеризує зміна числа сполучних ребер між Gi й Gj при перестановці вершин й . Використовуючи матрицю W , можна знайти підстановку, що збільшить число елементів у підматрицях R1 й R1’ . Такий процес повторюється доти, поки в підматриці R1 не зосередиться максимальне число одиниць.
В ітераційних алгоритмах передбачена можливість пошуку оптимального варіанта для різних початкових розбивок. Це пов'язане з тим, що при використанні ітераційних алгоритмів оптимальність рішення значною мірою залежить від того, наскільки вдало була зроблено початкова розбивка графа G(X,U).
Ітераційні алгоритми компонування забезпечують висока якість рішення завдання, однак вимагають більших витрат машинного часу, чим послідовні алгоритми. Для скорочення числа ітерацій обміну вершин між шматками в змішаних алгоритмах для одержання початкового «розрізування» графа застосовують послідовні методи формування його шматків. Із цією метою в деяких ітераційних алгоритмах використають процес групової перестановки взаємно непересічних пар вершин.
АЛГОРИТМИ РОЗМІЩЕННЯ
Вихідною інформацією при рішенні завдань розміщення є: дані про конфігурацію й розміри комутаційного простору, обумовлені вимогами установки й кріплення даної складальної одиниці в апаратурах; кількість і геометричні розміри конструктивних елементів, що підлягають розміщенню; схема з'єднань, а також ряд обмежень на взаємне розташування окремих елементів, що враховують особливості розроблювальної конструкції. Завдання зводиться до відшукання для кожного розташовуваного елемента таких позицій, при яких оптимізується обраний показник якості й забезпечуються найбільш сприятливі умови для наступного електричного монтажу. Особливе значення це завдання здобуває при проектуванні апаратур на друкованих платах.
Основна складність у постановці завдань розміщення полягає у виборі цільової функції. Зв'язано це з тим, що однієї з головних цілей розміщення є створення найкращих умов для подальшого трасування з'єднань, що неможливо перевірити без проведення самого трасування. Будь-які інші способи оцінки якості розміщення (мінімум числа перетинань ребер графа, що інтерпретує електричну схему з'єднань, розбивка графа на мінімальне число плоских суграфів і т.д.), хоча й дозволяють створити сприятливі для трасування умови, але не гарантують одержання оптимального результату, оскільки друковані провідники являють собою криволінійні відрізки кінцевої ширини, конфігурація яких визначається в процесі їхньої побудови й залежить від порядку проведення з'єднань. Отже, якщо для оцінки якості розміщення елементів вибрати критерій, безпосередньо пов'язаний з одержанням оптимального малюнка металізації друкованої плати, те кінцевий результат може бути знайдений тільки при спільному рішенні завдань розміщення, вибору черговості проведення з'єднань і трасування, що практично неможливо внаслідок величезних витрат машинного часу.
Тому всі застосовувані в цей час алгоритми розміщення використають проміжні критерії, які лише якісно сприяють рішенню основного завдання: одержанню оптимального трасування з'єднань. До таких критеріїв ставляться: 1) мінімум сумарної зваженої довжини з'єднань; 2) мінімум числа з'єднань, довжина яких більше заданої; 3) мінімум числа перетинання провідників; 4) максимальне число з'єднань між елементами, що перебувають у сусідніх позиціях або в позиціях, зазначених розроблювачем; 5) максимум числа ланцюгів простої конфігурації.
Найбільше поширення в алгоритмах розміщення одержав перший критерій, що порозумівається наступними причинами: зменшення довжин з'єднань поліпшує електричні характеристики пристрою, спрощує трасування друкованих плат; крім того, воно порівняно просто в реалізації.
Залежно від конструкції комутаційної плати й способів виконання з'єднань відстань між позиціями установки елементів підраховується по одній з наступних формул:
, ,
У загальному виді завдання розміщення конструктивних елементів на комутаційній платі формулюється в такий спосіб. Задано безліч конструктивних елементів R={r1,r2,...,rn} і безліч зв'язків між цими елементами V={v1,v2,...,vp}, а також безліч настановних місць (позицій) на комутаційній платі T={t1,t2,...,tk}. Знайти таке відображення безлічі R на безлічі T, що забезпечує екстремум цільової функції
, де cij – коефіцієнт зваженої зв’язності.
Силові алгоритми розміщення
В основу цієї групи алгоритмів покладений динамічний метод В.С. Линского. Процес розміщення елементів на платі представляється як рух до стану рівноваги системи матеріальних крапок (елементів), на кожну з яких діють сили притягання й відштовхування, що інтерпретують зв'язки між розташовуваними елементами. Якщо сили притягання, що діють між будь-якими двома матеріальними крапками ri й rj пропорційні числу електричних зв'язків між даними конструктивними елементами, то стан рівноваги такої системи відповідає мінімуму сумарної довжини всіх з'єднань. Введення сил відштовхування матеріальних крапок друг від друга й від границь плати виключає можливість злиття двох будь-яких крапок і сприяє їхньому рівномірному розподілу по поверхні монтажного поля. Щоб усунути виникнення в системі незатухаючих коливань, уводять сили опору середовища, пропорційні швидкості руху матеріальних крапок.
Таким чином, завдання оптимального розміщення елементів зводиться до знаходження такого місця розташування крапок, при якому рівнодіючі всіх сил звертаються в нуль.
До достоїнств даного методу ставляться можливість одержання глобального екстремуму цільової функції, а також відомість пошуку до обчислювальних процедур, для яких є розроблені чисельні методи.
Недоліками є трудомісткість методу й складність його реалізації (підбора коефіцієнтів для силових зв'язків); необхідність фіксування місця розташування деякого числа конструктивних елементів на платі для запобігання великої нерівномірності їхнього розміщення на окремих ділянках плати.
Ітераційні алгоритми розміщення
Ітераційні алгоритми мають структуру, аналогічну ітераційним алгоритмам компонування, розглянутим раніше. У них для поліпшення вихідного розміщення елементів на платі вводять ітераційний процес перестановки місцями пара елементів.
У випадку мінімізації сумарної зваженої довжини з'єднань формула для розрахунку зміни значення цільової функції при перестановці місцями елементів ri й rj , закріплених у позиціях tf й tg, має вигляд:
,
де p й h(p) – порядковий номер і позиція закріплення нерухомого елемента rp. Якщо , то здійснюють перестановку ri й rj , що приводить до зменшення цільової функції на , після чого роблять пошук і перестановку наступної пари елементів і т.д. Процес закінчується одержанням такого варіанта розміщення, для якого подальше поліпшення за рахунок парних перестановок елементів неможливо.
Використання описаного спрямованого перебору скорочує число аналізованих варіантів розміщення (у порівнянні з повним перебором), але приводить до втрати гарантії знаходження глобального екстремуму цільової функції.20
Алгоритми даний групи характеризуються досить високою швидкодією. Алгоритми із груповими перестановками елементів на практиці використаються рідко через їхню складність, що часто не виправдує досягає степінь, що, поліпшення результату.
Послідовні алгоритми розміщення
Послідовні алгоритми засновані на допущенні, що для одержання оптимального розміщення необхідно в сусідніх позиціях розташовувати елементи, максимально зв'язані один з одним. Сутність цих алгоритмів складається в послідовному закріпленні заданого набору конструктивних елементів на комутаційній платі щодо раніше встановлених. У якості спочатку закріплених на платі елементів звичайно вибирають рознімання, які штучно «розсовують» до країв плати. При цьому всі контакти рознімань рівномірно розподіляються по секціях (стовпцям і рядкам координатної сітки). На кожному l-ом кроці (l=1,2,…,n) для установки на комутаційну плату вибирають елемент із числа ще не розміщених, що має максимальний ступінь зв’язності з раніше закріпленими елементами Rl-1. У більшості використовуваних у цей час алгоритмів оцінку ступеня зв’язності роблять по одній з наступних формул:
;
,
де cij - коефіцієнт зваженої зв’язності елементів i й j; Jl-1 - безліч індексів елементів, закріплених на попередніх l-1 кроках; n - загальне число розміщених елементів.
Якщо настановні розміри всіх розташовуваних на платі елементів однакові, то обраний на черговому кроці елемент закріплюють у тій позиції із числа незайнятих, для якої значення цільової функції з обліком раніше розміщених елементів Rl-1 мінімально. Зокрема, якщо критерієм оптимальності є мінімум сумарної зваженої довжини з'єднань, те
,
де dfj – відстань між f-ої позицією установки елемента й позицією розміщеного раніше елемента rj; Tl-1 – безліч позицій, зайнятих елементами після (l-1)-го кроку алгоритму.
Процес розміщення алгоритму закінчується після виконання n кроків алгоритму.
Алгоритми, що використають послідовний процес закріплення елементів у позиціях, є в цей час самими швидкодіючими. Однак по якості одержуваного рішення послідовні алгоритми уступають ітераційним. Тому їх використають звичайно для одержання початкового розміщення елементів на платі.
АЛГОРИТМИ ТРАСУВАННЯ
Трасування з'єднань є, як правило, заключним етапом конструкторського проектування РЕА й складаються у визначенні ліній, що з'єднують еквіпотенціальні контакти елементів, і компонентів, що становлять проектований пристрій.
Завдання трасування – одна з найбільш трудомістких у загальній проблемі автоматизації проектування РЕА. Це пов'язане з декількома факторами, зокрема з різноманіттям способів конструктивно-технологічної реалізації з'єднань, для кожного з яких при алгоритмічному рішенні завдання застосовуються специфічні критерії оптимізації й обмеження. З математичної точки зору трасування - найскладніше завдання вибору з величезного числа варіантів оптимального рішення.
Одночасна оптимізації всіх з'єднань при трасуванні за рахунок перебору всіх варіантів у цей час неможлива. Тому розробляються в основному локально оптимальні методи трасування, коли траса оптимальна лише на даному кроці при наявності раніше проведених з'єднань.
Основне завдання трасування формулюється в такий спосіб: за заданою схемою з'єднань прокласти необхідних провідників на площині (платі, кристалі й т.д.), щоб реалізувати задані технічні з'єднання з обліком заздалегідь заданих обмежень. Основними є обмеження на ширину провідників і мінімальні відстані між ними.
Вихідною інформацією для рішення завдання трасування з'єднань звичайно є список ланцюгів, параметри конструкції елементів і комутаційного поля, а також дані по розміщенню елементів. Критеріями трасування можуть бути відсоток реалізованих з'єднань, сумарна довжина провідників, число перетинань провідників, число монтажних шарів, число міжшарових переходів, рівномірність розподілу провідників, мінімальна область трасування й т.д. Часто ці критерії є взаємовиключними, тому оцінка якості трасування ведеться за домінуючим критерієм при виконанні обмежень за іншими критеріями або застосовують аддитивну або мультиплікативну форму оцінної функції, наприклад наступного виду
, де F – аддитивний критерій; λi - вагарні коефіцієнт; fi - приватний критерій; p - число приватних критеріїв.
Відомі алгоритми трасування друкованих плат можна умовно розбити на три більші групи:
1) Хвильові алгоритми, засновані на Чи ідеях і розроблені Ю. Л. Зиманом і Г. Г. Рябовым. Дані алгоритми одержали широке поширення в існуючих САПР, оскільки вони дозволяють легко враховувати технологічну специфіку друкованого монтажу зі своєю сукупністю конструктивних обмежень, Ці алгоритми завжди гарантують побудова траси, якщо шлях для неї існує;
2) Ортогональні алгоритми, що володіють більшою швидкодією, чим алгоритми першої групи. Реалізація їх на ЕОМ вимагає в 75-100 разів менше обчислень у порівнянні із хвильовими алгоритмами. Такі алгоритми застосовують при проектуванні друкованих плат з наскрізними металізованими отворами. Недоліки цієї групи алгоритмів пов'язані з одержанням великої кількості переходів із шару на шар, відсутністю 100%-ой гарантії проведення трас, більшим числом паралельно, що йдуть провідників;
3) Алгоритми евристичного типу. Ці алгоритми частково засновані на евристичному прийомі пошуку шляхи в лабіринті. При цьому кожне з'єднання проводиться по найкоротшому шляху, обходячи перешкоди, що зустрічаються на шляху.
Хвильовий Лі алгоритм
Даний алгоритм являє класичний приклад використання методів динамічного програмування для рішення завдань трасування друкованих з'єднань. Основні принципи побудови трас за допомогою динамічного алгоритму зводяться до наступного.
Всі осередки монтажного поля підрозділяють на зайняті й вільні. Зайнятими вважаються осередки, у яких уже розташовані провідники, побудовані на попередніх кроках, або перебувають монтажні виводи елементів, а також осередку, що відповідають границі плати й забороненим для прокладання провідників ділянкам. Щораз при проведенні нової траси можна використати лише вільні осередки, число яких у міру проведення трас скорочується.
На безлічі вільних осередків комутаційного поля моделюють хвилю впливу з одного осередку в іншу, що з'єднують згодом загальним провідником. Перший осередок, зароджується хвиля впливів, називають джерелом, а другу - спадкоємцем хвилі. Щоб мати можливість стежити за проходженням фронту хвилі впливів, його фрагментам на кожному етапі привласнюють деякі ваги:
,
де Pk й Pk-1 - ваги осередків k-го й (k-1)-го фронтів; - вагова функція, що є показником якості проведення шляхи, кожен параметр якої характеризує шлях з погляду одного із критеріїв якості (довжини шляхи, числа перетинань і т.п.). На Pk накладають одне обмеження - ваги осередків попередніх фронтів не повинні бути більше ваг осередків наступних фронтів. Фронт поширюється тільки на сусідні осередки, які мають із осередками попереднього фронту або загальну сторону, або хоча б одну загальну крапку. Процес поширення хвилі триває доти, поки її фронт, що розширюється, не досягне приймача або на ?-ом кроці не найдеться ні одного вільного осередку, що могла б бути включена в черговий фронт, що відповідає випадку неможливості проведення траси при заданих обмеженнях.
Якщо в результаті поширення хвиля досягла приймача, то здійснюють «проведення шляху», що полягає в русі від приймача до джерела про пройденим на етапі поширення хвилі осередкам, стежачи за тим, щоб значення Pk монотонно убували. У результаті одержують шлях, що з'єднує ці дві крапки. З опису алгоритму треба, що всі умови, необхідні для проведення шляху, заставляються в правила приписання ваги осередкам.
Щоб виключити невизначеність при проведенні шляху для випадку, коли кілька осередків мають однакова мінімальна вага, уводять поняття шляхових координат, що задають перевагу проведення траси. Кожен напрямок кодують двійковим числом по mod q, де q - число сусідніх осередків, що переглядають. При цьому чому більш переважно той або інший напрямок, тим менший числовий код воно має. Наприклад, якщо задатися пріоритетним порядком проведення шляхи зверху, праворуч, знизу й ліворуч, те коди відповідних шляхових координат будуть 00, 01, 10, і 11. Приписання шляхових координат роблять на етапі поширення хвилі. При проведенні шляху рух від осередку до осередку здійснюють по шляхових координатах.
Істотними недоліками хвильового алгоритму є мала швидкодія й великий обсяг оперативної пам'яті ЕОМ, необхідний для зберігання інформації про поточний стан всіх осередків комутаційного поля, можливість побудови лише з'єднань типу «ввід-вивід». Спроби усунути зазначені недоліки привели до створення ряду модифікацій хвильового
Модифікації Лі алгоритму
Метод зустрічної хвилі
У даному методі джерелами хвиль є обидві осередки, що підлягають електричному об'єднанню. При цьому на кожному k-ом кроці по черзі будують відповідні фронти першої й другої хвиль, що поширюються із цих осередків. Процес триває доти, поки який-небудь осередок із фронту першої хвилі не потрапить на фронт другої хвилі або навпаки. Проведення шляху здійснюють із даного осередку в напрямку обох джерел за правилами, описаним у хвильовому Чи алгоритмі.
Оцінимо число осередків, що переглядають на етапі поширення хвилі, при використанні як джерела однієї або двох поєднуваних крапок. Нехай відстань між цими крапками R. Тоді для першого випадку в момент досягнення хвилею осередку-приймача площа переглянутої околиці має величину
17.07.2020 15:07-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора