Digital logic testing and verification using ordered binary decision diagrams

Date

1995-05

Journal Title

Journal ISSN

Volume Title

Publisher

Texas Tech University

Abstract

Computer-Aided Design has become a major part of design and testing of digital circuits. Since CAD systems use Boolean expressions extensively for testing and verifying digital circuits, it is necessary to find an efficient data structure algorithms for the representation and manipulation of Boolean expressions. This paper investigates Ordered Binary Decision Diagrams and several ordering techniques to satisfy this need. The OBDD program was implemented and tested on ISCAS89 benchmark circuits. A translator was developed to convert the benchmark circuits into a format that could be read by the OBDD program.

The effect of variable ordering on the size of the resulting graph was investigated. We implemented Depth First Traversal and Variable Interleaving algorithms for variable ordering. Furthermore, we developed two new variable ordering techniques, the Modified Depth First Traversal and the ordering given by the translator. The performance of these algorithms was compared to OBDDs produced by the original ordering (given in the ISCAS89 circuits) as well as by a random ordering. It was found that the ordering produced by the translator provided the smallest OBDDs overall.

Description

Citation