Title
Binary decision diagram algorithms for computer-aided logic design and verification
Date of Award
1991
Degree Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
Electrical Engineering and Computer Science
Advisor(s)
Edward P. Stabler
Keywords
Logic optimization
Subject Categories
Electrical and Computer Engineering
Abstract
Binary Decision Diagrams (BDDs) provide a compact representation for Boolean functions. This research is an effort to apply BDDs to various CAD applications, especially those of hierarchically structured circuits. The results include a universal BDD manipulator and an algorithm of using BDDs in logic synthesis, design verification, testing, etc.
The BDD manipulator, GBBDD, builds BDDs for any Boolean functions which are originally represented as any compositions of BDDs, Boolean formulae, Boolean networks, Boolean operations, Boolean variables and Boolean constants. It supports the largest set of BDD operations.
The BDD-based observability analysis (BBOA) calculates the influence relationship between circuit signals. It provides effective solutions to CAD applications dealing with the relationship between the behavior and the structure of logic circuits. In this research, BBOA has been successfully applied to logic minimization for 100% testability, test generation for 100% test coverage, restructuring of logic circuits, design diagnosis and optimized resynthesis. These applications are grouped into two systems: one for preserving circuit behavior as circuit structure changes and the other for modifying circuit structure to achieve specified circuit behavior. The success of this research effort is based on the recognition of the close relationship between various CAD applications.
Access
Surface provides description only. Full text is available to ProQuest subscribers. Ask your Librarian for assistance.
Recommended Citation
Li, Zhe Jeff, "Binary decision diagram algorithms for computer-aided logic design and verification" (1991). Electrical Engineering and Computer Science - Dissertations. 224.
https://surface.syr.edu/eecs_etd/224
http://libezproxy.syr.edu/login?url=http://proquest.umi.com/pqdweb?did=744652941&sid=1&Fmt=2&clientId=3739&RQT=309&VName=PQD
