Logic Gates Equivalences

Exclusive-OR and Equivalence Operations

XOR FEATURES:

simplification of special classes of functions using XOR/XNOR gates

• functions that cannot be significantly reduced using conventional minimization techniques can sometimes be simplified by implementing them with XOR/XNOR gates

• candidate functions that may be simplified this way have Minterms that are not ADJACENT (Will learn this in K-MAP)

• Technique: Write out function in SOP form, and “factor out” XOR/XNOR expressions

EXAMPLE;   F(W,X,Y,Z) = W' X' Y' Z' + W' X Y' Z + WXYZ + W X' Y Z'

                                        = X' Z' (W' Y' + WY) + XZ (W' Y' + W Y)

                                        = (X' Z' + X Z) (W'Y' + WY)

Two-level Implementation of Logic Networks

The maximum number of gates cascaded in series between an input and output is called the level of gates. For example, a sum of products (SOP) expression can be implemented using a two-level gate network, i.e., AND gates at the fi rst-level and an OR gate at the second

level. Similarly, a product of sums (POS) expression can be implemented by a two-level gate network, as OR gates at the fi rst level and an AND gate at the second level. It is important to note that INVERTERS are not considered to decide the level of gate network.

2-Level Gates implementations

For SOP forms AND gates will be in the first level and a single OR gate will be in the second level. 

For POS forms OR gates will be in the first level and a single AND gate will be in the second level.

Note that using inverters to complement input variables is not counted as a level.      

Degenerate and Nondegenerate Forms

It may be noted that, although there may be 16 combinations of two-level implementation of gates possible, four types of gates AND, OR, NAND, and NOR are considered. Eight of these combinations are similar in nature. As an example, an AND gate at first level with an AND gate at second level is practically performing a single operation. Similarly, an OR gate followed by an OR gate performs a single operation. These types of combinations are called degenerate forms.

The other eight combinations produce sum of the products or product of sums functionsand they are called nondegenerate forms. The eight nondegenerate forms are below. There are also the other types of 2-level combinational circuits. 

AND-OR   OR-AND   NOR-NOR   NAND-NAND   AND-NOR   OR-NAND   NOR-OR   NAND-AND

In each form the first gate represents the first level and second gate is for second level.

Implementing using 2-Level XOR-AND Gates  or 2-Level XOR-NOR Gates.

Implementing using 2-Level NAND-NAND Gates 

For COST Criterion measurement, we use the Gate INPUTS and OUTPUTS as equal cost, hence

         COST = No. of Gate INPUTS + No. of Gate OUTPUTS

EXAMPLE: Let us consider the function,  F=(XZ+Y′Z+X′YZ)′ . 

This function can be implemented using a 2-level Gates of AND-NOR.  

Then by De Morgans Theorem we can convert it to a NAND-AND.  

If we take the complement of F, then we can have a NAND-NAND implementation.

Eight Basic Forms for Two-Level Circuits

Multilevel Gating Networks

The number of levels can be increased by factoring the sum of products expression for an AND-OR network, or by multiplying out some terms in the product of sums expression for an OR-AND network. If a switching network is implemented using gates in more than two levels, then it is called a multilevel gate network. Some examples are given here to illustrate the multilevel gate network.

The number of gates, gate inputs, and levels in a circuit can be determined by inspection of the corresponding expression. In the example of Figure (a), the tree diagram drawn below the expression for Z indicates that the corresponding circuit will have four levels, six gates, and 13 gate inputs, as verified in Figure (b). 

Each node on the tree diagram represents a gate, and the number of gate inputs is written beside each node. 

We can change the expression for Z to three levels by partially multiplying it out:

                    Z = (AB + C) (D + E + FG) + H  = . AB(D+E ) + C(D+E) + ABFG + CFG + H

The resulting circuit requires three levels, six gates, and 19 gate inputs.  (Draw the logic circuit as exercise)

Example. Realize the function F = BC′ + A′B + D with a multilevel network.

Solution. The function can be realized in a two-level AND-OR network as shown is Figure (a). However, by factoring some part of the function, it can be rewritten as F = B(A′ + C′) + D and implemented as a multilevel gate network in Figure (b).

The logic circuit in Figure (a) consists of two 2-input AND gates, a 3-input OR gate, and fi ve literals or inputs, whereas the logic circuit in Figure (b) is a three-level representation of the same function containing two 2-input OR gates, a 2-input AND gate, and four literals. Thus it reduces the number of gate inputs by one.

Hence, from the above examples, we observe that the multilevel network has distinct advantages over the two-level network, which may be summarized as below.

1. Multilevel networks use less number of literals or inputs, thus reducing the number of wires for connection.

2. Sometimes the multilevel network reduces the number of gates.

3. It reduces the variety type of gates and hence the number of ICs (integrated circuits).

4. Multilevel gate networks can be very easily converted to universal gates realization. In that case the switching network can be   

    implemented by less variety of the logic gates.

However, the biggest disadvantage of the multilevel network is that it increases the propagation delay. The propagation delay is the inherent characteristics of any logic gate, and it increases with the increase of number of levels. So a designer must consider these

factors while designing a switching network and its application.

However, the biggest disadvantage of the multilevel network is that it increases the propagation delay. The propagation delay is the inherent characteristics of any logic gate, and it increases with the increase of number of levels. So a designer must consider these

factors while designing a switching network and its application.

Draw the 2-level Logic Circuits for the following Boolean Functions.

f(a, b, c, d) = Σm(1, 5, 6, 10, 13, 14)

f(a, b, c, d) =(c + d) (a' + b + c) (c' + d') ( a + b + c')