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.
decomposition logic functional minimum transition activity minimal transit activation age portability systems logic synthesis low power power technologies optimality technology mapping map multi-level network network two-input gates power dissipation implementation power consumption paper tree case zero gate delay model delays model algorithm optimum solution extensibility boolean networks experimentation standardization benchmark logic gates boolean functions circuit cad circuit optimisation sis logic synthesis system minimisation of switching nets cmos logic circuits input static cmos circuits huffman algorithm logic functions decomposition nonzero gate delay model logic cad