Logic Optimization Algorithm based on Shannon’s Expansion: Reduction in Area, Power and Delay for Pass Gate Implementation

Abstract

The reduction in hardware requirement for any application does not only guarantee the reduction of chip area but also significantly reduces the corresponding power consumption and delays. Hence, any heuristic used to reduce the hardware requirement for given logic is always well justified. In this paper, the number of pass gates required to implement the given Boolean Logic is reduced by sizeable amount with use of the proposed algorithm for logic expansion. The proposed algorithm defines the criteria for selection of literals at each step of Shannon’s expansion. In this paper, the reduction in hardware requirement for various Boolean Logics implemented using the Complementary metal–oxide–semiconductor (CMOS) Pass Gate technology is demonstrated with necessary example. The limitation of existing heuristic which is applicable to Boolean Function with non-repeated literals only is overcome in the proposed work. The proposed “Literal Selection Algorithm for Shannon’s Expansion” is applicable to all type of Boolean functions i.e. may be with all individual literals or having repeated literals and also demonstrates the promising results. This work can be further extended to dynamic logic.

Keywords: Boolean function, Shannon expansion, pass gate, transmission gate logic circuits