Control Systems and Computers, N2, 2016, Article 7
DOI: https://doi.org/10.15407/usim.2016.02.058
Upr. sist. maš., 2016, Issue 2 (262), pp. 58-64.
UDC 519.87
I.V. Kozin, Dr. (Ph.-Math.), E-mail: ainc00@gmail.com,
O.V. Kryvtsun, post-graduate student, E-mail: kryvtsun@ukr.net,
Zaporizhia National University, vul. Zhukovsky, 66, m. Zaporizhzhya, 69600
Modelling of the Single-Layer and Two-Layer
Routing Problems
Introduction. 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.
Methods. 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.
Results. 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 evolutionary-fragmentary 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.
Download full text! (Russian).
Keywords: routing problem, routing solution density, combinatorial optimization, fragmentary structure, evolutional model.
1. Luzin, S.YU., Polubasov, O.B. SAPR TopoR: trassirovka pechatnykh plat s BGA-komponentami. Sovremennaya elektronika. 2008. 7. pp. 44–49, http://www.soel.ru/ issues/ ?id=343867 (In Russian).
2. Zharikova, I.V., Kurapov, S.V., Nevlyudov I.SH. et. al., 2013. “Trassirovka podklyuchayushchey plastiny mnogozondovogo ustroystva kontrolya BGA-komponentov”. Visn. Zaporizsk. nats. un-tu. Fizyko-matematychni nauky, 2, pp. 28–36. (In Russian).
3. Kozin, I.V., Krivtsun, Ye.V., Pinchuk, V.P., 2015. “Evolyutsionno-fragmentarnaya model’ zadachi trassirovki”. Kibernetika i sistemnyy analiz, 51 (3), pp. 125–131. (In Russian).
4. Kozin, I.V., Polyuga, S.I., 2012. “O svoystvakh fragmentarnykh struktur”. Bulletin of Zaporozhye National Un-Tu: Zb. sciences works. Physics and mathematics. Zaporozhye: ZNU, 1, pp. 99-106. (In Russian).
Received 22.01.2016
