E-LESSON-8

IDOL Institute of Distance and Online Learning ENHANCE YOUR QUALIFICATION, ADVANCE YOUR CAREER.

B.C.A 2 All right are reserved with CU-IDOL Digital Circuits and Logic Designs Course Code: BCA111 Semester: First SLM Units: e-Lesson No: 8 5 www.cuidol.in Unit-8 (BCA111)

SOP and POS 2 33 OBJECTIVES INTRODUCTION INTRODUCTION After studying this unit, you will be able to: • Draw Karnaugh map In this session we are going to learn about • Explain various techniques of Karnaugh map • Karnaugh map • Solve problems related to logic simplification • Various techniques of Karnaugh map • Problems related to logic simplification www.cuidol.in Unit-8 (BCA111) INASllTITriUgThEt aOrFeDreISsTeArNvCedE AwNitDh OCNUL-IIDNOE LLEARNING

TOPICS TO BE COVERED 4 1. Introduction 2. Karnaugh Map (K-map) 3. Simplification of Boolean Expression using Karnaugh Map Techniques (Upto 4 Variables) www.cuidol.in Unit-8 (BCA111) All right are reserved with CU-IDOL

Introduction 5 • 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. www.cuidol.in Unit-8 (BCA111) All right are reserved with CU-IDOL

Karnaugh Mapmap) 6 • 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. www.cuidol.in Unit-8 (BCA111) All right are reserved with CU-IDOL

Karnaugh Mapmap) 7 • 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. www.cuidol.in Unit-8 (BCA111) All right are reserved with CU-IDOL

Karnaugh Map 8 map) www.cuidol.in Unit-8 (BCA111) All right are reserved with CU-IDOL

Karnaugh Mapap) 9 www.cuidol.in Unit-8 (BCA111) All right are reserved with CU-IDOL

Karnaugh Mapmap) 10 www.cuidol.in Unit-8 (BCA111) All right are reserved with CU-IDOL

Grouping in K-map) 11 • 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 variables from a term. • (iii) Octet: A group of eight adjacent 1’s (or 0’s) is called a octet. An octet eliminates variables from a term www.cuidol.in Unit-8 (BCA111) All right are reserved with CU-IDOL

Rules to Solve Boolean Expression using K-Map 12 (K-map) • In SOP, groups must not contain any cell containing ‘0’ and in POS, groups must not contain any cell containing ‘1’. • Groups must be formed horizontal or vertical but not diagonal. • 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. Groups must contain 1, 2, 4 or 8 cells. • Each 1 (or 0 in case of POS) must be present in at least one group. • Groups can overlap each other. • There should be as few groups as possible. • Redundant groups must be avoided. www.cuidol.in Unit-8 (BCA111) All right are reserved with CU-IDOL

Don’t care condition in Karnaugh Map 13 • 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 www.cuidol.in Unit-8 (BCA111) All right are reserved with CU-IDOL

Simplification of Boolean Expression using 14 Karnaugh Map (K-map) Techniques • A logic expression in the standard SOP form is as follows: • Y = A BC + A B C + ABC + A B C + A B C www.cuidol.in Unit-8 (BCA111) All right are reserved with CU-IDOL

Simplification of Boolean Expression…. 15 www.cuidol.in Unit-8 (BCA111) All right are reserved with CU-IDOL

Simplification of Boolean Expression… 16 • 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 • Sol: 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) • The logical expression representing a logic circuit is Y = Π M (2, 3, 5, 6, 7, 9, 13, 15) + d(8, 11). www.cuidol.in Unit-8 (BCA111) All right are reserved with CU-IDOL

Simplification of Boolean Expression using Karnaugh Map 17 (K-map) Techniques • A logic expression in the standard SOP form is as follows: www.cuidol.in Unit-8 (BCA111) All right are reserved with CU-IDOL

Multiple Choice Questions 18 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 Answers: 1.(a) 2.(c) 3.(a) www.cuidol.in Unit-8 (BCA111) All right are reserved with CU-IDOL

SUMMARY 19 Let us recapitulate the important concepts discussed in this session: •The Karnaugh Map, also known as the K-map, is a method to simplify Boolean expressions. •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. •In K-map, grouping is done on most number of 1’s for SOP and most number of 0’s for POS. •In POS procedure remains the same, only 1 is replaced by 0. •In SOP, groups must not contain any cell containing ‘0’ and in POS, groups must not contain any cell containing ‘1’. •Groups must be formed horizontal or vertical but not diagonal. •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. www.cuidol.in Unit-8 (BCA111) All right are reserved with CU-IDOL

FREQUENTLY ASKED QUESTION 20 Q1. Elaborate don't care condition in K-Map. Ans: 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. For Further details please refer to the subject SLM unit 8. Q2. Simplify the expression given below using K-map. Y = Σ m (0, 2, 3, 4, 6, 9, 12) + d (1, 2,10). Ans: For Further details please refer to the subject SLM unit 8. www.cuidol.in Unit-8 (BCA111) All right are reserved with CU-IDOL

References 21 1. www.tutorialspoint.com 2. Self Learning Material, Institute of Distance and Online Learning, Chandigarh University 3. docplayer.net 4. www.csie.nuk.edu.tw 5. www.thevbprogrammer.com 6. probabilitylectures.narod.ru 7. ergopalkrishnawithc.blogspot.in 8. www.ensolt.com 9. www.encoder.com 10. Lala. \"Number Systems and Binary Codes\", Principles of Modern Digital Design, 11. www.slideshare.net 12. www.freepatentsonline.com www.cuidol.in Unit-8 (BCA111) All right are reserved with CU-IDOL

22 THANK YOU www.cuidol.in Unit-8 (BCA111) All right are reserved with CU-IDOL