Advances in Computer Science and Information Technology. Computer Science and Information Technology. Second International Conference, CCSIT 2012, Bangalore, India, January 2-4, 2012. Proceedings, Part III

Research Article

Minimizing Boolean Sum of Products Functions Using Binary Decision Diagram

Download
213 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-27317-9_5,
        author={Debajit Sensarma and Subhashis Banerjee and Krishnendu Basuli and Saptarshi Naskar and Samar Sarma},
        title={Minimizing Boolean Sum of Products Functions Using Binary Decision Diagram},
        proceedings={Advances in Computer Science and Information Technology. Computer Science and Information Technology. Second International Conference, CCSIT 2012, Bangalore, India, January 2-4, 2012. Proceedings, Part III},
        proceedings_a={CCSIT PART  III},
        year={2012},
        month={11},
        keywords={Binary Decision Diagram DSOP Unate Function Binate Function},
        doi={10.1007/978-3-642-27317-9_5}
    }
    
  • Debajit Sensarma
    Subhashis Banerjee
    Krishnendu Basuli
    Saptarshi Naskar
    Samar Sarma
    Year: 2012
    Minimizing Boolean Sum of Products Functions Using Binary Decision Diagram
    CCSIT PART III
    Springer
    DOI: 10.1007/978-3-642-27317-9_5
Debajit Sensarma1,*, Subhashis Banerjee1,*, Krishnendu Basuli1,*, Saptarshi Naskar2,*, Samar Sarma3,*
  • 1: West Bengal State University
  • 2: Sarsuna College
  • 3: University Of Calcutta
*Contact email: mail.sb88@gmail.com, debajit.sensarma2008@gmail.com, krishnendu.basuli@gmail.com, sapgrin@gmail.com, Sssarma2001@yahoo.com

Abstract

Two-level logic minimization is a central problem in logic synthesis, and has applications in reliability analysis and automated reasoning. This paper represents a method of minimizing Boolean sum of products function with binary decision diagram and with disjoint sum of product minimization. Due to the symbolic representation of cubes for large problem instances, the method is orders of magnitude faster than previous enumerative techniques. But the quality of the approach largely depends on the variable ordering of the underlying BDD. The application of Binary Decision Diagrams (BDDs) as an efficient approach for the minimization of Disjoint Sums-of-Products (DSOPs). DSOPs are a starting point for several applications.