Ternary Decision Diagrams and their Applications

This chapter presents various ternary decision diagrams (TDDs) to represent logic functions. A path from the root node to the terminal node representing a constant 1 is called a 1-path. The 1-paths for a Reduced Ordered AND TDD (ROATDD) and prime TDD (PTDD) represent the sets of the implicants and the prime implicants (PIs) of the functions, respectively. The 1-paths for a Reduced Ordered TDD (RO-TDD) represent a sum-of-products expression (SOP). For any function, there is a unique ROATDD and a unique PTDD. For any SOP, there is a unique ROTDD. An arbitrary function of n variables can be represented by a TDD with O(3n/n) nodes. A symmetric function can be represented by a TDD with O(n3) nodes. A program to generate all the PIs by using PTDDs is developed and shown to be much faster than conventional methods.