A tree search algorithm for low multiplicative complexity logic design

作者：Tay Jia Jun^*; Wong M L Dennis; Wong Ming Ming; Zhang Cishen; Hijazin Ismat

来源：Future Generation Computer Systems-The International Journal of eScience, 2018, 83: 132-143.

DOI：10.1016/j.future.2018.01.063

• Logic design
• Multiplicative complexity
• Function decomposition
• Tree search algorithm

Low multiplicative complexity logic design is a useful heuristic to achieve low gate count implementation of logic circuit. In this work, we propose a deterministic approach based on the currently known lower and upper bounds of multiplicative complexity for logic minimization problems with not more than five inputs. The proposed tree search algorithm achieves circuit minimization through decomposition of Positive Polarity Reed-Muller expressions. This approach allows low multiplicative complexity logic design to be executed without the consistency issue associated with the randomized approach in the original algorithm. Experimental results show over 85% improvement in computation time compared to solving the same problems using the previous randomized approach. We also demonstrate that the quality of results produce by the proposed algorithm is comparable, and in some cases, better than the results reported in previous works using the same heuristic.

• 出版日期2018-6
• 单位南阳理工学院