Exact Modeling of Binary Decision Diagram Complexity

  • Authors

    • Mohamed Raseen
    • E Venitha
    2018-09-01
    https://doi.org/10.14419/ijet.v7i3.34.18976
  • Binary Decision Diagrams, Boolean Functions Complexity, Modeling.
  • An exact model of Binary Decision Diagram (BDD) complexity is derived in this paper. An estimate of BDD complexity using models has already been proposed. The estimated BDD complexity in previous papers is just an approximation of experimental data using a curve that fits the data. Mathematical analysis indicates that many curves can be fitted to the same data. This paper derives the exact model for the BDD complexity by analysis. In order to derive the exact model, relation between the SOP (Sum Of Product) terms and Min-terms was analyzed. Further the variation of BDD size for various Min-terms was also analyzed. Finally the plot between the experimental BDD size and the derived exact model proves the accuracy of the derived model.  

  • References

    1. [1] R. E. Bryant, "Graph-Based Algorithm for Boolean Function Manipulation," IEEE Trans. Computers, Vol. 35, pp. 677-691, 1986.

      [2] S. B. Akers, "Binary Decision Diagram," IEEE Trans. Computers, Vol. 27, pp. 509-516, 1978.

      [3] S. Minato, “Binary Decision diagrams and Applications for VLSICAD,†Kluwer Academic Publishers, 1995.

      [4] K. Priyank, “VLSI Logic Test, Validation and Verification, Properties & Applications of Binary Decision Diagrams,†Lecture Notes, Department of Electrical and Computer Engineering University of Utah, Salt Lake City, UT 84112.

      [5] M. Raseen, P.W.C. Prasad and A. Assi, "An Efficient Estimation of the ROBDD’s Complexity", Integration - The VLSI journal, Vol. 39, Issue 3, pp.211-228, Elsevier Publications, 2006.

      [6] M. Raseen, P.W.C. Prasad, and A. Assi, “Mathematical Model to Predict the Number of Nodes in an ROBDD,†The 47th IEEE International Midwest Symposium on Circuit and Systems (MWSCAS’ 2004), Vol. 3, pp. 431-434, Hiroshima, Japan, July 2004.

      [7] M. Raseen, Ali Assi, P.W.C. Prasad and A. Harb, “An Efficient Mathematical Estimation of the BDDs Complexityâ€, The 16th IASTED International Conference on Modelling and Simulation, pp 381-386, Mexico, May 2005

      [8] M. Raseen, P.W.C. Prasad and S.M.N.A. Senanayake, "XOR/XNOR functional behavior on ROBDD Representation", The 14th IASTED International Conference on Applied Simulation and Modeling, pp115-119, Spain, June 2005.

  • Downloads

  • How to Cite

    Raseen, M., & Venitha, E. (2018). Exact Modeling of Binary Decision Diagram Complexity. International Journal of Engineering & Technology, 7(3.34), 248-250. https://doi.org/10.14419/ijet.v7i3.34.18976