Extracting local don't cares for network optimization

Abstract

An algorithm for computing local don't cares (in terms of immediate fanin variables) at each intermediate node of a Boolean network is presented. These don't cares can be directly used for the simplification of each node by a two-level minimizer. The simplification is relatively fast and the optimized circuits are 100% testable in most cases. The method is more powerful than previous ones developed for node simplification because it computes almost the full local don't care set at each node using image computation techniques. External don't cares are used effectively and there is no restriction on how these are represented because BDDs (binary decision diagrams) are used to translate them into local don't cares. This algorithm has been implemented in the sequential interactive logic synthesis system (SIS), and experimental results are presented that show the effectiveness of the proposed algorithm on benchmark circuits with and without external don't cares.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>