Extended Implementation And Dynamic Minimization Of Bi-Kronecker Functional Decision Diagrams

Boolean functions play an increasingly important role in the field of computer-aided design and artificial intelligence.Recently,a new canonical form of Boolean functions was proposed,which is called Bi-Kronecker Functional Decision Diagram(BKFDD)and applies three singlevariable decompositions and three double-variable decompositions at the same time.It is a relatively advanced decision diagram.In addition,dynamic minimization algorithms of BKFDD are also proposed,which can effectively determine a better variable order with decomposition types,so that it is available to reduce the representation space of BKFDD.However,the theoretical basis and dynamic minimization algorithms of BKFDD still have the following shortcomings:(1)BKFDD does not have some boolean operation,such as restriction,existential quantification and universal quantification;(2)The current implementation of BKFDD only includes weak reduced BKFDD but not strong reduced BKFDD.(3)Dynamic minimization algorithms of BKFDD only support the optimization of variable order with four decomposition types currently,but BKFDD can theoretically support six decomposition types; Therefore,the work of paper is mainly divided into two parts to solve the above problems: an efficient implementation of BKFDD and an extension of dynamic minimization of BKFDD.This paper firstly completes the efficient implementation of BKFDD,including restriction,existential quantification,universal quantification,and strong reduced BKFDD.In this work,the above three efficient Boolean operations are designed and implemented according to the structural characteristics of BKFDD.In addition,combined with the chain reduction rule,the implementation of strong reduced BKFDD is discussed from the perspective of practical implementation,and the mutual conversion between weak reduced BKFDD and strong reduced BKFDD is completed.Subsequently,the paper extends the dynamic minimization algorithms of BKFDD based on resolving the problems of the original dynamic minimization algorithms.In the work,the reason why the dynamic minimization algorithms of BKFDD cannot support six decomposition types is firstly analyzed,and bring out the question about disappearance of complement information of edges.Next,the solution to the above question is given in terms of computed tables,nodes and temporary calculation results of Boolean operations,so that the dynamic minimization algorithms of BKFDD can support six decomposition types.Finally,the experimental comparison is carried out in ISCAS89,MCNC,EPFL and ITC99,which are four highly influential benchmark test cases.Compared with the original dynamic minimization algorithms of BKFDD,the extended dynamic minimization algorithms have better performance on large benchmarks.In summary,the paper focuses on the extended implementation of the new decision diagram BKFDD and the extension of its dynamic minimization.We design and implement three common Boolean operations in BKFDD,and complete the mutual conversion between weak reduced BKFDD and strong reduced BKFDD,and make the dynamic minimization algorithms of BKFDD support six decomposition types,which solves some of the existing shortcomings of BKFDD,and improves the practical application ability of BKFDD.