Bi-kronecker Functional Decision Diagrams: A Novel Canonical Representation Of Boolean Functions

Boolean Functions play an important role in the field of Artificial Intelligence and Electronic Design Automation.Binary Decision Diagrams(BDDs)are canonical form of Boolean functions.They are graph representation,and Boolean operations can be implemented using graph algorithms.Compared with other representations,BDDs are simple and easy to manipulate,the runtime of Boolean operations on BDDs is polynomial.FDDs are variants of BDDs,they can be more compact when representing XOR-intensive functions,but in the worst-case,the runtime of AND-Operation on FDDs is exponential.Kronecker Functional Decision Diagrams(KFDDs)are general forms of BDDs and FDDs.Under certain conditions,they are proved to be the most general decision diagram combining logic expansions based on single variable decomposition.With the development of electronic circuits,the logical abstraction of emerging devices is a two-input comparator,which makes the logic expansion based on single variable decomposition not fully applicable.The research on logic expansions based on biconditional decomposition began to be unfolded.Biconditional Binary Decision Diagrams(BBDDs)which based on a new expansion can be used to model new devices,and they have been shown to be more compact than BDDs on the Boolean functions Majority and Adder.In this paper,we study the logic expansions based on biconditional decomposition,and propose Bi-Kronecker Functional Decision Diagrams(BKFDDs),BKFDDs are canonical form that integrate expansions based on single variable and biconditional decomposition.They are generalizations of some existing decision graph: BDDs,FDDs,KFDDs and BBDDs.Under certain conditions,all possible logic expansions based on single variable and biconditional decomposition are combined in BKFDDs.A series of new reduction rules can be used to further reduce the size of BKFDDs due to the property of biconditional expansions.In addition,BKFDDs is a special and simple form of Linear Transform Kronecker Functional Decision Diagrams(LTKFDDs).The experimental results show that on large scale test cases BKFDDs outperform other existing decision diagrams in terms of size,and runtime of generating BKFDDs is reasonable.