Title: A heuristic approach to variable ordering for logic synthesis engine design: algorithmic insight

Authors: Harsh Arora; Arindam Banerjee; Rahul Rupchand Jidge

Addresses: Centre of Excellence in VLSI CAD/Advanced Computer Architecture, School of Computing Science and Engineering, Vellore Institute of Technology, Vellore-632014, Tamilnadu, India ' Centre of Excellence in VLSI CAD/Advanced Computer Architecture, School of Computing Science and Engineering, Vellore Institute of Technology, Vellore-632014, Tamilnadu, India ' Centre of Excellence in VLSI CAD/Advanced Computer Architecture, School of Computing Science and Engineering, Vellore Institute of Technology, Vellore-632014, Tamilnadu, India

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.

Keywords: logic minimisation; binary decision diagrams; BDD; reduced ordered BDD; ROBDD; variable ordering; logic synthesis; VLSI design.

DOI: 10.1504/IJCAD.2014.060703

International Journal of Circuits and Architecture Design, 2014 Vol.1 No.2, pp.141 - 155

Received: 06 Mar 2013
Accepted: 14 Jan 2014
Published online: 21 Jun 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article