Restructuring and logic minimization for testable PLA

The untestability cube-number product (UCP), a testability measure that can accurately indicate the extra logic needed in testable programmable logic arrays (PLAs), is discussed. Two UCP-based PLA synthesis algorithms are developed. The first one is a restructuring algorithm named REST, and the other is a logic minimizer for testable PLA named LMTPLA. REST can make the restructured PLA testable by taking less extra hardware. LMTPLA is based on EXPRESSO-II and REST. 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: deleting the cubes with poor testability and reserving the cubes with good testability; giving up the primes, if necessary: partitioning the more untestable cubes into smaller cubes; and 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%