Logic Synthesis with AND and OR Gates in Two Levels:Design of Single-Output Minimal Networks with AND and OR Gates in Two Levels.

Introduction

When logic networks are realized in transistor circuits on an integrated circuit chip, each gate in logic networks usually realizes more complex functions than AND or OR gates. But handy design methods are not available for designing logic networks with such complex gates under very diversified complex constraints such as delay time and layout rules. Thus, designers often design logic networks with AND, OR, and NOT gates as a starting point for design with more complex gates under complex constraints. AND, OR, and NOT gates are much easier for human minds to deal with. Logic networks with AND, OR, and NOT gates, after designing such networks, are often converted into transistor circuits. This conversion process illustrated in Figure 30.1 (the transistor circuit in this figure will be explained in later chapters) is called technology mapping. As can be seen, technology mapping is complex because logic gates and the corresponding transistor logic gates usually do not correspond one to one before and after technology mapping and layout has to be considered for speed and area.

Also, logic gates are realized by different types of transistor circuits, depending on design objectives. They are called logic families. There are several logic families, such as ECL, nMOS circuits, static CMOS, and dynamic CMOS, as discussed in Chapters 33, 38, and 39. Technology mapping is different for different logic families.

First, let us describe the design of logic networks with AND and OR gates in two levels, because handy methods are not available for designing logic networks with AND and OR gates in more than two levels.

Although logic networks with AND and OR gates in two levels may not be directly useful for designing transistor circuits to be laid out on an integrated circuit chip, there are some cases where they are directly usable, such as programmable logic arrays to be described in a later chapter.

Design of Single-Output Minimal Networks with AND and OR Gates in Two Levels

Suppose that we want to obtain a two-level network with a minimum number of gates and, then, as a secondary objective, a minimum number of connections under Assumptions 30.1 in the following, regardless of whether we have AND or OR gates, respectively, in the first and second levels, or in the second and first levels. In this case, we have to design a network based on the minimal sum and another based on the minimal product, and then choose the better network. Suppose that we want to design a two-level AND/OR network for the function shown in Figure 30.2(a). This function has only one minimal sum, as shown with loops in Figure 30.2(a). Also, it has only one minimal product, as shown in Figure 30.3(a). The network in Figure 30.3(b), based on this minimal product, requires one less gate, despite more loops, than the network based on the minimal sum in Figure 30.2(b), and consequently the network in Figure 30.3(b) is preferable.

The above design procedure of a minimal network based on a minimal sum is meaningful under the following assumptions.

Assumptions 30.1: (1) The number of levels is at most two; (2) Only AND gates and OR gates are used in one level and second the other level; (3) Complemented variables xi ’s as well as noncomple- mented xi’s for each i are available as the network inputs; (4) No maximum fan-in restriction is imposed on any gate in a network to be designed; (5) Among networks realizable in two levels, we will choose networks that have a minimum number of gates. Then, from those with the minimum number of gates, we will choose a network that has a minimum number of connections.

If any of these is violated, the number of logic gates as the primary objective and the number of connections as the secondary objective are not minimized. If we do not have the restriction “at most two levels,” we can generally have a network of fewer gates.

Karnaugh maps have been widely used because of convenience when the number of variables is small. But when the number of variables is many, maps are increasingly complex and processing with them become tedious, as discussed in Chapter 28. Furthermore, the corresponding logic networks with AND and OR gates in two levels are not useful because of excessive fan-ins and fan-outs.