Implement the logic circuit in Figure 4.25 using NOR gates only.Figure 4.25 Decomposition...

Implement the logic circuit in Figure 4.25 using NOR gates only.

Figure 4.25 Decomposition for Example 4.7.

Example 4.7

Figure 4.25a defines a five-variable function f in the form of a Karnaugh map. In searching for a good decomposition for this function, it is necessary to first identify the variables that will be used as inputs to a subfunction. We can get a useful clue from the patterns of 1s in the map. Note that there are only two distinct patterns in the rows of the map. The second and fourth rows have one pattern, highlighted in blue, while the first and third rows have the other pattern. Once we specify which row each pattern is in, then the pattern itself depends only on the variables that define columns in each row, namely, x₁, x₂, and x₅. Let a subfunction g(x₁, x₂, x₅) represent the pattern in rows 2 and 4. This subfunction is just

because the pattern has a 1 wherever any of these variables is equal to 1. To specify the location of rows where the pattern g occurs, we use the variables x₃ and x₄. The terms ₃x₄ and x₃₄ identify the second and fourth rows, respectively. Thus the expression (₃x₄ + x₃₄) · g represents the part of f that is defined in rows 2 and 4.

Next, we have to find a realization for the pattern in rows 1 and 3. This pattern has a 1 only in the cell where x₁ = x₂ = x₅ = 0, which corresponds to the term . But we can make a useful observation that this term is just a complement of g. The location of rows 1 and 3 is identified by terms  and x₃x₄, respectively. Thus the expression represents f in rows 1 and 3.

We can make one other useful observation. The expressions (₃x₄ +x₃₄) and (₃₄ + x₃x₄) are complements of each other, as shown in Example 4.6. Therefore, if we let k(x₃, x₄) = ₃x₄ + x₃₄, the complete decomposition of f can be stated as

The resulting circuit is given in Figure 4.25b. It requires a total of 11 gates and 19 inputs. The largest fan-in is three.

For comparison, a minimum-cost sum-of-products expression for f is

The corresponding circuit requires a total of 14 gates (including the five NOT gates to complement the primary inputs) and 41 inputs. The fan-in for the output OR gate is eight. Obviously, functional decomposition results in a much simpler implementation of this function.

Example 4.6

Consider the minimum-cost sum-of-products expression

and assume that the inputs x₁ to x₄ are available only in their true form. Then the expression defines a circuit that has four AND gates, one OR gate, two NOT gates, and 18 inputs (wires) to all gates. The fan-in is three for the AND gates and four for the OR gate. The reader should observe that in this case we have included the cost of NOT gates needed to complement x₁ and x₂, rather than assume that both true and complemented versions of all input variables are available, as we had done before.

Factoring x₃ from the first two terms and x₄ from the last two terms, this expression becomes

Now let g(x₁, x₂) = ₁x₂ + x₁₂ and observe that

Then f can be written as

which leads to the circuit shown in Figure 4.23. This circuit requires an additional OR gate and a NOT gate to invert the value of g. But it needs only 15 inputs. Moreover, the largest fan-in has been reduced to two. The cost of this circuit is lower than the cost of its two-level equivalent. The trade-off is an increased propagation delay because the circuit has three more levels of logic.

Figure 4.23 Logic circuit for Example 4.6.

In this example the subfunction g is a function of variables x₁ and x₂. The subfunction is used as an input to the rest of the circuit that completes the realization of the required function f. Let h denote the function of this part of the circuit, which depends on only three inputs: g, x₃, and x₄. Then the decomposed realization of f can be expressed algebraically as

The structure of this decomposition can be described in block-diagram form as shown in Figure 4.24.

Figure 4.24 The structure of decomposition in Example 4.6.