Моделирование однослойных и двухслойных трассировок
Описана математическая модель многослойной трассировки на основе представления ее в виде допустимого слова в некотором конечном алфавите. Показана фрагментарная структура задачи поиска трассировки минимальной плотности. Наличие фрагментарной структуры позволяет для поиска приближенных решений исполь...
Saved in:
| Published in: | Управляющие системы и машины |
|---|---|
| Date: | 2016 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2016
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/113319 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Моделирование однослойных и двухслойных трассировок / И.В. Козин, Е.В. Кривцун // Управляющие системы и машины. — 2016. — № 2. — С. 58-64. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862700620637536256 |
|---|---|
| author | Козин, И.В. Кривцун, Е.В. |
| author_facet | Козин, И.В. Кривцун, Е.В. |
| citation_txt | Моделирование однослойных и двухслойных трассировок / И.В. Козин, Е.В. Кривцун // Управляющие системы и машины. — 2016. — № 2. — С. 58-64. — Бібліогр.: 4 назв. — рос. |
| collection | DSpace DC |
| container_title | Управляющие системы и машины |
| description | Описана математическая модель многослойной трассировки на основе представления ее в виде допустимого слова в некотором конечном алфавите. Показана фрагментарная структура задачи поиска трассировки минимальной плотности. Наличие фрагментарной структуры позволяет для поиска приближенных решений использовать стандартную эволюционную модель на перестановках.
Запропоновано математичну модель багатошарового трасування на основі представлення трасування у вигляді допустимого слова в деякому скінченному алфавіті. Показано фрагментарну структуру задачі пошуку трасування мінімальної щільності. Наявність фрагментарної структури дозволяє використовувати стандартну еволюційну модель на перестановках для пошуку наближених рішень.
The printed circuit board (PCB) routing in a contact high-density region is an important and difficult technical task. The main structural and technological constraints are the density distribution of the conductors, the number of layers, the number of vias and others. The single-layer and two-layer routing problems on the PCB with a matrix arrangement of the contacts are considered. The construction of the feasible routing solution set mapping into the set of code words over a finite alphabet is described. The properties of the set of code words are investigated. The concepts of full word, 1-regular and 2-regular words are introduced. The routing algorithm for code word realization is designed. It is shown that every full single-layer routing solution is determined by 1-regular word up to equivalence, and, conversely, the realization of each 1-regular word defines a full single-layer routing solution. It is established that the two-layer routing realization set corresponds to each 2-regular word. It is well founded that any full two-layer routing solution is a 2-regular word realization. It is grounded that both 1-regular and 2-regular word sets can be represented as a maximal fragment set of some fragmentary structure. The 1-regular and 2-regular word generation algorithms are introduced. The concept of routing solution density is presented and the problem of the minimal density routing solution search as the combinatorial optimization problem on the set of feasible words is formulated. Based on the fragmentary representation, the evolutionaryfragmentary model of the routing problem, where search space is a permutation set, is proposed. As the crossover operator in the model, the binary operator, which keeps the sequence of the elements in permutations is selected. The mutation operator in this model implements transposition of two random elements in the permutation. The proposed approach allows to use the universal method of the approximate optimal solutions searching, based on evolutionary-fragmentary model, for the routing problems.
|
| first_indexed | 2025-12-07T16:39:35Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-113319 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0130-5395 |
| language | Russian |
| last_indexed | 2025-12-07T16:39:35Z |
| publishDate | 2016 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Козин, И.В. Кривцун, Е.В. 2017-02-06T14:58:33Z 2017-02-06T14:58:33Z 2016 Моделирование однослойных и двухслойных трассировок / И.В. Козин, Е.В. Кривцун // Управляющие системы и машины. — 2016. — № 2. — С. 58-64. — Бібліогр.: 4 назв. — рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/113319 519.87 Описана математическая модель многослойной трассировки на основе представления ее в виде допустимого слова в некотором конечном алфавите. Показана фрагментарная структура задачи поиска трассировки минимальной плотности. Наличие фрагментарной структуры позволяет для поиска приближенных решений использовать стандартную эволюционную модель на перестановках. Запропоновано математичну модель багатошарового трасування на основі представлення трасування у вигляді допустимого слова в деякому скінченному алфавіті. Показано фрагментарну структуру задачі пошуку трасування мінімальної щільності. Наявність фрагментарної структури дозволяє використовувати стандартну еволюційну модель на перестановках для пошуку наближених рішень. The printed circuit board (PCB) routing in a contact high-density region is an important and difficult technical task. The main structural and technological constraints are the density distribution of the conductors, the number of layers, the number of vias and others. The single-layer and two-layer routing problems on the PCB with a matrix arrangement of the contacts are considered. The construction of the feasible routing solution set mapping into the set of code words over a finite alphabet is described. The properties of the set of code words are investigated. The concepts of full word, 1-regular and 2-regular words are introduced. The routing algorithm for code word realization is designed. It is shown that every full single-layer routing solution is determined by 1-regular word up to equivalence, and, conversely, the realization of each 1-regular word defines a full single-layer routing solution. It is established that the two-layer routing realization set corresponds to each 2-regular word. It is well founded that any full two-layer routing solution is a 2-regular word realization. It is grounded that both 1-regular and 2-regular word sets can be represented as a maximal fragment set of some fragmentary structure. The 1-regular and 2-regular word generation algorithms are introduced. The concept of routing solution density is presented and the problem of the minimal density routing solution search as the combinatorial optimization problem on the set of feasible words is formulated. Based on the fragmentary representation, the evolutionaryfragmentary model of the routing problem, where search space is a permutation set, is proposed. As the crossover operator in the model, the binary operator, which keeps the sequence of the elements in permutations is selected. The mutation operator in this model implements transposition of two random elements in the permutation. The proposed approach allows to use the universal method of the approximate optimal solutions searching, based on evolutionary-fragmentary model, for the routing problems. ru Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Программная инженерия и программные средства Моделирование однослойных и двухслойных трассировок Моделювання одношарових і двошарових трасувань Modelling of the Single-Layer and Two-Layer Routing Problems Article published earlier |
| spellingShingle | Моделирование однослойных и двухслойных трассировок Козин, И.В. Кривцун, Е.В. Программная инженерия и программные средства |
| title | Моделирование однослойных и двухслойных трассировок |
| title_alt | Моделювання одношарових і двошарових трасувань Modelling of the Single-Layer and Two-Layer Routing Problems |
| title_full | Моделирование однослойных и двухслойных трассировок |
| title_fullStr | Моделирование однослойных и двухслойных трассировок |
| title_full_unstemmed | Моделирование однослойных и двухслойных трассировок |
| title_short | Моделирование однослойных и двухслойных трассировок |
| title_sort | моделирование однослойных и двухслойных трассировок |
| topic | Программная инженерия и программные средства |
| topic_facet | Программная инженерия и программные средства |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/113319 |
| work_keys_str_mv | AT koziniv modelirovanieodnosloinyhidvuhsloinyhtrassirovok AT krivcunev modelirovanieodnosloinyhidvuhsloinyhtrassirovok AT koziniv modelûvannâodnošarovihídvošarovihtrasuvanʹ AT krivcunev modelûvannâodnošarovihídvošarovihtrasuvanʹ AT koziniv modellingofthesinglelayerandtwolayerroutingproblems AT krivcunev modellingofthesinglelayerandtwolayerroutingproblems |