Abstract
We present the mechanical verification of an algorithm for building a BDD from an AND/INVERTER graph (AIG). The algorithm uses two methods to simplify an input AIG using BDDs of limited size; it repeatedly applies these methods while varying the BDD size limit. One method is similar to dynamic weakening in that it replaces oversized BDDs by a conservative approximation; the other method introduces fresh variables to represent oversized BDDs. This algorithm is written in the executable logic of the ACL2 theorem prover. The primary contribution is the verification of our conversion algorithm. We state its correctness theorem and outline the major steps needed to prove it.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aagaard, M.D., Jones, R.B., Seger, C.-J.H.: Formal verification using parametric representations of boolean constraints. In: Proceedings of the 36th Design Automation Conference, pp. 402–407 (1999)
Berman, C.L., Trevillyan, L.H.: Functional comparison of logic designs for VLSI circuits. In: IEEE International Conference on Computer-Aided Design, November 5-9, pp. 456–459 (1989)
Boyer, R.S., Hunt Jr, W.A.: Function memoization and unique object representation for ACL2 functions. In: ACL ’06: Proceedings of the sixth international workshop on the ACL2 theorem prover and its applications, pp. 81–89. ACM, New York (2006)
Hazelhurst, S., Seger, C.-J.H.: Symbolic trajectory evaluation. In: Kropf, T. (ed.) Formal Hardware Verification. LNCS, vol. 1287, pp. 3–78. Springer, Heidelberg (1997)
Hunt Jr., W.A., Swords, S.: Centaur technology media unit verification. In: Bouajjani, A., Maler, O. (eds.) CAV 2009. LNCS, vol. 5643, pp. 353–367. Springer, Heidelberg (2009)
Kaufmann, M., Moore, J.S., Boyer, R.S.: ACL2 version 3.3 (2008), http://www.cs.utexas.edu/~moore/acl2/
Kaufmann, M., Moore, J.S., Manolios, P.: Computer-Aided Reasoning: An Approach. Kluwer Academic Publishers, Norwell (2000)
Kuehlmann, A., Ganai, M.K., Paruthi, V.: Circuit-based boolean reasoning. In: Proceedings of the 38th Design Automation Conference, pp. 232–237 (2001)
Kuehlmann, A., Krohm, F.: Equivalence checking using cuts and heaps. In: Proceedings of the 34th Design Automation Conference, June 9-13, pp. 263–268 (1997)
Melham, T.F., Jones, R.B.: Abstraction by symbolic indexing transformations. In: Aagaard, M.D., O’Leary, J.W. (eds.) FMCAD 2002. LNCS, vol. 2517, pp. 1–18. Springer, Heidelberg (2002)
Seger, C.-J.H., Jones, R.B., O’Leary, J.W., Melham, T., Aagaard, M.D., Barrett, C., Syme, D.: An industrially effective environment for formal hardware verification. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 24(9), 1381–1405 (2005)
Somenzi, F.: CUDD: CU decision diagram package release 2.4.1 (2005), http://vlsi.colorado.edu/~fabio/CUDD/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Swords, S., Hunt, W.A. (2010). A Mechanically Verified AIG-to-BDD Conversion Algorithm. In: Kaufmann, M., Paulson, L.C. (eds) Interactive Theorem Proving. ITP 2010. Lecture Notes in Computer Science, vol 6172. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14052-5_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-14052-5_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14051-8
Online ISBN: 978-3-642-14052-5
eBook Packages: Computer ScienceComputer Science (R0)