Abstract
This research is a study of multilevel logic optimization based on a functional approach using ordered binary decision diagrams (OBDD). Compatibility relationships between internal nodes in a circuit are used in conjunction with implication based transformations to optimize multilevel combinational circuits. Implications are further partitioned into four classifications; in-line, off-line, strictly-strong and strictly-weak. The CUDD library package for BDD manipulation is used here to find all compatibilities by building all internal functions and finding all boolean differences. Redundancies are eliminated by the characteristics inherent in the compatibility criteria. Compatibility allows for the substitution of non equivalent nodes based on observability at the outputs and thus generating redundancies upstream. Implication transformations are then applied and a search for compatibilities is performed again. Since the search for compatibilities involves a wider set than redundancies, the potential for greater reduction increases. Implications are further divided into more specific catagories based on whether one node is upstream of the other node (in-line) else (off-line), and if the implications are found using absolute internal functions (strictly-strong) or permissible functions based on boolean differences (strictly-weak). A study of the success rates of using Strictly-strong-in-line, Strictly-strong-Off-line, Strictly-weak-in-line and Strictly-weak-off-line implications for generating redundancies is made to see if any of the catagories are better suited for optimization. Verification of the reduced circuit is trivial since the BDD for a given order is canonical, and thus compatibility substitution and implication transformation should not change the output BDD's.
Koh, T Pinn Ronnie (1999). A study of compatibility in conjunction with implication based optimization and different forms of implications. Master's thesis, Texas A&M University. Available electronically from
https : / /hdl .handle .net /1969 .1 /ETD -TAMU -1999 -THESIS -K64.