Abstract:
In general, a cellular circuit of functional and switching elements is a mathematical model of integrated circuits and, first of all, very large-scale integrated circuits (VLSI), which takes into account the features of their physical synthesis. The fundamental difference of this model from the well-studied classes of circuits of functional elements (Boolean cicruits) is the presence of additional requirements for the geometry of the circuit, which ensure that the necessary routing resources are taken into account when creating VLSI. The subject of study by many authors was the complexity of the implementation of the so-called universal multipole of order $ n, n=1, 2, \ldots, $ i.e. systems of all functions of the algebra of logic in $n$ Boolean variables in various classes of circuits. In this paper, we establish asymptotically tight bounds of a high degree of accuracy for the area of cellular circuits. At the same time, a family of circuit universal multipole of order $n$ with an area equal to the upper bound is constructively built, and a method for obtaining the corresponding lower bound is proposed.
Fulltext:
PDF file (324 kB)