Fast Algebraic Rewriting Based on And-Inverter Graphs
Authors:
- 13 November 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 37 (9) , 1907-1911
Abstract
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.Keywords
Funding Information
- National Science Foundation (CCF-1319496, CCF-1617708)
- NSA grant Enhanced Equivalence Checking in Crypto-Analytic Applications
This publication has 16 references indexed in Scilit:
- Formal Verification Using Don't-Care and Vanishing Polynomials2016
- Formal Verification of Arithmetic Circuits by Function ExtractionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2016
- Efficient Symbolic Computation for Word-Level Abstraction From Combinational Circuits for Verification Over Finite FieldsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2015
- Verification of gate-level arithmetic circuits by function extraction2015
- Groebner basis based formal verification of large arithmetic circuits using Gaussian elimination and cone-based polynomial extractionMicroprocessors and Microsystems, 2015
- STABLE: A new QF-BV SMT solver for hard verification problems combining Boolean reasoning with computer algebra2011
- Z3: An Efficient SMT Solver2008
- DAG-aware AIG rewriting a fresh look at combinational logic synthesis2006
- Using SAT for combinational equivalence checking2002
- A new retiming-based technology mapping algorithm for LUT-based FPGAs1998