Scholarlink

Abstract <p>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 (VLSIs), which take 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 circuits) 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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11970_2025_7226_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="102" /> </InlineMediaObject> <EquationSource Format="TEX">\(n,n=1,2,\ldots\)</EquationSource> <!--BMatMGU2570050Lozhkin-m1--> </InlineEquation>, that is, systems of all functions of the algebra of logic in <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11970_2025_7226_Article_IEq2.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="14" /> </InlineMediaObject> <EquationSource Format="TEX">\(n\)</EquationSource> <!--BMatMGU2570050Lozhkin-m2--> </InlineEquation> 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 multipoles of order <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11970_2025_7226_Article_IEq2.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="14" /> </InlineMediaObject> <EquationSource Format="TEX">\(n\)</EquationSource> <!--BMatMGU2570050Lozhkin-m3--> </InlineEquation> with an area equal to the upper bound is constructively built, and a method for obtaining the corresponding lower bound is proposed.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Asymptotic Estimates of a High Degree of Accuracy for the Complexity of a Universal Multipole in a Model of Cellular Circuits

  • 期刊论文

  • 发表日期：

    2025年8月1日

查看全文
  • S. A. Lozhkin,
  • V. S. Zizov

摘要

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 (VLSIs), which take 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 circuits) 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\) , that is, 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 multipoles 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.