K-Map, Logic Gates.pdf .

K-Map, Logic Gates.pdf

1. Department of Electronics and Communication Engineering, MIT, Manipal Department of Electronics and Communication Engineering, MIT, Manipal 21
DIGITAL ELECTRONICS
CHAPTER-5: LOGIC GATES
Reference:
▪Malvinoand Leach, Digital Principles & applications, 7
th
edition, TMH, 2010
▪Morris Mano, “Digital design”,Prentice Hall of India, Third
Edition.
PART-II

2. Department of Electronics and Communication Engineering, MIT, Manipal Department of Electronics and Communication Engineering, MIT, Manipal 22
MODULE -2
LOGIC GATES
Boolean Algebra & Logic gates

3. Department of Electronics and Communication Engineering, MIT, Manipal Department of Electronics and Communication Engineering, MIT, Manipal 2
Logic Gates
▪OBJECTIVES
At the end of this module students will be able to :
•Describe basic logic gates and the concept of universal logic.
•Build a logic circuit for the given Boolean expressions.
•Write Boolean expressions for the given logic circuit.
•Differentiate combinational and sequential circuits.
3

4. Department of Electronics and Communication Engineering, MIT, Manipal Department of Electronics and Communication Engineering, MIT, Manipal 2
Logic Gates
▪A logic gate is a digital circuit with one or more input
signals and only one output signal.
▪The input and output signals are either HIGH (1) or
LOW (0).
4
Logic gate

5. Department of Electronics and Communication Engineering, MIT, Manipal
▪ORGate:
5
Input Output
A B Y= A+B
0 0 0
0 1 1
1 0 1
1 1 1
Table: Truth table for two input OR gate
Logic GatesF
RL
D1
D2
X
Y

6. Department of Electronics and Communication Engineering, MIT, Manipal 6
▪ANDGate:B
Y
A
Input Output
A B Y=A.B
0 0 0
0 1 0
1 0 0
1 1 1
Table: Truth table for two input OR gate
Logic GatesY
X
D2
D1
RL
+Vcc
F

7. Department of Electronics and Communication Engineering, MIT, Manipal 7
▪Not Gate (Inverter):
Logic Gates
Input output
A Y=
0 1
1 0A
Truth Table for NOT gate
=+Vcc
A
RL
F

8. Department of Electronics and Communication Engineering, MIT, Manipal 8
▪NANDGate:TheoutputofaNANDgateisLOWonlywhenall
inputsareHIGHandoutputoftheNANDisHIGHifoneormore
inputsareLOW.
▪NORGate:TheoutputoftheNORgateisHIGHonlywhenall
theinputsareLOW.Y
A
B
Universal GatesA
B
Y
Universalgates:NANDandNORgatesarecalledUniversalgates.

9. Department of Electronics and Communication Engineering, MIT, Manipal 9
▪NAND gate as Universal gate:
NOT operation:
AND operation:
OR operation:
NOR operation:A
A
A

A A
B

AB Y=A.B A
A
A
B
B
B BB
AA
A+B A
B

BA+A+B
Universal Gates

10. Department of Electronics and Communication Engineering, MIT, Manipal 10
Logic Gates
XOR Gate or Exclusive OR gate: output is HIGH only when any one
of the input is HIGH. (inequality comparator)A
B
Y
XNORGateorExclusiveNORGate:complementaryofXOR
operation.
TheoutputofXNORgateisHigh,whenalltheinputsare
identical;otherwiseitislow.A
B
Y

11. Department of Electronics and Communication Engineering, MIT, Manipal 11
Types of Digital Circuits:
▪Combinational Digital Circuits
▪Sequential Digital Circuits
Digital circuits

12. Department of Electronics and Communication Engineering, MIT, Manipal 12
Figure (a) Combinational Circuit (b) Sequential circuit
(a)
(b)
Digital circuits

13. Department of Electronics and Communication Engineering, MIT, Manipal 13
Elements of combinational logic:
▪Literal
Ex-XandX’arebothliterals.SimilarlyABCD’consistsof4
literalsA,B,CandD’.
▪Productterm
Ex-X,XY’,XYZaretheproducttermswhenX,Y,ZareBoolean
variables.
▪Sumterm
Ex-X+Y’,X+Y+ZarethesumtermswhenX,Y,Zare
Booleanvariables.
Digital circuits

