Boolean Algebra and Logic Simplification Boolean operations and Expressions: Boolean algebra is the mathematics of digital logic. A basic knowledge of Boolean algebra is indispensable to the study and analysis of logic circuits. Variable, complement, and literal are terms used in Boolean algebra. A variable is a symbol (usually an italic uppercase letter or word) used to represent an action, a condition, or data. Any single variable can have only a 1 or a 0 value. The complement is the inverse of a variable and is indicated by a bar over the variable (overbar). For example, the complement of the variable A is A. If A = 1, then A = 0. If A = 0, then A = 1. Thüomplement of the variable A is read as "not A" or "A bar." Sometimes a prime symbol rather than an overbar is used to denote the complement of a variable. A literal is a variable or the complement of a variable. Boolean Addition: Boolean addition is equivalent to the OR operation. The basic rules are illustrated with their relation to the OR gate in Figure: 0+0=0 0+1=1 1+0=1 In Boolean algebra, a sum term is a sum of literals. In logic circuits, a sum term is produced by an OR operation with no AND operations involved. Some examples of sum terms are A + B, A + B, A + B + C, and A + B + C + A sum term is equal to I when one or more of the literals in the term are l. A sum term is equal to 0 only if each of the literals is 0. Boolean Multiplication: Boolean multiplication is equivalent to the AND operation. The basic rules are illustrated with their relation to the AND In Boolean algebra, a product term is the product of literals. In logic circuits, a product term is produced by an AND operation with no OR operations involved. Some examples of product terms are AB, AB, ABC, and ABCD. A product term is equal to 1 only if each of the literals in the term is 1. A product term is equal to 0 when one or more of the literals are 0.
2
Laws and Rules of Boolean algebra Laws of Boolean Algebra: The basic laws of Boolean algebra—the commutative laws for addition and multiplication, the associative laws for addition and multiplication, and the distributive law—are the same as in ordinary algebra. Each of the laws is illustrated with two or three variables, but the number of variables is not limited to this. Commutative Law: The commutative law of addition for two variables is written as: A + B = B + A This law states that the order in which the variables are ORed makes no difference. Remember, in Boolean algebra as applied to logic circuits, addition and the OR operation are the same. Figure illustrates the commutative law as applied to the OR gate: Application of commutative law of addition. The commutative law of multiplication for two variables is This law states that the order in which the variables are ANDed makes no difference. Figure illustrates this law as applied to the AND gate. Remember, in Boolean algebra as applied to logic circuits, multiplication and the AND function are the same. FIGURE Application of commutative law of multiplication. Associative Laws: The associative law of addition is written as follows for three variables: This law states that when ORing more than two variables, the result is the same regardless of the grouping of the variables. Figure illustrates this law as applied to 2-input OR gates.
3
Figure: Application of associative law of addition The associative law of multiplication is written as follows for three variables: This law states that it makes no difference in what order the variables are grouped when ANDing more than two variables. Distributive Law: The distributive law is written for three variables as follows: (AB)C This law states that ORing two or more variables and then ANDing the result with a single variable is equivalent to ANDing the single variable with each of the two or more variables and then ORing the products. B+C x x Rules of Boolean Algebra: Table lists 12 basic rules that are useful in manipulating and simplifying Boolean expressions. Rules 1 through 9 will be viewed in terms of their application to logic gates. Rules 10 through 12 will be derived in terms of the simpler rules and the laws.
4
2. 3. 4. 6. Basic rules of Boolean algebra. +1=1 +Ä=I 7. 8. 9. 10. 12. A + AB A A '+ AB = A -h B (A + + C) = A + BC Rule 1: A + O = A A variable ORed with 0 is always equal to the variable. If the input variableA is l, the output variable X is I , which is equal to A IfA is 0, the output is 0, which is also equal to A. This rule is illustrated in Figure where the lower input is fixed at 0. Rule 2: A +1 = 1 A variable ORed with I is always equal to l. A I on an input to an OR gate produces a I on the output, regardless of the value of the variable on the other input. This rule is illustrated in Figure 1 where the lower input is fixed at l. A +1=1 Rule 3: A O = O A variable ANDed with 0 is always equal to 0. Any time one input to an AND gate is 0, the output is 0, regardless of the value of the variable on the other input. This rule is illustrated in Figure where the lower input is fixed at 0.
5
Rule 4: A • 1 = A A variable ANDed with I is always equal to the variable. IfA is 0, the output of the AND gate is 0. If A is l, the output of the AND gate is I because both inputs are now Is. This rule is shown in Figure 1 where the lower input is fixed at L x 1 1 Rule 5: A + A = A A variable ORed 'With itself is always equal to the variable. If A is 0, then 0 + 0 0; and if A is l, then I + I l. This is shown in Figure inputs are the same variable. x where both 1 Rule 6: A + Ä = 1 A variable ORed with its complement is always equal to l. If A is O, then O -F O O + I L If A is l, then I + I 1 — L See Figure where one input is the complement of the other.
6
Rule 7: A. A = A = 0, then 0 •0 A A variable ANDed with itself is always equal to the variable. If = 0; and if A = l, then I •l = l. Figure illustrates this rule. Rule 8: A • Ä = O A variable ANDed with its complement is always equal to 0. Either A or A will always be 0; and when a 0 is applied to the input of an AND gate, the output will be 0 also. Figure Rule 9: .Ä = A illustrates this rule. The double complement of a variable is always equal to the variable. If you start with the variable A and complement (invert) it once, you get A. If you then take A and complement (invert) it, you get A, which is the original variable. This rule is shown in Figure using inverters. Rule 10: A + AB = A and rule 4 as follows: A -l- AB = A This rule can be proved by applying the distributive law, rule 2, I + AB = A(l + B) Factoring (distributive law) Rule4:A •1 = A Rule 11: A + B This rule can be proved as follows: A + ÄB (A + AB) -k ÄB = (AA + AB) + AB AA -k AB + AA + AB Rule 10: A —A + AB Rule 7: A = AA Rule 8: adding AA 0 Factoring Rule6:A + A = 1 Rule 4: drop the I
7
Rule 12: (A + + C) = A + BC This rule can be proved as follows: (A -k + C) = AA -k AC -k AB + BC A -k AC + AB + BC + C) + AB + BC = A •1 + AB + BC = + B) + BC = A •1 + BC A + BC DeMorgan's Theorem: DeMorgan's first theorem is stated as follows: Distributive law Rule 7: AA = A Factoring (distributive law) Rule2: 1 + c = 1 Factoring (distributive law) Rule2: 1 + B = 1 Rule 4: A 1 The complement of a product of variables is equal to the sum of the complements of the variables. The formula for expressing this theorem for two variables is As stated, DeMorgan's theorems also apply to expressions in which there are more than two variables. The following examples illustrate the application of DeMorgan's theorems to 3-variable and 4-variable expressions. Applying DeMorgan's first theorem to gates: Inputs N egatVe-OR DeMorgan's second theorem is stated as follows: A O 1 .1 B O O Output .1 .1 .1 1 1 1 The complement of a sum of variables is equal to the product of the complements of the variables.
8
The complement of a sum of variables is equal to the product of the complemented variables. Applying DeMorgan's second theorem to gates: I nputs Output NCR EXAMPLE: O 1 O 1 O .1 O O O O o O Apply DeN10rgan's theorems to the expressions XYZ and X + Y + Z. Solution XYZ Example: XYZ Apply IDeMorgan's theorems to the expressions WXYZ and W + X + Y + Z Solution wrxyz WXYZ Each variable in DeMorgants theorems as stated can also repre- sent a combination of other variables. For example, X can be equal to the term AB + C, and Y can be equal to the term A + BC. So if you can apply DeMorgan's theorem for two variables as stated by XY X + Y to the expression (AB + C)(A + BC), you get the following result: Notice that in the preceding result you have two terms, AB + C and A + BC, to each of which you can again apply DeMorgan's theorem X + Y XY individually, as follows: (AB + C) + (A + BC) (AB)C + A(BC)
9
Notice that you still have two terms in the expression to which DeMorgan's theorem can again be applied. These terms are AB and BC. A final application of DeMorgan's theorem gives the following result: (AB)C + A(BC) (A + mc + + C) Applying DeMorgan's Theorems The following procedure illustrates the application of DeMorgan's theorems and Boolean algebra to the specific expression Step 1: Step 2: Step 3: Step 4: Step 5: A + BC + + F) Identify the terms to which you can apply DeMorgan's theorems, and think of each term as a single variable. Let A + BC = X and D(E + F) = Y. SinceX+Y x Y, Use rule 9 (A — A) to cancel the double bars over the left term (this is not part of DeMorgan's theorem). Apply DeMorgan's theorem to the second term. Use rule 9 (A — A) to cancel the double bars over the E + F part of the term. Apply DeMorgan's theorems to each expression: (b) (A + B) + CD (c) (A + B)CD + E + F Solution (b) (A + B) + CD (A + B)CD + D) (c) (A + B)CD + E + F (CA + + F) Boolean Analysis of Logic Circuits: AB(C + D) (AB + C + DD)EF Boolean algebra provides a concise way to express the operation of a logic circuit formed by a combination of logic gates so that the output can be determined for various combinations of input values.
10
Boolean Expression for a Logic Circuit To derive the Boolean expression for a given combinational logic circuit, begin at the left-most inputs and work toward the final output, writing the expression for each gate. For the example circuit in Figure the Boolean expression is determined in the following three steps: 1. The expression for the left-most AND gate with inputs C and D is CD. 2. The output of the left-most AND gate is one of the inputs to the OR gate and B is the other input. Therefore, the expression for the OR gate is B + CD. 3. The output of the OR gate is one of the inputs to the right-most AND gate and A is the other input. Therefore, the expression for this AND gate is A(B + CD), which is the final output expression for the entire circuit. CD Logic Simplification using Boolean Algebra: A logic expression can be reduced to its simplest form or changed to a more convenient form to implement the expression most efficiently using Boolean algebra. The approach taken in this section is to use the basic laws, rules, and theorems of Boolean algebra to manipulate and simplify an expression. Using Boolean algebra techniques, simplify this expression:
11
Solution The following is not necessarily the only approach. Step 1: Step 2: Step 3: Step 4: Step 5: Apply the distributive law to the second and third terms in the expression, as follows: AB + AB + AC + BB + BC Apply rule 7 (BB = B) to the fourth term. AB + AB + AC + B + BC Apply rule 5 (AB + AB AB) to the first two terms. AB + AC + B + BC Apply rule 10 (B + BC B) to the last two terms. AB + AC + B Apply rule 10 (AB + B B) to the first and third terms. B + AC Figure shows that the simplification process in Example has significantly reduced the number of logic gates required to implement the expression. Part (a) shows that five gates are required to implement the expression in its original form; however, only two gates are needed for the simplified expression, shown in part (b). It is important to realize that these two gate circuits are equivalent. That is, for any combination of levels on the A, B, and C inputs, you get the same output from either circuit. (a) These two circuits are equivalent. Sinmplify the following Boolean expression: IAB(C + + AB]C (b)
12
Solution Step 1: Step 2: Step 3: Step 4: Step 5: Step 6: Step 7: Step 8: Step 9: Apply the distributive law to the terms within the brackets. Apply rule 8 (BB + + AB)C — O) to the second term within the parentheses. (ABC + A + A mc Apply rule 3 (A • O D O) to the second term within the parentheses. (ABC + O + AB)C Apply rule 1 (drop the O) within the parentheses. (ABC + AB)C Apply the distributive law. Apply rule 7 (CC — Factor out BC. Apply rule 6 (A + .A ABcc + C) to the first term. ABC + ABC Apply rule 4 (drop the 1 fic
13
Simplify the following Boolean expression: Solution Step 1: Step 2: Step 3: Step 4: Step 5: Step 6: Apply DeMorgan's 'theorem to the first term. Apply DeMorgan's theorem to each term in parentheses. (A + + C) + ABC Apply the distributive law to the two terms in parentheses. .ÄÄ + + + + ÄBC Apply VIVIe 7 (AA A) to the first term, and apply rule 10 IA B + ABC AB(I + C) AB] to the third and last terms. Apply rule 10 [A + ÄC + C) = A] to the first and second terms. A + + BC Apply rule 10 [A + AB + B) = Al to the first and second terms. A + BC Standard forms of Boolean Expressions: All Boolean expressions, regardless of their form, can be converted into either of two standard forms: the sum- of-products form or the product-of-sums form. The Sum-of-Products (SOP) Form A product term was defined as a term consisting of the product (Boolean multiplication) of literals (variables or their complements). When two or more product terms are summed by Boolean addition, the resulting expression is a sum-of-products (SOP). Some examples are AB + ABC ABC + CDE + BCD AB + ABC + In an SOP expression, a single overbar cannot extend over more than one variable; however, more than one variable in a term can have an overbar. For example, an SOP expression can have the term ABC but not Domain of a Boolean Expression The domain of a general Boolean expression is the set of variables contained in the expres- sion in either complemented or uncomplemented form. For example, the domain of the expression AB + ABC is the set of variables A, B, C and the domain of the expression ABC + CDE + is the set of variables A, B, C, D, E
14
Conversion of a General Expression to SOP Form Any logic expression can be changed into SOP form by applying Boolean algebra techniques. For example, the expression A (B + CD) can be converted to SOP form by applying the distributive law: A (B + CD) = AB + ACT) The Standard SOP Form: A standard SOP expression is one in which all the variables in the domain appear in each product term in the expression. For example, ABCD + A BCD + ABC D is a standard SOP expression. Converting Product Terms to Standard SOP: Each product term in an SOP expression that does not contain all the variables in the domain can be expanded to standard form to include all variables in the domain and their complements. As stated in the following steps, a nonstandard SOP expression is converted into standard form using Boolean algebra rule 6 (A + A = 1). A variable added to its complement equals 1. Step 1: Multiply each nonstandard product term by a term made up of the sum of a missing variable and its complement. This results in two product terms. Step 2: Repeat Step 1 until all resulting product terms contain all variables in the domain in either complemented or uncomplemented form. Convert the following Boolean expression into standard SOP form: + + ABCD Solution The domain of this SOP expression is A, B, C, D. Take one term at a time. The first term, ABC, is missing variable D or D, so multiply the first term by D + D as follows: Anc = -+ D) = AnCD + AncD In this case, two standard product terms are the result. The second term, AB, is missing variables C or C and D or D, so first multiply the second term by C + C as follows: AB + C) = ABC + ABC The two resulting terms are missing variable D or D, so multiply both terms by D + D as follows: = ABCD + ABCD + ABCD + ABCD In this case, four standard product terms are the result. The third tem, ABCD, is already in standard form. The complete standard SOP form of the original expression is as follows: Abc + + ABCD = + + ÄTCD + ÄTCD + ÄFCD + + ABCD
15
The Product-of-Sums (POS) Form A sum term was defined as a term consisting of the sum (Boolean addition) of literals (variables or their complements). When two or more sum terms are multiplied, the resulting expression is a product-of-sums (POS). Some examples are (A + + OcC + D + + C + D) A POS expression can contain a single-variable term, as in + + + C + D). In a POS expression, a single overbar cannot extend over more than one variable; however, more than one variable in a term can have an overbar. For example, a POS expression can have the term A + B + C but not A + B + C. The Standard POS Form: A POS expressions in which some of the sum terms do not contain all of the variables in the domain of the expression. For example, the expression has a domain made up of the variables A, B, C, and D. Notice that the complete set of variables in the domain is not represented in the first two terms of the expression; that is, D or D is missing from the first term and C or C is missing from the second term. A standard POS expression is one in which all the variables in the domain appear in each sum term in the expression. For example, is a standard POS expression. Converting a Sum Term to Standard POS Each sum term in a POS expression that does not contain all the variables in the domain can be expanded to standard form to include all variables in the domain and their complementsw As stated in the following steps, a nonstandard POS expression is convened into standard form using Boolean algebra rule 8 (A A = 0) its complement equals 0. : A variable multiplied by Step 1: Step 2: Step 3: Add to each nonstandard product term a term made up of the product of the missing variable and its complement. This results in two sum terms. As you know, you can add 0 to anything without changing its value. Apply rule 12 Repeat Step I until all resulting sum terms contain all variables in the domain in either complemented or uncomplemented form.
16
Convert the following Boolean expression into standard POS form: Solution The domain of this POS expression is A, B, C, D. Take one term at a time. The first term, A + B + C, is missing variable D or D, so add DD and apply Jule 12 as follows: The second term, B + C + D, is missing variableA or A, so add AA and apply rule 12 as follows: + C + D = + C + D + AA = (A + + C + + + C + D) The third term, A + + C + D, is alrady in standard form lhe standard POS form ofthe original expression is as follows: Determining Standard Expressions from a Truth Table To determine the standard SOP expression represented by a truth table, list the binary val- ues of the input variables for which the output is I . Convert cach binary value to the corre- sponding product term by replacing each I with the corresponding variable and each O with the corresponding variable complement. For example, the binary value 1010 is converted to a product term as follows: 1010 AÄcD If you substitutev you can see that the product term is 'l : TO determine the standard POS expression represented by a truth table, list the binary values for which the output is O. Convert each binary value to the corresponding sum term by replacing each 1 with the corresponding variable complement and cach O with the cor- responding Variable, For example, the binary Value is converted to a sum term as follows: If you substitutC% you can see that the sum term is O: The Karnaugh Map: A Karnaugh map provides a systematic method for simplifying Boolean expressions and, if properly used, will produce the simplest SOP or POS expression possible, known as the minimum expression. Karnaugh map is similar to a truth table because it presents all of the possible values of input variables and the resulting output for each value. Instead of being organized into columns and rows like a truth table, The Karnaugh map is an array of cells in which each cell represents a binary value of the input variables. The number of cells in a Karnaugh map, as well as the number of rows in a truth table, is equal to the total number of possible input variable combinations. For three variables, the number of cells is 23 = 8. For four variables, the number of cells is 24 = 16.
17
The 3-Variable Karnaugh Map The 3-variable Karnaugh map is an array of eight cells, as shown in Figure In this case, B, and C are used for the variables although other letters could be used. Binary values of A and B are along the left side (notice the sequence) and the values of C are across the top. The value of a given cell is the binary values of A and B at the left in the same row combined with the value of C at the top in the same column. For example, the cell in the upper left porner has a binary value of 000 and the cell in the lower right comer has a binary value of 101. Figure shows the standard product terms that are represented by each cell in the Kamaugh map. c oo 01 Il 10 o 1 c oo 01 11 10 o 1 ÄÄc ÄBF ÄBC ABä ABC ABC ABC The 4-Variable Karnaugh Map The 4-variable Karnaugh map is an array of sixteen cells, as shown in Figure '(ah Binary values of A and B are along the left side and the values of C and D are across the top. "Ihe value of a given cell is the binary values of A and B at the left in the same row combined with the binary values of C and D at the top in the same columm For example, the cell in the upper right comer has a binary value of 0010 and the cell in the lower right corner has a binary value of 10104 Figure (b) shows the standard product terms that are represented by each cell in the 4-variable Kamaugh map. CD 01 oo 01 11 10 10 CD oo 01 11 10 ÄDFD -ABCD 01 ÄBFD ÄBÜD ÄBCD .ÄncD Il ABCD ABED ABCD ABCD 10 AFD AFFD .AFcD (b) Karnaugh Map SOP Minimization:
18
A minimized SOP expression contains the fewest possible terms with the fewest possible variables per term. Mapping a Standard SOP Expression For an SOP expression in standard form, a 1 is placed on the Karnaugh map for each product term in the expression. Each I is placed in a cell corresponding to the value of a product term. For example, for the product term ABC, a I goes in the 101 cell on a 3-variable map. When an SOP expression is completely mapped, there will be a number of Is on the Karnaugh map equal to the number of product terms in the standard SOP expression. The cells that do not have a 1 are the cells for which the expression is 0. The following steps shows the mapping process. Step 1: Determine the binary value of each product term in the standard SOP expression. Step 2: As each product term is evaluated, place a 1 on the Karnaugh map in the cell. 1 1 ABC + + ABC + 001 110 1 oo 01 11 10 1 1 1 Exarnple of rnapping a standard SOP expression. Mapping a Nonstandard SOP Expression A Boolean expression must first be in standard form before you use a Karnaugh map. If an expression is not in standard form, then it must be converted to standard form. For example, assume that one of the product terms in a certain 3-variable SOP expression is A B. This term can be expanded numerically to standard form as follows. First, write the binary value of the two variables and attach a 0 for the missing variable C: 100. Next, write the binary value of the two variables and attach a 1 for the missing variable C: 101. The two standard SOP terms ABC and ABC. resulting binary numbers are the values of the Karnaugh Map Simplification of SOP Expressions The process that results in an expression containing the fewest possible terms with the fewest possible variables is called minimization. After an SOP expression has been mapped, a minimum SOP expression is obtained by grouping the Is and determining the minimum SOP expression from the map. Grouping the Is You can group Is on the Karnaugh map according to the following rules by enclosing those adjacent cells containing Is. The goal is to maximize the size of the groups and to minimize the number of groups. 1. A group must contain either 1, 2, 4, 8, or 16 cells, which are all powers of two. In the case of a 3-variable map, 23 = 8 cells is the maximum group. 2. Each cell in a group must be adjacent to one or more cells in that same group, but all cells in the group do not have to be adjacent to each other. 3. Always include the largest possible number of Is in a group in accordance with rule 1. 4. Each 1 on the map must be included in at least one group. The Is already in a group can be included in another group as long as the overlapping groups include noncommon Is.
19
Determining the Minimum SOP Expression from the Map When all the Is representing the standard product terms in an expression are properly mapped and grouped, the process of determining the resulting minimum SOP expression begins. The following rules are applied to find the minimum product terms and the minimum SOP expression: 1. Group the cells that have Is. Each group of cells containing Is creates one product term composed of all variables that occur in only one form (either uncomplemented or complemented) within the group. Variables that occur both uncomplemented and complemented within the group are eliminated. These are called contradictory variables. 2. Determine the minimum product term for each group. (a) For a 3-variable map: (1) A I-cell group yields a 3-variable product term (2) A 2-cell group yields a 2-variable product term (3) A 4-cell group yields a I-variable term (4) An 8-cell group yields a value of I for the expression (b) For a 4-variable map: (1) A I-cell group yields a 4-variable product term (2) A 2-cell group yields a 3-variable product term (3) A 4-cell group yields a 2-variable product term (4) An 8-cell group yields a I-variable term (5) A 16-cell group yields a value of I for the expression 3. When all the minimum product terms are derived from the Karnaugh map, they are summed to form the minimum SOP expression. Example: Use a Karnaugh map to minimize the following standard SOP expression: Abc + ÄBC + ABC + + ABC Solution The binary values of the expression are 101 +011 +001 +000+ IOO Map the standard SOP expression and group the cells as shown 1 AB O Äc 01 11 10 1 The resulting minimum SOP expression is
20
Karnaugh Map POS Minimization: Mapping a Standard POS Expression For a POS expression in standard form, a 0 is placed on the Karnaugh map for each sum term in the expression. Each 0 is placed in a cell conesponding to the value of a sum term. For example, for the sum term A + B + C, a 0 goes in the 010 cell on a 3-variable map. When a POS expression is completely mapped, there will be a number of Os on the Karnaugh map equal to the number of sum terms in the standard POS expression. The cells that do not have a 0 are the cells for which the expression is l. Usually, when working with POS expressions, the Is are left om The following steps show the mapping process. Step 1: Determine the binary value of each sum term in the standard POS expression. This is the binary value that makes the term equal to 0. Step 2: As each sum term is evaluated, place a 0 on the Karnaugh map in the corre- sponding cell. o 1 010 110 101 3 01 11 10 Example of mapping a standard POS expression.l Example: Map the following standard POS expression on a Karnaugh map: Solution Evaluate the expression as shown below and place a 0 on the 4-variable Karnaugh map sum term in the expression. for each standard 1100 1011 0010 0011
21
CD oo AB oo 01 11 01 11 o 10 o 10 Example: Use a Karnaugh map to minimize the following POS expression: Solution The first term must be expanded into A + B + C + D and A + B + C + D to get a standard POS expression, which is then mapped; and the cells are grouped as shown in Figure 4—46. The sum term for each group is shown and the resulting minimum POS expression is CD 01 11 10 o 00 01 11 10 0 0 0 Combinational Logic Analysis When logic gates are connected together to produce a specified output for certain specified combinations of input variables, with no storage involved, the resulting circuit is in the category of combinational logic.
22
AND-OR Logic Figure 5—1(a) shows an AND-OR circuit consisting of two 2-input AND gates and one 2-input OR gate; The Boolean expressions for the AND gate outputs and the resulting SOP expression for the output X are shown on the diagram. In general, an AND-OR circuit can have any number of AND gates, each with anv number of innuts. SOP X=AB+CD CD (a) Logic diagram (ANSI standard distinctive shape symbols) An AND-OR circuit directly implements an SOP expression, assuming the complements (if any) of the variables are available. The operation of the AND-OR circuit in Figure is stated as follows: For a 4-input AND-OR logic circuit, the output X is HIGH (1) if both input A and input B are HIGH (1) or both input C and input D are HIGH (1). AND-OR-Invert Logic When the output of an AND-OR circuit is complemented (inverted), it results in an AND-OR- Invert circuit. Recall that AND-OR logic directly implements SOP expressions. POS expres- sions can be implemented with AND-OR-Invert logic. This is illustrated as follows, starting with a POS expression and developing the conesponding _AND-OR-Invert (AOI) expressionr X (A + + D) — — AB + CD —AB + CD The logic diagram in Figure shows an AND-OR-Invert circuit with four inputs and the development of the POS output expression. In general, an AND-OR-Invert circuit can have any number of AND gates, each with any number of inputs. POS AB + CD AB + CD (a) FIGURE An AND-OR-Invert circuit produces a POS output. For a 4-input AND-OR-Invert logic circuit, the output X is LOW (0) if both input A and input B are HIGH (1) or both input C and input D are HIGH (1). Exclusive-OR Logic
23
The exclusive-OR gate is considered a type of logic gate with its own unique symbol, it is actually a combination of two AND gates, one OR gate, and two inverters. Exclusive-OR logic symbols as shown : (a) Logic diagram The output expression for the circuit in Figure 5-5 is Evaluation of this expression results in the truth table in Table Notice that the output is HIGH only when the two inputs are at opposite levels. A special exclusive-OR opera- tor is often used, so the expression X Aj + AB can be stated as "X is equal to A exclusive-OR B" and can be written as X -AOB Exclusive-NOR Logic As you know, the complement of the exClusive-OR function is the exclusive-NOR, which is derived as follows: Truth table for an exclusive- OR o o 1 1 0 1 0 1 x 1 1 Notice that the output X is HIGH only when the two inputs, A and B, are at the same level. The exclusive-NOR can be implemented by simply inverting the output of an exclusive- OR, as shown in Figure XOR x Combinational Logic using NAND and NOR Gates:
24
NAND Logic As you have learned, a NAND gate can function as either a NAND or a negative-OR because, by DeMorgan's theorem, NAND Consider the NAND logic in Figure following steps: negative-OR The output expression is developed in the AB + CD X-AB+CD CD -AB + CD. NAND logic for X NOR Logic A NOR gate can åmction as either a NOR or a negative-AND, as shown by DeMorgan's theorem. FIGURE NOR NOR logic for X negative-AND
25
Consider the NOR logic in Figure The output expression is developed as follows: As you can see in Figure , the output expression (A + + D) consists of two OR terms ANDed together. This shows that gates (32 and (33 act as OR gates and gate Gl acts an AND gate. Functions of Combinational Logic Half Adder and Full Adders Half- Adder: the basic rules for binary addition as stated 1 1 = 10 The operations are performed by a logic circuit called a half-adder. The half-adder accepts two binary digits on its inputs and produces two binary digits on its outputs-—a sum bit and a carry bit. A half-adder is represented by the logic symbol in Figure FIGURE Input bits out Logic symbol for a half-adder. Sum Outputs Carry
26
= sum Cout output carry A and B = input variables (operands) TABLE 6-1 Half-adder truth table. cout AB O O 1 1 0 1 0 1 0 0 0 1 0 1 1 0 From the operation of the half-adder as stated in Table expressions can be derived for the sum and the output carry as functions of the inputs. Notice that the output carry (Cout) is a I only when both and B are Is; therefore, Cout can be expressed as the AND of the input variables. cout = AB Now observe that the sum output (Y) is a I only if the input variables, A and B, are not equal. The sum can therefore be expressed as the exclusive-OR of the input variables. the logic implementation required for the half-adder func- tion can be developed. The output carry is produced with an AND gate withÅ and B on the inputs, and the sum output is generated with an exclusive-OR gate, as shown in Figure FIGURE Half-adder logic diagram. The Full-Adder The second category of adder is the full-adder. The full-adder accepts two input bits and an input carry and generates a sum output and an output carry. The basic difference between a full-adder and a half-adder is that the full-adder accepts an input carry. A logic symbol for a full-adder is shown in Figure and the truth table in Table shows the operation of a full-adder.
27
Input bits Input cany out Sum Output carry FIGURE Logic symbol for a 'full-adder. Open file F06-03 to verify operation. TABLE Full-adder truth table. in out Cin = input carry, sometimes designated as CI Cout = output carry, sometimes designated as CO The full-adder must add the two input bits and the input carry. From the half-adder you know that the sum of the input bits A and B is the exclusive-OR of those two variables, A O B. For the input carry (Cin) to be added to the input bits, it must be exclusive-ORed with A O B, yielding the equation for the sum output of the full-adder.
28
This means that to implement the full-adder sum function, two 2-input exclusive-OR gates can be used, The first must generate the term A O B, and the second has as its inputs the output of the first XOR gate and the input carw, as illustrated in Figure 6-4(a). (a) Logic required to form the sum of three bits FIGURE out (b) Full-adder logic symbol (b) Complete logic circuit for a full-adder (each half-adder is enclosed by a shaded area) Full-adder logic. The output carry of the full-adder is therefore produced by input A .ANDed with input B and A O B ANDed with Cin. These two terms are ORed, as expressed in Equation . This function is implemented and combined with the sum logic to form a complete full-adder circuit, as shown in Figure (b). out Parallel Binary Adders: = AB + (A 9B)qn Equation Two or more full-adders are connected to form parallel binary adders. a single full-adder is capable of adding two I-bit numbers and an input carry. To add binary numbers with more than one bit, you must use additional full-adders. When one binary number is added to another, each column generates a sum bit and a 1 or 0 carry bit to the next column to the left. To add two binary numbers, a full-adder (FA) is required for each bit in the numbers. So for 2-bit numbers, two adders are needed; for 4-bit numbers, four adders are used; and so on. The carry output of each adder is connected to the carry input of the next higher-order adder, as shown in Figure. a half-
29
adder can be used for the least significant position or the carry input of a full-adder can be made 0 (grounded) because there is no carry input to the least significant bit position. General format, addition of two 2-bit numbers: A2A I + B2Bl FA2 out (MSE) FAI cout E El (LSE) Block diagram of a basic 2-bit parallel adder using two full-adders In Figure the least significant bits (LSB) of the two numbers are represented by Al and Bl. The next higher-order bits are represented by A2 and B2. The three sum bits are El, 22, and 23. Notice that the output carry from the left-most full-adder becomes the most significant bit (MSB) in the sum, 23. Four-Bit Parallel Adders : A group of four bits is called a nibble. A basic 4-bit parallel adder is implemented with four full-adder stages as shown in Figure. The LSBs (Al and Bl) in each number being added go into the right-most full-adder; the higher-order bits are applied as shown to the successively higher-order adders, with the MSBs (A4 and B4) in each number being applied to the left-most full-adder. The carry output of each adder is connected to the carry input of the next higher-order adder as indicated. These are called internal carries. 1 2 3 4 FA4 (MSB) (a) Block diagram FA3 out FA2 cout FAI (LSB) Binary number A Binary number B Input carry (b) Logic symbol 1 2 3 4 1 2 3 4 co 4-bit sum Output carry The input labeled CO is the input carry to the least significant bit adder; C4, in the case of four bits, is the output carry of the most significant bit adder; and El (LSB) through 24 (MSB) are the sum outputs. The logic symbol is shown in Figure.
30
Truth Table for a 4-Bit Parallel Adder The subscript n represents the adder bits and can be 1, 2, 3, or 4 for the 4-bit adder. Cn-l is the carry from the previous adder. Carries C 1, C2, and C3 are generated internally. CO is an external carry input and C4 is an output. Truth table for each stage of a 4-bit parallel adder. o o o o 1 1 1 1 O O 1 1 O o 1 1 O O 1 O 1 O 1 o 1 1 O 1 o O 1 o o o 1 o 1 1 1 Comparators: The basic function of a comparator is to compare the magnitudes of two binary quantities to determine the relationship of those quantities. In its simplest form, a comparator circuit determines whether two numbers are equal. Equality: the exclusive-NOR gate can be used as a basic comparator because its output is a 0 if the two input bits are not equal and a comparator. 1 1 if the input bits are equal. Figure shows the exclusive-NOR gate as a 2-bit The input bits are equal. 1 01 The input bits are not equal. In order to compare binary numbers containing two bits each, an additional exclusive- NOR gate is necessary. The two least significant bits (LSBs) of the two numbers are compared by gate Gl, and the two most significant bits (MSBs) are compared by gate G2, as shown in Figure below. If the two numbers are equal, their corresponding bits are the same, and the output of each exclusive-NOR gate is a 1. If the corresponding sets of bits are not equal, a 0 occurs on that exclusive-NOR gate output.
31
LSBs MSBs HIGH indicates equality. General format: Binary •number A —+ AIAO Binary number B —+ BIBO In order to produce a single output indicating an equality or inequality of two numbers, an AND gate can be combined with XNOR gates, as shown in Figure above. The output of each exclusive-NOR gate is applied to the AND gate input. When the two input bits for each exclusive-NOR are equal, the corresponding bits of the numbers are equal, producing a 1 on both inputs to the AND gate and thus a 1 on the output. When the two numbers are not equal, one or both sets of corresponding bits are unequal, and a O appears on at least one input to the AND gate to produce a 0 on its output. Thus, the output of the AND gate indicates equality (1) or inequality (0) of the two numbers. Inequality In addition to the equality output, fixed-function comparators can provide additional out- puts that indicate which of the two binary numbers being compared is the larger. That is, there is an output that indicates when numberA is greater than number B (A > B) and an output that indicates when number A is less than number B (A < B), as shown in the logic symbol for a 4-bit comparator in Figure To determine an inequality of binary numbers A and B, you first examine the highest- order bit in each number. The following conditions are possible: 2. IfA3 3. IfA3 — I and B3 — 0, number A is greater than number B. O and B3 l, number A is less than number B. B3, then you must examine the next lower bit position for an inequality. COMP 0 3 0 3 Logic symbol for a 4-bit comparator with inequality indication.
32
These three operations are valid for each bit position in the numbers. The general procedure used in a comparator is to check for an inequality in a bit position, starting with the highest-order bits (MSBs). When such an inequality is found, the relationship of the two numbers is established, and any other inequalities in lower-order bit positions must be ignored. Decoders: A decoder is a digital circuit that detects the presence of a specified combination of bits (code) on its inputs and indicates the presence of that code by a specified output level. In its general form, a decoder has n input lines to handle n bits and from one to 2n output lines to indicate the presence of one or more n-bit combinations. The Basic Binary Decoder: Suppose you need to determine when a binary 1001 occurs on the inputs of a digital circuit. An AND gate can be used as the basic decoding element because it produces a HIGH output only when all of its inputs are HIGH. Therefore, you must make sure that all of the inputs to the AND gate are HIGH when the binary number 1001 occurs; this can be done by inverting the two middle bits (the Os), as shown in Figure. 1 1 (a) FIGURE 1 1 (LSB) 1 (MSB) (b) 3210 Decoding logic for the binary code 1001 with an active-HIGH output. Ao is the LSB and A3 is the MSB. The 4-Bit Decoder In order to decode all possible combinations of four bits, sixteen decoding gates are required (24 = 16). This type of decoder is commonly called either a 4-1ine-to-16-line decoder because there are four inputs and sixteen outputs or a I-of-16 decoder because for any given code on the inputs, one of the sixteen outputs is activated. A list of the sixteen binary codes and their corresponding decoding functions is given in Table.
33
Decoding functions and truth table for a 4-line-to-1 6-line (1-of-16) decoder with active-LOW outputs. Decimal Digit 10 11 12 13 14 15 Binary Inputs o o o Decoding Function 1140 1140 143A2A 214 IA o 1.40 1140 1.40 Outputs 1 2 .34 5 o 6 1 I 12 o 13 1 14 15 o o o o 8 9 10 11 1 1 If an active-LOW output is required for each decoded number, the entire decoder can be implemented with NAND gates and inverters. In order to decode each of the sixteen binary codes, sixteen NAND gates are required (AND gates can be used to produce active-HIGH outputs). A logic symbol for a 4-1ine-to-16-line (I-of-16) decoder with active-LOW outputs is shown in Figure The BIN/DEC label indicates that a binary input makes the corre- sponding decimal output active. The input labels 8, 4, 2, and I represent the binary weights of the input bits (23222120).
34
BIN/DEC 1 2 4 8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Logic symbol for a 4-1ine-to-16-line (I-of-1 6) decoder. Encoders encoder is a combinational logic circuit that essentially performs a reverse decoder function. An encoder accepts an active level on one of its inputs representing a digit, such as a decimal or octal digit, and converts it to a coded output, such as BCD or binary. The process of converting from familiar symbols or numbers to a coded format is called encoding. The Decimal-to-BCD Encoder: This type of encoder has ten inputs—one for each decimal digit—and four outputs corresponding to the BCD code, as shown in Figure. Decimal input DEC/BCD o 1 2 3 4 5 6 7 8 9 1 2 4 8 BCD output Logic symbol for a decimal-to-BCD encoder. The BCD (8421) code is listed in Table. From this table you can determine the relationship between each BCD bit and the decimal digits in order to analyze the logic. For instance, the most significant bit of the BCD code, A3, is always a 1 for decimal digit 8 or 9. An OR expression for bit A3 in terms of the decimal digits can therefore be written as:
35
TABLE BCD Code Decimal Digit Bit 142 is always a I for decimal digit 4, 5, 6 or 7 and can be expressed as an OR function as follows: Bit Al is always a I for decimal digit 2, 3, 6, or 7 and can be expressed as Finally, Ao is always a I for decimal digit l, 3, 5, 7, or 9. The expression for Ao is Now let's implement the logic circuitry required 'for encoding each decimal digit to a BCD code by using the logic expressions just developed. It is simply a matter of ORing the appropriate decimal digit input lines to form each BCD output. The basic encoder logic resulting from these expressions is shown in Figure (LSB) (MSB) Basic logic diagram of a decimal-to-BCD encoder.. The basic operation of the circuit in Figure is as follows: When a HIGH appears on one of the decimal digit input lines, the appropriate levels occur on the four BCD output lines. For instance, if input line 9 is HIGH (assuming all other input lines are LOW), this condition will produce a HIGH on outputs Ao and .A3 and LOWs on outputs Al and 142, which is the BCD code (1001) for decimal 9.
36
Unit 111 Latches and Flip-flop Two categories of bistable devices are the latch and the flip-flop. Bistable devices have two stable states, called SET and RESET; they can retain either of these states indefinitely, making them useful as storage devices. The basic difference between latches and flip-flops is the way in which they are changed from one state to the other. The flip-flop is a basic building block for counters, registers, and other sequential control logic. Latches The latch is a type of temporary storage device that has two stable states (bistable) and is normally placed in a category separate from that of flip-flops. Latches are similar to flip-flops because they are bistable devices that can reside in either of two states using a feedback arrangement, in which the outputs are connected back to the opposite inputs. The main difference between latches and flip-flops is in the method used for changing their state. The S-R (SET-RESET) Latch A latch is a type of bistable logic device or multivibrator. An active-HIGH input S-R (SET-RESET) latch is formed with two cross-coupled NOR gates, as shown in Figure (a); an active-LOW input S-R latch is formed with two cross-coupled NAND gates, as shown in Figure (b). Notice that the output of each gate is connected to an input of the opposite gate. This produces the regenerative feedback that is characteristic of all latches and flip-flops. (a) Active-HIGH input S -R latch (b) Active-LOW input SR latch Negative-OR FIGURE eauivalent of the NAND aate To explain the operation of the latch, we will use the NAND gate S-R latch in Figure (b), This latch is redrawn in Figure with the negative-OR equivalent symbols used for the NAND gates. The latch in Figure has two inputs, S and R, and two outputs, Q and Q. Let's start by assuming that both inputs and the Q output are HIGH, which is the normal latched state. Since the Q output is connected back to an input of gate and the R input is HIGH, the output of G2 must be LOW This LOW output is coupled back to an input of gate Gl, ensur- ing that its output is HIGH, When the Q output is HIGH, the latch is in the SET state, It will remain in this state indefinitely until a LOW is tempor#ily applied to the input, With a LOW on the R input and a HIGH on S, the output of gate is forced HIGH. This HIGH on the Q output is
37
coupled back to an input of (31, and since the S input is HIGH, the output of Gl goes LOW. This LOW on the Q output is then coupled back to an input of (32, ensuring that the Q output remains HIGH even when the LOW on the R input is removed. When the Q output is LOW, the latch is in the RESET state. Now the latch remains indefinitely in the RESET state until a momentary LOW is applied to the S input. In normal operation, the outputs of a latch are always complements of each other. When e is HIGH, Q is LOW, and when Q is LOW, Q is HIGH. An invalid condition in the operation of an active-LOW input S-R latch occurs when LOWs are applied to both S and R at the same time. As long as the LOW levels are simultaneously held on the inputs, both the Q and Q outputs are forced HIGH, thus violating the basic complementary operation of the outputs. Figure illustrates the active-LOW input S-R latch operation for each of the four possible combinations of levels on the inputs. (The first three combinations are valid, but the last is not.) Table summarizes the logic operation in truth table form. Momentary LOW oll..ls 1 (HIGH) Q 0 Outputs make transitions when S LOW and remain in same state after 0 goes back HIGH. 1 olus 1 RESET means that the Q output is LOW. 1 No transitions occur because latch is already SET Latch starts RESET (Q 0). Latch Stans out SET (Q l).
38
1 1 1 1 Outputs make transitions when R goes LOW and remain in same state after R goes back HIGHw Latch stans out SET (Q = l). No transitions occur because latch is already RESET Latch starts out RESET (Q 0). (b) Tv,o possibilities for the RESET operation Outputs do not change statem Latch remains SET if previously SET and 0 remains RESET if previously RESET. Output states are uncertain when input LOWs go back HIGH at approximately the same time. 1 0 HIGHS on both inputs (c) No-change condition Simultaneous LOWs on both inputs (d) Invalid condition The three modes of basic S-R latch operation (SET, RESET, no-change) and the invalid condition. TABLE Truth table for an active-LOW input S-R latch. Inputs 1 1 Outputs 1 1 0 NC 1 1 NC 0 1 1 Comments No change. Latch remains in present state. Latch SET. Latch RESET Invalid condition Logic symbols for both the active-HIGH input and the active-LOW input latches are shown in Figure
39
(a) Active-HIGH input S-R latch (b) Active-LOW input S-R latch Logic symbols for the S-R and S-R latch.
Discussion
Copyright Infringement: All the contents displayed here are being uploaded by our members. If an user uploaded your copyrighted material to LearnPick without your permission, please submit a Takedown Request for removal.
Need a Tutor or Coaching Class?
Post an enquiry and get instant responses from qualified and experienced tutors.
If you have your own Study Notes which you think can benefit others, please upload on LearnPick. For each approved study note you will get 25 Credit Points and 25 Activity Score which will increase your profile visibility.