BCA 111 DCLD

Boolean Algebra 2 93 Table 6.5: Associative Law 1 A B C B+C A+B A+(B+C) (A+B)+C 0 0 00 0 0 0 1 1 0 01 1 0 1 1 1 0 10 1 1 1 1 1 0 11 1 1 1 1 1 00 0 1 1 1 01 1 1 1 1 10 1 1 1 1 11 1 1 1 Logical Implementation A Y=A+B+C == > Y=A+B+C B+C A B B+C B C C Fig. 6.3: Logical Implementation  Law 2 The associative law of multiplication states that it makes no difference in what order the variables are grouped when AND several variables. As shown in the figure, this law as applied to AND gates. The above laws can be proved using induction method. Proof by perfect induction method Table 6.6: Associative Law 2 A B C B.C A.B A.(B.C) (A.B).C 0 000 0 0 0 0 0 001 0 0 0 010 0 0 0 CU IDOL SELF LEARNING MATERIAL (SLM)

94 Digital Circuits and Logic Designs 00 01 1 1 0 00 10 0 0 0 00 10 1 0 0 00 11 0 0 1 11 11 1 1 1 AB Logical Implementation == > Y = ABC A Y=A+B+C B C B+C Fig. 6.4: Logical Implementation (e) Distributive law The distributive laws states that factoring or multiplication of different term in an expression is allowed. They are expressed as follows: (a) A.(B+C) = AB + AC (b) A+(B.C) = (A+B)(A+C) (a) LAW 1: The distributive law states that ORing several variables and ANDing the result with a single variable is equivalent to ANDing the result with a single variable with each of the several variables and then ORing the products. The Figure illustrates this law in terms of gate implementation. A A AB X=A (B + C) Is B equivalent X = AB + AC B to: AC CC Fig. 6.5: Distributive law CU IDOL SELF LEARNING MATERIAL (SLM)

Boolean Algebra 2 95 Proof by Perfect Induction Method (A+B)(A+C) A.(B+C) = AB + AC A+(B.C) = (A+B)(A+C) 0 0 Table 6.7: Induction Method 0 1 A B C B+C A.B A.C A.(B+C) A.B+A.C A+(BC) 1 0 000 0 0 0 0 0 0 0 001 1 0 0 0 0 1 1 010 1 0 0 0 0 011 1 0 0 0 0 100 0 0 0 0 0 6.3 Simplification of Boolean Expression using Boolean Algebra Technique 1. Y = (A+B)(A+C) = AA +AC +AB + BC = A + AC + AB + BC since A.A = A = A(1+C+B) +BC Since 1+C+B = 1 2. A(A+ A )+B = AA+A A +B by the distributive law = A+0+B because AA = A and A A = 0 = A+B because A + 0 = A 3. (A+B)( A +B) B = (A+B)( A B +B B ) by the distributive law = (A+B)( A +0) because B= 0 = (A+B)( A B ) because A B + 0 = A B = A A B + B A B by the distributive law = A0 + A 0 because A A = 0 and B B = 0 =0 because 0 AND with anything is 0 CU IDOL SELF LEARNING MATERIAL (SLM)

96 Digital Circuits and Logic Designs Examples : Q.1 (A + B)(A + C) = A + BC This rule can be proved as follows: (A + B)(A + C) = AA + AC + AB + BC Distributive law = A + AC + AB + BC AA = A = A( 1 + C) + AB + BC 1 + C = 1 = A. 1 + AB + BC Factoring (distributive law) = A(1 + B) + BC 1+B=1 = A. 1 + BC A.1=A = A + BC Q.2 (A + B)(A + C) = A + BC This rule can be proved as follows: (A + B)(A + C) = AA + AC + AB + BC Distributive law = A + AC + AB + BC AA = A = A( 1 + C) + AB + BC = A. 1 + AB + BC Factoring (distributive law) = A(1 + B) + BC 1+B=1 = A. 1 + BC A.1=A = A + BC Q.3 Using Boolean algebra techniques, simplify this expression: AB + A(B + C) + B(B + C) Solution: Step 1: Apply the distributive law to the second and third terms in the expression, as follows: AB + AB + AC + BB + BC CU IDOL SELF LEARNING MATERIAL (SLM)

Boolean Algebra 2 97 Step 2: Apply rule 7 (BB = B) to the fourth term. AB + AB + AC + B + BC Step 3: Apply rule 5 (AB + AB = AB) to the first two terms. AB + AC + B + BC Step 4: Apply rule 10 (B + BC = B) to the last two terms AB + AC + B Step 5: Apply rule 10 (AB + B = B) to the first and third terms. B+AC At this point the expression is simplified as much as possible. 6.4 Summary While George Boole’s set of laws and rules allows us to analyse and simplify a digital circuit, there are two laws within his set that are attributed to Augustus De Morgan (a nineteenth century English mathematician) which views the logical NAND and NOR operations as separate NOT AND and NOT OR functions respectively. But before we look at De Morgan’s Theory in more detail, let’s remind ourselves of the basic logical operations where A and B are logic (or Boolean) input binary variables, and whose values can only be either “0” or “1” producing four possible input combinations, 00, 01, 10, and 11. 6.5 Key Words/Abbreviations  Induction: the action or process of inducting someone to a post or organization . 6.6 Learning Activity 1. Explain Commutative law. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- CU IDOL SELF LEARNING MATERIAL (SLM)

98 Digital Circuits and Logic Designs 2. Simplification of Boolean expression using Boolean algebra technique. 1. Y = (A+B)(A+C) ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 6.7 Unit End Questions (MCQ and Descriptive) A. Descriptive Types Questions 1. Explain simplification concepts of Boolean expression. 2. Describe various Boolean techniques. B. Multiple Choice/Objective Type Questions 1. Boolean algebra is also called________ . (a) Switching algebra (b) arithmetic algebra (c) linear algebra (d) algebra 2. X*y = y*x is (a) Commutative law (b) identity element (c) associative law (d) inverse property 3. According to Boolean algebra absorption law, which of the following is correct? (a) x+ xy =x (b) (x+ y) = xy (c) Xy + y =x (d) x + y =y 4. A Boolean function may be transformed into (a) Matrix (b) logical graph (c) map (d) logical diagram 5. To perform product of maxterms Boolean function must be brought into (a) OR terms (b) AND terms (c) NOT terms (d) NAND terms Answers 1. (a), 2. (b), 3. (c), 4. (d), 5. (a) CU IDOL SELF LEARNING MATERIAL (SLM)