14. Department of Electronics and Communication Engineering, MIT, Manipal 14
Continued……..
▪Sumofproducts(SOP):EachproducttermisthelogicalANDof
literals.
Ex:Y+XY’+XYZ
▪ProductsofSums(POS):EachsumtermisthelogicalORof
literals.
Ex:(X+Y’)((X’Y+Z)(X+Y+Z)
Digital circuits

15. Department of Electronics and Communication Engineering, MIT, Manipal 15
Continued……..
▪Canonicalform:Canonicalisdefinedas“conformingtoageneral
rule”.(Standardform)
Alltheliteralsexisteithercomplimentedornoncomplimentedform.
▪CanonicalSumofProducts:
Ex:f(A,B,C)=A’B’C+A’BC’+A’BC+ABC’
▪CanonicalProductofSums:
Ex:f(X,Y)=(X+Y’)(X+Y)(x’+y)
Digital circuits

16. Department of Electronics and Communication Engineering, MIT, Manipal 16
Continued……..
▪Minterm:Eachproductterminthestandard(canonical)SOP
expression.
▪Maxterm:Eachsumterminthestandard(canonical)POS
expression
Logic Gates

17. Department of Electronics and Communication Engineering, MIT, Manipal 17
Building logic circuits using Boolean expression
➢Examplesofcombinationalcircuits
DrawthelogiccircuitfortheBooleanexpression.Y=A’BC+AB’
C+ABC’.
( Do the reverse process also)

18. Department of Electronics and Communication Engineering, MIT, Manipal 18
Combinational circuits
▪Half adder circuitA
B
Sum
Carry
Half Adder
Input Output
A B Sum Carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

19. Department of Electronics and Communication Engineering, MIT, Manipal 19
▪Sum= A’B+AB’ =A XOR B
▪Carry= A.B Carry =A.B
Sum= AB+AB=AB
A B

B

A
Continued…….

20. Department of Electronics and Communication Engineering, MIT, Manipal 20
▪Self test
1.Show that NOR is a universal gate.
2.Draw the logic circuit for the Boolean expression. Y= BC+A’ C+AB’C.
3.Implement the half adder circuit using XOR gates.
4.Implement the full adder circuit using logic gates.

21. Department of Electronics and Communication Engineering, MIT, Manipal
Summary
▪Logicgatesarefundamentalbuildingblocksofdigitalsystems
▪ThebasicsetoflogicgatesareAND,ORandNOTandthissetiscalled
Universalset.
▪NANDandNORarecalledUniversalgates.
▪Inputsandoutputsoflogicgatescanoccurintwolevels.Thesetwolevels
aretermedasHIGHandLOW,orTRUEandFALSE,orONandOFF,or
simply1or0.
▪Logiccircuitswhoseoutputatanyinstantoftimeisentirelydependent
upontheinputsignalspresentatthattimeareknownascombinational
digitalcircuits.
▪Logiccircuitswhoseoutputatanyinstantoftimedepend,notonlyonthe
presentinputbutalsoonthepastoutputsarecalledSequentialCircuits.
21

22. Department of Electronics and Communication Engineering, MIT, Manipal
▪Exercise:
1.Draw the logic circuit for the Boolean expression. Y= BC+A’ C+AB’C.
2.Show that AB+(A+B) is equivalent to A ʘ B. Also construct the
corresponding logic diagrams.
3.The most suitable gate to check whether the number of 1s in a digital
word is even or odd is -----------
4.a)X-OR b) NAND c) NOR d) AND, OR and NOT
5.Realize NOR and NAND gate using discrete components.
6.ImplementFullSubtractorusingBasicgates.
7.Implementfulladderusingtwohalfadders.
22

23. Department of Electronics and Communication Engineering, MIT, Manipal
Module-3
KARNAUGH MAP (K –MAP)
23

24. Department of Electronics and Communication Engineering, MIT, Manipal 24
KARNAUGH MAP (K –MAP)
▪OBJECTIVES
At the end of this module students will be able to :
•Explain the standard form of Boolean expressions.
•Apply the K-map for Boolean expression simplification and design of
logic circuits.

25. Department of Electronics and Communication Engineering, MIT, Manipal
KARNAUGH MAP (K –MAP)
25
Karnaughmap(k–map)methodofsimplifyingtheBoolean
expressions:
➢Booleanexpressioncanbeexpressedinsumofproduct(SOP)formor
productofsum(POS)form.
▪BooleanexpressioninSOPform:
Y=AB’C+ABC+A’BC
▪EachoftheproducttermsinthestandardSOPformiscalleda
minterm.
▪BooleanexpressioninPOSform:
Y=(A+B+C’)(A’+B+C)(A+B+C)
▪EachsumterminthestandardPOSformiscalledamaxterm.

