A tree search algorithm for low multiplicative complexity logic design

Jia Jun Tay, M. L. Dennis Wong, Ming Ming Wong, Cishen Zhang, Ismat Hijazin

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)
48 Downloads (Pure)


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 ve 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.
Original languageEnglish
Pages (from-to)132-143
Number of pages12
JournalFuture Generation Computer Systems
Early online date3 Feb 2018
Publication statusPublished - Jun 2018


Dive into the research topics of 'A tree search algorithm for low multiplicative complexity logic design'. Together they form a unique fingerprint.

Cite this