Information content of the ternary decision diagrams

Abstract

Information content of the ternary decision diagrams (EXOR-TDD) was discussed from the standpoint of spectral transform. Since the EXOR-TDDs are defined in an extended (redundant) basis, its information content is much greater than that of other decision diagrams. To construct the EXOR-TDD for a given function f, the Boolean derivatives of all possible orders were determined with respect to all variables of f. Therefore, different AND-EXOR decision diagrams are contained in the EXOR-TDDs as individual subtrees. Since each of the subtrees is an AND-EXOR expression for f, a procedure was proposed to determine the coefficient of these expressions by analyzing the paths in the EXOR-TDD. The logical Gibbs derivatives also were shown to be obtainable from the EXOR-TDDs.