Geodesic
Asymptotically sharp estimates for the area of multiplexers in the cellular circuit model
Diskretnaya Matematika, Tome 34 (2022) no. 4, pp. 52-68

Voir la notice de l'article provenant de la source Math-Net.Ru

A general cellular circuit of functional and switching elements (CCFSE) is a mathematical model of integral circuits (ICs), which takes into account peculiarities of their physical synthesis. A principal feature of this model distinguishing it from the well-known classes of circuits of gates (CGs) is the presence of additional requirements on the geometry of the circuit which ensure the accounting of the necessary routing resources for IC creation. The complexity of implementation of a multiplexer function of Boolean algebra (FBA) in different classes of circuits has been extensively studied. In the present paper, we give asymptotically sharp upper and lower estimates for the area of a CCFSE implementing a multiplexer FBA of order $n$. We construct a family of circuit multiplexers of order $n$ of area equal to the halved upper estimate, and provide a method of delivering the corresponding lower estimate.
Keywords: planar circuit, very large scale integration, lookup function, multiplexer, Boolean circuit, cellular circuit. 
@article{DM_2022_34_4_a4,
     author = {S. A. Lozhkin and V. S. Zizov},
     title = {Asymptotically sharp estimates for the area of multiplexers in the cellular circuit model},
     journal = {Diskretnaya Matematika},
     pages = {52--68},
     publisher = {mathdoc},
     volume = {34},
     number = {4},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2022_34_4_a4/}
}
TY  - JOUR
AU  - S. A. Lozhkin
AU  - V. S. Zizov
TI  - Asymptotically sharp estimates for the area of multiplexers in the cellular circuit model
JO  - Diskretnaya Matematika
PY  - 2022
SP  - 52
EP  - 68
VL  - 34
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2022_34_4_a4/
LA  - ru
ID  - DM_2022_34_4_a4
ER  - 
%0 Journal Article
%A S. A. Lozhkin
%A V. S. Zizov
%T Asymptotically sharp estimates for the area of multiplexers in the cellular circuit model
%J Diskretnaya Matematika
%D 2022
%P 52-68
%V 34
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2022_34_4_a4/
%G ru
%F DM_2022_34_4_a4
S. A. Lozhkin; V. S. Zizov. Asymptotically sharp estimates for the area of multiplexers in the cellular circuit model. Diskretnaya Matematika, Tome 34 (2022) no. 4, pp. 52-68. http://geodesic.mathdoc.fr/item/DM_2022_34_4_a4/