SOP restructuring by exploiting don't cares

In this paper we define and study the properties of a generalized Shannon expansion on non-disjoint subsets of the Boolean space. This expansion consists in projecting the original function onto several overlapping subsets. Since the logic can be distributed among the projection subsets, input combinations asserted by a subset may be exploited as don't cares for the other subsets. Our target is to exploit these don't cares to obtain more compact networks based on SOP expressions. In particular, we show how to take advantage of don't cares, derived from the projections, in two synthesis techniques, i.e., using a Boolean and an algebraic algorithm. Experimental results show that in the Boolean case 65% of the considered benchmarks achieve more compact area when implemented using projected don't cares. The benefit in the algebraic approach is reduced (35% of instances benefit from the proposed technique), even though there are examples with an interesting decrease of the area.