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 num- ber of non-terminal nodes in the BDD, the AND_TDD, and the EXOR_TDD for f, respectively. Let N(Kleene_TDD : F) 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).
展开▼