Equivalence Verification of Polynomial Datapaths Using Ideal Membership Testing
Authors:
- 18 June 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 26 (7) , 1320-1330
Abstract
This paper addresses the equivalence verification problem of register-transfer level (RTL) descriptions that implement arithmetic computations (such as add, mult) over bit vectors with finite widths. A bit vector of size represents integer values from 0 to 2m-1, implying that the corresponding integer values are reduced modulo 2m(%2m). This suggests that bit-vector arithmetic can be efficiently modeled as algebra over finite integer rings, where the bit-vector size (m) dictates the cardinality of the ring (Z2 m). This paper models the arithmetic datapath verification problem as the equivalence testing of polynomial functions from Z2 n 1timesZ2 n 2times...timesZ2 n drarrZ2 m. We formulate the equivalence problem into that of proving whether f-gequiv0%2m. Fundamental concepts and results from ldquonumber,rdquo ldquoring,rdquo and ldquoideal theoryrdquo are subsequently employed to develop systematic complete algorithmic procedures to solve the problem. We demonstrate the application of the proposed theoretical concepts to high-level (behavioral/RTL) verification of bit-vector arithmetic within practical computer-aided design settings. Using our approach, we verify a set of arithmetic datapaths at RTL, where contemporary verification approaches prove to be infeasible.Keywords
This publication has 22 references indexed in Scilit:
- Computing Gröbner Bases for Vanishing Ideals of Finite Sets of Points2006
- Improved use of the carry-save representation for the synthesis of complex arithmetic circuits2005
- Computer Algebra Handbook2003
- On polynomial functions from Zn1 × Zn2 × … × Znr to ZmDiscrete Mathematics, 1996
- VIS: A system for verification and synthesis1996
- On polynomial functions from Zn to ZmDiscrete Mathematics, 1995
- Probabilistic Algorithms for Deciding Equivalence of Straight-Line ProgramsJournal of the ACM, 1983
- On polynomial functions (mod m)Journal of Number Theory, 1974
- A Generalization of Fermat's TheoremProceedings of the American Mathematical Society, 1957
- MiscellaneaThe American Mathematical Monthly, 1918