RESTRUCTURING AND LOGIC MINIMIZATION FOR TESTABLE PLA

Abstract

Based on the testable design techniques proposed in [12], [13], we first derive a testability measure named UCP (Untestability Cube-number Product) which can accurately indicate the extra logic needed in testable PLA. Using UCP as a cost function, we have developed two new algorithms. The first one is a restructuring algorithm named REST, and the other is a logic minimizer for testable PLA named LMTPLA. REST can not only restructure a minimized PLA and improve its UCP, but also preserve the same logic function and almost the same chip area simultaneously. Thus, we can make the restructured PLA testable by taking less extra hardware. In order to get a minimum UCP, two new techniques are proposed: 1) Cube-Reduction, and 2) Cube-Partition. Using Cube-Reduction, we can make cubes far from the primes and increases the testability. By Cube-Partition, we may find out those hard-to-test cubes and partition them into smaller but easier-to-test cubes. LMTPLA is principally based on ESPRESSO-II and REST. Different from other logic minimizers, it can consider the testability at the logic minimization process. In order to minimize UCP as well as the number of product terms, four strategies are developed: 1) deleting the cubes with poor testability and reserving the cubes with good testability, 2) giving up the primes, 3) if necessary, partitioning the more untestable cubes into smaller cubes, and 4) deleting the procedures which are useless in LMTPLA. REST and LMTPLA have been implemented on SUN4/260 in C language. For 40 benchmark circuits, the hardware overheads required are reduced by about 30-40%.