Matrix-valued EXOR-TDDs in decomposition of switching functions

Abstract

EXOR Ternary Decision Diagrams (EXOR-TDDs) proved useful in several applications in logic design. This paper shows that EXOR-TDDs are also useful in functional decomposition. We prove that checking simple disjoint decomposition of f with respect to a subset of r variables is equivalent to building the EXOR-TDD for a matrix-valued function of (n-r) variables. Transferring the problem of decomposition into the problem of building EXOR-TDDs permits formulation of a simple decomposition procedure. The same method applies to simple disjoint bi-decomposition of switching functions.