Verified Technology Mapping in an Agda DSL for Circuit Design: Circuit refinement through gate and data concretisation

Abstract

The use of mechanized proofs for verification of programming language metatheory is a well-established field of study, as is the application of analogous results to the design of digital circuits. Our interest resides in the use of dependent types to formalize and verify circuit transformations. In this specific paper we focus on the technology mapping step of the circuit design flow, which can be seen as a well-typed substitution of syntax for (primitive) semantics. We formalize the technology mapping refinement and show that it indeed preserves state-transition semantics, since it is compositional.