A heuristic approach to variable ordering for logic synthesis engine design: algorithmic insight
by Harsh Arora; Arindam Banerjee; Rahul Rupchand Jidge
International Journal of Circuits and Architecture Design (IJCAD), Vol. 1, No. 2, 2014

Abstract: Logic synthesis is used in VLSI design to convert technology independent high level description of a complex electronic circuit into optimized gate level netlist. In Boolean algebraic factorisation, a logic expression is considered as polynomials. The conventional methods such as truth table, K-map, SOP/POS forms yield satisfactory results for the Boolean functions comprises of AND/OR expressions. But, optimality of Boolean factorisation for AND/OR/XOR intensive functions is degraded. In the proposed work, we plan to analyse vide detailed insight into a state of the art minimisation algorithm employing data structure to form the basis for synthesis engine. As the time and space complexities greatly depend on the number of nodes of the binary decision diagram (BDD), an appropriate variable ordering is essential to derive the optimal reduced ordered binary decision diagram (ROBDD). Our work proposes a heuristic approach to derive proper ordering of input variables for BDD tree with minimum computation to reduce the space complexity of the circuit, thereby enhancing the performance.

Online publication date: Sat, 21-Jun-2014

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Circuits and Architecture Design (IJCAD):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com