DESIGN OF HEURISTIC ALGORITHMS BASED ON SHANNON EXPANSION FOR LOW-POWER LOGIC-CIRCUIT SYNTHESIS

A pair of heuristic algorithms based on Shannon expansion are proposed for the synthesis of low-power combinational circuits. Selecting an i nput variable for a given function, the bipartitioning algorithm perfo rms Shannon expansion with respect to a selected variable to reduce th e power dissipation of the subcircuit implementing the cofactor. The m ultiple partitioning algorithm partitions a given circuit into several subcircuits such that only a subcircuit can be activated at a time to reduce unnecessary signal transitions. In the algorithm, a circuit is recursively partitioned by applying Shannon expansion as long as powe r consumption is reduced. Experimental results for the MCNC benchmarks show that the bipartitioning and multiple partitioning algorithms bas ed on Shannon expansion are effective by generating circuits consuming 39.1 and 50.5% less power on the average, respectively, when compared to the conventional algorithm based on precomputation logic.