Implicit enumeration techniques applied to asynchronous circuit verification

The authors address the problem of verifying that the gate-level implementation of an asynchronous circuit, with given or extracted bounds on wire and gate delays, is equivalent to a specification of the asynchronous circuit behavior described as a classical flow table. They give a procedure to extract the complete set of possible flow tables from a gate-level description of an asynchronous circuit under the bounded wire delay model. Given an extracted flow table and the initial flow table specification, procedures are outlined to construct a product flow table to check for machine equivalence. Assuming discretized gate delays, it is shown that implicit enumeration techniques based on binary decision diagram representations can be used to efficiently verify asynchronous circuits.