Incremental column-wise verification of arithmetic circuits using computer algebra
Formal Methods in System Design · 2020-12 · 56 (1-3) · 22-54
DOI: 10.1007/s10703-018-00329-2 ↗Kurz gefasst
Fachartikel in der Zeitschrift Formal Methods in System Design, online erschienen am 26.02.2019. Verfasst von Daniela Kaufmann und 2 weiteren Autor:innen. Beteiligte Einrichtung: Institute for Formal Models and Verification, Johannes Kepler University, Linz, Austria. Die Arbeit wurde bisher 27-mal zitiert (Crossref) und nennt 37 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Austrian Science Fund FWF, Austrian Science Fund.
Abstract (Originalsprache)
Verifying arithmetic circuits and most prominently multiplier circuits is an important problem which in practice still requires substantial manual effort. The currently most effective approach uses polynomial reasoning over pseudo boolean polynomials. In this approach a word-level specification is reduced by a Gröbner basis which is implied by the gate-level representation of the circuit. This reduction returns zero if and only if the circuit is correct. We give a rigorous formalization of this approach including soundness and completeness arguments. Furthermore we present a novel incremental column-wise technique to verify gate-level multipliers. This approach is further improved by extracting full- and half-adder constraints in the circuit which allows to rewrite and reduce the Gröbner basis. We also present a new technical theorem which allows to rewrite local parts of the Gröbner basis. Optimizing the Gröbner basis reduces computation time substantially. In addition we extend these algebraic techniques to verify the equivalence of bit-level multipliers without using a word-level specification. Our experiments show that regular multipliers can be verified efficiently by using off-the-shelf computer algebra tools, while more complex and optimized multipliers require more sophisticated techniques. We discuss in detail our complete verification approach including all optimizations.
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- Institute for Formal Models and Verification, Johannes Kepler University, Linz, Austria.
- Institute for Algebra, Johannes Kepler University, Linz, Austria.
ORCID-Profile: Armin Biere
Förderung
- Austrian Science Fund FWF
- Austrian Science Fund
Zitieren
APA
Kaufmann, D., Biere, A., & Kauers, M. (2020). Incremental column-wise verification of arithmetic circuits using computer algebra. Formal Methods in System Design, 56(1-3), 22-54. https://doi.org/10.1007/s10703-018-00329-2
Vancouver
Kaufmann D, Biere A, Kauers M. Incremental column-wise verification of arithmetic circuits using computer algebra. Formal Methods in System Design. 2020;56(1-3):22-54. doi:10.1007/s10703-018-00329-2
BibTeX
@article{Kaufmann2020,
author = {Kaufmann, Daniela and Biere, Armin and Kauers, Manuel},
title = {Incremental column-wise verification of arithmetic circuits using computer algebra},
journal = {Formal Methods in System Design},
year = {2020},
volume = {56},
number = {1-3},
pages = {22--54},
doi = {10.1007/s10703-018-00329-2}
}
EUVIMED