Efficient Symbolic Computation for Word-Level Abstraction From Combinational Circuits for Verification Over Finite Fields
Authors:
- 17 November 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 35 (7) , 1206-1218
Abstract
This paper introduces a technique to derive a word-level abstraction of the function implemented by a combinational logic circuit. The abstraction provides a canonical representation of the function as a polynomial ${Z} {= {\mathcal {F}}(A)}$ over the finite field $ {{\mathbb {F}}_{2^{k}}}$ , where ${Z}$ and $ {A}$ represent the ${k}$ -bit output and input bit-vectors (words) of the circuit, respectively. This canonical abstraction can be utilized for formal verification and equivalence checking of combinational circuits. Our approach to abstraction is based upon concepts from computational commutative algebra and algebraic geometry. We show that the abstraction ${Z} {= {\mathcal {F}}(A)}$ can be derived by computing a Gröbner basis of the polynomials corresponding to the circuit, using a specific elimination term order derived from the circuit’s topology. Computing Gröbner bases using elimination term orders is infeasible for large circuits. To overcome this limitation, we describe an efficient symbolic computation to derive the word-level polynomial. Our algorithms exploit: 1) the structure of the circuit; 2) the properties of Gröbner bases; 3) characteristics of finite fields $ {{\mathbb {F}}_{2^{k}}}$ ; and 4) modern algorithms from symbolic algebra, to derive the canonical polynomial representation. This approach is employed to verify (and detect bugs in) large combinational finite field arithmetic circuits, where contemporary verification techniques are known to be infeasible.Keywords
Funding Information
- U.S. National Science Foundation through the Division of Computing and Communication Foundations (CCF-1320335, CCF-1320385)
This publication has 17 references indexed in Scilit:
- Verification of gate-level arithmetic circuits by function extraction2015
- Function Extraction from Arithmetic Bit-Level Circuits2014
- Quantifier Elimination over Finite Fields Using Gröbner Bases2011
- Modular Datapath Optimization and Verification Based on Modular-HEDIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2010
- Bug AttacksLecture Notes in Computer Science, 2008
- A Technique for Representing Multiple Output Binary Functions with Applications to Verification and SimulationIEEE Transactions on Computers, 2007
- Equivalence Verification of Polynomial Datapaths Using Ideal Membership TestingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2007
- Taylor Expansion Diagrams: A Canonical Representation for Verification of Data Flow DesignsIEEE Transactions on Computers, 2006
- Montgomery Multiplication in GF(2k)Designs, Codes and Cryptography, 1998
- A new architecture for a parallel finite field multiplier with low complexity based on composite fieldsIEEE Transactions on Computers, 1996