Journal of VLSI Design Tools and Technology
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 circuitsKeywords
References (8)
- Shannon, Claude E. , The Synthesis of Two-Terminal Switching Circuits, Bell System Technical Journal 1949; 28: 59 – 98p.
- H. Kim, I. S. Choi, H. Y. Hwang, Design of Heuristic Algorithms based on Shannon Expansion for Low-Power Logic Synthesis, Circuits, Devices and Systems, IEEE Proceedings , 1997; 144(6): 355– 360p.
- Jose Luis Neves, Alexander Albicki, A Pass Transistor Regular Structure for Multilevel Combinational Circuits , ASIC Conference and Exhibit, 1994. Proceedings, Seventh Annual IEEE International 1994; 88–91p.
- Rupesh S. Shelar, Sachin S. Sapatnekar, An Efficient Algorithm for Low Power Pass Transistor Logic Synthesis , Design Automation Conference, 2002. Proceedings of ASP -DAC 2002. 7th Asia and South Pacific and the 15th International Conference on VLSI Design. Proceedings, 2002; 87–92p.
- Theodore F. Tabloski, Frederic J. Mowle , A Numerical Expansion Technique and Its Application to Minimal Multiplexer Logic Circuits, Computers, IEEE Transactions on, 1976; C-25( 7): 684– 702p.
- S. Ghosh, S. Bhunia, K. Roy, Shannon Expansion Based Supply-Gated Logic for Improved Power and Testability, Test Symposium, 2005. Proceedings. 14th Asian, 2005; 404–409p.
- Siwat Saibua, Po-Yu Kuo, Dian Zhou, et al. A Folding Strategy for SAT Solvers based on Shannon’s Expansion Theorem, SOC Conference (SOCC), 2010 IEEE International, 2010; 177–181p.
- K T Lau., I mplementation of Digital IC Functions with Pass Transistor Switching circuits, Consumer Electronics, IEEE Transactions on 1988; 34(2): 318–320p.