Search

Technology mapping transforms an abstract representation of a multilevel logic circuit into an interconnection of gates from a library. We have examined the approach to technology mapping that uses tree covering. The Boolean network is first decomposed in simple gates—typically NANDs and inverters: The result is called the subject graph. Matching then identifies all possible ways in which a gate of the subject graph can be implemented by a gate in the library. The best combination of matches is then chosen by a dynamic programming approach. Dynamic programming solves exactly only the covering part of the problem. Therefore, the results are of good quality, but no global optimality is guaranteed. [ABSTRACT FROM AUTHOR]

In this chapter, we have completed the brief, introductory treatment that was given in Section 1.4.4. Three main topics were covered. First, we gave, in Section 12.2, a summary of the various faults models in widespread usage at the time of writing. Second, our main focus was the treatment of automatic test pattern generation, in Section 12.3. After treating issues of excitation and sensitization (especially the method of unique sensitization). This led us naturally to the subject of logical implications. (Section 12.3.3). Third, we discussed at some length how the basic tools of the ATPG trade could be used to perform redundancy removal (Section 12.4) on a given multilevel logic circuit. This operation leaves the Boolean network in a locally optimum "prime and irredundant" state. [ABSTRACT FROM AUTHOR]

We began in this chapter by identifying some common characteristics of local Search algorithms (algorithms that start from an initial solution and try to find a better one by applying successive modifications). Then we studied the set of methods that combine to make the local search algorithm known as the ESPRESSO algorithm for logic minimization. Two methods were discussed for quickly checking whether a given implicant is prime: one based on tautology/equivalence checking, and one based on intersection with the OFF-set of the function to be minimized. Fast methods for tautology checking were discussed, based on unateness or partial unateness of the cover being checked. And similarly fast methods for computing the OFF-set were discussed. We then gave a method for computing the essential primes, and closed by showing how the whole paradigm of heuristic minimization could be extended to multiple-valued logics. [ABSTRACT FROM AUTHOR]

If you gave this chapter a careful reading, and went through a selection of the solved problems of Section 3.8, you should be comfortable with: 1.Sets and Venn diagrams, binary relations and functions, partitions and equivalence classes.2.Reflexivity, symmetry, antisymmetry, and transitivity of binary relations.3.Three important kinds of reflexive binary relations: equivalence classes, partial orders, and compatibility relations.4.The hierarchical relationship between partial orders, lattices, and Boolean algebras. Equivalence relations are one of the cornerstones in the theoretical foundation of FSM synthesis and formal verification. They will be a principal focus of the treatment of state minimization of completely specified FSMs in Chapter 7.1. Compatibility relations play a similar role in the discussion of state minimization for incompletely specified machines, the subject of Section 8.1 of Chapter 8. Since Boolean algebras are based on lattices and partial orders, the theory of partial orders permeates the entire book. We have treated "large" Boolean algebras and subalgebras, and have shown how logic synthesis "lives" in the world of the "large" Boolean algebra, Fn(0,1), of n- variable switching functions. We have related intervals and subalgebras of Fn(0,1) to don't cares and sets of permissible functions, which play prominent in logic synthesis algorithms. [ABSTRACT FROM AUTHOR]

In this chapter we have briefly surveyed the panoply of design methodologies which the semiconductor industry has employed in producing the powerful chips that are becoming commonplace today. We have characterized the IC design process as one of optimal tradeoff of competing design goals: 1.The area on the chip required by the circuit being designed;2.The critical path delay of the circuit;3.The testability of the circuit, measured in stuck-at fault coverage;4.The power dissipated by the circuit. Along the way we have developed basic notions of critical path delay analysis, test generation, graph models, CMOS implementation of logic functions, and complexity of algorithms. All of these notions will be recurring themes in the sequel, as we develop theoretical and intuitional background for effective use of the dominant extant VLSI CAD tools for synthesis and verification. For those inclined to take the next step and be a VLSI CAD tool developer, this book offers many sections on advanced topics, and extensive pointers into the relevant literature. The serious student will find that mastery of the techniques covered in the "Problem" section of each chapter will put him/her into the position of being immediately, effectively, and competitively productive in a VLSI CAD or design group. [ABSTRACT FROM AUTHOR]