Simplification of Boolean Functions Using Boolean Differences

Abstract

This paper presents a new method for simplification of Boolean functions based on Boolean differences. The proposed method is applicable to various forms of Boolean functions, including truth tables and Binary Decision Diagrams (BDDs). The Boolean differences are extended to cover the truth tables with don't-care components and cutset graphs in BDDs. The results of simplification agree with Quine-McCluskey and ESPRESSO methods. Experimental tests on MCNC and Berkeley PLA benchmarks show that the proposed method gains a performance of 1.5-10 times faster than ESPRESSO. The algorithms of the proposed method are implemented in Java/Perl/C++, and a toolset for logic function simplification is developed.