On properties of Kleene TDDs
Yukihiro Iguchi, Tsutomu Sasao, Munehiro Matsuura · 2002
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 Kleenean ternary function corresponding to f. Then N(BDD:f)/spl les/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/sup n//n), and O(n/sup 3/) for arbitrary functions, and symmetric functions, respectively. There exist a 2n-variable function, where Kleene-TD Ds require O(n) nodes with the best order, while O(3/sup n/) nodes in the worst order.