On SAT-Based Model Checking of Speed-Independent Circuits

Abstract

Formal verification plays an important role in the quality assurance of digital circuits. Apart from the now standard equivalence checking between design steps, functional correctness can be proven with model checking. In one approach, a Boolean satisfiability (SAT) problem describing the circuit's implementation and expected properties is generated for each of a bounded number of time steps and fed to a SAT solver. In synchronous circuits, the time steps correspond to cycles of the global clock. The execution of asynchronous, specifically speed-independent (SI) circuits, however, relies on local handshakes instead of a global time reference. This absence of a global clock requires a different approach for choosing time steps for the SAT problem.This paper presents how bounded, SAT-based model checking can be used on SI asynchronous circuits. We aim to give a general and accessible introduction to this topic, highlight the inherent computational complexity and show that setting up a basic model checker for SI circuits is possible with quite simple means, without any reliance on (expensive) commercial tools. For our reference implementation used in the provided examples we use the open source Z3 solver.