A tree search algorithm for low multiplicative complexity logic design
| Autor: | Cishen Zhang, M. L. Dennis Wong, Jia Jun Tay, Ming Ming Wong, Ismat Hijazin |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Computer Networks and Communications
Computer science Heuristic (computer science) Computation 020208 electrical & electronic engineering 02 engineering and technology Tree traversal Logic synthesis Gate count Hardware and Architecture Logic gate 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Circuit minimization for Boolean functions Algorithm Software |
| Zdroj: | Future Generation Computer Systems. 83:132-143 |
| ISSN: | 0167-739X |
| DOI: | 10.1016/j.future.2018.01.063 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect