A Recursive Paradigm to Solve Boolean Relations
Open Access
- 12 September 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 58 (4) , 512-527
Abstract
A Boolean relation can specify some types of flexibility of a combinational circuit that cannot be expressed with don't cares. Several problems in logic synthesis, such as Boolean decomposition or multilevel minimization, can be modeled with Boolean relations. However, solving Boolean relations is a computationally expensive task. This paper presents a novel recursive algorithm for solving Boolean relations. The algorithm has several features: efficiency, wide exploration of solutions, and customizable cost function. The experimental results show the applicability of the method in logic minimization problems and tangible improvements with regard to previous heuristic approaches.Keywords
This publication has 25 references indexed in Scilit:
- Safe BDD Minimization Using Don't Cares2005
- Minimization of Boolean relations2003
- Flexibility in Logic2002
- A survey of Boolean matching techniques for library bindingACM Transactions on Design Automation of Electronic Systems, 1997
- Optimization of combinational logic circuits based on compatible gatesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1995
- Two-level logic minimization: an overviewIntegration, 1994
- Heuristic minimization of multiple-valued relationsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993
- Multiple-Valued Minimization for PLA OptimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- Useless prime implicants of incompletely specified multiple-output switching functionsInternational Journal of Parallel Programming, 1980
- Minimization of Boolean Functions*Bell System Technical Journal, 1956