Logic Synthesis from Polynomials with Coefficients in the Field of Rationals
Logic Synthesis from Polynomials with Coefficients in the Field of Rationals
复制标题
DOI：
10.1109/ismvl57333.2023.00026
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Bhavani Sampathkumar;Bailey Martin;Ritaja Das;P. Kalla;Florian Enescu
中科院分区：
文献类型：
--
作者：
Bhavani Sampathkumar;Bailey Martin;Ritaja Das;P. Kalla;Florian Enescu
本文提出了一种新的概念，用系数在有理数域$(\mathbb{q})$中的多元多项式进行逻辑综合，其中变量只取布尔值。在使用基于计算机代数和代数几何的技术综合和验证算术电路期间会遇到这样的多项式。该方法以$\mathbb{q}$上具有二元变量的多项式f为输入，在两个元素的有限域$\Left({{\mathbb{F}_2}}\right)$上推导出相应的多项式f$，使得f具有与f相同的变种(零集).由于${\mathbb{F}_2}$与布尔代数同构，因此通过将乘积和和分别映射为与和和，可以将$\tilde f$转换为布尔网络.我们证明了我们的代数变换的正确性，并给出了相应的递归算法。在{\mathbb{F}_2}中的平移的$\tilde f\结果对应于正Davio分解，并且使用显式和隐式表示来计算。该方法被用于部分综合框架下的算术电路子功能的综合。我们的方法的有效性在各种整数乘法器架构上得到了验证，在这些架构中，其他当代的方法是不可行的。
This paper introduces a novel concept of performing logic synthesis from multivariate polynomials with coefficients in the field of rationals $(\mathbb{Q})$, where the variables take only Boolean values. Such polynomials are encountered during synthesis and verification of arithmetic circuits using computer algebra and algebraic geometry based techniques. The approach takes as input a polynomial f over $\mathbb{Q}$ with binary variables, and derives a corresponding polynomial $\tilde f$ over the finite field $\left( {{\mathbb{F}_2}} \right)$ of two elements, such that f has the same variety (zero-set) as f. As ${\mathbb{F}_2}$ is isomorphic to Boolean algebra, $\tilde f$ can be translated to a Boolean network by mapping the products and sums as AND and XOR operators, respectively. We prove the correctness of our algebraic transformation, and present a recursive algorithm for the same. The translated $\tilde f \in {\mathbb{F}_2}$ resultingly corresponds to a positive Davio decomposition, and is computed using both explicit and implicit representations. The approach is used to synthesize subfunctions of arithmetic circuits, under the partial synthesis framework. The efficacy of our approach is demonstrated over various integer multiplier architectures, where other contemporary approaches are infeasible.