Decomposition of logic functions for minimum transition activity

In this age of portable electronic systems, the problem of logic synthesis for low power has acquired great importance. The most popular approach has been to target the widely-accepted two-phase paradigm of technology-independent optimization and technology mapping for power minimization. Before mapping, each function of a multi-level network is decomposed into two-input gates. How this decomposition is done can have a significant impact on the power dissipation of the final implementation. The problem of decomposition for low power was recently addressed by Pedram et al. (1993). However, they ignore the power consumption due to glitches, which can be a sizeable fraction of the total power. In this paper, we show how to obtain a transition-optimum binary tree decomposition (i.e., the one which has minimum number of transitions in the worst case, including those due to glitches) for some specific functions (AND, OR, and EX-OR) for zero gate delay model. For a non-zero gate delay model, we present conditions under which our algorithm yields an optimum solution for such functions. We propose a straightforward extension of this algorithm for arbitrary functions and Boolean networks. Experimental results on a set of standard combinational benchmarks indicate that on average, our algorithm generates networks (using two-input gates) that have 16% fewer transitions in the worst case than the networks generated by a simple-minded two-input technology-decomposition algorithm implemented in sis, a widely used logic synthesis system