Faster synthesis of combinational logic based on multiplexer trees and binary decision diagrams

Multiplexers are well known as a basic building element of digital and mixed signal circuits thanks to their ability to perform any Boolean function. Optimization is a significant part of synthesis of combinational logic, since performance has to be improved, area and power consumption have to be reduced. The paper presents a novel faster optimization method for multiplexer trees using basic BDD reduction methods, residual variables, a hash table and top-down approach. An option to automatically replace some multiplexers in the multiplexer tree with basic logic gates has been added in order to achieve better results. This method also works with multiple Boolean functions at once so that we can design circuits with more than one output. Experimental results show that implemented algorithm reduces total amount of multiplexers in optimized multiplexer tree by up to 99,99% in comparison to non-optimized multiplexer tree. In addition up to 63,46% of multiplexers can be replaced with a logic gate OR, AND or XOR, which can reduce total amount of transistors needed to realise given combinational logic by up to 24,23%.