A study of compatibility in conjunction with implication based optimization and different forms of implications /
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...
| Main Author: | |
|---|---|
| Format: | Thesis eBook |
| Language: | English |
| Published: |
[Place of publication not identified] :
[publisher not identified] ;
1999.
|
| Subjects: | |
| Online Access: | Link to OAKTrust copy |
| Summary: | 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. |
|---|---|
| Item Description: | "Major subject: Computer Engineering". Vita. |
| Physical Description: | ix, 33 leaves : illustrations ; 28 cm. Also available online. Issued also on microfiche from Lange Micrographics. |
| Bibliography: | Includes bibliographical references (leaves 28-30). |