On Properties of Kleene TDDs

Yukihiro IGUCHI, Tsutomu SASAO, Munehiro MATSUURA

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(3ⁿ/n), and O(n³) 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ⁿ) nodes in the worst order.

• Publication: IEICE TRANSACTIONS on Information Vol.E81-D No.7 pp.716-723
• Publication Date: 1998/07/25
• Type of Manuscript: Special Section PAPER (Special Issue on Test and Diagnosis of VLSI)
• Category: Logic Simulation and Logic Optimization

Authors

Yukihiro IGUCHI
Tsutomu SASAO
Munehiro MATSUURA

Keyword

binary decision diagram,  ternary decision diagram,  logic simulation,  ternary logic