An Efficient Algorithm for Local Don´t Care Sets Calculation

Local don´t cares of an internal node expressed in terms of its immediate inputs are usually of interest. One can directly apply any two-level minimizer on the on-set and the local don´t cares set to simplify an internal node. In this paper, we propose a memory efficient technique to calculate local don´t cares of internal nodes in a combinational circuit. Our technique of calculating local don´t cares makes use of automatic test pattern generation (ATPG) approach which allows us to identify quickly whether a cube in the local space is a don´t care or not. Unlike other approaches which construct an intermediate form of don´t cares in terms of the primary inputs, our technique directly computes the don´t care cubes in the local space. This gives us a significant advantage over the previous approaches in memory usage. Experimental results on MCNC benchmarks are very encouraging.