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

Анотація наукової статті за медичними технологіями, автор наукової роботи - Чеченя Вадим Сергійович


Область наук:
  • Медичні технології
  • Рік видавництва діє до: 2016
    Журнал: Радіоелектроніка та інформатика
    Наукова стаття на тему 'Абстрактні АВТОМАТ І ФОРМУВАННЯ кортеж з непересічними Сполучених'

    Текст наукової роботи на тему «абстрактний АВТОМАТ І ФОРМУВАННЯ кортеж з непересічними Сполучених»

    ?УДК 519.172

    Абстрактні АВТОМАТ І ФОРМУВАННЯ кортеж з непересічними Сполучених

    Чечені В.С._

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

    При проектуванні сучасних складних електронних пристроїв характерною особливістю є застосування мікросхем великої та надвеликої ступеня інтеграції - це друковані плати, які містять корпусу типу LGA, BGA, CGA.

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

    На дозвіл завдання отримання якісного малюнка схеми здатна вплинути тільки розробка математичного апарату для проектування плоских конструктивів в області розміщення компонентів матричних корпусів. 1.Постановка завдання

    Для вирішення подібних завдань необхідний принципово новий підхід до процесу трасування [1,2]. Тому в даній роботі представлений метод побудови малюнка схеми без перетину провідників з мінімальною кількістю шарів для проектування плоских конструктивів з BGA компонентами. Розроблено математичний апарат проведення з'єднань, оцінки якості проведення з'єднань, оптимізації отриманого рішення. Запропонована математична модель проведення з'єднань з метою формування кортежу з'єднань представлена ​​у вигляді циклічного фрагмента.

    Тому сам процес проведення з'єднань можна описати як комбінаторних завдання розміщення та перестановки елементів.

    2. Огляд літератури

    Мікросхеми в корпусі BGA відносно недорогі і мають малі розміри [3]. Але, не дивлячись на свою популярність застосування, трасування друкованих плат за участю корпусів BGA проблематична. Причин, за якими необхідний швидкий вихід на периферію, кілька. Звичайна послідовна трасування з перекладанням не усуває кратних перетинів провідників. У зв'язку з цим можуть з'являтися «зайві міжшарові переходи», ще більше збільшуючи щільність розміщення контактів [4]. У свою чергу збільшення міжшарових переходів тягне за собою ряд інших факторів-зменшення товщини провідників і відстаней між ними, специфіки міжшарових з'єднань, що є катастрофою для BGA. Незважаючи на розвиток САПР, сучасні програмні засоби не в змозі впоратися з поставленим завданням [4]. Тому часто якість виконаної роботи, а саме малюнок проведення з'єднань залишає бажати кращого.

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

    3. Матеріали та методи

    Розглянемо методи формування кортежу з'єднань, коли місце розташування контактів на зовнішньому контурі повинно бути представлено циклічним фрагментом, тобто розташування контактів повинно бути задано у вигляді циклічної послідовності [1,2,5-7]. Математична модель проведення з'єднань з метою формування кортежу з'єднань у вигляді циклічного фрагмента полягає у формуванні послідовності з'єднань різного рівня. Проведення з'єднань асоціюється з розміщенням і перестановкою елементів в кортежі. На кожному кроці побудови між контактами поточного рівня необхідно розмістити сліди з'єднань контактів попереднього рівня. При цьому потрібно зробити рівномірне проведення з'єднань по макродіскретам.

    Розглянемо докладно структуру макродіскрета (рис. 1). Як приклад розглянемо макродіскрет М1.

    Мал. 1. Макродіскрет Мб

    Макродіскрет складається з чотирьох контактів: правий нижній контакт bi, лівий нижній контакт ai, правий верхній контакт b2, лівий верхній контакт Ьз. Також є чотири топомет-рических лінії у вигляді спрямованих відрізків (bi, b2), (b2, b3), (b3, ai), (ai, bi). З нижнього правого контакту є можливість проведення тільки чотирьох з'єднань. Таким чином, на рівні Ub ^<t bit b2 | Ьз |> є чотири можливі способи розташування слідів з'єднань попереднього рівня. Стрілками вказано можливе місце розташування слідів попереднього рівня. Таким чином, можна характеризувати кожне розташування елементів в кортежі характеристичним вектором Sb. У характеристичний вектор Sb позиції з ненульовим значенням характеризують слід з'єднань попереднього рівня, наприклад (рис. 2): кортежу ybi = <ai, bi, b2, b3> відповідає характеристичний вектор Sbi = (i, 0,0,0); кортежу yb2 = <bi, ai, b2, b3> відповідає характеристичний вектор Sb2 = (0, i, 0,0); кортежу yb3 = <bi, b2, ai, b3> відповідає характеристичний вектор Sb3 = (0,0, i, 0); кортежу yb4 = <bi, b2, b3, ai> відповідає характеристичний вектор Sb4 = (0,0,0, i).

    • 6 - функція переходів АА, яка парам стан - вхідний сигнал (БШ ^) ставить у відповідність стан АА Бб, тобто Бб = (БШ ^), Бб е 8;

    • А - функція виходів АА, яка парам стан - вхідний сигнал (БШ ^) ставить у відповідність вихідний сигнал АА yg, тобто yg = (БШ ^), yg е У;

    • - початковий стан. АА працює в дискретні моменти часу, і в момент часу 1 = 0 автомат завжди знаходиться в стані Б1. У момент часу 1 = 0 + А1 автомат може перейти в інший стан.

    Мал. 3. Проведення з'єднань в макродіскрете Mi

    Мал. 4. Граф роботи автомата

    БЬ1 Бь2 = Бьз = БЬ4 =

    = (1,0,0,0) (0,1,0,0) (0,0,1,0) (0,0,0,1)

    Мал. 2. Розподіл з'єднань в рівні Ь

    Для опису процесу послідовного побудови з'єднань, починаючи з макродіскрета М1, скористаємося методами теорії автоматів [15-17].

    Визначення. Абстрактний автомат є математичною моделлю дискретного пристрою і описується шестікомпонентним набором АА = (8, Х, У, а, Л, а 1), де

    • 8 = {81,82, ..., Бт, ..., БМ} - безліч станів;

    • X = {х1, Х2, ..., Х ^ ..., Хр} - безліч вхідних сигналів;

    • У = {у1, у2, ... ^, ..., уа} - безліч вихідних сигналів;

    Розглянемо формування кортежу для рівня Ь (рис. 3 і рис. 4). Тут є всього один елемент множини вхідних сигналів х1 = {<Ь1, Ь2, Ьз>,<а1>}, Що складається з кортежу контактів рівня іь (саМІь = 3) і сліду з'єднання контакту а1 нижнього рівня Іа (саМІа = 1). Стан автомата визначається безліччю 8, що складається з чотирьох характеристичних векторів: Б1 = (1,0,0,0), 82 = (0,1,0,0), бз = (0,0,1,0), 84 = (0,0,1,0). Потужність кожного вектора визначається як саг ^ = Саміка + 1, тобто потужність кортежу контактів поточного шару плюс одиниця. Функція переходів г) парі стану = (0,1,0,0) і вхідного сигналу х1 = {<Ь1, Ь2, Ьз>,<а1>} Ставить у відповідність стан АА у вигляді вектора 6 = (0, ь1, а1, Ь2,0, Ьз, 0). Функція виходів Л = (1>1, а 1, Ь2, Ьз) парі стану Б2 = (0,1,0,0) і вхідного сигналу х1 = {<Ь1, Ь2, Ьз>,<а1>} Ставить у відповідність один з елементів безлічі вихідних сигналів У, а саме у = <Ь1, а1, Ь2, Ь2>. Початковий стан визначається як 82 = (0,1,0,0).

    АА,,

    АЛ,

    АЛ,

    АА, | -

    АА "

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

    У загальному випадку процес побудови циклічного фрагмента для зовнішніх висновків компонента BGA можна уявити як послідовну роботу абстрактних автоматів, де ви-

    Ходнев сигнал одного автомата є вхідним сигналом наступного автомата (рис. 5). На рівні Іс ^ <Т с1Т с2Т СЗТ с4Т с5Т> є шість можливих способів розташування слідів з'єднань попереднього рівня. Стрілками вказано можливе місце розташування слідів попереднього рівня. Одночасно можуть бути задіяні тільки чотири сліду з'єднань з попереднього рівня. Розглянемо ці можливості, перерахувавши всі характеристичні вектори

    Якщо при проведенні з'єднань враховувати рівномірний їх розподіл по макродіскретам, то з цією метою потрібно виключити з розгляду вектори 8с1,8с2,8сз, 8сб, 8с7,8с14, так як по сторонам с2 - сз і сз - с4 діагонального макродіскрета (3 і 4 місця в характеристичний вектор) здійснюється проведення по одному з'єднанню. Але дані боку належать одному диагональному макродіскрету Моз, тобто виходить, що в даному макродіскрете Моз здійснюється проведення двох з'єднань. А це суперечить вимогам рівномірного розподілу сполук по макродіскретам. Сформуємо кортежі (рис. 6) для рівня з відносного кортежу попереднього рівня Ь і вектора 8с4 = (1,1,1,0,1,0): УС1 ^ <Т з1 Т с2 Т сз ​​Т с4 Т с5 Т>

    а1 ь1 Ь2 0 Ьз 0 <а1, з1, Ьх, с2, Ь2, сз, с4, Ье, с5>; ВУС2 ^ <Т з1 Т с2 Т сз ​​Т с4 Т с5 Т>

    Ь1 а1 Ь2 0 Ьз 0 <Ь1, з1, Я1, с2, Ь2, сз, с4, Ье, с5>; Ус3 ^ <Т з1 Т с2 Т сз ​​Т с4 Т с5 Т> Ь1 Ь2 а1 0 Ьз 0 <Ь1, з1, Ь2, с2, Я1, сз, с4, Ье, с5>; Ус4 ^ <Т з1 Т с2 Т сз ​​Т с4 Т с5 Т> Ь1 Ь2 Ьз 0 а1 0 <Ь1, з1, Ь2, с2, Ье, сз, с4, Я1, с5>.

    Мал. 6. Кортежі для характеристичного вектора 8с4 = (1,1,1,0,1,0)

    Розглянемо формування кортежу УСЗ для рівня Іс УСЗ = <Ь1, з1, Ь2, с2, а1, сз, с4, Ьз, с5>.

    В автоматі ААС є чотири елементи множини вхідних сигналів

    х1 = {<с1, с2, сз, с4, с5>,<а1, ь1, Ь2, Ьз>}, Х2 = {<з:, с2, сз, с4, с5>,<Ь:, а1, Ь2, Ьз>}, Хз = {<з:, с2, сз, с4, с5>,<Ь:, Ь2, а1, Ьз>}, Х4 = {<с1, с2, сз, с4, с5>,<а1, ь1, Ь2, Ьз>}, Що складаються з кортежу контактів рівня Іс (саг-dUc = 5) і сліду з'єднання контакту а1, И, Ь2, Ьз нижнього рівня іь (саМІа = 4). Стан автомата визначається безліччю 8, що складається з 15-ти характеристичних векторів: 81 = (1,1,1,1,0,0), 84 = (0,1,1,1,1,0), 8з = (0 , 0,1,1,1,1), 84 = (1,1,1,0,1,0) і т.д. Потужність кожного вектора визначається як саМУ1 = саМІс + 1, тобто потужність кортежу контактів поточного шару плюс одиниця. Функція переходів 6 парі стану = (1,1,1,0,1,0) і вхідного сигналу хз = {<с1, с2, сз, с4, с5>,<Ь1, Ь2, а1, Ьз>} Ставить у відповідність стан АА у вигляді вектора 6 = (ь1, з1, Ь2, с2, а1, сз, 0, с4, Ьз, с5,0).

    Однак в макродіскрете М4 = {<Ь2, а1, с4>, <с4, Ьз, с5>, <С5, Ьз>, <Ьз, а1, Ь2>} Здійснюється проведення двох з'єднань а1 і Ьз. Для задоволення конструктивно-технологічних умов для рівномірного завантаження макродіскретов

    Поспіль чотири компонента поспіль три компонента поспіль два компонента

    8с1 = (1,1,1,1,0,0) 8с4 = (1,1,1,0,1,0) 8с10 = (1,1,0,1,1,0)

    8с2 = (0,1,1,1,1,0) 8с5 = (1,1,1,0,0,1) 8с11 = (1,1,0,0,1,1)

    8сз = (0,0,1,1,1,1) 8сб = (0,1,1,1,0,1) 8с12 = (0,1,1,0,1,1)

    8с7 = (1,0,1,1,1,0) 8с1Е = (1,1,0,1,0,1)

    8с8 = (1,0,0,1,1,1) 8с14 = (1,0,1,1,0,1)

    8с9 = (0,1,0,1,1,1) 8с15 = (1,0,1,0,1,1)

    © -9-лг- © ..... @

    © (Е © ...... ©

    ......©

    е в ?>

    УС1 =

    <а1, з1, ь1, с2, Ь2, сз, с4, Ьз, с5> © -..... ®

    у ©

    ф -? О) -...... ©

    <а> (?> (й>_

    Ус3 =

    <Ь1, з1, Ь2, с2, а1, сз, с4, Ьз, с5>

    © -.....

    - ©

    © (?) <Й)

    ВУС2 =

    <Ь1, з1, а1, с2, Ь2, сз, с4, Ьз, с5>

    © в ф)

    Ус4 =

    <Ь1, з1, Ь2, с2, Ьз, сз, с4, а1, с5>

    ш

    Мал. 7. Проведення з'єднань для рівня з Рис. 8. Граф стану автомата

    здійснюємо зрушення вправо на вільні місця з'єднання а1 і Ьз в функції переходу вектора (рис. 9):

    6 = (ь1, С1, Ь2, С2, а1, Сз, 0, С4, Ьз, С5,0) - "

    6 = (ЬьС1, Ь2, С2,0, Сз, а1, С4,0, С5, Ьз), тим самим змінюючи стан автомата на Б1з = (1,1,0,1,01).

    УСЗ ^ <Т з1 Т с2 Т сз ​​Т с4 Т с5 Т>

    Ь1 Ь2 0 а1 0 Ьз ^ <Ьх, з1, Ь2, с2, сз, ах, с4, С5, Ье>.

    Мал. 10. Ус4 = <Ь1, з1, Ь2, с2, Ьз, сз, с4, а1, С5> ^ <Ь1, з1, Ь2, с2, Ьз, сз, с4, С5, а 1>

    Таким чином, формується безліч кортежів для рівня з:

    (а> в

    Ус5 =

    <а1, з1, ь1, с2, Ь2, сз, с4, С5, Ьз>

    ф е) (5)

    Ус7 =

    <Ь1, з1, Ь2, с2, а1, сз, с4, С5, Ьз>

    Ус6 =

    <Ь1, з1, а1, с2, Ь2, сз, с4, С5, Ьз>

    © е)

    Ус8 =

    <Ь1, з1, Ь2, с2, Ьз, сз, с4, С5, а 1>

    Мал. 9. Перетворення УСЗ = <Ь1, з1, Ь2, с2, а1, сз, с4, Ьз, с5> ^ =<Ь1, з1, Ь2, с2, сз, а1, с4, С5, Ьз>

    Функціями виходять Л = (ь1, С1, Ь2, С2,0, Сз, а1, С4,0, С5, Ьз) парі стану Б1з = (1,1,0,1,0,1) і вхідного сигналу х1 = {<с1, с2, сз, с4, с5>,<Ь1, Ь2, а1, Ьз>} Ставить у відповідність один з елементів безлічі вихідних сигналів У, а саме Уз = <Ь1, С1, Ь2, С2, сз, а1, с4, с5, Ьз>. Але тоді і кінцеве стан визначиться як Б1з = (1,1,0,1,0,1). Розглянемо кортеж Ус4 =

    <Ь1, з1, Ь2, с2, Ьз, сз, с4, а1, С5>. У макродіскрете М4 = {<Ь2, Ьз, с4>,<с4, а1, с5>,<С5, Ьз>,<Ьз, с4, Сз, а1, С2, Ь2>} Здійснюється проведення двох з'єднань а1 і Ьз. Для задоволення конструктивно-технологічних умов виконуємо зрушення вправо з'єднання а1 і отримуємо новий кортеж (рис.10):

    Ус4 = <Ь1, з1, Ь2, с2, Ьз, Сз, с4, С5, а 1>

    Ус4 ^ <Т з1 Т с2 Т сз ​​Т с4 Т с5 Т>

    Ь1 Ь2 Ьз 0 а1 0 ^ <Ь1, з1, Ь2, с2, Ьз, сз, с4, ах, С5> ^

    ^ <Т з1 Т с2 Т сз ​​Т с4 Т с5 Т> Ь1 Ь2 Ьз 0 0 а1 ^ <Ь1, з1, Ь2, с2, Ьз, Сз, с4, С5, Ьз>

    Мал. 11. Кортежі з характеристичним вектором

    Бс5 = (1,1,1,0,0,1)

    в й

    Ус9 =

    <ах, с1, с2, сз, Ьх, с4, Ь2, С5, Ьз>

    (?> Ф й

    Ус11 =

    <Ьх, с1, с2, сз, Ь2, с4, ах, С5, Ьз>

    про <й>

    © ©

    (5) (?) (Й)

    Ус10 =

    <Ь1, с1, с2, сз, а1, с4, Ь2, С5, Ьз>

    (?) В (й)

    Ус12 =

    <Ь1, с1, с2, сз, Ь2, с4, Ьз, С5, а 1>

    Мал. 12. Кортежі з характеристичним вектором

    Бс8 = (1,0,0,1,1,1)

    На рівні Іа = <ТdlТd2ТdзТd4Тd5Тd6Тd7Т> є вісім можливих способів розташування слідів з'єднань попереднього рівня. Стрілками вказано можливе місце розташування слідів попереднього рівня. Одночасно можуть бути задіяні тільки дев'ять слідів з'єднань з попереднього рівня. Для рівномірного розподілу всіх з'єднань, виникає необхідність прокладки двох з'єднань в одному макродіскрете. Розглянемо ці можливості, перерахувавши всі характеристичні вектори

    = (2,1,1,1,1,1,1,1); 8С2 = (1,2,1,1,1,1,1,1);

    8сз = (1,1,2,1,1,1,1,1); 8С4 = (1,1,1,2,1,1,1,1);

    8С5 = (1,1,1,1,2,1,1,1); 8С6 = (1,1,1,1,1,2,1,1);

    8а7 = (1,1,1,1,1,1,2,1); 8сШ = (1,1,1,1,1,1,1,2).

    З розгляду слід виключити вектори Sd4 і Sd5, як свідомо не відповідають вимозі рівномірного завантаження з'єднань в макродіскретах, так як кількість з'єднань в діагональному макродіскрете більше двох. Припустимо, що для рівня

    І ^<ТdlТd2ТdзТd4Тd5ТdбТd7Т> вектором "У ^ за участю попереднього кортежу рівня Іс Ус17 = <з1, а1, с2, сз, ь1, с4, Ь2, С5, Ьз> формується новий кортеж

    Уа1 ^ <Т dl Т d2 Т dз Т d4 Т d5 Т dб Т d7 Т>

    з1, а 1 с2 сз ь1 с4 Ь2 с5 Ьз ^

    <з1, а1Д, с2 ^ 2, сз4з, ь1 ^ 4, с445, Ь2Д, с547, Ьз> Тут розподіл з'єднань по макродіскретам має вигляд (рис. 1З): М1 = {<Ь1, Ь2>,<Ь2, Ьз>,<Ьз, а1>,<а1, ь1>}; М2 = {<з1, а1, с2>,<с2, ь1, Ь2>,<Ь2, ь1>,<Ь1, а1, з1>}; Моз = {<с2, сз>,<сз, ь1, с4>,<с4, Ь2>,<Ь2, ь1, с2>}; М4 = {<Ь2, с4>,<с4, Ь2, с5>,<С5, Ьз>,<Ьз, Ь2>}; М5 = {^ 1, с242>,^ 2, с2>,<с2, а1, з1>,<з1, а1Д>}; Мб = {<d2, Cз, dз>,<dз, Cз>,<Cз, C2>,<C2, d2>};

    М7 = {<dз, Ьl, d4>,<d4, C4, d5>,<d5, C4, Ьl, Пн>,<Пн, dз>}; М8 = {<Cз, Ьl, C4, d5>,<d5, Ь2, dб>,<dб, Ь2, C4>,<C4, Ьl, Cз>}; М9 = {<с4, Ь24б>^ Б, С5 ^ 7>^ 7, с5><С5, Ь2, с4>}.

    Мал. 1З. кортеж у<і =

    <Cl, al, dl, C2, d2, сз, dз, Ьl, d4, C4, d5, Ь2, d6, C5, d7, Ьз>

    У макродіскрете М8 проведені три з'єднання. Для отримання кортежу з більш рівномірним розподілом з'єднань по макродіскретам слід здійснити зрушення з'єднань, починаючи з а1 до С5 вправо: Уdl =

    <з1, а1Д, с2 ^ 2, сз4з, ь1 ^, с445, Ь2 ^ б, С5 ^ 7, Ьз> ^ <Cl, d 1, al, d2, C2, dз, Cз, d4, Ьl, d5, C4, dб, Ь2, C5, d7, Ьз>

    =<З l, dl, al, d2, c2, dз, Пн, d4, bl, d5, c4, d6, b2, c5, d7, bз>

    <с, di, ei, ai, d2, e2, c2, e3, d3, e4, c3, e5, d4, e6, bi, d5, e7, c4, d6, es, b2, c5, e9, d7, b3>

    Для рівня Ue ^ <teite2te3te4te5te6te7te8te9t> вектором Sei = (2,2,1,1,1,1,2,2,2,2) c участю попереднього кортежу yd1 =

    <З l, dl, al, d2, c2, dз, Пн, d4, bl, d5, c4, d6, b2, c5, d7, bз> рівня Ud формуємо новий кортеж ye1 ^ <t e1 t e2 t e3 t e4 t es T e6 t e7 t es T e9 t> з1, d1 a1, d2 c2 d3 c3 d4 b1, d5 c4, d6 b2, c5 d7, Ьз ^ <З l, dl, el, al, d2, e2, c2, eз, dз, e4, Пн, e5, d4, e6, bl, d5, e7, c4, d6, e8, b2, c5, e9, d7, b3>.

    Тут розподіл з'єднань по макродіскретам має вигляд (рис. 16).

    М1 = {<Ь 1, b2>,<b2, b3>,<b3, a1>,<a1, Ь 1>}; М2 = {<c1, a1, c2>,<c2, b1, b2>,<b2, b1>,<b1, a1, c1>}; Моз = {<c2, c3>,<c3, b1, c4>,<c4, b2>,<b2, b1, c2>}; М4 = {<b2, c4>,<c4, b2, c5>,<c5, b3>,<b3, b2>};

    М5 = {<d1, a1, d2>,<d2, c2>,<c2, a1, c1>,<c1, d1>}; Мб = {<d2, c2, d3>,<d3, c3>,<c3, c2>,<c2, d2>}; М7 = {<d3, c3, d4>,<d4, b1, d5>,<d5, b1, c3>,<c3, d3>}; Ms = {<c3, b1, d5>,<d5, c4, d6>,<d6,, c4>,<c4, b1, c3>}; M9 = {<c4, d6>,<d6, b2, c5, d7>,<d7, c5>,<c5, b2, c4>};

    M10 = {<e1, a1, d2, e2>,<e2, d2>,<d2, a1, d1>,<d1, e1>};

    M11 = {<e2, c2, e3>,<e3, d3>,<d3, c2, d2>,<d2, e2>}; M12 = {<e3, d3, e4>,<e4, c3, d4>,<d4, c3, d3>,<d3, e3>}; M13 = {<e4, c3, e5>,<e5, d4, e6>,<e6, d4>,<d4, c3, e4>}; M14 = {<d4, e6>,<e6, b1, d5, e7>,<e7, d5>,<d5, b1, d4>}; M15 = {<d5, e7>,<e7, c4, d6, es>,<es, d6>,<d6, c4, d5>}; M16 = {<d6, es>,<es, b2, c5, e9>,<e9, d7>,<d7, c5, b2, d6>}.

    (К) S. \\ © \\ v \ \ "^

    е

    U-%

    .....0

    D.....

    <3> <3> & © ?> o

    Мал. 16. Кортеж

    yf1 =

    <Cl, dl, fl, el, a1, d2, f2, e2, c2, e3, f3, d3, e4, c3, f4, e5, d4, f5, e6, f6, b1, f7, d5, e7, fB, c4, d6, f9, eB, b2, f10, c5, e9, f11, d7, b3>

    Розглянемо розподіл з'єднань по макродіскретам для даного кортежу уп (рис. 17):

    М1 = {<Ь1, Ь2>,<Ь2, Ьз>,<Ьз, а1>,<а1, ь1>}; М2 = {<С1, а1, С2>,<С2, ь1, Ь2>,<Ь2, ь1>,<Ь1, а1, С1>}; Моз = {<С2, Сз>,<Сз, ь1, С4>,<С4, Ь2>,<Ь2, ь1, С2>}; М4 = {<Ь2, С4>,<С4, Ь2, С5>,<С5, Ьз>,<Ьз, Ь2>}; М5 = {<yo1, а142>,^ 2, С2>,<С2, а1, С1>,<С1Д>}; Мб = {<d2, С2, dз>,<dз, Сз>,<Сз, С2>,<С2, d2>};

    М7 = {<dз, Пн, d4>,<d4, Ьl, d5>,<d5, Ьl, Пн>,<Пн, dз>}; М8 = {<Сз, Ь145>,^ 5, С44б>,^ Б "С4>,<С4, ь1, Сз>}; М9 = {<С4, dб>,<dб, Ь2, С5, d7>,<d7, С5>,<С5, Ь2, С4>};

    М10 = {<е1, а142, е2>,<е2 ^ 2>,^ 2, а1Д>,^ 1, е1>}; М11 = {<e2, С2, eз>,<eз, dз>,<dз, С2, d2>,<d2, e2>}; М12 = {<eз, dз, e4>,<e4, Пн, d4>,<d4, Пн, dз>,<dз, eз>}; М1з = {^ Сз ^^ Д ^^ БД ^^^ з ^^; М14 = {<d4, eб>,<eб, Ьl, d5, e7>,<e7, d5>,<d5, Ьl, d4>};

    М15 = {^^^^ Д ^^ Д ^^^ Д ^;

    М1Б = {<dб, e8>,<e8, Ь2, С5, e9>,<e9, d7>,<d7, С5, Ь2, dб>}.

    М17 = {<fl, el, al, d2, f2>,<f2, e2>,<e2, d2, al, el>,<el, fl>}; М18 = {<f2, e2, С2, eз, fз>,<fз, eз>,<eз, С2, e2>,<e2, f2>}; М19 = {<fз, dз, e4, Пн, f4>,<f4, Пн, e4>,<e4, dз, eз>,<eз, fз>}; М20 = {<f4, e5, d4, f5>,<f5, d4, e5>,<e5, Пн, e4>,<e4, Пн, f4>}; М2l = {<f5, eб, Fб>,<Fб, Ьl, f7>,<f7, Ьl, eб, d4, С5>,<e5, d4, f5>}; М22 = {<e5, d4, eб, Ьl, f7>, <f7, d5, e7, f8>, ^^ ДД ^, <eб, d4, e5>};

    М23 = {<eб, Ьl, d5, e7, f8>, <f8, С4, dб, f9>, <f9, dб, С4, e7>,

    ^ ДД ^ б ^;

    М24 = {<e7, С4, dб, f9>, <f9, e8, Ь2, fl0>, <fl0, Ь2, e8>,

    М25 = {<e8, Ь2, fl0>, <fl0, С5, e9, fl1>, <fl1, e9>,

    З розподілу сполук по макродіскретам слід, що по макродіскретам М21 (d4, eб, Ьl, d5, e7) і М22 (ИД ^^ Д) проходить 5 з'єднань. За макродіскрету М2з проходить чотири з'єднання (С4Д ^ 8, Ь2). Спробуємо розподілити з'єднання більш рівномірно. З цією метою (див. Рис. 17) можна здійснити перестановку пар сполук (Сз ^ 4) і ^ Д). Отримаємо інший кортеж уп.

    Розподіл з'єднань по макродіскретам має інший вигляд:

    М1 = {<Ь1, Ь2>,<Ь2, Ьз>,<Ьз, а1>,<а1, ь1>}; М2 = {<С1, а1, С2>,<С2, ь1, Ь2>,<Ь2, ь1>,<Ь1, а1, С1>}; Моз = {<С2, Сз>,<Сз, ь1, С4>,<С4, Ь2>,<Ь2, ь1, С2>}; М4 = {<Ь2, С4>,<С4, Ь2, С5>,<С5, Ьз>,<Ьз, Ь2>}; М5 = {<dl, al, d2>,<d2, С2>,<С2, al, Сl>,<Сl, dl>}; Мб = {^ 2, С2Д>,^ З, Сз>,<Сз, С2>,<С2Д>}; М7 = {<dз, Пн, d4>,<d4, Ьl, d5>,<d5, Ьl, Пн>,<Пн, dз>}; М8 = {<Сз, Ь1Д>,^ 5, С4Д>,^ Б "С4>,<С4, ь1, Сз>}; М9 = {<С4, dб>,<dб, Ь2, С5, d7>,<d7, С5>,<С5, Ь2, С4>};

    М10 = {<el, al, d2, e2>,<e2, d2>,<d2, al, dl>,<dl, el>}; М11 = {<e2, С2, eз>,<eз, dз>,<dз, С2, d2>,<d2, e2>}; М12 = {<eз, dз, сз, e4>,<e4, d4>,<d4, Пн, dз>,<dз, eз>};

    М1з = {^ Д ^^^^^ БД ^^^}; М14 = {^^^ БДР ^^^ Д ^^ ДД ^;

    М15 = {<d5, e7>,<e7, С4, dб, e8>,<e8, dб>,<dб, С4, d5>}; М1Б = {<dб, e8>,<e8, Ь2, С5, e9>,<e9, d7>,<d7, С5, Ь2, dб>}.

    М17 = {<fl, el, al, d2, f2>,<f2, e2>,<e2, d2, al, el>,<el, fl>}; М18 = {<f2, e2, С2, eз, fз>,<fз, eз>,<eз, С2, e2>,<e2, f2>}; М19 = {<fз, dз, Пн, e4, f4>,<f4, e4>,<e4, Пн, dз, eз>,<eз, fз>}; М20 = {<f4, d4, e5, f5>,<f5, e5>,<e5, d4, e4>,<e4, f4>};

    М21 = {^^^ б ^^ б ^^^^^^ Д ^^^^^};

    М22 = {<e5, eб, Ьl, f7>, <f7, d5, e7, f8>, <f8, e7, d5, Ьl, eб>, <eб, d4, e5>};

    М2з = {<eб, Ьl, d5, e7, f8>, <f8, С4, dб, f9>, ^ Д ^^, <e7, d5, Ьl, eб>};

    М24 = {<e7, С4, dб, f9>, <f9, e8, Ь2, fl0>, ^ Юд ^^ <e8, dб, С4, e7>};

    М25 = {<e8, Ь2, fl0>, <fl0, С5, e9, fl1>, ^ П ^, <e9, С5, Ь2, e8>}.

    Але все одно в макродіскретах М22, М2з і М24 є по 4 сполуки. Спробуємо поміняти місцями пару з'єднань (Ь ^ б), отримаємо новий кортеж (рис. 18):

    УА =

    <ClД, fl, el, alД, f2, e2, С2, eз, fзД, Пн, e4, f4Д, e5, f5, Ьl, Fб, eб, П7, d5, e7, f8, С4, dб, f9, e8, Ь2, flo, С5, e9, fll, d7, Ьз>.

    Мал. 17. Новий кортеж

    уя =

    <з1 Д, П1, С1, al, d2, f2, e2, c2, eз, fз, dз, Пн, e4, f4, d4, e5, f5, eб, Fб, bl, f7, d5, e7, f8, С4 , dб, f9, e8, b2, flo, С5, e9, fll, d7, bз>

    Мал. 18. Новий кортеж

    уя =

    <Cl, dl, С1, а1, d2, f2, e2, c2, eз, fз, dз, Пн, e4, f4, d4, e5, f5, bl ^^^ Д, e7, f8, С4, dб, f9, e8, b2, fl0, С5, e9, fl1, d7, bз>

    Розподіл з'єднань по макродіскретам має вигляд:

    М1 = {<Ь1, Ь2>,<Ь2, Ьз>,<Ьз, а1>,<а1, ь1>}; М2 = {<С1, а1, С2>,<С2, ь1, Ь2>,<Ь2, ь1>,<Ь1, а1, С1>}; Моз = {<С2, Сз>,<Сз, ь1, С4>,<С4, Ь2>,<Ь2, ь1, С2>}; М4 = {<Ь2, С4>,<С4, Ь2, С5>,<С5, Ьз>,<Ьз, Ь2>}; М5 = {<dl, al, d2>,<d2, С2>,<С2, al, Сl>,<Сl, dl>}; Мб = {^ 2, С24з>,^ З, Сз>,<Сз, С2>,<С2Д>};

    М7 = {^ з, Сз44>,^ 4, Ь1Д>,^ 5, ь1, Сз>,<СЗД>}; М8 = {<Пн, Ьl, d5>,<d5, С4, dб>,<dб ,, С4>,<С4, Ьl, Пн>}; М9 = {<С44б>,^ Б, Ь2, С5Д>,^ 7, С5>,<С5, Ь2, С4>};

    М10 = {<el, al, d2, e2>,<e2, d2>,<d2, al, dl>,<dl, el>}; М11 = {<e2, С2, eз>,<eз, dз>,<dз, С2, d2>,<d2, e2>}; М12 = {<eз, dз, сз, e4>,<e4, d4>,<d4, Пн, dз>,<dз, eз>}; М1з = {<e4, d4, e5>,<e5, Ьl, eб>,<eб, Ьl, d4>,<d4, e4>};

    М14 = {^ Д ^ б ^^ Д ^^^^^ Д ^^;

    М15 = {<d5, e7>,<e7, С4, dб, e8>,<e8, dб>,<dб, С4, d5>}; М1Б = {<dб, e8>,<e8, Ь2, С5, e9>,<e9, d7>,<d7, С5, Ь2, dб>}.

    М17 = {<fl, el, al, d2, f2>,<f2, e2>,<e2, d2, al, el>,<el, fl>}; М18 = {<f2, e2, С2, eз, fз>,<fз, eз>,<eз, С2, e2>,<e2, f2>}; М19 = {<fз, dз, Пн, e4, f4>,<f4, e4>,<e4, Пн, dз, eз>,<eз, fз>}; М20 = {<f4, d4, e5, f5>,<f5, e5>,<e5, d4, e4>,<e4, f4>}; М21 = {<f5, Ьl, Fб>,<Fб, eб, f7>,<f7, eб, Ьl, e5>,<e5, f5>}; М22 =

    {<e5, Ьl, eб, f7>,<f7, d5, e7, f8>,<f8, e7, d5, eб>,<eб, Ьl, e5>};

    М2з =

    {<eб, d5, e7, f8>,<f8, С4, dб, f9>,<f9, dб, С4, e7>,<e7, d5, eб>}; М24 =

    {<e7, С4, dб, f9>,<f9, e8, Ь2, flo>,<flo, Ь2, e8>,<e8, dб, С4, e7>}; М25 =

    Але тепер можна поміняти місцями пару з'єднань (ь1, С5) і зрушити вправо з'єднання e7, С4, dб, e8, Ь2 розподіливши їх рівномірно по макродіскретам. В результаті отримаємо наступний кортеж (рис. 19):

    УА =

    <Cl, dl, fl, el, al, d2, f2, e2, С2, eз, fз, dз, Пн, e4, f4, d4, e5, f5, Ьl, Fб, eб

    e e o »© e s

    Мал. 19. Новий кортеж

    yfi =

    <ci, di, fi, ei, ai, d2, f2, e2, C2, e3, f3, d3, C3, e4, f4, d4, e5, f5, bi, f6, e6, f7,

    d5, e7, f8, C4, d6, f9, es, b2, fio, C5, e9, fii, d7, b3>

    Розподіл з'єднань по макродіскретам має вигляд:

    Mi = {<bi, b2>,<b2, b3>,<b3, ai>,<ai, bi>}; М2 = {<Ci, ai, C2>,<C2, bi, b2>,<b2, bi>,<bi, ai, Ci>}; М3 = {<C2, C3>,<C3, bi, C4>,<C4, b2>,<b2, bi, C2>}; M4 = {<b2, C4>,<C4, b2, C5>,<C5, b3>,<b3, b2>}; M5 = {<di, ai, d2>,<d2, C2>,<C2, ai, Ci>,<Ci, di>}; Мб = {<d2, C2, d3>,<d3, C3>,<C3, C2>,<C2, d2>}; M7 = {<d3, C3, d4>,<d4, bi, d5>,<d5, bi, C3>,<C3, d3>}; M8 = {<C3, bi, d5>,<d5, C4, d6>,<d6,, C4>,<C4, bi, C3>}; M9 = {<C4, d6>,<d6, b2, C5, d7>,<d7, C5>,<C5, b2, C4>}; Mio = {<ei, ai, d2, e2>,<e2, d2>,<d2, ai, di>,<di, ei>}; Mii = {<e2, C2, e3>,<e3, d3>,<d3, C2, d2>,<d2, e2>}; Mi2 = {<eз, dз, Пн, e4>,<e4, d4>,<d4, Пн, dз>,<dз, eз>}; Mi3 = {<e4, d4, bi, e5>,<e5, e6>,<e6, bi, d4>,<d4, e4>}; Mi4 = {<d4, bi, e6>,<e6,, d5, e7>,<e7, d5>,<d5, bi, d4>}; Mi5 = {<d5, e7>,<e7, C4, d6, e8>,<e8, d6>,<d6, C4, d5>}; Mi6 = {<d6, e8>,<e8, b2, C5, e9>,<e9, d7>,<d7, C5, b2, d6>}.

    Mi7 = {<fi, ei, ai, d2, f2>,<f2, e2>,<e2, d2, ai, ei>,<ei, fi>}; Mi8 = {<f2, e2, C2, e3, f3>,<f3, e3>,<e3, C2, e2>,<e2, f2>}; Mi9 = {<f3, d3, C3, e4, f4>,<f4, e4>,<e4, C3, d3, e3>,<e3, f3>}; M20 = {<f4, d4, bi, f5>,<f5, e5>,<e5, bi, d4, e4>,<e4, f4>}; M2i = {<f5, e5, f6>,<f6, e6, f7>,<f7, e6, e5>,<e5, f5>}; M22 = {<e5, e6, f7>,<f7, d5, f8>,<f8, d5, e6>,<e6, e5>}; M23 = {<e6, d5, f8>,<f8, e7, f9>,<f9, e7>,<e7, d5, e6>}; M24 = {<e7, f9>,<f9, C4, d6, e8, fio>,<fio, e8>,<e8, d6, C4, e7>}; M25 =

    {<e8, fio>,<fio, b2, C5, e9, fii>,<fii, e9>,<e9, C5, b2, e8>}. висновки

    Запропонована математична модель дозволяє описати малюнок проведення з'єднань між контактами BGA компонент теоретико-множинними методами без конкретної промальовування на площині. Дана модель дозволяє зберігати, описувати і видозмінювати інформацію загального малюнка з'єднань як в разі непересічних з'єднань, так і з'єднань з перетином.

    Література: 1. Курапов С.В., Дваподхода до проведе-ніюсоедіненій в плоских конструктивах / Курапов С.В., Давидовський М.В. // Компоненти та технології. 2015. №7. C. i42-i47. 2. Курапов С. В. Методипостро-еніятопологіческого малюнка графа / Курапов С. В., Толок А. В. // Автоматика і телемеханіка. 2013. №9. C.78-97. 3. Charles P. BGA Breakoutsand Routing. 2oio. i7op. 4. Лузін C. САПР TopoR: трассіровкапе-чатні плат з BGA-компонентами / Лузін C., Полубасов О. М.: СТА-ПРЕСС. Сучасна електроніка. 2oo8. №7. С.44-48. 5. Кофман А. Введення в приклад-нуюкомбінаторіку / А. Кофман. М .: Наука, ГРФМЛ, 1975. 480 с. 6. Свамі М. Графи, мережі та алгоритми / М. Свамі, К. Тхуласіраман. М .: Світ, i984. 455 с. 7. Комбінаторниеалгорітми, теорія і практика / [Е. Рейнгольд, Ю. Нівергельт Н. Дер]. М .: Мир. 1980. 480 с.

    Transliteratedbibliography:

    1. Kurapov S.V., Dva podhoda k provedeniju soedinenij v ploskih konstruktivah / Kurapov S.V., Davidovskij M.V. // Komponenty i tehnologii. 2015. № 7. s. 142 -147.

    2. Kurapov S. V. Metody postroenija topologicheskogo risunka grafa / Kurapov S. V., Tolok A. V. // Avtomatika i telemehanika. 2013. №9. C.78-97.

    3. CharlesPfeil BGA Breakoutsand Routing / C. Pfeil, 2010. 170p.

    4. Luzin C. SAPR TopoR: trassirovka pechatnyh plat s BGA-komponentami / Luzin C., Polubasov O. M .: STA-PRESS, Sovremennaja elektronika. 2008. №7. 1.44-48.

    5. Kofman A. Vvedenie v prikladnujukombinatoriku / A.Kofman. M .: Nauka, GRFML, 1975. 480 s.

    6. Svami M. Grafy, seti i algoritmy / M. Svami, K. Thulasiraman. M .: Mir, 1984. 455 s.

    7. Kombinatornye algoritmy, teorija i praktika / [Je. Rejngold, Ju. Nivergelt, N. Der]. M .: Mir, 1980. 480 s.

    Надійшла до редколегії 23.08.2016

    Чеченя Вадим Сергійович, викладач інформатики КВНЗ «Запорізький педагогічний коледж» ЗОР. Адреса: Україна, 69000, Запоріжжя, вул. Запорож-кого козацтва, 6, e-mail: chechenj a @ ukr. net. Chechenja Vadim Sergeevich, Informatics teacher, KVNZ "Zaporozhye Pedagogical College" ZOR. Address: Zaporozhskogo kozachestva str., 6, Zaporizhzhya, Zaporizhzhya, 69000, Ukraine, e-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..


    Завантажити оригінал статті:

    Завантажити