On Properties of Kleene TDDs

IGUCHI Yukihiro, SASAO Tsutomu, NATSUURA Munehiro

On Properties of Kleene TDDs

被引用文献1件参考文献17件

IGUCHI Yukihiro

the Department of Computer Science, Meiji University
SASAO Tsutomu

the Department of Computer Science and Electronics, Kyushu Institute of Technology
NATSUURA Munehiro

the Department of Computer Science and Electronics, Kyushu Institute of Technology

この論文をさがす

CiNii Books

説明

Three types of ternary decision diagrams(TDDs)are considered:AND_TDDs, EXOR_TDDs, and Kleene_TDDs. Kleene_TDDs are useful for logic simulation in the presence of unknown inputs. Let N(BDD:f), N(AND_TDD:f), and N(EXOR_TDD:f)be the number of non-terminal nodes in the BDD, the AND_TDD, and the EXOR_TDD for f, respectively. Let N(Kleene_TDD:F)be the number of non-terminal nodes in the Kleene_TDD for F, where F is the regular ternary function corresponding to f. Then N(BDD:f)≦N(TDD:f). For parity functions, N(BDD:f)=N(AND_TDD:f)=N(EXOR_TDD:f)=N(Kleene_TDD:F). For unate functions, N(BDD:f)=N(AND_TDD:f). The sizes of Kleene_TDDs are O(3^n/n), and O(n^3)for arbitrary functions, and symmetric functions, respectively. There exist a 2n-variable function, where Kleene_TDDs require O(n)nodes with the best order, while O(3^n)nodes in the worst order.