Understanding Algebraic Rewriting for Arithmetic Circuit Verification: A Bit-Flow Model
- 23 April 2019
- 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. 39 (6) , 1346-1357
Abstract
This paper addresses theoretical aspects of arithmetic circuit verification based on algebraic rewriting. Its goal is to advance the understanding of algebraic techniques for arithmetic circuit verification in the context of symbolic computer algebra. The paper offers a new insight into the arithmetic circuit verification problem, by viewing the computation performed by the circuit as the flow of digital data. In the proposed bit-flow model , the circuit is modeled as a network of logic components satisfying a bit-flow conservation law . We prove that the value of the flow of data in the circuit is invariant throughout the circuit and use this to prove soundness and completeness of the rewriting technique, independently from the computer algebra arguments. The efficiency of the method is illustrated with impressive results for large integer multipliers. The verification system and benchmarks are offered in an open source software environment.Keywords
Funding Information
- National Science Foundation (CCF-1617708)
This publication has 19 references indexed in Scilit:
- Column-wise verification of multipliers using computer algebra2017
- Formal Verification of Arithmetic Circuits by Function ExtractionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2016
- Logic Debugging of Arithmetic Circuits2015
- Arithmetic Bit-Level Verification Using Network Flow Model2013
- STABLE: A new QF-BV SMT solver for hard verification problems combining Boolean reasoning with computer algebra2011
- ABC: An Academic Industrial-Strength Verification Tool2010
- An Algebraic Approach for Proving Data Correctness in Arithmetic Data PathsLecture Notes in Computer Science, 2008
- Efficient construction of binary moment diagrams for verifying arithmetic circuits2002
- A new efficient algorithm for computing Gröbner bases (F4)Journal of Pure and Applied Algebra, 1999
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986