Digital design with CPLD applications and VHDL (R. Dueck, 2000)

Note that when two bubbles touch, they cancel out, as in the doubly inverted P input or the connection between the outputs of gates 1 and 2 and the inputs of gate 3. In the re-

sultant Boolean expression, bars of the same length cancel; bars of unequal length do not.

SECTION 3.1A REVIEW PROBLEM

3.1Write the Boolean expression for the logic diagrams in Figure 3.6, paying attention to the rules of order of precedence.

A

B

Y

C

D

a.

W

X

OUT

Y

Z

b.

FIGURE 3.6

Section Review Problem 3.1

Logic Diagrams from Boolean Expressions

K E Y T E R M S

Levels of gating The number of gates through which a signal must pass from input to output of a logic gate network.

Double-rail inputs Boolean input variables that are available to a circuit in both

true and complement form.

Synthesis The process of creating a logic circuit from a description such as a Boolean equation or truth table.

We can derive a logic diagram from a Boolean expression by applying the order of precedence rules. We examine an expression to create the first level of gating from the circuit inputs, then combine the output functions of the first level in the second level gates, and so forth. Input inverters are often not counted as a gating level, as we usually assume that each variable is available in both true (noninverted) and complement (inverted) form. When input variables are available to a circuit in true and complement form, we refer to them as double-rail inputs.

The first level usually will be AND gates if no parentheses are present, OR gates if parentheses are used. (Not always, however; parentheses merely tell us which functions to synthesize first.) Although we will try to eliminate bars over groups of variables by use of DeMorgan’s theorems and the bubble-to-bubble convention, we should recognize that a bar over a group of variables is the same as having those variables in parentheses.

Let us examine the Boolean expression Y AC BD AD. Order of precedence tells us that we synthesize the AND functions first. This yields three 2-input AND gates, with outputs AC, BD, and AD, as shown in Figure 3.7a. In the next step, we combine these AND functions in a 3-input OR gate, as shown in Figure 3.7b.

3.2 Sum-of-Products and Product-of-Sums Forms

K E Y T E R M S

Product term A term in a Boolean expression where one or more true or complement variables are ANDed (e.g., A C).

Minterm A product term in a Boolean expression where all possible variables appear once in true or complement form (e.g., A B C; A B C).

Sum term A term in a Boolean expression where one or more true or complement variables are ORed (e.g., A B D).

Maxterm A sum term in a Boolean expression where all possible variables ap-

pear once, in true or complement form (e.g., (A B C); (A B C)).

Sum-of-products (SOP) A type of Boolean expression where several product terms are summed (ORed) together (e.g., A B C A B C A B C).

Product-of-sums (POS) A type of Boolean expression where several sum terms are multiplied (ANDed) together (e.g., (A B C)(A B C)(A B C)).

Bus form A way of drawing a logic diagram so that each true and complement input variable is available along a continuous conductor called a bus.

Suppose we have an unknown digital circuit, represented by the block in Figure 3.16. All we know is which terminals are inputs, which are outputs, and how to connect the power supply. Given only that information, we can find the Boolean expression of the output.

The first thing to do is find the truth table by applying all possible input combinations in binary order and reading the output for each one. Suppose the unknown circuit in Figure 3.16 yields the truth table shown in Table 3.4.

The truth table output is HIGH for three conditions:

1.When A AND B AND C are all LOW, OR

2.When A is LOW AND B AND C are HIGH, OR

3.When A is HIGH AND B AND C are LOW.

Each of those conditions represents a minterm in the output Boolean expression. (A minterm is a product term (AND term) that includes all variables (A, B, C) in true or complement form.) The minterms are:

1.A B C

2.A B C

3.A B C

68 C H A P T E R 3 • Boolean Algebra and Combinational Logic

Since condition 1 OR condition 2 OR condition 3 produces a HIGH output from the circuit, the Boolean function Y consists of all three minterms summed (ORed) together, as follows:

Y A B C A B C A B C

This expression is in a standard form called sum-of-products (SOP) form. Figure 3.17 shows the equivalent logic circuit.

FIGURE 3.17

Logic Circuit for Y A B C ABC A B C

The inputs A, B, and C and their complements are shown in bus form. Each variable is available, in true or complement form, at any point along a conductor. This is a useful, uncluttered notation for circuits that require several of the input variables more than once.

N O T E

We can derive an SOP expression from a truth table as follows:

1.Every line on the truth table that has a HIGH output corresponds to a minterm in the truth table’s Boolean expression.

2.Write all truth table variables for every minterm in true or complement form. If a variable is 0, write it in complement form (with a bar over it); if it is 1, write it in true form (no bar).

3.Combine all minterms in an OR function.

Solution

XOR: The truth table yields two product terms: AB and AB. Thus, the SOP form of the XOR function is A B AB AB. Figure 3.18 shows the logic diagram for this equation.

A B

A B AB AB

FIGURE 3.18

Example 3.7

SOP Form of XOR Function

XNOR: The product terms for this function are: A B and AB. The SOP form of the XNOR function is A B A B AB. The logic diagram in Figure 3.19 represents the XNOR

A B

A B AB AB

FIGURE 3.19

Example 3.7

SOP Form of XNOR Function

We can also find the Boolean function of a truth table in product-of-sums (POS) form. The product-of-sums form of a Boolean expression consists of a number of maxterms (i.e., sum terms (OR terms) containing all variables in true or complement form) that are ANDed together. To find the POS form of Y, we will find the SOP expression for Y and apply DeMorgan’s theorems.

Recall DeMorgan’s theorems:

x y z x y zx y z x y z

When the theorems were introduced, they were presented as two-variable theorems, but in fact they are valid for any number of variables.