The authors explore the relationship between algebraic transformations for area optimization and the testability of combinational logic circuits. It is shown that for each multifault in an algebraically factored circuit there is an equivalent multifault in the original circuit. Using this result, it is shown how algebraic factorization may be applied to minimized two-level circuits, to synthesize area-optimized, completely multifault testable multilevel circuits. When a circuit is synthesized using algebraic factorization from a minimized two-level circuit, a reasonably small set of tests that give complete multifault coverage of the synthesized circuit can be derived from the single-fault tests for the original two-level circuit. It is shown that single-fault testability is not an invariant maintained by algebraic transformations, and a simple single-fault irredundant circuit on which the application of algebraic transformations activate a latent multifault, making the resulting algebraically transformed circuit single-fault redundant is presented.>

The authors present a number of results exploring the relationship between algebraic transformations for area optimization and the testability of combinational logic circuits. They show that for each multifault in an algebraically factored circuit there is an equivalent multifault in the original circuit, and it is well known that two-level single-output circuits that are single-fault testable are also multifault testable. They also show how these results imply that algebraic factorization may be applied to minimized (and therefore completely single-fault testable) two-level circuits, in order to synthesize area optimized, completely multifault testable circuits. Furthermore, when algebraic factorization is applied to a minimized two-level circuit all tests needed for complete multifault coverage of the synthesized circuit can be derived from the single-fault tests for the original two-level circuit.>

A hierarchical procedure for net routing on l*m*n grid-graphs, where l is the number of layers, m is the number of rows, and n is the number of columns, is presented. The hierarchy reduces the overall problem to a sequence of subproblems, where each subproblem works on an l*m'*n portion of the overall grid. For each subproblem, an initial constructive placement (CP) of as many nets as possible is used; then a generalized dynamic programming (DP) algorithm to solve the Steiner problem of an l*2*n grid-graph is used for any remaining nets. The CP procedure uses simplistic routing assumptions to route quickly as many nets as possible. If all nets are routed, the subproblem solution is (locally) optimal and the corresponding branch of the binary recursion tree generated by the hierarchy is pruned. For any unrouted nets, the generalized DP procedure is called to route each net, one at a time, with a run time complexity of O(K*n) where n is the number of columns and K is a function of the grid cross section and layer/wiring restrictions. There are no a priori layer restrictions or limitations on the number of layers used; three-layer cases and even some four-layer cases are feasible for the PYRAMID 90-X.>

Uses of implied network values or conditions in the context of multilevel logic synthesis are presented. The use of these implications has resulted in performance-enhanced versions, ESPRESSOMLT2 and MLTAUT2, of the two cornerstone tools of the BOLD system, ESPRESSOMLT (multilevel logic minimizer based on tautology checking) and MLTAUT (multilevel logic verifier). The relationship between the implied values and the intermediate don't care set is presented. Then it is shown how this relationship can be exploited to reduce the number of tautology calls and the number of leaves in the binary recursion tree of tautology checking. A parallelized version MLTAUT2P, which runs on a Sun 3/75 LAN, is discussed. ESPRESSOMLT2, is expected to have speedups of up to a factor of 20 and the parallelized version a factor of over 100.>

An approach is described for the minimization of multilevel logic circuits. A multilevel representation of a block of combinational logic is defined, called a Boolean network. A procedure is then proposed, called ESPRESSOMLD, to transform a given Boolean network into a prime, irredundant, and R-minimal form. This procedure rests on the extension of the notions of primality and irredundancy, previously used only for two-level logic minimization, to combinational multilevel logic circuits. The authors introduce the concept of R-minimality, which implies minimality with respect to cube reshaping, and demonstrate the crucial role played by this concept in multilevel minimization. Theorems are given that prove the correctness of the proposed procedure. Finally, it is shown that prime and irredundant multilevel logic circuits are 100% testable for input and output single-stuck faults, and that these tests are provided as a byproduct of the minimization.>