A heuristic approach to variable ordering for logic synthesis engine design: algorithmic insight. (1st January 2014)

• Record Type: Journal Article
• Authors: Arora, Harsh; Banerjee, Arindam; Jidge, Rahul Rupchand
• Is Part Of: International journal of circuits and architecture design. Volume 1:Number 2(2014)
• Page Start: 141
• Page End: 155
• Publication Date: 2014-01-01
• Subjects: logic minimisation -- binary decision diagram -- BDD -- reduced ordered binary decision diagrams -- ROBDD -- variable ordering; Electronic circuit design -- Periodicals; Electronic circuit design -- Mathematical models -- Periodicals; Computer-aided design -- Periodicals; Computer engineering -- Periodicals; 621.381505
• Languages: English
• ISSNs: 2051-7025

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.