Boolean Algebra 2 99 6.8 References 1. https://www.electronics-tutorials.ws/boolean/demorgan.html 2. https://www.tutorialspoint.com/computer_logical_organization/boolean_algebra.htm 3. http://web.csulb.edu/~hill/ee201/Boolean%20Algebra.pdf   CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 7 SOP AND POS 1 Structure: 7.0 Learning Objectives 7.1 Introduction 7.2 Form of Boolean Expression for Logic Network 7.3 Minterm 7.4 Maxterm 7.5 Summary 7.6 Key Words/Abbreviations 7.7 Learning Activity 7.8 Unit End Questions (MCQ and Descriptive) 7.9 References 7.0 Learning Objectives After studying this unit, you will be able to:  Define Boolean expression  Explain minterms and max-terms related to Boolean expression 7.1 Introduction The SOP (Sum of Product) and POS (Product of Sum) are the methods for deducing a particular logic function. ... The prior difference between the SOP and POS is that the SOP CU IDOL SELF LEARNING MATERIAL (SLM)

SOP and POS 1 101 contains the OR of the multiple product terms. Conversely, POS produces a logical expression comprised of the AND of the multiple OR terms. In Boolean algebra, 0 is used to represent the ‘open’ state or ‘false’ state of logic gate. Similarly, 1 is used to represent the ‘closed’ state or ‘true’ state of logic gate. A Boolean expression is an expression which consists of variables, constants (0-false and 1-true) and logical operators which results in true or false. A Boolean function is an algebraic form of Boolean expression. A Boolean function of n-variables is represented by f(x1, x2, x3,…., xn). By using Boolean laws and theorems, we can simplify the Boolean functions of digital circuits. Boolean functions can be represented by using NAND gates and also by using K-map (Karnaugh map) method. We can standardize the Boolean expressions by using by two standard forms. 7.2 Form of Boolean Expression for Logic Network 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. Boolean Expression for a Logic Circuit: Fig. 7.1: The expression for the left-most To derive the Boolean expression for a given AND gate with inputs C and D is CD. logic circuit, begin at the leftmost inputs and work toward the final output, writing the expression for each gate. For example, the Boolean expression for the circuit is determined as shown in the adjoining figure. The expression for the left-most AND gate with inputs C and D is CD. 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. 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. CU IDOL SELF LEARNING MATERIAL (SLM)

102 Digital Circuits and Logic Designs Example 1. A + AB = A = A(1 + B) Factoring (distributive law) = A.L (1 + B) = 1 = A A.1=A 2. AB + A(B + C) + B(B + C) Step 1: Apply the distributive law to the second and third terms in the expression, as follows: = AB + AB + AC + BB + BC Step 2: Apply rule 7 (BB = B) to the fourth term. =AB + AB + AC + B + BC Step 3: Apply rule 5 (AB + AB = AB) to the first two terms. =AB + AC + B + BC Step 4: Apply rule 10 (B + BC = B) to the last two terms. =AB + AC + B Step 5: Apply rule 10 (AB + B = B) to the first and third terms. =B+AC At this point the expression is simplified as much as possible. A AB+A(B+C)+B(B+C) B B+AC B CA C (a) (b) Fig. 7.2: Boolean Expression for a Logic Circuit CU IDOL SELF LEARNING MATERIAL (SLM)

SOP and POS 1 103 7.3 Minterm For a Boolean function of n variables x1, x2,.....xn, a product term in which each of the n variables appear once either in their complemented form or in their uncomplemented form is called a minterm. The minterm is denoted as mi where i is in the range of 0 ≤ i < 2ⁿ. For example: A B C (for 3 variables), AB C D (for 4 variables) A variable is in complemented form, if its value is 0, and the variable is uncomplemented form, if its value is 1. For 3 variable input the minterms will be Table 7.1: Minterm A B C Minterm (mi) 0 0 0 A B C = m0 0 0 1 A B C = m1 0 1 0 A B C = m2 0 1 1 A BC = m3 1 0 0 A B C = m4 1 0 1 A B C = m5 1 1 0 AB C = m6 1 1 1 ABC =m7 Minterm of n variables = product of n literals in which each variable appears exactly once either in T or F form, but not in both. (Also known as a standard product term) Each minterm has value 1 for exactly one combination of values of variables. E.g. ABC (111) = m7 A function can be written as a sum of minterms, which is referred to as a minterm expansion or a standard sum of products CU IDOL SELF LEARNING MATERIAL (SLM)

104 Digital Circuits and Logic Designs 7.4 Maxterm For a Boolean function of n variables x1, x2,.....xn, a sum term in which each of the n variables appear once either in their complemented or in their uncomplemented form is called maxterm. Maxterms are a dual of the minterms because they exhibit a complementary symmetry in all respects. Instead of using ANDs and complements, we use ORs and complements and proceed similarly. The maxterm is denoted as Mi where i is in the range of 0 ≤ i < 2ⁿ. For example: A + B + C (for 3 variables), A + B + C + D (for 4 variables) In maxterm, each variable is complimented, if its value is assigned to 1, and each variable is uncomplemented if its value is assigned to 0. For 3 variable input, the maxterms will be: Table 7.2: Maxterm A B C Maxterm (Mi) 0 0 0 A + B + C = M0 0 0 1 A + B + C = M1 0 1 0 A + B + C = M2 0 1 1 A + B + C = M3 1 0 0 A +B + C = M4 1 0 1 A + B + C = M5 1 1 0 A + B + C = M6 1 1 1 A + B + C = M7 A maxterm of n variables = sum of n literals in which each variable appears exactly once in T or F from, but not in both. Each maxterm has a value of 0 for exactly one combination of values of variables. E. g. A + B + C’ (001) => M1 (the value is 0). Therefore, Mi = m’i A function can be written as a product of maxterms, which is referred to as a maxterm expansion or a standard product of sums. CU IDOL SELF LEARNING MATERIAL (SLM)

SOP and POS 1 105 Examples Q. 1. What is Minterm? Minterms are AND terms with every variable present in either true or complemented form. Given that each binary variable may appear normal (e.g., x) or complemented (e.g., x), there are 2n minterms for n variables. Example: Two variables (X and Y) produce 2 × 2 = 4 combinations: XY (both normal) XY(X normal, Y complemented) XY (X complemented, Y normal) XY(both complemented) Q.2. What are Maxterm? For a Boolean function of n variables x1, x2,.....xn, a sum term in which each of the n variables appear once either in their complemented or in their uncomplemented form is called maxterm. Maxterms are a dual of the minterms because they exhibit a complementary symmetry in all respects. Instead of using ANDs and complements, we use ORs and complements and proceed similarly. The maxterm is denoted as Mi where i is in the range of 0 ≤ i < 2ⁿ. For example: A + B + C (for 3 variables), A + B+ C + D (for 4 variables) In maxterm, each variable is complimented, if its value is assigned to 1, and each variable is uncomplemented if its value is assigned to 0. Q.3. Express the Boolean function F = x + y z as a sum of minterms. Solution: = x + y z = x + (y z) AND (multiply) has a higher precedence than OR (add) = x(y+y’)(z+z’) + (x+x’) yz expand 1st term by ANDing it with (y + y’)(z + z’), and 2nd term with (x + x’) = x y z + x y z’ + x y’ z + x y’ z’ + x’ y z = m7 + m6 + m5 + m4 + m3 = (3, 4, 5, 6, 7) CU IDOL SELF LEARNING MATERIAL (SLM)

