Computing a perfect input assignment for probabilistic verification

Maxim Teslenko; Elena Dubrova; Hannu Tenhunen

doi:10.1117/12.607828

30 June 2005 Computing a perfect input assignment for probabilistic verification

Maxim Teslenko, Elena Dubrova, Hannu Tenhunen

Proceedings Volume 5837, VLSI Circuits and Systems II; (2005) https://doi.org/10.1117/12.607828
Event: Microtechnologies for the New Millennium 2005, 2005, Sevilla, Spain

Abstract

Design verification is the task of establishing that a given design meets the intended behavior. The growing complexity of verification instances requires new methods that can provide high quality verification coverage for large, complex designs. Probabilistic verification complements existing simulation-based and formal verification techniques by providing a distinct trade-off between coverage and capacity. Probabilistic approach maps two Boolean functions onto hash values and compare these values for equivalence. The major drawback of probabilistic verification is the non-zero probability of collision of hash values of two non-equivalent functions, producing "false positive" verification results. In this paper, we prove the existence of a perfect input assignment which never causes collisions. We show that the equivalence of hash values computed for a perfect input assignment implies the equivalence of functions with 100% probability.

Citation Download Citation

Maxim Teslenko, Elena Dubrova, and Hannu Tenhunen "Computing a perfect input assignment for probabilistic verification", Proc. SPIE 5837, VLSI Circuits and Systems II, (30 June 2005); https://doi.org/10.1117/12.607828

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available