For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE.
 On Properties of Kleene TDDsYukihiro IGUCHI  Tsutomu SASAO  Munehiro MATSUURA  Publication IEICE TRANSACTIONS on Information and Systems   Vol.E81-D   No.7   pp.716-723Publication Date: 1998/07/25 Online ISSN:  DOI:  Print ISSN: 0916-8532Type of Manuscript: Special Section PAPER (Special Issue on Test and Diagnosis of VLSI)Category: Logic Simulation and Logic OptimizationKeyword: binary decision diagram,  ternary decision diagram,  logic simulation,  ternary logic,  Full Text: PDF(631.4KB)>> Buy this Article Summary:  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:) be the number of non-terminal nodes in the Kleene -TDD for , where 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:). For unate functions,N(BDD:f)=N(AND-TDD:f). The sizes of Kleene-TDDs are O(3n/n), and O(n3) 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(3n) nodes in the worst order.