Fast Algebraic Rewriting Based on And-Inverter Graphs
Fast Algebraic Rewriting Based on And-Inverter Graphs
复制标题
基于与逆图的快速代数重写
DOI：
10.1109/tcad.2017.2772854
复制
发表时间：
2018
影响因子：
2.9
通讯作者：
A. Mishchenko
中科院分区：
文献类型：
--
作者：
Cunxi Yu;M. Ciesielski;A. Mishchenko
使用计算机代数技术构造代数多项式被认为是分析门级算术电路的最新技术。然而，现有的方法直接对门级网表进行代数重写，存在潜在的内存爆炸问题。介绍了一种基于门级设计与反相图表示的代数重写技术。利用基于AIG的割计数和真值表计算，确定了代数重写的有效阶，从而大大简化了构造中的多项式。文中还提出了一种通过处理冗余多项式进一步降低代数重写复杂度的自动方法。
Constructing algebraic polynomials using computer algebra techniques is believed to be state-of-the-art in analyzing gate-level arithmetic circuits. However, the existing approach applies algebraic rewriting directly to the gate-level netlist, which has potential memory explosion problem. This paper introduces an algebraic rewriting technique based on the and-inverter graph (AIG) representation of gate-level designs. Using AIG-based cut-enumeration and truth table computation, an efficient order of algebraic rewriting is identified, resulting in dramatic simplifications of the polynomial under construction. An automatic approach, which further reduces the complexity of algebraic rewriting by handling redundant polynomials, is also proposed.