106 Digital Circuits and Logic Designs Q.4Express the Boolean function F = x + y z as a product of maxterms. = x + y z = x + (y z) AND (multiply) has a higher precedence than OR (add) = (x + y) (x + z) use distributive law to change to product of OR term = (x + y + z z’) (x + y y’ + z) expand 1st term by OR it with z z’, and 2nd term with y y’ = (x + y + z) (x + y + z’) (x + y' + z) = M0 M1 M2 = (0, 1, 2) Q.5Express F’ = (x + y z)’ as a sum of minterms. = (x + y z)’ = (x + (y z))’ AND (multiply) has a higher precedence than OR (add) = x’ (y’ + z’) use dual or De Morgan’s Law = (x’ y’) + (x’ z’) use distributive law to change to sum of AND terms = x’ y’ (z + z’) + x' (y + y’) z’ expand 1st term by ANDing it with (z + z’), and 2nd term with (y + y') = x' y' z + x' y' z' + x' y z' = m1 + m0 + m2 = (0, 1, 2) Q.6Express F ' = (x + y z)' as a product of maxterms. = (x + y z)’ = (x + (y z))’ AND (multiply) has a higher precedence than OR (add) = x’ (y' + z’) use dual or De Morgan’s Law = (x' + y y’ + z z’) (x x’ + y’ + z’) expand 1st term by ORing it with y y' and z z', and 2nd term with x x' = (x’ + y + z) (x’ + y + z’) (x’ + y’ + z) (x’ + y’ + z’) (x + y’ + z’) = M4 M6 M5 M7 M3 = (3, 4, 5, 6, 7) CU IDOL SELF LEARNING MATERIAL (SLM)

SOP and POS 1 107 7.5 Summary The sum-of-products (SOP) form is a method (or form) of simplifying the Boolean expressions of logic gates. In this SOP form of Boolean function representation, the variables are operated by AND (product) to form a product term and all these product terms are OR (summed or added) together to get the final function. A sum-of-products form can be formed by adding (or summing) two or more product terms using a Boolean addition operation. Here the product terms are defined by using the AND operation and the sum term is defined by using OR operation. The sum-of-products form is also called as Disjunctive Normal Form as the product terms are OR together and Disjunction operation is logical OR. Sum-of-products form is also called as Standard SOP. The product of sums form is a method (or form) of simplifying the Boolean expressions of logic gates. In this POS form, all the variables are OR, i.e. written as sums to form sum terms. All these sum terms are AND (multiplied) together to get the product-of-sum form. This form is exactly opposite to the SOP form. So this can also be said as “Dual of SOP form”. Here the sum terms are defined by using the OR operation and the product term is defined by using AND operation. When two or more sum terms are multiplied by a Boolean OR operation, the resultant output expression will be in the form of product-of-sums form or POS form. The product-of-sums form is also called as Conjunctive Normal Form as the sum terms are AND together and Conjunction operation is logical AND. Product-of-sums form is also called as Standard POS. 7.6 Key Words/Abbreviations  SOP form: Sum Of Products form  POS form: Product Of Sums form 7.7 Learning Activity 1. What is Minterm? ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- CU IDOL SELF LEARNING MATERIAL (SLM)

108 Digital Circuits and Logic Designs 2. Express the Boolean function F = x + y z as a sum of minterms. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 3. Express F' = (x + y z)' as a product of max. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 7.8 Unit End Questions (MCQ and Descriptive) A. Descriptive Types Questions 1. Define Boolean expression. 2. Explain minterms and maxterms related to Boolean expression. B. Multiple Choice/Objective Type Questions 1. The terms in SOP are called __________. (a) maxterms (b) minterms (c) midterms (d) sumterms 2. A sum of products expression is a product term (min term) or several min terms AND together. (a) True (b) False (c) none of above (d) both 3. Which of the following is an incorrect SOP expression? (a) x+x.y (b) (x+y)(x+z) (c) x (d) x+y 4. The corresponding minterm when x=0, y=0 and z=1. (a) x.y.z’ (b) X’+Y’+Z (c) X+Y+Z’ (d) x’.y’.z CU IDOL SELF LEARNING MATERIAL (SLM)

SOP and POS 1 109 5. LSI stands for ___________ . (b) Large System Integration (a) Large Scale Integration (d) Large Symbolic Integration (c) Large Symbolic Integration Answers 1. (b), 2. (b), 3. (b), 4. (d), 5. (a) 7.9 References 1. https://www.electronicshub.org/boolean-logic-sop-form-pos-form/ 2. https://www.slideshare.net/manesh1983/logic-simplification-sop-and-pos-forms 3. https://techdifferences.com/difference-between-sop-and-pos.html 4. https://www.ibiblio.org/kuphaldt/socratic/output/sop_pos.pdf   CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 8 SOP AND POS 2 Structure: 8.0 Learning Objectives 8.1 Introduction 8.2 Karnaugh Map (K-map) 8.3 Simplification of Boolean Expression using Karnaugh Map (K-map) Techniques (Upto 4 Variables) 8.4 Summary 8.5 Key Words/Abbreviations 8.6 Learning Activity 8.7 Unit End Questions (MCQ and Descriptive) 8.8 References 8.0 Learning Objectives After studying this unit, you will be able to:  Draw Karnaugh map  Explain various techniques of Karnaugh map  Solve problems related to logic simplification CU IDOL SELF LEARNING MATERIAL (SLM)

SOP and POS 2 111 8.1 Introduction The SOP (Sum of Product) and POS (Product of Sum) are the methods for deducing a particular logic function. In other words, these are the ways to represent the deduced reduced logic function. We can use the deduced logic function in designing a logic circuit. The prior difference between the SOP and POS is that the SOP contains the OR of the multiple product terms. Conversely, POS produces a logical expression comprised of the AND of the multiple OR terms. Before understanding SOP and POS, we must learn various related terms so that the entire thing would collectively make some sense. 8.2 Karnaugh Map (K-map) Introduction The Karnaugh Map, also known as the K-map, is a method to simplify Boolean expressions. Maurice Karnaugh, a telecommunications engineer, developed the Karnaugh Map at Bell Labs in 1953 while designing digital logic based telephone switching circuits. A Karnaugh Map is a graphical representation of the logic system. It simplifies logic functions more quickly and easily compared to Boolean algebra. It is used for many small design problems. We will be studying Karnaugh map in detail later in the unit. A Karnaugh Map is a grid-like representation of a truth table. It is always drawn as a rectangular grid. The number of squares in the grid is equal to the number in the truth table. For example, for n variables, the number of rows in a truth table are 2n. Therefore, for 3 variables, number of rows are 2n = 23 = 8. Since number of squares in K-map = number of rows in truth table Therefore, number of squares for 3 variables = 8 It is just another way of presenting a truth table, but the mode of presentation gives more insight. A Karnaugh map has 0 and 1 entries at different positions. Each position in a grid corresponds to a truth table entry. CU IDOL SELF LEARNING MATERIAL (SLM)

112 Digital Circuits and Logic Designs (I) Structure of K-map (i) For 2 variables, there will be 4 squares in a K-map. Following are the structures of K-map for 2 variables: Table 8.1: 2 Variables K-map B B BAA A 0 1B 1 A 0 A0 B0 A1 B1 (ii) For 3 variables, there will be 23 = 8 squares in a K-map. Following are the structures of K-map for 3 variables. The sequence of K-map is in gray code form that is only 1 bit can be varied at a time Table 8.2: 3 Variables K-map C C 0 C1 AB A B A B AB A B AB C 00 01 11 10 00 C0 01 11 C1 10 (iii) For 4 variables, there will be 24 = 16 squares in a K-map. Following are the structures of K-map for 4 variables: Table 8.3: 4 Variables K-map CD CD C D CD CD AB 00 01 11 10 A B 00 A B 01 AB 11 A B 10 CU IDOL SELF LEARNING MATERIAL (SLM)

SOP and POS 2 113 AB A B A B AB A B CD 00 01 11 10 C D 00 C D 01 C D 11 D 10 (II) Grouping in K-map In K-map, grouping is done on most number of 1’s for SOP and most number of 0’s for POS. We will be first studying about SOP in detail. In POS procedure remains the same, only 1 is replaced by 0 The grouping follows the binary rule i.e. we can group 1, 2, 4, 8, 16..... number of 1’s or 0’s but we cannot group 3, 5, 7, ....number of 1’s or 0’s. (i) Pair: A group of two adjacent 1’s (or 0’s) is called a pair. A pair eliminates 1 variable from a term. (ii) Quad: A group of four adjacent 1’s (or 0’s) is called a quad. A quad eliminates 2 variables from a term. (iii) Octet: A group of eight adjacent 1’s (or 0’s) is called a octet. An octet eliminates 3 variables from a term. (III) Rules to Solve Boolean Expression using K-Map 1. In SOP, groups must not contain any cell containing ‘0’ and in POS, groups must not contain any cell containing ‘1’. 2. Groups must be formed horizontal or vertical but not diagonal. 3. While forming groups, first try to form group of eight cells (octet), then group of four cells (quad), then a pair and finally if any 1 (or 0) is left then group of 1. 4. Groups must contain 1, 2, 4 or 8 cells. 5. Each 1 (or 0 in case of POS) must be present in at least one group. CU IDOL SELF LEARNING MATERIAL (SLM)

114 Digital Circuits and Logic Designs 6. Groups can overlap each other. 7. There should be as few groups as possible. 8. Redundant groups must be avoided. Example of Redundant group is as shown below. Table 8.4: K-map CD C D 00 C D 01 CD 11 C D 10 AB A B 00 0 1 0 0 A B 01 0 1 1 1 AB 11 1 1 1 0 A B 10 0 0 1 0 In the above given K-map, the four 1’s included in a quad are also grouped in pairs. Thus, all four 1’s are grouped twice: in a quad and in pairs. This is called redundancy. While simplifying the equation using K-map redundancy should be avoided, i.e., in the above example a quad can be avoided to avoid redundancy. (IV) Don’t Care Conditions In SOP form, we enter 1 in the K-map structure for high output and 0 in the remaining cells but it is not always true that the cells not containing 1 will contain 0 because some combinations of input variable do not occur. Also for some functions, the outputs corresponding to certain combinations of input variables do not matter. In such situations, we have freedom to assume 0 or 1 as output for such combinations. These conditions are called as “Don’t care conditions” and in K-map it is represented as ‘x’ mark in the corresponding cell. The don’t care condition can be assumed to be 0 or 1 as per the need of simplification. The don’t care conditions are indicated by d ( ). Note that every don’t care mark need not be considered while grouping CU IDOL SELF LEARNING MATERIAL (SLM)

SOP and POS 2 115 For example 1. Simplify the expression given below using K-map. Y = ∑ m (0, 3, 4, 6, 9, 12) + d (1, 2, 10) Solution: Y = ∑ m (0, 3, 4, 6, 12) + d (1, 2, 10) Therefore, Y = ∑ m (0000, 0011, 0100, 0110, 1100) + d (0001, 0010, 1010) Table 8.5: K-map for Don’t Care Condition CD A A B AB AB AB 00 01 11 10 C D 00 1 11 0 C D01 BX 00 0 C D11 1 00 0 C D 10 X 10 x 8.3 Simplification of Boolean Expression using Karnaugh Map (K-map) Techniques (Upto 4 Variables) 1. A logic expression in the standard SOP form is as follows: Y = A B C + A B C + AB C + A B C + A B C Solution: Prepare a K-map structure for 3 variables. Table 8.6: K-map BC B C BC BC BC A 00 01 11 10 A0 0 1 0 1 0 1 A1 1 1 Solve the K-map to get simplified expression. CU IDOL SELF LEARNING MATERIAL (SLM)

116 Digital Circuits and Logic Designs (ii) Find the logical expression for the given K-map: CD 0 Table 8.7: K-map 0 0 BC CD CD CD 1 A CD AB 0 0 0 0 0 AB 0 0 0 0 AB 0 0 0 AB 1 1 1 Solution: Y = ABCD + ABCD + ABCD + ABC D  = AB CD  CD  CD  C D = AB CD  D CD  D  = AB C  C [ C+ C ] Y = AB (iii) Find the logical expression for the given K-map: Table 8.8: K-map BC CD CD CD A AB 0 1 0 AB 0 1 0 AB 0 1 0 AB 0 1 0 Solution: Y = ABCD + ABCD + ABCD + ABCD  = CD AB  AB  AB  AB = CD AB  B AB  B CU IDOL SELF LEARNING MATERIAL (SLM)

SOP and POS 2 117  = CD A  A = CD Examples: 1. The logical expression representing a logic circuit is Y = ∑ m (2, 3, 5, 6, 7, 9, 13, 15) + d(8, 11). Draw the K-map and find the minimized logical expression Solution: From the given expression, Y = m2 + m3 + m5 + m6 + m7 + m9 + m13 + m15 + d (8, 11) Y = 0010 + 0011 + 0101 + 0110 + 0111 + 1001 + 1101 + 1111 + d (1000 + 1011) Table 8.9 AB AB AB AB CD 0 0 0 0 CD 0 1 0 1 CD 1 1 1 X CD 1 1 0 0 2. The logical expression representing a logic circuit is Y = ∏ M (2, 3, 5, 6, 7, 9, 13, 15) + d(8, 11). Draw the K-map and find the minimized logical expression. Solution: From the given expression, Y = M2 + M3 + M7 + M6 + M11 + M14 + M15 + d (0, 10, 8) Y = 0010 + 0011 + 0111 + 0110 + 1011 + 1110 + 1111 + d (0000 + 1010 + 1000) The K-map structure will be: CU IDOL SELF LEARNING MATERIAL (SLM)

118 Digital Circuits and Logic Designs CD AB Table 8.10 AB AB AB 00 11 10 AB C D 00 x 01 x C D 01 CD 11 0 0 0 0 C D 10 0 0 0 x Y= C 3. Simplify the expression given below using K-map. Y = ∑ m (0, 3, 4, 6, 9, 12) + d (1, 2, 10). Solution: Y = ∑ m (0, 3, 4, 6, 12) + d (1, 2, 10) Therefore, Y = ∑ m (0000, 0011, 0100, 0110, 1100) + d (0001, 0010, 1010) CD AB Table 8.11 AB AB AB 00 AB 11 10 01 C D 00 1 1 1 0 0 C D 01 x 0 0 0 0 0 0 CD 11 1 1 x C D 10 x Y = A B + A C D +B C D 8.4 Summary When we add two or multiple product terms by a Boolean addition, the output expression is a sum-of-products (SOP). For example, the expression a’bc’ + a’bd’ + a’bc’d shows a SOP expression. It can also have a single variable term within the expression like a + bc +a’b. These CU IDOL SELF LEARNING MATERIAL (SLM)

SOP and POS 2 119 logical expressions are simplified in a way that they must not contain redundant information while creating the minimal version of it. POS (Product of Sum) is the representation of the Boolean function in which the variables are first summed, and then the Boolean product is applied in the sum terms. For example, (a’+b).(a+b’+c) is POS expression where we can see that the variables are added then each bigger term is the product of the other. The SOP and POS, both forms are used for representing the expressions and also holds equal importance. In an effort for finding whether your reduced Boolean expression is correct or not for designing the logical circuit, one can compare the SOP and POS form of expression and check whether they are equivalent or not. Additionally, for any binary value, the resultant of SOP and POS are either be both 1 or 0 based on the binary value. 8.5 Key Words/Abbreviations  K-map: Karnaugh map  Quad: A group of four adjacent 1’s (or 0’s) is called a quad.  Octet: A group of eight adjacent 1’s (or 0’s) is called a octet. 8.6 Learning Activity 1. Simplify the expression given below using K-map. Y = ∑ m (0, 3, 4, 6, 9, 12) + d (1, 2, 10) ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 2. Simplify the logic expression F (A, B, C, D, E) = ∑ m (0, 5, 6, 8, 9, 10, 11, 16, 20, 24, 25, 26, 27, 29, 31) ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- CU IDOL SELF LEARNING MATERIAL (SLM)

120 Digital Circuits and Logic Designs 8.7 Unit End Questions (MCQ and Descriptive) A. Descriptive Type Questions 1. Draw Karnaugh map. 2. Explain various techniques of Karnaugh map. 3. To solve problems related to logic simplification. B. Multiple Choice/Objective Type Questions 1. LSI stands for __________. (a) Large Scale Integration (b) Large System Integration (c) Large Symbolic (d) Large Symbolic Integration 2. Which operation is shown in the following expression: (X+Y’) (X+Z) (Z’+Y’) (a) NOR (b) EX-OR (c) SOP (d) POS 3. The number of minterms for an expression comprising of 3 variables? (a) 8 (b) 3 (c) 0 (d) 1 4. The number of cells in a K-map with n-variables. (a) 2n (b) n2 (c) 2n (d) n 5. The output of AND gates in the SOP expression is connected using the __________ gate. (a) XOR (b) NOR (c) AND (d) OR Answers 1. (a), 2. (c), 3. (a), 4. (c), 5. (d) CU IDOL SELF LEARNING MATERIAL (SLM)

SOP and POS 2 121 8.8 References 1. https://www.google.com/searchq=sop+pos+form&rlz=1C1CHBF_enIN862IN862&oq =sop+pos+form&aqs=chrome..69i57j0l7.6908j0j8&sourceid=chrome&ie=UTF-8 2. https://www.electronicshub.org/boolean-logic-sop-form-pos-form/   CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 9 COMBINATIONAL LOGIC CIRCUITS Structure: 9.0 Learning Objectives 9.1 Introduction 9.2 Difference between Combinational and Sequential Circuit 9.3 Multiplexer 9.4 Demultiplexer 9.5 Flip-flop 9.6 Adder 9.7 Subtractor 9.8 Summary 9.9 Key Words/Abbreviations 9.10 Learning Activity 9.11 Unit End Questions (MCQ and Descriptive) 9.12 References 9.0 Learning Objectives After studying this unit, you will be able to:  Define combinational circuits and sequential circuits  Draw the block diagram of multiplexer, demultiplexer, adder and subtractor  Explain functioning of multiplexer, demultiplexer, adder and subtractor

Combinational Logic Circuits 123 9.1 Introduction Combinational Logic Circuits are memoryless digital logic circuits whose output at any instant in time depends only on the combination of its inputs unlike Sequential Logic Circuits whose outputs are dependant on both their present inputs and their previous output state giving them some form of memory. The outputs of Combinational Logic Circuits are only determined by the logical function of their current input state, logic “0” or logic “1”, at any given instant in time. The output of combinational circuit, at any instant of time, depends only on the levels present at input terminals. The combinational circuit do not use any memory. The previous state of input does not have any effect on the present state of the circuit. 9.2 Difference between Combinational and Sequential Circuit (i) Combinational Circuits Combinational circuits are defined as the time-independent circuits which do not depend upon previous inputs to generate any output and termed as combinational circuits. Combination logic circuits are made up from basic logic AND, OR or NOT gates that are “combined” or connected together to produce more complicated switching circuits. As combination logic circuits are made up from individual logic gates, they can also be considered as “decision making circuits” and combinational logic is about combining logic gates together to process two or more signals in order to produce at least one output signal according to the logical function of each logic gate. Combinational Circuit —  Output depends only upon present input.  Speed is fast.  It is designed easily.  There is no feedback between input and output.  This is time-independent.  Elementary building blocks: Logic gates. CU IDOL SELF LEARNING MATERIAL (SLM)

124 Digital Circuits and Logic Designs  Used for arithmetic as well as Boolean operations.  Combinational circuits do not have capability to store any state.  As combinational circuits do not have clock, they do not require triggering.  These circuits do not have any memory element.  It is easy to use and handle.  Examples – Encoder, Decoder, Multiplexer and Demultiplexer. (ii) Sequential Circuits Sequential circuits are those which are dependent on clock cycles and depends on present as well as past inputs to generate any output. There are many applications in which digital output are required to be generated in accordance with which the input signal are received. These requirements are not fulfilled by combinational logic system. These applications require output to be generated that are not only dependent on the present output to be generated, but they are also dependent on the history of these inputs. The past history is provided by feedback from the output back to the input. Sequential Circuit –  In this, output depends upon present as well as past input.  Speed is slow.  It is designed tough as compared to combinational circuits.  There exists a feedback path between input and output.  This is time-dependent.  Elementary building blocks: Flip-flops.  Mainly used for storing data.  Sequential circuits have capability to store any state or to retain earlier state.  As sequential circuits are clock dependent, they need triggering.  These circuits have memory element. CU IDOL SELF LEARNING MATERIAL (SLM)

Combinational Logic Circuits 125  It is not easy to use and handle.  Examples – Flip-flops, Counters. Combinational Circuit Sequential Circuit It contains no memory elements. It contains memory elements. The present value of its outputs are determined The present value of its outputs are determined by solely by the present values of its inputs. the present value of its inputs and its past state. Its behavior is described by the set of output Its behavior is described by the set of next-state functions. (memory) functions and the set of output functions. 9.3 Multiplexer A Multiplexer is a device that selects between several (analog or digital) input signals and forwards it to a single output line. If a multiplexer has n data inputs, m select input and only one output, then relation between number of data inputs (n) and number of select lines (m) is given by n = 2m. n input Multiplexer 1 output signals signal Enable / strobe m select lines Fig. 9.1: Basic Multiplexer Diagram Depending on the digital code apply at the select lines, one of the n data is selected and transmitted to the single output. Hence, Multiplexer is also called as Data Selector. The function of the multiplexer can be easily understood from the above block diagram. CU IDOL SELF LEARNING MATERIAL (SLM)

126 Digital Circuits and Logic Designs The primary use of Multiplexers is to increase the amount of data that can be sent over the network within a certain amount of time and bandwidth. Another use of Multiplexers is to implement Boolean functions of multiple variables. Different Multiplexers 1. 16:1 Multiplexer 2. 2:1 multiplexer 1. 16:1 Multiplexer: Implement 16 × 1 Multiplexer using 8 × 1 Multiplexer and 2 × 1 Multiplexer. We know that 8 × 1 Multiplexer has 8 data inputs, 3 selection lines and one output whereas 16 × 1 Multiplexer has 16 data inputs, 4 selection lines and one output. So, we require two 8 × 1 Multiplexers in the first stage in order to get the 16 data inputs. Since each 8 × 1 Multiplexer produces one output, we require a 2 × 1 Multiplexer in second stage by considering the outputs of first stage as inputs and to produce the final output. A, B, C and D are control inputs. D0 to D15 are data inputs. Io T1 I2 I3 I4 T5 I6 16 × 1 I7 MUX 0 I8 I0 I10 I11 I12 I13 I14 I15 S0 S1 S2 S3 Fig. 9.2: Multiplexer Diagram 16:1 CU IDOL SELF LEARNING MATERIAL (SLM)

Combinational Logic Circuits 127 0 0 1 1 MUX 2 2 4×1 3 3 4 S1 S0 5 6 0 MUX 7 1 8 2 4×1 9 3 10 S1 S0 0 11 1 MUX f 12 13 2 4×1 14 3 15 S1 S0 0 1 MUX AB 2 4×1 3 S1 S0 0 1 MUX 2 4×1 3 S1 S0 Fig. 9.3: Multiplexer Diagram 16:1 using 4:1 Multiplexer Table 9.1: Truth Table Selection Inputs Output S3 S2 S1 S0 Y 0000 I0 0001 I1 0010 I2 0011 I3 0100 I4 0101 I5 0110 I6 0111 I7 1000 I8 CU IDOL SELF LEARNING MATERIAL (SLM)

128 Digital Circuits and Logic Designs 1001 I9 1010 I10 1011 I11 1100 I12 1101 I13 1110 I14 1111 I15 2. 2:1 Multiplexer: As the name suggests, the functioning of this multiplexer is very clear. It will have 2 input signals, 1 output signal and select line is calculated as 2 = 21. Therefore, 1 select line. The Strobe or Enable pin (E) determines the operating condition of the Multiplexer. If E = 1, the multiplexer is in the working condition. If E = 0, the multiplexer will not work. The block diagram and truth table are as follows: D0 D1 2:1 MUX Y E So Fig. 9.4: Block Diagram of 2:1 Multiplexer Table 9.2: Select Input Enable (E) Select Input (m) Output (Y) 0 0 0 0 1 0 1 0 D0 1 1 D1 CU IDOL SELF LEARNING MATERIAL (SLM)

Combinational Logic Circuits 129 S D1 D0 Fig. 9.5: Multiplexer Circuit using Logic Gates 9.4 Demultiplexer A Demultiplexer is a circuit which performs the reverse operation of Multiplexer. It accepts a single input and distributes it over several outputs. In Demultiplexer, there is only one input line. If m select lines are present and n output lines are present, then relation n = 2m is established. Data Demultiplexer n output input signals Enable /Strobe m select lines Fig. 9.6: Block Diagram of Demultiplexer CU IDOL SELF LEARNING MATERIAL (SLM)

130 Digital Circuits and Logic Designs Different Demultiplexers 1. 1:8 Demultiplexer 2. 1:4 Demultiplexer 3. 1:2 Demultiplexer 1. 1:8 Demultiplexer: This Demultiplexer has one input signal and eight output signals 8 = 23, hence 3 select lines. The block diagram and truth table of Demultiplexer is as shown below: Input Outputs Din YO Y1 Y2 Y3 Y4 Y5 Y6 Y7 S2 S1 S0 Fig. 9.7: Block Diagram of 1:8 Demultiplexer Din Din YO Y1 A 1:4 Y2 DEMUX Y3 B C E S0 Y4 S1 Y5 C Y6 S1 S0 Y7 Din 1:4 DEMUX E Fig. 9.8: Block Diagram of 1:8 Demultiplexer using 1:4 Demultiplexer CU IDOL SELF LEARNING MATERIAL (SLM)

Combinational Logic Circuits 131 Data Input Table 9.3: Select Input Outputs Selection Inputs D S2 S1 S0 Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y0 D 0000000000D D 0 0 1 0 0 0 0 0 0D0 D 0 1 0 0 0 0 0 0D0 0 D 0 1 1 0 0 0 0D0 0 0 D 1 0 0 0 0 0D0 0 0 0 D 1 0 1 0 0D0 0 0 0 0 D 1 1 0 0D0 0 0 0 0 0 D 1 1 1D0 0 0 0 0 0 0 2. 1:4 Demultiplexer: This Demultiplexer has one input signal and four output signals 4 = 22, hence 2 select lines. The block diagram and truth table of Demultiplexer is as shown below: Input 1:4 Outputs Din DEMUX Y0 Y1 Y2 Y3 S1 S0 Fig. 9.9: Block Diagram of 1:4 Demultiplexer Table 9.4: Truth Table and K-map Din S1 S0 YO Y1 Y2 Y3 1001000 1010100 1100010 1110001 CU IDOL SELF LEARNING MATERIAL (SLM)

132 Digital Circuits and Logic Designs S1 S0 Din Y0 Y1 Y2 Y3 Fig. 9.10: 1:4 Demultiplexer using Logic Gates 3. 1:2 Demultiplexer: This Demultiplexer has one input signal and two output signals 2 = 21, hence 1 select line. The block diagram and truth table of Demultiplexer is as shown below: E Outputs Y1 Input D Y0 Select S Fig. 9.11: Block Diagram of 1:2 Demultiplexer Table 9.5: Select Input Select Input Outputs S 0 D Y1 Y0 0 0 1 00 1 1 0 10 0 00 11 9.5 Flip -flop Flip-flop is formed using logic gates, which are in turn made of transistors. They are basic building blocks in the memory of electronic devices. They are widely used in: CU IDOL SELF LEARNING MATERIAL (SLM)

Combinational Logic Circuits 133  Registers: As the flip-flops have two stable states, we use them in memory elements like registers for data storage. Generally, we use registers in electronic devices like computers.  Counters: The groups of interconnected flip-flops are uses as counters to count the increment or decrement of an event occurrence.  Frequency division: Flip-flops are used as frequency division circuits, which divide the input frequency exactly to its half. Frequency division circuits are used to regularize the frequency of electronic circuits.  Data transfer: We use shift registers (A special type of registers) to transfer the data from one flip-flop to another, which are connected in a specific order. Types of Flip-flops Based on their operations, flip-flops are basically of four types. They are: 1. R-S flip-flop 2. D flip-flop 3. J-K flip-flop 4. T flip-flop 1. S-R Flip-flop S The S-R flip-flop is basic flip-flop among all the flip- Q flops. All the other flip-flops are developed after SR-flip- CK flop. R SR flip-flop is represented as shown in the adjoining figure. Fig. 9.12: SR Flip-flop S-R stands for SET and RESET. This can also be called RS flip-flop. Difference is RS is inverted SR flip-flop. Any flip-flop can be build using logic gates. NAND and NOR gates were used as they are universal gates. CU IDOL SELF LEARNING MATERIAL (SLM)

134 Digital Circuits and Logic Designs Table 9.6: Truth Table of SR Flip-flop Inputs Outputs Action S R Q Q’ 0 0 Qn Q’n No Change 0 1 0 1 Reset 1 0 1 0 Set 1 1 0 0 Undefined Working: From the above truth table, it is clear that SR flip-flop will be set or reset for four conditions. 1. For last condition, it will be in invalid state. 2. SR flip-flop will be set when S = 1 and R = 0. If S = 1 and R = 1, then the previous state is remembered by the flip-flop. 3. Flip-flop will be reset when S = 0 and R = 1. If S = 1 and R = 1, then it will remember the previous state. 4. But when both the inputs are zeros, SR flip-flop will be in an uncertain state where both Q and Q’ will be same. This is not same allowed.. 2. D Flip-flop D Q In the SR flip-flop, an uncertain state CP Q’ occurred. This can be avoided by using D flip-flop. Here, D stands for “Data”. It is constructed from SR flip-flop. The Fig. 9.13: D Flip-flop two inputs (S and R) of the clocked SR flip-flop are connected to an inverter. It is one of the most widely used flip-flops. It has a clock signal (Clk) as one input and data (D) as other. There are two outputs and these outputs are complement to each other. CU IDOL SELF LEARNING MATERIAL (SLM)

Combinational Logic Circuits 135 Table 9.7: Truth Table of D Flip-flop Clk D Q Q 0 0 QQ 0 1 QQ 1001 1110 Working:  D flip-flop will work depending on the clock signal.  When the clock is low, there will be no change in the output of the flip-flop, i.e., it remembers the previous state.  When the clock signal is high and if it receives any data on its data pin, it changes the state of output.  When data is high, Q is reset to 0, while Q is set to 0 if data is low. A master slave D flip-flop can be constructed using D flip-flop. 3. J-K Flip-flop JK flip-flop is named after Jack Kilby, an electrical engineer who invented IC. A JK flip-flop is a modification of SR flip-flop. In this, the J input is similar to the set input of SR flip-flop and the K input is similar to the reset input of SR flip-flop. The condition J = K = 1 which is not allowed in SR flip-flop (S = R = 1) is interpreted as a toggle command.  Two data inputs J and K.  One clock signal input (CLK).  Two outputs Q and Q’. CU IDOL SELF LEARNING MATERIAL (SLM)

136 Digital Circuits and Logic Designs K latch latch Q C Pulse detector toggle toggle latch latch J Q latch latch latch latch latch latch Fig. 9.14: JK Flip-flop Working:  When J is low and K is low, Q returns its previous state value, i.e., it holds the current state.  When J is low and K is high, the flip-flop will be in reset state, i.e., Q = 0, Q’ = 1.  When J is high and K is low, the flip-flop will be in set state, i.e., Q = 1, Q’ = 0.  When J is high and K is high, the flip-flop will be in Toggle state or flip state. This means that the output will complement to the previous state value. 4. T Flip-flop D Q In the SR flip-flop, an uncertain state CP Q’ occurred. This can be avoided by using D flip-flop. Here, D stands for “Data”. It is constructed from SR flip-flop. The Fig. 9.15: T Flip-flop two inputs (S and R) of the clocked SR flip-flop are connected to an inverter. T flip-flop is also known as “Toggle Flip-flop”. Toggle is to change the output to complement of the previous state in the presence of clock input signal. CU IDOL SELF LEARNING MATERIAL (SLM)

Combinational Logic Circuits 137  T input.  One clock signal input (CLK).  Two outputs Q and Q’. CIK Q(t) T Q(t)’ Fig. 9.16:T Flip-flop Table 9.8: Truth Table of T Flip-flop T Qn Qn+1 000 011 101 110 Working: The operation of the T flip-flop is explained below. When the T input is low, the next sate of the T flip-flop is same as the present state, i.e., it holds the current state.  T = 0 and present state = 0 then the next state = 0.  T = 0 and present state = 1 then the next state = 1. When the T input is high, then the next sate of the T flip-flop is toggled, i.e., it is same as the complement of present state on clock transition.  T = 1 and present state = 0 then the next state = 1.  T = 1 and present state = 1 then the next state = 0. CU IDOL SELF LEARNING MATERIAL (SLM)

138 Digital Circuits and Logic Designs 9.6 Adder An adder, also called summer, is a digital circuit that performs addition of numbers. Adder circuit is a combinational digital circuit that is used for adding two numbers. It produces a sum bit (denoted by S) and a carry bit (denoted by C) as the output. Adders are used for adding binary numbers but they can also be used for adding other formats like BCD (Binary Coded Decimal, XS-3, etc.). Besides addition, adder circuits can be used for a lot of other applications in digital electronics like address decoding, table index calculation, etc. Adder circuits are of two types: 1. Half adder 2. Full adder. 1. Half adder: Half adder is a combinational arithmetic circuit that adds two numbers and produces a sum bit (S) and carry bit (C) as the output. If A and B are the input bits, then sum bit (S) is the X-OR of A and B and the carry bit (C) will be the AND of A and B. Thus, a half adder circuit can be easily constructed using one X-OR gate and one AND gate. The disadvantage of half adder circuit is that it can add only two input bits (A and B) and has nothing to do with the carry if there is any in input. So, if the input to a half adder have a carry, then it will be neglected and only A and B bits will be added. That means the binary addition process is not complete and that is why it is called a half adder. The truth table, schematic representation and XOR/AND realization of a half adder are shown in the figure below. Circuit Diagram: A SUM B CARRY Fig. 9.17: Half Adder CU IDOL SELF LEARNING MATERIAL (SLM)

Combinational Logic Circuits 139 Table 9.9: Truth Table of Half Adder Input Output A B Sum (S) Carry (C) 0 00 0 0 11 0 1 01 0 1 10 1 Binary calculation: 0 + 0 = 0 0+1=1 1+0=1 1 + 1 = 10 Boolean Equation: Symbol S Sum S = A  B AB A B HA A Carry – C = AB C B 2. Full adder: This type of adder is a Fig. 9.18: Half Adder Sum little more difficult to implement than a half adder. The main difference between a Circuit Diagram half adder and a full adder is that the full a b Cin adder has three inputs and two outputs. The first two inputs are A and B and the third Cout input is an input carry designated as Cin. The full adder is used as basic Fig. 9.19: Full Adder building block of a 4-bit, 8-bit and BCD adder. CU IDOL SELF LEARNING MATERIAL (SLM)

140 Digital Circuits and Logic Designs Symbol Table 9.10: Truth Table of T Flip-flop A Input Output B CIN A B C Sum (S) Carry (C) 0 00 0 0 0 01 1 0 0 10 1 0 0 11 0 1 1 00 1 0 1 01 0 1 1 10 0 1 1 11 1 1 COUT Boolean Equation S S = A  B  Cin FULL Cout = AB A  C  B C ADDER in in Fig. 9.20: Symbol of Full Adder (a) Full Adder using Half Adder: A full-adder can also be constructed from two half adders and an OR gate, as shown in the diagram below. Consider the addition of A + B + Cin. This can be grouped as (A + B) + Cin where A + B represents the output of the half adder that receives A and B inputs. This partial sum is added to Cin by the other half adder, yielding the complete sum bit S. If any of the half adder logic produces a carry, there will be an output carry. Thus, Cout will be an OR function of the half adder Carry outputs. CU IDOL SELF LEARNING MATERIAL (SLM)

Combinational Logic Circuits 141 Logic Diagram Cout S AA C HALF BB ADDER S AC Cin HALF ADDER BS Circuit Diagram Fig. 9.21: Full Adder using Half Adder A BS Ci Co Fig. 9.22: Circuit Diagram Boolean Equation S = A BC in Cout = ((A  B)  C )  (A  B) in = (A  B  A B) C  A B in = AB  C  A B C  A B in in = AB  C  A B C  A B(1 C ) in in in = AB  C  A B C  A B  A  B C in in in = B  C (A  A)  A B  C  A B in in CU IDOL SELF LEARNING MATERIAL (SLM)

142 Digital Circuits and Logic Designs = B  C  A B  C  A B in in = B  C  A B  C  A B(1 C ) in in in = B  C  A B  C  A B  A B  C in in in = B  C  A B  A C (B  B) in in = B  C  A B  A C in in = A B A C B  C in in 6.5.1 N-bit binary Adder Half adder and full adder circuit can be used to add 1-bit numbers only. But if we want to add together two n-bit numbers, then n number of 1-bit full adders need to be connected or “cascaded” together to produce Ripple Carry Adder. Cascading is a process of connecting output of one circuit to the input of next. A “ripple carry adder” is simply “n” 1-bit full adders cascaded together with each full adder representing a single weighted column in a long binary addition. It is called a ripple carry adder because the carry signals produce a “ripple” effect through the binary adder from, LSB to MSB. For example, to add together two 4-bit numbers, the two outputs of the first full adder will provide the first place digit sum (S) of the addition plus a carry-out bit that acts as the carry-in digit of the next binary adder. The second binary adder in the chain also produces a summed output (the 2nd bit) plus another carry-out bit and we can keep adding more full adders to the combination to add larger numbers, linking the carry bit output from the first full binary adder to the next full adder, and so forth. CU IDOL SELF LEARNING MATERIAL (SLM)