Logic gates and Boolean Algebra_VSG

Digital Electronics:
- Logic Gates
-Universal Gates
-Boolean Algebra rules and laws
- K-Map technique

1. Prof. Vaibhav S. Galbale Assistant Professor MIT,ACSC,Alandi,Pune F.Y.B.Sc. Electronics of B.Sc (Computer Science) SEMESTER I PAPER II ELC 112: Principles of Digital Electronics 2 Credits

2. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Unit 2: Logic gates and Boolean Algebra Contents:- Logic gates (NOT, AND, OR, NAND, NOR, XOR gate) with their symbol, Boolean equation and truth table, Universal gates. Introduction of CMOS and TTL logic families, Parameters like voltage levels, propagation delay, noise margin, fan in, fan out, power dissipation (TTL NAND, inverter, CMOS gates etc. not expected) Rules and laws of Boolean algebra, De Morgan’s theorem, simplification of Logic equations using Boolean algebra rules, Min terms, Max terms, Boolean expression in SOP and POS form, conversion of SOP/POS expression to its standard SOP/POS form Introduction to Karnaugh Map, problems based on SOP (upto 4 variables), digital designing using K Map for: Gray to Binary and Binary to Gray conversion

3. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic gates Introductions:- Logic gates are the basic components in digital electronics. These gates are used to create digital circuits right from simple to complex logic circuit and even complex integrated circuits. Complex microprocessor or microcontroller ICs are constructed using many logic gates. Logic gates are the fundamental building blocks of all digital systems. It has one or more inputs and one output with some logical relationship between them. Logic gate accepts binary signals i.e. True or False, ON or OFF, 1 or 0 and have an ability to make decisions. The state of the output is decided by the input states. All logic gates implements some Boolean function which correlates output with input through some logical operation. Logic gates are mainly designed with the electronic switches using diodes and transistors. There are three basic gates – AND, OR and NOT . NAND and NOR gates are derived gates are also known as universal logic gates. An XOR gate is inequality detector gate and can be used in comparator, adders, parity generators etc.

4. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic gates Introductions:- The original ANSI/IEEE distinctive shape symbols and new ANSI/IEEE standard outline symbols of logic gates are prominently introduced. Logic gates are commercially available in two basic logic families, such as IC 74XX series for TTL (Transistor Transistor Logic) and IC 40XX/45XX for CMOS (Complementary Metal Oxide Semiconductor) series. These all logic gates packaged as Small Scale Integration (SSI) ICs. Digital systems are constructed using logic gates. The logic gate is the most basic building block of any digital system capable of making decision including computers. Each one of the basic logic gates is a piece of hardware or an electronic circuit that can be used to implement some basic logic expression. It is an electronic circuit with one or many inputs and only one output.

5. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic gates NOT gate: NOT gate has one-input and one-output. It is a logic circuit whose output is always the complement of the input. Figure indicates the logic symbol and truth table of NOT gate along with simple implementation using switches. The NOT gate is popularly known as inverter. It performs logical inversion or complementation.

6. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic gates AND gate : AND gate is a logic circuit having two or more inputs and one output. The AND gate performs logical multiplication i.e. AND function. Figure indicates the logic symbol and truth table of two input AND gate along with simple implementation using switches. “The output of an AND gate is HIGH only when all of its inputs are in the HIGH state. In all other cases, the output is LOW.” For AND gate, Y = A.B

7. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic gates OR Gate : An OR gate is a logic circuit with two or more inputs and one output. The OR gate performs logical addition i.e. OR function. Figure shows the logic symbol and truth table of two input OR gate along with simple implementation using switches. “The output of an OR gate is LOW only when all of its inputs are in the LOW state. In all other cases, the output is HIGH.” For OR gate, Y = A + B

8. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic gates NAND gate: NAND gate is combination of AND and NOT gates. The NAND gate provides AND functions with inverted output. Figure shows the logic symbol and truth table of two input NAND gate along with simple implementation using switches. For NAND gate, Y = A.B “The output of a NAND gate is a logic ‘0’ when all its inputs are a logic ‘1’. For all other input combinations, the output is a logic ‘1’.”

9. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic gates NOR gate: NOR gate is combination of OR and NOT gates. The NOR gate provides OR function with inverted output. Figure shows the logic symbol and truth table of two input NOR gate along with simple implementation using switches. For NOR gate, Y = A + B “The output of a NOR gate is a logic ‘1’ when all its inputs are logic ‘0’. For all other input combinations, the output is a logic ‘0’.”

10. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic gates XOR (Exclusive OR) gate: Exclusive OR gate is basically designed to exclude the condition of standard OR gate so as to generate real binary addition. An XOR gate is a two inputs and one output logic circuit. Figure indicates the logic symbol and truth table of two input XOR gate along with simple implementation using switches. For XOR gate, Y = A .B + A .B “The output of an XOR gate is at logic ‘1’ when the inputs are dissimilar and at logic ‘0’ when the inputs are similar.”

11. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic gates X NOR (Exclusive NOR) gate: XNOR is obtained by the combination of NOT and XOR gates. XNOR gate is a two inputs and one output XOR gate with active low output. Figure indicates the logic symbol and truth table of two input XNOR gate along with simple implementation using switches. For X NOR gate, Y = A .B + A .B “The output of an XNOR gate is at logic ‘1’ when the inputs are similar and at logic ‘0’ when the inputs are dissimilar.”

12. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic gates Universal Logic Gates : Any Boolean / logic expression can be realized using the AND, OR, and NOT gates. From these three primary gates, two derived gates NAND and NOR are usually realized. It is possible to construct basic gates namely NOT, AND, OR using combination of NAND gates or a combination of NOR gates . For this reason NAND and NOR gates are called as universal logic gates. NAND gate as universal logic gate : Let us consider now NAND gate as a universal logic gate. Figure shows the implementation of basic logic gates using only NAND gates. NAND gate can be used to as NOT gate by connecting all its inputs together and applying input to the common terminal. The output of NAND gate generates output as NOT A.

13. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Universal Logic gates NAND gate as universal logic gate : For constructing AND gate, two NAND gates are required. The first NAND gate provides complement of A AND B., whereas the second NAND gate acts like an inverter. The double complement will cancel each other to provide AND gate.

14. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Universal Logic gates NAND gate as universal logic gate : Three NAND gates are required to construct the OR gate. First level two NAND gates will act like an inverter. These two inverters will complement the inputs. The third NAND gate will perform ANDing of the complemented inputs first and then inverts the result. This provides final output as logical OR functions.

15. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Universal Logic gates NOR gate as universal logic gate : Let us consider now NOR gate as a universal logic gate. Figure shows the implementation of basic logic gates using only NOR gates. A NOR gate can be used to as NOT gate by connecting all its inputs together and applying input to the common terminal. The output of NOR gate generates output as NOT A i.e. complement of A.

16. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Universal Logic gates NOR gate as universal logic gate : The construction of OR gate requires two NOR gates. The first NOR gate provides complement of A OR B. Whereas the second NOR gate acts like an inverter. The double complement will cancel each other to provide action of OR gate.

17. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Universal Logic gates NOR gate as universal logic gate : Three NOR gates are required to construct the AND gate. In the first level two NOR gates will act like an inverter. These two inverters will complement the inputs. The third NOR gate will perform ORing of the complemented inputs first and then inverts the result. This provides final output as logical AND functions.

18. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic Families Introduction of CMOS and TTL logic families: In today's world Integrated Circuits plays vital role miniaturization of technology. In IC it is possible to accommodate a number of powerful devices on a single chip. IC is an assembly of electronic components with miniature devices built up on a semiconductor substrate. Hence it featured with small size and low cost of IC’s.

19. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic Families Introduction of CMOS and TTL logic families:

20. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic Families Classification of logic families:

21. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic Families

22. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic Families

23. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic Families

24. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic Families

25. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic Families

26. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic Families Logic Level:- Logic level is the state of digital signal corresponding to DC voltage that represent logic 1 or logic 0. Each logic family has a specific range of voltage that represent logic 1 or logic 0. Logic family TTL MOS CMOS LOGIC Logic 1 Logic 0 Logic 1 Logic 0 Logic 1 Logic 0 VOLTAGE 2.4v To 5v 0v To 0.4v Supply Voltage 0v 3v To 18v 0v To 1.5v

27. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Parameters of Logic Families

28. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Parameters of Logic Families

29. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Parameters of Logic Families

30. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Parameters of Logic Families

31. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Parameters of Logic Families

32. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Parameters of Logic Families Power Dissipation: The power dissipation term indicates the amount of power dissipated by gates for its operation. It is determined by the current Icc that draws from a supply voltage Vcc. The average power dissipation is given by, Pd = Vcc X Icc

33. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune This is the time required for Input to produce the output. It is characterized by - Rise Time and Fall Time Parameters of Logic Families

34. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Parameters of Logic Families

35. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Parameters of Logic Families

36. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Parameters of Logic Families

37. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Parameters of Logic Families

38. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Parameters of Logic Families

39. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune TTL Logic Families:- Characteristics of TTL Logic Families The output of a TTL device can serve as an input to a maximum of 10 gates, i.e., the fan-out  is 10 . A  logic low voltage  for a TTL is defined between  0V-0.2V . A  logic high voltage  for a TTL is at  5V . The  noise margin  is at around  4V . The propagation delay is about  9ns . A typical TTL component draws a power of about  11mW . Advantages of TTL Logic Families TTL has a strong drive capability. It is least susceptible to electrical damage. Requires only one supply voltage (otherwise for CMOS) Lesser immune to noise when compared to ECL, but more than CMOS. Fastest saturation, when compared to other logic families Low output impedance for all states

40. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Disadvantages of TTL Logic Families TTL dissipates a lot of power, thus not making it suitable for battery-powered devices. Not recommended in VLSI chips as it requires more space and isolation Expensive compared to MOSFETs. Common TTL Logic Ics :- 74  family 74LS  (Low-power Schottky ) family 74F  (Fast) family 74AS  (Advanced Schottky ) family 74ALS  (Advanced Low-power Schottky ) family TTL Logic Families:-

41. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Characteristics of CMOS Logic Families CMOS supports a very large fan-out, more than 50 transistors. It has excellent noise immunity amongst all families. A  logic low voltage  for CMOS is about 0 volts to 1.5 volts A  logic high voltage  for CMOS is somewhere between  3.5V to 5V . The propagation delay is the worst when compared with TTL and ECL families at about 200ns. TTL Logic Families:-

42. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Logic Families:- Advantages of CMOS Logic Families Has the highest fan-out, when compared with TTL and ECL Works well over a wide range of temperature Noise immunity is better than TTL and ECL Disadvantages of CMOS Logic Families Average propagation delay is the least in comparison with TTL and ECL

43. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean Algebra Boolean Algebra Boolean algebra is an algebra for binary number system. Unlike traditional algebra, Boolean algebra is easy to learn. It operates only on two numbers 0 & 1. There are only three operations: addition, multiplication, and complementation. The algebra of a number system basically describes how to perform arithmetic using the operators of the system acting upon the system's variables. Boolean algebra describes the arithmetic of a two-state system and is therefore the mathematical language of digital electronics. The variables in Boolean algebra are represented by symbols such as A, B, C, X, Y etc.

44. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean Algebra Boolean Algebra The rules of Boolean algebra are different from those of conventional algebra in the following aspects: 1. Symbols used in Boolean algebra do not represent numerical values. 2. Arithmetic operations (addition, subtraction, multiplication, division etc.) are not performed in Boolean Algebra. E.g. 1+1 is not 2. 3. There are no fractions, negative numbers, squares etc. 4. Boolean algebra allows only two possible values (0 and 1) or (L or H) for any variable. These variables represent the input and output state (e.g. voltage in a circuit). These states can be represented by ‘0’ or ‘1’in Boolean algebra. Figure 1: Binary variables, operations and functions

45. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Parameters of Logic Families Boolean Algebra There are three basic operations ‒ Boolean product ‒ Boolean Sum ‒ Boolean complementation Boolean functions are implemented using combination of these operations. Addition and multiplication are two basic operations performed on the binary variables. Laws of Boolean Algebra The rules, laws and theorems of Boolean algebra can be used to simplify many a complex Boolean expression and also to transform the given expression into a more useful and meaningful equivalent expression. Similar to real algebra, the Boolean algebra also possess certain well – defined rules and laws.

46. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean Algebra Let us now discuss the most important laws of Boolean algebra. (I) Identity Law : A term ANDed with a ‘1’ or ORed with ‘0’ equal to that term. A.1=A [A variable ANDed with 1 is always equal to the variable.] . 2. A+0=A [A variable ORed with 0 is equal to the variable.]

47. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean Algebra Let us now discuss the most important laws of Boolean algebra. (II) Null Law : A term ANDed with a ‘0’ equals to 0 or ORed with ‘1’ will equal 1. 3. A.0=0 [A variable ANDed with 0 is always equal to 0.] 4. A+1=1 [A variable ORed with 1 is always equal to 1.]

48. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean Algebra Let us now discuss the most important laws of Boolean algebra. (III) Idempotent Law: An input that is ANDed or ORed with itself is equal to the input. 5. A.A = A [A variable ANDed with itself is always equal to the variable] 6. A+A =A [A variable ORed with itself is always equal to the variable]

49. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean Algebra Let us now discuss the most important laws of Boolean algebra. (IV) Inverse Law: A term ANDed with its complement equals ‘0’ and a term ORed with its complement equal 1. 7. A.A =0 [A variable ANDed with its complement is always equal to 0] 8. A+A =1 [A variable ORed with its complement is always equal to 1]

50. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean Algebra Let us now discuss the most important laws of Boolean algebra. (V) Double complementation: A term that is complemented twice is equal to the original term. 9. A = A [ A double complementation of a variable is always equal to the variable] (VI) Commutative Law: This law indicates that the order of application of two separate terms is not important. 10. A.B = B.A [ The order in which two variables are ANDed makes no difference on the Result.] 11. A+B=B+A [ The order in which two variables are ORed makes no difference on the Result.]

51. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean Algebra Let us now discuss the most important laws of Boolean algebra. (VII) Associative Law: This law enables the removal of the brackets from the expression and regrouping of the variables. 12. A.(B.C) = (A.B).C 13. A+(B+C) = (A+B) +C (VII) Distributive Law: This law allows the multiplying or factoring out an expression 14. A.(B+C) = A.B +A.C 15. A+(B.C) = (A+B).(B+C) (VIII) Absorptive Law: This law permits a reduction of a complicated expression to a simpler one by absorbing similar terms. 16. A.(A+B)=A 17. A+(A.B)=A

52. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean Algebra

53. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean Algebra

54. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean Algebra A+(A.B) = A.A +A.B (distributive law) = A +AB = A.(1+B) = A .1 = A

55. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean Algebra

56. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean Algebra

57. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean Algebra De Morgan’s Theorem: De Morgan , a mathematician has suggested two theorems which are extremely useful to simplify complicated boolean expressions. But before we look at DeMorgan’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. Truth Table for Each Logical Operation

58. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean Algebra De Morgan’s First Theorem: Is state that the complement of the product of variables is equal to the sum of the complements of each variables. Thus the equivalent of the NAND function will be a negative-OR function, proving that  A.B  = A + B. We can show this operation using the following table. =

59. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean Algebra De Morgan’s Second Theorem: Is state that the complement of the sum of variables is equal to the product of the complements of variables. Thus the equivalent of the NAND function will be a negative-OR function, proving that  A+B  = A . B We can show this operation using the following table. =

60. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune DeMorgan’s Equivalent Gates

61. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Minterm and Maxterm Minterm: The minterm represent when product of all variable or literal in thee given equation is in the either complement or without complement. The AND gate is used for making logic circuit using minterm equation. It is denoted by ‘m’: Ex. i ) ABC ii) ABC iii) ABC The equation represented by ANDing of variable with or without complement form. Maxterm: The maxterm represent when sum of all variable or literal in thee given equation is in the either complement or without complement. The OR gate is used for making logic circuit using maxterm equation. It is denoted by ‘M’: Ex. i ) A+B+C ii) A+B+C iii) A+B+C The equation represented by ORing of variable with or without complement form.

62. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Minterm and Maxterm Minterm & Maxterm table for 2 variables : A B Minterm(m) Maxterm(M) m0= A . B M0=A + B 1 m1= A .B M0=A+B 1 m2= A .B M0=A+B 1 1 m3= A.B M0=A+B

63. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean expression in SOP and POS form The boolean algebra the logical equation can be represented by two forms, i.e. Sum of Product(SOP) and Product of Sum (POS) by using them any logical representation can be obtained. Sum of Product (SOP) : The sum of product can be obtained when two or more product terms added by using the addition operator. These product term can b with complement or without complement form. Ex. Y= AB+AB Y= ABC +ABC Product of Sum(POS) : The product of sum can be obtained when two or more sum terms multiplied by using the multiplication or product operator. These product term can b with complement or without complement form. Ex. Y= (A+B).(A+B) Y= (A+B+C).(A+B+C)

64. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean expression in SOP and POS form Canonical or Standard SOP and POS form: The canonical or standard form is a type of form in which each equation if all variables or literals with or without complement form are present in each combination. Suppose if each product terms contains all variable of the equation with their sum them it is called as canonical or standard SOP form . Ex. Y= ABC +ABC+ ABC Similarly, suppose if each sum terms contains all variable of the equation with their product the it is called as canonical or standard POS form . Ex. Y= (A+B+C).(A+B+C).(A+B+C)

65. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean expression in SOP and POS form SOP expression to its Standard SOP form: The SOP form can be obtained when two or more product boolean terms added by using addition operator. So that there is difference in only SOP and Standard SOP form as- Ex. Y= AB+ABC SOP from Y = ABC + ABC Standard SOP from The conversion of SOP to standard SOP form can be implemented by using three step method as – Find the missing variable or literals in each term. Then AND the term with the term made by ORing the missing variable and its complement. Simplify the expression.

66. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean expression in SOP and POS form conversion of SOP expression to its Standard SOP form: Ex. Convert the expression Y= AC+B C+AB into the standard SOP form. Sol:- Y= AC+B C+AB i ) Find the missing variable or literals in each term. Y= AC+B C +AB B A C (Missing variables) ii) Then AND the term with the term made by ORing the missing variable and its complement. Y= AC(B+B)+B C (A+A)+AB(C+C) {A+A =1} iii) Simplify the expression. Y= ABC+ABC+ABC +ABC +ABC+ABC {A+A = A} Y= ABC+ABC + AB C +A B C Therefore this is in STD SOP form

67. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean expression in SOP and POS form POS expression to its Standard POS form: The POS form can be obtained when two or more sum boolean terms added by using multiplication or product operator. So that there is difference in only POS and Standard POS form as- Ex. Y= (A+B).(A+B+C) POS from Y = (A+B+C) . (A+B+C) Standard POS from The conversion of POS to standard POS form can be implemented by using three step method as – Find the missing variable or literals in each term. Then OR the term with the term made by ANDing the missing variable and its complement. Simplify the expression.

68. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean expression in SOP and POS form POS expression to its Standard POS form: Ex. Convert the expression Y= (A+C).(B+C).(A+B) into the standard POS form. Sol:- Y= (A+C).(B+C).(A+B) i ) Find the missing variable or literals in each term. Y= (A+C).(B+C).(A+B) B A C (Missing variables) ii) Then OR the term with the term made by ANDing the missing variable and its complement. Y= (A+C+B.B).(B +C+ A.A)+(A+B+C.C) {A.A =0} iii) Simplify the expression. put A+C=X,B+C=Y,A+B=Z into above equation: Y= (X+B.B).(Y+ A.A)+Z+C.C)

69. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Boolean expression in SOP and POS form POS expression to its Standard POS form: Ex. Convert the expression Y= (A+C).(B+C).(A+B) into the standard POS form. iii) Simplify the expression. put A+C=X,B+C=Y,A+B=Z Y= (X+B.B).(Y+ A.A)+Z+C.C) Use, A+BC=(A+B)(A+C) in above equation Y= (X+B).(X+B).(Y+ A).(Y+A).(Z+C).(Z+C) Put values of X,Y and Z in above equation: Y= (A+B+C).(A+B+C).(A+B+C).(A+B+C).(A+B+C).(A+B+C) { A+A=A} Y= (A+B+C).(A+B+C).(A+B+C).(A+B+C) There for this is STD POS form.

70. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune K-Map Introduction to K-Map: The Karnaugh map or shortly called K-map is the systematic method of solving a Boolean equation. It is also a pictorial representation off any logical expression used in the digital system. The K-map is combination of rows and columns together called ‘ cells ’, which depending upon the number of variable used in the logical equations. Suppose, A two variable k-map A and B, in these two rows and two columns used which makes four cells, it has possible four positions like AB,AB,AB and AB .

71. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune K-Map Introduction to K-Map:

72. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune K-Map Introduction to K-Map: In K-map the cell contains binary 0 and 1 where the combination of variable is present in the equation or not. For ex. 3 variable k map having equation like- Y=ABC+AB C+ABC+ABC+A BC, in the k-map put binary 1 where the combination of variable is present and put binary 0 where there is no variable combination is present then the k map becomes-

73. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune K-Map Pairs, Quads, Octets and Overlapping in K-Map: In K-map the cell contains binary 0 and 1 where the combination of variable is present in the equation or not. 1) Pairs: In the K-map if a group of two 1s that are vertically or horizontally adjacent to each other then it is called as a pair.

74. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune K-Map Pairs, Quads, Octets and Overlapping in K-Map: In K-map the cell contains binary 0 and 1 where the combination of variable is present in the equation or not. 2) Quad: In the K-map if a group of four 1s that are vertically or horizontally adjacent to each other then it is called as a Quad.

75. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune K-Map Pairs, Quads, Octets and Overlapping in K-Map: In K-map the cell contains binary 0 and 1 where the combination of variable is present in the equation or not. 3) Octet: In the K-map if a group of Eight 1s that are vertically or horizontally adjacent to each other then it is called as a Octet.

76. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune K-Map Pairs, Quads, Octets and Overlapping in K-Map: In K-map the cell contains binary 0 and 1 where the combination of variable is present in the equation or not. 4) Overlapping: In the K-map overlapping group can be form by overlapping or some time sharing a number of 1s that are vertically or horizontally adjacent to each other in pairs, quad and octet then it is called as a Overlapping.

77. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune K-Map Problem based on SOP: The following are various example of k-map for 3 and 4 varibles : Example1: Minimize the expression Y= A B C+ A B C+A B C+A B C

78. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune K-Map Problem based on SOP: The following are various example of k-map for 3 and 4 variables: Example2: Minimize the expression Y= A B C D+ A B C D+A B C D+A B CD +A B C D+A B C D +A B C D

79. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Designing using K-Map Digital designing using K-map for Binary to Gray and Gray to Binary Conversion: The binary to Gray code system is important role in the digital electronics system, there is a difference of one-bit position in successive pair , Most of the time there is need of a gray code sequence of digital system operation and they are having binary input so there is need of conversion from binary to gray code conversion or vice versa. Converting Binary to Gray Code –

80. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Designing using K-Map Binary to Gray Convertor:

81. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Designing using K-Map Binary to Gray Convertor: To find the corresponding digital circuit, we will use the K-Map technique for each of the gray code bits as output with all of the binary bits as input. K-map for –g0 K-map for –g1

82. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Designing using K-Map Binary to Gray Convertor: To find the corresponding digital circuit, we will use the K-Map technique for each of the gray code bits as output with all of the binary bits as input. K-map for –g2 K-map for –g3

83. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Designing using K-Map Binary to Gray Convertor: To find the corresponding digital circuit, we will use the K-Map technique for each of the gray code bits as output with all of the

84. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Designing using K-Map Gray to Binary Convertor:

85. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Designing using K-Map Gray to Binary Convertor: Truth table :

86. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Designing using K-Map Gray to Binary Convertor: Using K-map to get back the binary bits from the gray code – K-map for b0 - K-map for b1-

87. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Designing using K-Map Gray to Binary Convertor: Using K-map to get back the binary bits from the gray code – K-map for b2 - K-map for b3-

88. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Designing using K-Map Gray to Binary Convertor: Using K-map to get back the binary bits from the gray code –

89. Mr.V.S.Galbale MIT,ACSC,Alandi,Pune Designing using K-Map Gray to Binary Convertor: Using above equation design logic circuit diagram –

90. Questions…..? Mr.V.S.Galbale MIT,ACSC,Alandi,Pune thank you…..!