26. Department of Electronics and Communication Engineering, MIT, Manipal 26
•Steps to convert SOP to canonical SOP:
➢Find the missing literal in each product term.
➢AND each product term having missing literals with terms by
ORingthe literal and its complement.
➢Expand the terms and reduce the expression by removing
repeated terms.
▪Ex1: F(A,B,C) = AC+AB+BC
= A (B+B’)C+AB(C+C’)+(A+A’)BC
= AB’C+ABC’+A’BC+ABC

27. Department of Electronics and Communication Engineering, MIT, Manipal 27
Selftest
1.DeterminetheBooleanfunctionofthetruthtableincanonicalS0P
formandsimplifytheexpression.
Inputs Output
A B C Y
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 0

28. Department of Electronics and Communication Engineering, MIT, Manipal 28
▪Introduction
▪Structure of a K -map :
•Two variable K –map has 2
2
= 4 cells
•Three variable K-map has 2
3
= 8 cells
•Four variable K-map has 2
4
= 16 cells.
KARNAUGH MAP (K –MAP)

29. Department of Electronics and Communication Engineering, MIT, Manipal 29
KARNAUGH MAP (K –MAP)
2-Variable K-MAP 3-Variable K-MAP

30. Department of Electronics and Communication Engineering, MIT, Manipal 30
KARNAUGH MAP (K –MAP)
4-Variable K-MAP

31. Department of Electronics and Communication Engineering, MIT, Manipal 31
Simplification of Boolean expressions in SOP form:
1.Place logical 1s in the appropriate cells.
2. Two or Four or Eight adjacent logical ‘1s’ can be grouped
together.
KARNAUGH MAP (K –MAP)
Example

32. Department of Electronics and Communication Engineering, MIT, Manipal 32
▪PROBLEM : Reduce the following Boolean expression using K-map:
f = AB + AB’C + A’BC’ + BC’
KARNAUGH MAP (K –MAP)
Soln.The given Boolean expression is not in SOP form.
f = AB(C + C’) + AB’C + A’BC’ + BC’(A +A’)
= ABC + ABC’ + AB’C + A’BC’ + ABC’+ A’BC’
= ABC + ABC’ + AB’C + A’BC’
= Ʃm( 7, 6, 5, 2 )
Ans. f = AC + BC’
➢Simplify using 3-variable K-map

33. Department of Electronics and Communication Engineering, MIT, Manipal 33
Self test
Problem 1Reduce the Boolean expression
f = Ʃm(0, 2, 3, 4, 5, 6) using K-map and implement it in AOI logic.
Ans:f = C’ + AB’ + A’B
Problem 2 Reduce the expression f= A’B’+A’B+AB using mapping
Ans: f=A’+B
KARNAUGH MAP (K –MAP)

34. Department of Electronics and Communication Engineering, MIT, Manipal 34
KARNAUGH MAP (K –MAP)
▪Don’t care terms
•The combinations for which the values of the expression are
not specified are called don’t care combinations.
•The don’t care terms are denoted by d or X.
Ex1:SimplifythefollowingBooleanexpressionusingKMap.
F(A,B,C)=Σm(3,4)+d(2,5,6)
BC
A 00 01 11 10
0
1
0 0 1 X
1 X 0 X
F=AB’+A’B

35. Department of Electronics and Communication Engineering, MIT, Manipal 35
KARNAUGH MAP (K –MAP)
Summary
1.TheK-mapisachartoragraph,composedofanarrangementof
adjacentcells,eachrepresentingaparticularcombinationof
variablesinsumofproductform.
2.Itisameansofshowingtherelationshipbetweenthelogicinputs
anddesiredoutput.
3.K-mapislimitedto6variables.
4.AnyBooleanexpressioncanbeexpressedinastandardorcanonical
orexpandedsum(OR)ofproducts(AND)form–SOPform—orina
standardorcanonicalorexpandedproduct(AND)ofsums(OR)form
–POSform.

36. Department of Electronics and Communication Engineering, MIT, Manipal 36
A B Y
0 0 0
0 1 1
1 0 1
1 1 1
Exercise:
1.Consider the truth table of a function. Transfer the outputs to the K map and
write the Boolean expression.
2. Simplify the following Boolean expressions using K maps.
F = Σm(0,2,4,6)
F = Σm(0,2,4,6) + d( 5,7).