Файл: Digital design with CPLD applications and VHDL (R. Dueck, 2000).pdf

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.

N O T E

Deriving a POS expression from a truth table:

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

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

3.Combine all maxterms in an AND function.

Note that these steps are all opposite to those used to find the SOP form of the Boolean expression.

Solution All minterms (for SOP form) and maxterms (for POS form) are shown in the last two columns of Table 3.5.

Boolean Expressions:

SOP form:

Y A B C D A B C D A B C D A B C D A B C D A B C DA B C D A B C D

POS form:

Y (A B C D)(A B C D)(A B C D)(A B C D) (A B C D)(A B C D)(A B C D)

(A B C D)

The logic circuits are shown in Figures 3.21 and 3.22.

SECTION 3.2 REVIEW PROBLEM

3.3Find the SOP and POS forms of the Boolean functions represented by the following truth tables.

3.3 Theorems of Boolean Algebra

The main reason to learn Boolean algebra is to learn how to minimize the number of logic gates in a network. Boolean expressions with many terms, such as those represented by the logic diagrams in Figures 3.21 and 3.22, are seldom in their simplest form. It is often possible to apply some techniques of Boolean algebra to derive a simpler form of expression that requires fewer gates to implement.

For example, the logic circuit in Figure 3.21 requires eight 4-input AND gates and an 8-input OR gate. Using Boolean algebra, we can reduce its Boolean expression to Y AD A B C A B D A B C. This form can be implemented with 4 AND gates and a 4-input OR. You will use a simplification technique for this example in an end-of- chapter problem. In the meantime, let us examine some basic rules of Boolean algebra.

Commutative, Associative, and Distributive Properties

K E Y T E R M S

Commutative property A mathematical operation is commutative if it can be applied to its operands in any order without affecting the result. For example, addition is commutative (a b b a), but subtraction is not (a b b a).

Associative property A mathematical function is associative if its operands can be grouped in any order without affecting the result. For example, addition is associative ((a b) c a (b c)), but subtraction is not ((a b) c a (b c)).

Distributive property Full name: distributive property of multiplication over addition. The property that allows us to distribute (“multiply through”) an AND across several OR functions. For example, a(b c) ab ac.

AND and OR functions are both commutative and associative. The commutative property states that AND and OR operations are independent of input order. For inputs x and y,

Theorem 1: xy yx

and

Theorem 2: x y y x

The associative property allows us to perform several two-input AND or OR functions in any order. In other words,

Theorem 3: (xy)z x(yz) (xz)y

and

Theorem 4: (x y) z x (y z) (x z) y