Boolean algebra simplification and combination circuits

Boolean algebra simplification and Combination circuits

1. UNIT II
Boolean Algebra Simplification
and Combinational Circuits
By Dr. DhobaleJ V
Associate Professor
School of Engineering & Technology
RNB Global University, Bikaner
RNB Global University, Bikaner. 1Course Code -19004000

2. Objectives
SimplificationofBooleanfunctionbyK-Map.
SimplificationofBooleanfunctionbyQ.M.
Adder–Half,Full,BCD,HighSpeed.
Subtractor,Multiplier,dividers.
ALU,CodeConversion–Encoder,Decoder.
Comparators,Multiplexers,Demultiplexers.
ImplementationusingICs.
2RNB Global University, Bikaner.Course Code -19004000

3. Boolean Algebra –Simplification
AsimplifiedBooleanexpressionusesthe
fewestgatespossibletoimplementagiven
expression.
Ex.Simplify-AB+A(B+C)+B(B+C)
3RNB Global University, Bikaner.Course Code -19004000

4. Boolean Algebra –Simplification
Ex.Simplify-AB+A(B+C)+B(B+C)
Solution-AB+AB+AC+BB+BC
AB+AB+AC+B+BC
AB+AC+B+BC
AB+AC+B
B+AC
4RNB Global University, Bikaner.Course Code -19004000

5. Boolean Algebra –Simplification
Ex.Simplify-AB+A(B+C)+B(B+C)
5RNB Global University, Bikaner.Course Code -19004000

6. Boolean Algebra –Simplification
Ex.Simplify–1.C+BC
2.AB(A+B)(B+B)
3.(A+C)(AD+AD)+AC+C
4.A(A+B)+(B+AA)(A+B)
6RNB Global University, Bikaner.Course Code -19004000

7. Boolean Algebra –Simplification
Ex.Simplify–1.C+BC
Solution-C+BC
=C+(B+C)
=(C+C)+B
=1+B
=1
7RNB Global University, Bikaner.Course Code -19004000

8. Boolean Algebra –Simplification
Ex.Simplify–
2.AB(A+B)(B+B)
Solution–AB(A+B)(B+B)
=AB(A+B)
=(A+B)(A+B)
=AA+AB+AB+BB
=A+A(B+B)
=A+A
=A
8RNB Global University, Bikaner.Course Code -19004000

9. Boolean Algebra –Simplification
Ex.Simplify–
3.(A+C)(AD+AD)+AC+C
Solution-(A+C)(AD+AD)+AC+C
=(A+C)A(D+D)+AC+C
=(A+C)A+C
=AA+AC+C
=A+C
9RNB Global University, Bikaner.Course Code -19004000

10. Boolean Algebra –Simplification
Ex.Simplify–4.A(A+B)+(B+AA)(A+B)
Solution-A(A+B)+(B+AA)(A+B)
=AA+AB+(B+A)(A+B)
=0+AB+AB+BB+AA+AB
=AB+AB+0+A+AB
=AB+A(B+1+B)
=AB+A(1+1)
=AB+A
=(A+A)(A+B)
=A+B
10RNB Global University, Bikaner.Course Code -19004000

11. Boolean Algebra –Simplification
StandardformofBooleanexpression
(CanonicalForm):AllBooleanexpressions,
regardlessoftheirform,canbeconvertedinto
eitheroftwostandardforms:thesum-of-
productsformortheproduct-ofsumsform.
Standardizationmakes theevaluation,
simplification,andimplementationofBoolean
expressionsmuchmoresystematicand
easier.
11RNB Global University, Bikaner.Course Code -19004000

12. Boolean Algebra –Simplification
StandardformofBooleanexpression:
TheSum-of-Products(SOP)Form.
Whentwoormoreproducttermsaresummed
byBooleanaddition,theresultingexpression
isasum-of-products(SOP).
Ex. AB + ABC
ABC + CDE + BCD
AB + BCD + AC
Also, an SOP expression can contain a single-
variable term, as in A + ABC + BCD.
12RNB Global University, Bikaner.Course Code -19004000

13. Boolean Algebra –Simplification
StandardformofBooleanexpression:
TheSum-of-Products(SOP)Form.
InanSOPexpressionasingleoverbar
cannotextendovermorethanonevariable.
13RNB Global University, Bikaner.Course Code -19004000

14. Boolean Algebra –Simplification
StandardformofBooleanexpression:
14RNB Global University, Bikaner.Course Code -19004000

15. Boolean Algebra –Simplification
StandardformofBooleanexpression
ConvertingProductTermstoStandardSOP:
EachproductterminanSOPexpressionthat
doesnotcontainallthevariablesinthe
domaincanbeexpandedtostandardSOPto
includeallvariablesinthedomainandtheir
complements.
anonstandardSOPexpressionisconverted
intostandardformusingBooleanalgebrarule
6(A+A=1).
15RNB Global University, Bikaner.Course Code -19004000

16. Boolean Algebra –Simplification
StandardformofBooleanexpression
ConvertingProductTermstoStandardSOP:
16RNB Global University, Bikaner.Course Code -19004000

17. Boolean Algebra –Simplification
StandardformofBooleanexpression
ConvertingProductTermstoStandardSOP:
Example-ConvertthefollowingBoolean
expressionintostandardSOPform:
ABC+AB+ABCD
Solution-ThedomainofthisSOPexpression
A,B,C,D.
Takeonetermatatime.Thefirstterm,ABC,
ismissingvariableDorD,somultiplythefirst
termby(D+D)asfollows:
17RNB Global University, Bikaner.Course Code -19004000

18. Boolean Algebra –Simplification
StandardformofBooleanexpression
ConvertingProductTermstoStandardSOP:
ABC=ABC(D+D)=ABCD+ABCD
Inthiscase,twostandardproducttermsare
theresult.
Thesecondterm,AB,ismissingvariablesC
orCandDorD,sofirstmultiplythesecond
termbyC+Casfollows:
AB=AB(C+C)=ABC+ABC
18RNB Global University, Bikaner.Course Code -19004000

19. Boolean Algebra –Simplification
StandardformofBooleanexpression
ConvertingProductTermstoStandardSOP:
ABC=ABC(D+D)=ABCD+ABCD
AB=AB(C+C)=ABC+ABC
ThetworesultingtermsaremissingvariableD
orD,somultiplybothtermsby(D+D)as
follows:
ABC(D+D)+ABC(D+D)
=ABCD+ABCD+ABCD+ABCD
19RNB Global University, Bikaner.Course Code -19004000

20. Boolean Algebra –Simplification
StandardformofBooleanexpression
ConvertingProductTermstoStandardSOP:
Inthiscase,fourstandardproducttermsare
theresult.Thethirdterm,ABCD,isalreadyin
standardform.ThecompletestandardSOP
formoftheoriginalexpressionisasfollows:
ABC + AB + ABCD = ABCD + ABCD + ABCD
+ ABCD + ABCD + ABCD + ABCD
20RNB Global University, Bikaner.Course Code -19004000

21. Boolean Algebra –Simplification
StandardformofBooleanexpression
TheProduct-of-Sums(POS)Form:Asum
termwasdefinedbeforeasatermconsisting
ofthesum(Booleanaddition)ofliterals
(variablesortheircomplements).Whentwoor
moresumtermsaremultiplied,theresulting
expressionisaproduct-of-sums(POS).
Examples -(A + B)(A + B + C)
(A + B + C)( C + D + E)(B + C + D)
(A + B)(A + B + C)(A + C)
21RNB Global University, Bikaner.Course Code -19004000

22. Boolean Algebra –Simplification
StandardformofBooleanexpression
TheProduct-of-Sums(POS)Form:APOS
expressioncancontainasingle-variableterm,
asinA(A+B+C)(B+C+D).
InaPOSexpression,asingleoverbarcannot
extendovermorethanonevariable;however,
morethanonevariableinatermcanhavean
overbar.
Forexample,aPOSexpressioncanhavethe
termA+B+CbutnotA+B+C.
22RNB Global University, Bikaner.Course Code -19004000

23. Boolean Algebra –Simplification
StandardformofBooleanexpression
TheProduct-of-Sums (POS)Form:
ImplementationofaPOSExpressionsimply
requiresANDingtheoutputsoftwoormore
ORgates.AsumtermisproducedbyanOR
operationandtheproductoftwoormoresum
termsisproducedbyanANDoperation.
Followingfigureshowsfortheexpression(A+
B)(B+C+D)(A+C).
23RNB Global University, Bikaner.Course Code -19004000

24. Boolean Algebra –Simplification
StandardformofBooleanexpression
TheProduct-of-Sums(POS)Form:
24RNB Global University, Bikaner.Course Code -19004000

25. Boolean Algebra –Simplification
StandardformofBooleanexpression
TheProduct-of-Sums(POS)Form:The
StandardPOSForm-Sofar,wehaveseen
POSexpressionsinwhichsomeofthesum
termsdonotcontainallofthevariablesinthe
domainoftheexpression.
Forexample,theexpression
(A+B+C)(A+B+D)(A+B+C+D)
25RNB Global University, Bikaner.Course Code -19004000

26. Boolean Algebra –Simplification
StandardformofBooleanexpression
TheProduct-of-Sums(POS)Form:hasa
domainmadeupofthevariablesA,B,C,and
D.
Noticethatthecompletesetofvariablesinthe
domainisnotrepresentedinfirsttwotermsof
theexpression;thatis,DorDismissingfrom
thefirsttermandCorCismissingfromthe
secondterm.
StandardExp.is–
(A+B+C+D)(A+B+C+D)(A+B+C+D)
26RNB Global University, Bikaner.Course Code -19004000

27. Boolean Algebra –Simplification
StandardformofBooleanexpression
TheProduct-of-Sums (POS)Form:
ConvertingaSumTermtoStandardPOS-
Rules–
1.Addtoeachnonstandardproducttermaterm
madeupoftheproductofthemissing
variableanditscomplement.Thisresultsin
twosumterms.Asyouknow,youcanadd0
toanythingwithoutchangingitsvalue.
27RNB Global University, Bikaner.Course Code -19004000

28. Boolean Algebra –Simplification
StandardformofBooleanexpression
TheProduct-of-Sums (POS)Form:
ConvertingaSumTermtoStandardPOS-
Rules–
2.ApplyBooleanRuleNo.12A+BC=(A+
B)(A+C).
3.RepeatStep1untilallresultingsumterms
containallvariablesinthedomainineither
complementedornoncomplementedform.
28RNB Global University, Bikaner.Course Code -19004000

29. Boolean Algebra –Simplification
StandardformofBooleanexpression
TheProduct-of-Sums (POS)Form:
ConvertingaSumTermtoStandardPOS-
Example-ConvertthefollowingBoolean
expressionintostandardPOSform:
(A+B+C)(B+C+D)(A+B+C+D)
Solution-ThedomainofthisPOSexpression
isA,B,C,D.Takeonetermatatime.Thefirst
term,A+B+C,ismissingvariableDorD,so
addDDandapplyrule12asfollows:
29RNB Global University, Bikaner.Course Code -19004000

30. Boolean Algebra –Simplification
StandardformofBooleanexpression
TheProduct-of-Sums (POS)Form:
ConvertingaSumTermtoStandardPOS-
A+B+C=A+B+C+DD=(A+B+C+
D)(A+B+C+D)
Thesecondterm,B+C+D,ismissing
variableAorA
B+C+D=B+C+D+AA=(A+B+C+
D)(A+B+C+D)
Thethirdterm,A+B+C+D,isalreadyin
standardform.
30RNB Global University, Bikaner.Course Code -19004000

31. Boolean Algebra –Simplification
StandardformofBooleanexpression
TheProduct-of-Sums (POS)Form:
ConvertingaSumTermtoStandardPOS-
(A + B + C)(B + C + D)(A + B + C + D) = (A +
B + C + D)(A + B + C +D) (A + B + C + D)(A +
B + C + D) (A + B + C + D)
31RNB Global University, Bikaner.Course Code -19004000

32. Boolean Algebra –Simplification
32RNB Global University, Bikaner.Course Code -19004000

33. Boolean Algebra –Simplification
33RNB Global University, Bikaner.Course Code -19004000

34. Boolean Algebra –Simplification
34RNB Global University, Bikaner.Course Code -19004000

35. Boolean Algebra –Simplification
ExpresstheBooleanfunctionF=A+BCina
sumofminterms(SOP).
Solution-ThetermAismissingtwovariables
becausethedomainofFis(A,B,C)
A=A(B+B)=AB+AB
ThetermBCismissingAvaiable
BC(A+A)=BCA+BCA
ThetermAB+ABismissingC
AB(C+C)+AB(C+C)
=ABC+ABC+ABC+ABC
35RNB Global University, Bikaner.Course Code -19004000

36. Boolean Algebra –Simplification
Finalsolutionis
=ABC+ABC+ABC+ABC+ABC+ABC
=ABC+ABC+ABC+ABC+ABC
F=m
7+m
6+m
5+m
4+m
1
Inshortnotation
F(A,B,C)=Ʃ(1,4,5,6,7)
F(A,B,C)=Ʃ(0,2,3)
36RNB Global University, Bikaner.Course Code -19004000

37. Boolean Algebra –Simplification
Thecomplementofafunctionexpressedas
thesumofmintermsequaltothesumof
mintermsmissingfromtheoriginalfunction.
TruthTableforF=A+BC
37RNB Global University, Bikaner.Course Code -19004000

38. Boolean Algebra –Simplification
ExpressF=xy+xzinaproductofmaxterms
form.
38RNB Global University, Bikaner.Course Code -19004000

39. Boolean Algebra –Simplification
ExpressF=xy+xzinaproductofmaxterms
form.
Solution–F=xy+xz
=(xy+x)(xy+z)
=(x+x)(y+x)(x+z)(y+z)
=(y+x)(x+z)(y+z)
F=(x+y+zz)(x+yy+z)(xx+y+z)
=(x+y+z)(x+y+z)(x+y+z)(x+y+z)
(x+y+z)(x+y+z)
39RNB Global University, Bikaner.Course Code -19004000

40. Boolean Algebra –Simplification
ExpressF=xy+xzinaproductofmaxterms
form.
Solution–
F=(x+y+z)(x+y+z)(x+y+z)(x+y+z)
F=M
4M
5M
0M
2
F(x,y,z)=Π(0,2,4,5)
F(x,y,z)=Π(1,3,6,7)
Thecomplementofafunctionexpressedas
theproductofmaxtermsequaltotheproduct
ofmaxtermsmissingfromtheoriginalfunction.
40RNB Global University, Bikaner.Course Code -19004000

41. Boolean Algebra –Simplification
Example-Developatruthtableforthe
standardSOPexpressionABC+ABC+ABC.
41RNB Global University, Bikaner.Course Code -19004000

42. Boolean Algebra –Simplification
Example-Developatruthtableforthe
standardSOPexpressionABC+ABC+ABC.
42RNB Global University, Bikaner.Course Code -19004000

43. Boolean Algebra –Simplification
Example-Determinethetruthtableforthe
followingstandardPOSexpression:
(A+B+C)(A+B+C)(A+B+C)(A+B+C)(A+B+C)
43RNB Global University, Bikaner.Course Code -19004000

44. Boolean Algebra –Simplification
Example-Determinethetruthtableforthe
followingstandardPOSexpression:
(A+B+C)(A+B+C)(A+B+C)(A+B+C)(A+B+C)
44RNB Global University, Bikaner.Course Code -19004000

45. KARNAUGH MAP MINIMIZATION
AKarnaughmapprovidesasystematic
methodforsimplifyingBooleanexpressions
and,ifproperlyused,willproducethesimplest
SOPorPOSexpressionpossible,knownas
theminimumexpression.
Asyouhaveseen,theeffectivenessof
algebraicsimplificationdependsonyour
familiaritywithallthelaws,rules,and
theoremsofBooleanalgebraandonyour
abilitytoapplythem.
45RNB Global University, Bikaner.Course Code -19004000

46. KARNAUGH MAP MINIMIZATION
AKarnaughmapissimilartoatruthtable
becauseitpresentsallofthepossiblevalues
ofinputvariablesandtheresultingoutputfor
eachvalue.
Insteadofbeingorganizedintocolumnsand
rowslikeatruthtable,theKarnaughmapisan
arrayofcellsinwhicheachcellrepresentsa
binaryvalueoftheinputvariables.
46RNB Global University, Bikaner.Course Code -19004000

47. KARNAUGH MAP MINIMIZATION
Thecellsarearrangedinawaysothat
simplificationofagivenexpressionissimplya
matterofproperlygroupingthecells.
Karnaughmapscanbeusedforexpressions
withtwo,three,fourandfivevariables.
Anothermethod,calledtheQuine-McClusky
methodcanbeusedforhighernumbersof
variables.
47RNB Global University, Bikaner.Course Code -19004000

48. KARNAUGH MAP MINIMIZATION
ThenumberofcellsinaKarnaughmapis
equaltothetotalnumberofpossibleinput
variablecombinationsasisthenumberof
rowsinatruthtable.
Forthreevariables,thenumberofcellsis2
3
=
8.
48RNB Global University, Bikaner.Course Code -19004000

49. KARNAUGH MAP MINIMIZATION
ThreeVariableKarnaughMap:The3-variable
Karnaughmapisanarrayofeightcells,as
showninfigbelow.
49RNB Global University, Bikaner.Course Code -19004000

50. KARNAUGH MAP MINIMIZATION
ThreeVariableKarnaughMap:Inthiscase,A,
B,andCareusedforthevariablesalthough
otherletterscouldbeused.
BinaryvaluesofAandBarealongtheleft
side(noticethesequence)andthevaluesofC
areacrossthetop.
Thevalueofagivencellisthebinaryvaluesof
AandBattheleftinthesamerowcombined
withthevalueofCatthetopinthesame
column.
50RNB Global University, Bikaner.Course Code -19004000

51. KARNAUGH MAP MINIMIZATION
ThreeVariableKarnaughMap:Forexample,
thecellintheupperleftcornerhasabinary
valueof000andthecellinthelowerright
cornerhasabinaryvalueof101.
51RNB Global University, Bikaner.Course Code -19004000

52. KARNAUGH MAP MINIMIZATION
FourVariableKarnaughMap:The4-variable
Karnaughmapisanarrayofsixteencells,as
showninfigbelow.
52RNB Global University, Bikaner.Course Code -19004000

53. KARNAUGH MAP MINIMIZATION
FourVariableKarnaughMap:Binaryvaluesof
AandBarealongtheleftsideandthevalues
ofCandDareacrossthetop.
Thevalueofagivencellisthebinaryvaluesof
AandBattheleftinthesamerowcombined
withthebinaryvaluesofCandDatthetopin
thesamecolumn.
Forexample,thecellintheupperrightcorner
hasabinaryvalueof0010andthecellinthe
lowerrightcornerhasabinaryvalueof1010.
53RNB Global University, Bikaner.Course Code -19004000

54. KARNAUGH MAP MINIMIZATION
FourVariableKarnaughMap:belowshown
thestandardproducttermsthatare
representedbyeachcellinthe4-variable
Karnaughmap.
54RNB Global University, Bikaner.Course Code -19004000

55. KARNAUGH MAP MINIMIZATION
CellAdjacency:ThecellsinaKarnaughmap
arearrangedsothatthereisonlyasingle
variablechangebetweenadjacentcells.
Adjacencyisdefinedbyasinglevariable
change.
Inthe3-variablemapthe010cellisadjacent
tothe000cell,the011cell,andthe110cell.
The010cellisnotadjacenttothe001cell,the
111cell,the100cell,orthe101cell.
55RNB Global University, Bikaner.Course Code -19004000

56. KARNAUGH MAP MINIMIZATION
CellAdjacency:belowfigshowsAdjacent
cellsonaKarnaughmaparethosethatdiffer
byonlyonevariable.Arrowspointbetween
adjacentcells.
56RNB Global University, Bikaner.Course Code -19004000

57. KARNAUGH MAP MINIMIZATION
KARNAUGH MAPSOPMINIMIZATION:For
anSOPexpressioninstandardform,a1is
placedontheKarnaughmapforeachproduct
termintheexpression.
Each 1 is placed in a cell corresponding to the
value of a product term.
57RNB Global University, Bikaner.Course Code -19004000

58. KARNAUGH MAP MINIMIZATION
KARNAUGH MAPSOPMINIMIZATION:
Example-MapthefollowingstandardSOP
expressiononaKarnaughmap.
ABC+ABC+ABC+ABC
Solution-
58RNB Global University, Bikaner.Course Code -19004000

59. KARNAUGH MAP MINIMIZATION
KARNAUGH MAPSOPMINIMIZATION:
Example-MapthefollowingstandardSOP
expressiononaKarnaughmap
ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+
ABCD
Solution-
59RNB Global University, Bikaner.Course Code -19004000

60. KARNAUGH MAP MINIMIZATION
KARNAUGH MAPSOPMINIMIZATION:
Example- MapthefollowingSOP
expressiononaKarnaughmap:A+AB+ABC
Solution-TheSOPexpressionisobviously
notinstandardformbecauseeachproduct
termdoesnothavethreevariables.
First expand the terms numerically as follows:
60RNB Global University, Bikaner.Course Code -19004000

61. KARNAUGH MAP MINIMIZATION
KARNAUGH MAPSOPMINIMIZATION:
Example- MapthefollowingSOP
expressiononaKarnaughmap:A+AB+ABC
Solution-
61RNB Global University, Bikaner.Course Code -19004000

62. KARNAUGH MAP MINIMIZATION
KARNAUGH MAPSOPMINIMIZATION:
Example- MapthefollowingSOP
expressiononaKarnaughmap:A+AB+ABC
Solution-
62RNB Global University, Bikaner.Course Code -19004000

63. KARNAUGH MAP MINIMIZATION
KARNAUGH MAPSOPMINIMIZATION:
Example- MapthefollowingSOP
expressiononaKarnaughmap:
BC+AB+ABC+ABCD+ABCD+ABCD
Solution-TheSOPexpressionisobviously
notinstandardformbecauseeachproduct
termdoesnothavefourvariables.
63RNB Global University, Bikaner.Course Code -19004000

64. KARNAUGH MAP MINIMIZATION
KARNAUGH MAPSOPMINIMIZATION:
Example- MapthefollowingSOP
expressiononaKarnaughmap:
BC+AB+ABC+ABCD+ABCD+ABCD
Solution–
64RNB Global University, Bikaner.Course Code -19004000

65. KARNAUGH MAP MINIMIZATION
KARNAUGH MAPSOPMINIMIZATION:
Example- MapthefollowingSOP
expressiononaKarnaughmap:
BC+AB+ABC+ABCD+ABCD+ABCD
Solution–
65RNB Global University, Bikaner.Course Code -19004000

66. KARNAUGH MAP MINIMIZATION
KARNAUGH MAPSOPMINIMIZATION:
Groupingthe1s,youcangroup1sonthe
Karnaughmapaccordingtothefollowing
rulesbyenclosingthoseadjacentcells
containing1s.
Thegoalistomaximizethesizeofthegroups
andtominimizethenumberofgroups.
66RNB Global University, Bikaner.Course Code -19004000

67. KARNAUGH MAP MINIMIZATION
KARNAUGH MAPSOPMINIMIZATION:
1.Agroupmustcontaineither1,2,4,8,or16
cells,whichareallpowersoftwo.Inthecase
ofa3-variablemap,23=8cellsisthe
maximumgroup.
2.Eachcellinagroupmustbeadjacenttoone
ormorecellsinthatsamegroup.
3.Alwaysincludethelargestpossiblenumber
of1sinagroupinaccordancewithrule1.
67RNB Global University, Bikaner.Course Code -19004000

68. KARNAUGH MAP MINIMIZATION
KARNAUGH MAPSOPMINIMIZATION:
4.Each1onthemapmustbeincludedinat
leastonegroup.The1salreadyinagroup
canbeincludedinanothergroupaslongas
theoverlappinggroupsincludenoncommon
1s.
68RNB Global University, Bikaner.Course Code -19004000

69. KARNAUGH MAP MINIMIZATION
KARNAUGH MAPSOPMINIMIZATION:
Examples-
69RNB Global University, Bikaner.Course Code -19004000

70. KARNAUGH MAP MINIMIZATION
KARNAUGH MAPSOPMINIMIZATION:
Solution–Thegroupingareshownbelow
70RNB Global University, Bikaner.Course Code -19004000

71. KARNAUGH MAP MINIMIZATION
KARNAUGH MAPSOPMINIMIZATION:
Solution–Determinetheminimumproduct
termforeachgroup.
a.Fora3-variablemap:
1.A1-cellgroupyieldsa3-variableproductterm
2.A2-cellgroupyieldsa2-variableproductterm
3.A4-cellgroupyieldsa1-variableterm
4.An8-cellgroupyieldsavalueof1forthe
expression
71RNB Global University, Bikaner.Course Code -19004000

72. KARNAUGH MAP MINIMIZATION
KARNAUGH MAPSOPMINIMIZATION:
Solution–b. For a 4-variable map:
1.A 1-cell group yields a 4-variable product term
2.A 2-cell group yields a 3-variable product term
3.A 4-cell group yields a 2-variable product term
4.An 8-cell group yields a 1-variable term
5.A 16-cell group yields a value of 1 for the
expression
72RNB Global University, Bikaner.Course Code -19004000

73. KARNAUGH MAP MINIMIZATION
KARNAUGH MAPSOPMINIMIZATION:
Example–
73RNB Global University, Bikaner.Course Code -19004000

74. KARNAUGH MAP MINIMIZATION
KARNAUGH MAPSOPMINIMIZATION:
Solution–Theresultingminimumproductterm
foreachgroupisshowninfigaboveThe
minimumSOPexpressionsforeachofthe
Karnaughmapsinthefigureare:
(a)AB+BC+ABC (C) AB + AC + ABD
(b) B + A C + AC (d) D + ABC + BC
74RNB Global University, Bikaner.Course Code -19004000

75. KARNAUGH MAP MINIMIZATION
75RNB Global University, Bikaner.Course Code -19004000

76. KARNAUGH MAP MINIMIZATION
76RNB Global University, Bikaner.Course Code -19004000

77. KARNAUGH MAP MINIMIZATION
77RNB Global University, Bikaner.Course Code -19004000

78. KARNAUGH MAP MINIMIZATION
78RNB Global University, Bikaner.Course Code -19004000

79. KARNAUGH MAP MINIMIZATION
79RNB Global University, Bikaner.Course Code -19004000

80. KARNAUGH MAP MINIMIZATION
80RNB Global University, Bikaner.Course Code -19004000

81. KARNAUGH MAP MINIMIZATION
81RNB Global University, Bikaner.Course Code -19004000

82. KARNAUGH MAP MINIMIZATION
82RNB Global University, Bikaner.Course Code -19004000

83. KARNAUGH MAP MINIMIZATION
Simplifyz=f(A,B)=AB+ABusingalgebraic
equationandKarnaughMap(K-Map).
83RNB Global University, Bikaner.Course Code -19004000

84. KARNAUGH MAP MINIMIZATION
Simplifyz=f(A,B)=AB+ABusingalgebraic
equationandKarnaughMap(K-Map).
Solution-z=AB+AB
=A(B+B)
=A
84RNB Global University, Bikaner.Course Code -19004000

85. KARNAUGH MAP MINIMIZATION
UsingKarnaughMap.
z=AB+AB
NoofVariables2thereforwerequired4cell
map. BA0 1
0
1
85RNB Global University, Bikaner.Course Code -19004000
1
1

86. KARNAUGH MAP MINIMIZATION
UsingKarnaughMap.
z=AB+AB
NoofVariables2thereforwerequired4cell
map. BA0 1
0 A
1
86RNB Global University, Bikaner.Course Code -19004000
1
1

87. KARNAUGH MAP MINIMIZATION
Solve
z=f(A,B)=AB+AB+AB
87RNB Global University, Bikaner.Course Code -19004000

88. KARNAUGH MAP MINIMIZATION
Solve
z=f(A,B)=AB+AB+AB
NoofVariables2thereforwerequired4cell
map. BA0 1
0
1
88RNB Global University, Bikaner.Course Code -19004000
11
1

89. KARNAUGH MAP MINIMIZATION
Solve
z=f(A,B)=AB+AB+AB
NoofVariables2thereforwerequired4cell
map. BA0 1
0
1
89RNB Global University, Bikaner.Course Code -19004000
11
1

90. KARNAUGH MAP MINIMIZATION
90RNB Global University, Bikaner.Course Code -19004000

91. KARNAUGH MAP MINIMIZATION
91RNB Global University, Bikaner.Course Code -19004000

92. KARNAUGH MAP MINIMIZATION
92RNB Global University, Bikaner.Course Code -19004000

93. Karnaugh Map (K-Map)
93RNB Global University, Bikaner.Course Code -19004000

94. KARNAUGH MAP MINIMIZATION
Simplify–usingKarnaughMap
ABC+ABC+ABC+ABC
94RNB Global University, Bikaner.Course Code -19004000

95. KARNAUGH MAP MINIMIZATION
Simplify–usingKarnaughMap
ABC+ABC+ABC+ABC
A BC0001 1110
0
1
95RNB Global University, Bikaner.Course Code -19004000
1
1 1 1

96. KARNAUGH MAP MINIMIZATION
Simplify–usingKarnaughMap
ABC+ABC+ABC+ABC
A BC0001 1110
0
1
96RNB Global University, Bikaner.Course Code -19004000
1
1 1 1

97. KARNAUGH MAP MINIMIZATION
Simplify–usingKarnaughMap
ABC+ABC+ABC+ABC BC
A BC0001 1110
0
1 AB
AC =AC+BC+AB
97RNB Global University, Bikaner.Course Code -19004000
1
1 1 1

98. KARNAUGH MAP MINIMIZATION
SimplifyusingKarnaughMap
f(A,B,C,D)=ABCD+ABCD+ABCD+ABCD+
ABCD+ABCD+ABCD
98RNB Global University, Bikaner.Course Code -19004000

99. KARNAUGH MAP MINIMIZATION
f(A,B,C,D)=ABCD+ABCD+ABCD+ABCD+
ABCD+ABCD+ABCD
ABCD00011110
00
01
11
10
99RNB Global University, Bikaner.Course Code -19004000
1
1
1 1 1 1
1

100. KARNAUGH MAP MINIMIZATION
f(A,B,C,D)=ABCD+ABCD+ABCD+ABCD+
ABCD+ABCD+ABCD
ABCD00011110
00
01
11 AB
10
BC =AB+BC
100RNB Global University, Bikaner.Course Code -19004000
1
1
1 1 1 1
1

101. KARNAUGH MAP MINIMIZATION
Don’tCareCondition:Sometimesinput
combinationsareofnoconcern
Becausetheymaynotexist
•Example:BCDusesonly10ofpossible16
inputcombinations
Sincewe“don’tcare”whattheoutput,wecan
usethese“don’tcare”conditionsforlogic
minimization
•Theoutputforadon’tcareconditioncanbe
either0or1
WEDON’TCARE!!!
101RNB Global University, Bikaner.Course Code -19004000

102. KARNAUGH MAP MINIMIZATION
Don’tCareconditionsdenotedby:
X,-,d,2
•Xisprobablythemostoftenused
•Canalsobeusedtodenoteinputs
Example:ABC=1X1=AC
•Bcanbea0ora1
102RNB Global University, Bikaner.Course Code -19004000

103. KARNAUGH MAP MINIMIZATION
Don’tCareconditionsdenotedby:
103RNB Global University, Bikaner.Course Code -19004000

104. Adders –Half & Full Adder
Adderisacircuitwhichaddstwobinarybits.
Inordertounderstandthefunctioningofeither
ofthesecircuits,wemustspeakofarithmetic
interms
“plustables”,specificallythesumofadding
anytwoone–digitnumbers:2+2=4,2+3=
5,etc.
addnumbersthathadmorethanonedigit
each:23+34=57,but23+38=61.
Thisadaptationofadditiontomultipledigit
numbersgivesrisetothefulladder.
104RNB Global University, Bikaner.Course Code -19004000

105. Adders –Half & Full Adder
Webeginwithtwosimplesums,each
involvingonlysingledigits.2+2=4,and5+5
=10.
Iftheseareso,whydowewritethefollowing
sum25+25as25+25=50,andnotas25+
25=410?Whatdigitiswrittenintheunit’s
columnofthesum?
Thereasonthatwedonotdothisistheidea
ofacarryfromtheunit’scolumntotheten’s
column.
105RNB Global University, Bikaner.Course Code -19004000

106. Adders –Half & Full Adder
Theadditionasfollows:1.5+5is0,witha
carry–outof1,whichgoesintotheten’s
column.2.2+2is4,butwehaveacarry–inof
1fromtheunit’scolumn,sowesay2+2+1=
5.Thesumdigitinthiscolumnisa5.
Wehavejustnotedthatthedecimalnumber2
isrepresentedinbinaryas10.
Itmustbethecasethat,inbinaryaddition,we
havethesumas1+1=10Thisreadsas“the
addition1+1resultsinasumof0anda
carry–outof1”.
106RNB Global University, Bikaner.Course Code -19004000

107. Adders –Half & Full Adder
Recallthedecimalsum25+25.
1
25
25
50
The1writtenabovethenumbersintheten’s
columnshowsthecarry–outfromtheunit’s
columnasacarry–intotheten’scolumn.
107RNB Global University, Bikaner.Course Code -19004000

108. Adders –Half & Full Adder
TheHalfAdder:Thehalfaddertakestwo
singlebitbinarynumbersandproducesasum
andacarry–out,called“carry”.
Hereisthetruthtabledescriptionofahalf
adder.WedenotethesumA+B.
AB SumCarry
00 0 0
01 1 0
10 1 0
11 0 1
108RNB Global University, Bikaner.Course Code -19004000

109. Adders –Half & Full Adder
Writtenasastandardsum,thelastrow
representsthefollowing:
01
+01
1o
Thesumcolumnindicatesthenumbertobe
writtenintheunit’scolumn,immediatelybelow
thetwo1’s.Wewritea0andcarrya1
109RNB Global University, Bikaner.Course Code -19004000

110. Adders –Half & Full Adder
Anadderisadigitallogiccircuitinelectronics
thatimplementsadditionofnumbers.
Inmanycomputersandothertypesof
processors,addersareusedtocalculate
addresses,similaroperationsandtable
indicesintheALUandalsoinotherpartsof
theprocessors.
Addersareclassifiedintotwotypes:halfadder
andfulladder.
Thehalfaddercircuithastwoinputs:AandB,
whichaddtwoinputdigitsandgeneratea
carryandsum.
110RNB Global University, Bikaner.Course Code -19004000

111. Adders –Half & Full Adder
Thefulladdercircuithasthreeinputs:Aand
C,whichaddthethreeinputnumbersand
generateacarryandsum.
111RNB Global University, Bikaner.Course Code -19004000

112. Adders –Half & Full Adder
Anadderisadigitalcircuitthatperforms
additionofnumbers.
Thehalfadderaddstwobinarydigitscalledas
augendandaddendandproducestwooutputs
assumandcarry;XORisappliedtoboth
inputstoproducesumandANDgateis
appliedtobothinputstoproducecarry.
Thefulladderadds3onebitnumbers,where
twocanbereferredtoasoperandsandone
canbereferredtoasbitcarriedin.And
produces2-bitoutput,andthesecanbe
referredtoasoutputcarryandsum.
112RNB Global University, Bikaner.Course Code -19004000

113. Adders –Half & Full Adder
Half-adderTruthTable:
113RNB Global University, Bikaner.Course Code -19004000

114. Adders –Half & Full Adder
FullAdder
Thisadderisdifficulttoimplementthanahalf-
adder.
Thedifferencebetweenahalf-adderandafull-
adderisthatthefull-adderhasthreeinputs
andtwooutputs,whereashalfadderhasonly
twoinputsandtwooutputs.
ThefirsttwoinputsareAandBandthethird
inputisaninputcarryasC-IN.
114RNB Global University, Bikaner.Course Code -19004000

115. Adders –Half & Full Adder
Whenafull-adderlogicisdesigned,youstring
eightofthemtogethertocreateabyte-wide
adderandcascadethecarrybitfromone
addertothenext.
TheoutputcarryisdesignatedasC-OUTand
thenormaloutputisdesignatedasS.
115RNB Global University, Bikaner.Course Code -19004000

116. Adders –Half & Full Adder
Full-adderTruthTable:
116RNB Global University, Bikaner.Course Code -19004000

117. Adders –Half & Full Adder
Withthetruth-table,thefulladderlogiccanbe
implemented.YoucanseethattheoutputSis
anXORbetweentheinputAandthehalf-
adder,SUMoutputwithBandC-INinputs.
WetakeC-OUTwillonlybetrueifanyofthe
twoinputsoutofthethreeareHIGH.
So,wecanimplementafulladdercircuitwith
thehelpoftwohalfaddercircuits.Atfirst,half
adderwillbeusedtoaddAandBtoproduce
apartialSumandasecondhalfadderlogic
canbeusedtoaddC-INtotheSumproduced
bythefirsthalfaddertogetthefinalSoutput.
117RNB Global University, Bikaner.Course Code -19004000

118. Adders –Half & Full Adder
Ifanyofthehalfadderlogicproducesacarry,
therewillbeanoutputcarry.So,COUTwillbe
anORfunctionofthehalf-adderCarry
outputs.Takealookattheimplementationof
thefulladdercircuitshownbelow.
118RNB Global University, Bikaner.Course Code -19004000

119. Adders –BCD Adder
ABCDadderisacombinationalcircuitwhich
addstwobcdnumbers.
WHATAREBCDNUMBERS?
BCDisaclassofencodinginwhicheach
decimaldigitisrepresentedbysomefixed
numberofbits.Usually4or8bitsareused.
119RNB Global University, Bikaner.Course Code -19004000

120. Adders –BCD Adder
120RNB Global University, Bikaner.Course Code -19004000

121. Adders –BCD Adder
Upto9thebcdrepresentationissameasthe
decimalrepresentationandafterthe9.
Thefirst4digitsinBCDrepresentationisused
toshowthefirstdigitindecimalandnextfour
digitsinBCDareusedtorepresentnextdigit
indecimal.
121RNB Global University, Bikaner.Course Code -19004000

122. Adders –BCD Adder
TruthTable:
122RNB Global University, Bikaner.Course Code -19004000

123. Adders –BCD Adder
WHYonly4BITADDERCANNOTBEUSED
?:
whenweprovidetwo4bitsBCDnumberto
the4bitadders,theoutputexceedstheBCD
range,orcalledBCDrepresentation.
WEWANTTOOUTPUTALSOINBCD.but
whenwedirectlytaketheoutputofthe4bit
adderthenitwillbeainvalidrepresentation.
Thereforeweneedsomemechanismthrough
whichwecanchangetheoutputofthe4bit
adderintoavalidBCDrepresentation.
123RNB Global University, Bikaner.Course Code -19004000

124. Adders –BCD Adder
Forthenumberswhichdoesnotsatisfythe
conditionofBCD,6isadded.seeinthe
table,whenthesumis01010thebcd
representationisobtainedbyadding6,so
therepresentationinBCDis10000.
124RNB Global University, Bikaner.Course Code -19004000

125. Adders –BCD Adder
125RNB Global University, Bikaner.Course Code -19004000

126. Subtractor
Subtractor:Subtractoristheonewhichused
tosubtracttwobinarynumber(digit)and
providesDifferenceandBorrowasaoutput.In
digitalelectronicswehavetwotypesof
subtractor.
1.HalfSubtractor
2.FullSubtractor
126RNB Global University, Bikaner.Course Code -19004000

127. Subtractor –Half & Full
HalfSubtractor:HalfSubtractorisusedfor
subtractingonesinglebitbinarydigitfrom
anothersinglebitbinarydigit.Thetruthtableof
HalfSubtractorisshownbelow.
127RNB Global University, Bikaner.Course Code -19004000

128. Subtractor –Half & Full
HalfSubtractor:HalfSubtractorisusedfor
subtractingonesinglebitbinarydigitfrom
anothersinglebitbinarydigit.Thetruthtable
ofHalfSubtractorisshownbelow.
128RNB Global University, Bikaner.Course Code -19004000

129. Subtractor –Half & Full
FullSubtractor:AlogicCircuitWhichisused
forSubtractingThreeSinglebitBinarydigitis
knownasFullSubtractor.TheTruthTableof
FullSubtractorisShownBelow.
129RNB Global University, Bikaner.Course Code -19004000

130. Subtractor –Half & Full
130RNB Global University, Bikaner.Course Code -19004000

131. Multiplexer & De-multiplexer
Amultiplexer(MUX)isacircuitthataccept
manyinputbutgiveonlyoneoutput.
Ademultiplexerfunctionexactlyinthereverse
ofamultiplexer,thatisademultiplexer
acceptsonlyoneinputandgivesmany
outputs.
Generallymultiplexeranddemultiplexerare
usedtogether,becauseofthecommunication
systemsarebidirectional.
131RNB Global University, Bikaner.Course Code -19004000

132. Multiplexer & De-multiplexer
Multiplexer:Multiplexermeansmanyintoone.
Amultiplexerisacircuitusedtoselectand
routeanyoneoftheseveralinputsignalstoa
signaloutput.
Ansimpleexampleofannonelectroniccircuit
ofamultiplexerisasinglepolemultiposition
switch.
132RNB Global University, Bikaner.Course Code -19004000

133. Multiplexer & De-multiplexer
Multiplexer:
Howevercircuitsthatoperateathighspeed
requirethemultiplexertobeautomatically
selected.
Amechanicalswitchcannotperformthistask
satisfactorily.Therefore,multiplexerusedto
performhighspeedswitchingareconstructed
ofelectroniccomponents.
133RNB Global University, Bikaner.Course Code -19004000

134. Multiplexer & De-multiplexer
Multiplexer:
Multiplexerhandletwotypeofdatathatis
analoganddigital.Foranalogapplication,
multiplexerarebuiltofrelaysandtransistor
switches.Fordigitalapplication,theyarebuilt
fromstandardlogicgates.
Themultiplexerusedfordigitalapplications,
alsocalleddigitalmultiplexer,isacircuitwith
manyinputbutonlyoneoutput.
134RNB Global University, Bikaner.Course Code -19004000

135. Multiplexer & De-multiplexer
Multiplexer:
Byapplyingcontrolsignals,wecansteerany
inputtotheoutput.Fewtypesofmultiplexer
are2-to-1,4-to-1,8-to-1,16-to-1multiplexer.
Followingfigureshowsthegeneralideaofa
multiplexerwithninputsignal,mcontrol
signalsandoneoutputsignal.
135RNB Global University, Bikaner.Course Code -19004000

136. Multiplexer & De-multiplexer
Multiplexer:
136RNB Global University, Bikaner.Course Code -19004000

137. Multiplexer & De-multiplexer
Multiplexer:Understanding4-to-1Multiplexer:
The4-to-1multiplexerhas4inputbit,2control
bits,and1outputbit.
ThefourinputbitsareD0,D1,D2andD3.only
oneofthisistransmittedtotheoutputy.
TheoutputdependsonthevalueofABwhich
isthecontrolinput.
Thecontrolinputdetermineswhichoftheinput
databitistransmittedtotheoutput.
137RNB Global University, Bikaner.Course Code -19004000

138. Multiplexer & De-multiplexer
Multiplexer: Understanding 4-to-1 Multiplexer:
138RNB Global University, Bikaner.Course Code -19004000

139. Multiplexer & De-multiplexer
Multiplexer: Understanding 4-to-1 Multiplexer:
Forinstance,asshowninfig.whenAB=00,
theupperANDgateisenabledwhileallother
ANDgatesaredisabled.Therefore,databit
D0istransmittedtotheoutput,givingY=Do.
IfthecontrolinputischangedtoAB=11,all
gatesaredisabledexceptthebottomAND
gate.Inthiscase,D3istransmittedtothe
outputandY=D3.
139RNB Global University, Bikaner.Course Code -19004000

140. Multiplexer & De-multiplexer
Multiplexer: Understanding 4-to-1 Multiplexer:
140RNB Global University, Bikaner.Course Code -19004000

141. Multiplexer & De-multiplexer
Multiplexer: Examples:
1.Anexampleof4-to-1multiplexerisIC74153
inwhichtheoutputissameastheinput.
2.Anotherexampleof4-to-1multiplexeris
45352inwhichtheoutputisthecompliment
oftheinput.
3.Exampleof16-to-1linemultiplexeris
IC74150.
141RNB Global University, Bikaner.Course Code -19004000

142. Multiplexer & De-multiplexer
Multiplexer:Applications:Multiplexerareused
invariousfieldswheremultipledataneedto
betransmittedusingasingleline.Following
aresomeoftheapplicationsofmultiplexers
1.Communication system –Multiple data
2.Telephone network –Multiple Audio signals
3.Computer memory –Bus to storage
4.Transmission from the computer system of a
satellite -GPS
142RNB Global University, Bikaner.Course Code -19004000

143. Multiplexer & De-multiplexer
De-Multiplexer(DEMUX):Demultiplexer
meansonetomany.
Ademultiplexerisacircuitwithoneinputand
manyoutput.
Byapplyingcontrolsignal,wecansteerany
inputtotheoutput.Fewtypesofdemultiplexer
are1-to2,1-to-4,1-to-8and1-to16
demultiplexer.
143RNB Global University, Bikaner.Course Code -19004000

144. Multiplexer & De-multiplexer
De-Multiplexer:
144RNB Global University, Bikaner.Course Code -19004000

145. Multiplexer & De-multiplexer
De-Multiplexer:The1-to-4demultiplexerhas1
inputbit,2controlbit,and4outputbits.
Anexampleof1-to-4demultiplexerisIC
74155.The1-to-4demultiplexerisshownin
figurebelow-
145RNB Global University, Bikaner.Course Code -19004000

146. Multiplexer & De-multiplexer
De-Multiplexer:
146RNB Global University, Bikaner.Course Code -19004000

147. Multiplexer & De-multiplexer
De-Multiplexer:Theinputbitislabelledas
DataD.Thisdatabitistransmittedtothedata
bitoftheoutputlines.Thisdependsonthe
valueofAB,thecontrolinput.
WhenAB=01,theuppersecondANDgateis
enabledwhileotherANDgatesaredisabled.
Therefore,onlydatabitDistransmittedtothe
output,givingY1=Data.
IfDislow,Y1islow.IFDishigh,Y1ishigh.
ThevalueofY1dependsuponthevalueofD.
Allotheroutputsareinlowstate.
147RNB Global University, Bikaner.Course Code -19004000

148. Multiplexer & De-multiplexer
De-Multiplexer:Ifthecontrolinputischanged
toAB=10,allthegatesaredisabledexcept
thethirdANDgatefromthetop.Then,Dis
transmittedonlytotheY2output,andY2=
Data.
Exampleof1-to-16demultiplexerisIC74154
ithas1inputbit,4controlbitsand16output
bit.
148RNB Global University, Bikaner.Course Code -19004000

149. Multiplexer & De-multiplexer
De-Multiplexer:ApplicationsofDemultiplexers
are:
1.Demultiplexerarealsoused for
reconstructionofparalleldataandALU
circuits.
2.CommunicationSystem-Themultiplexerand
demultiplexerworktogethertocarryoutthe
processoftransmissionandreceptionofdata
incommunicationsystem.
149RNB Global University, Bikaner.Course Code -19004000

150. Multiplexer & De-multiplexer
De-Multiplexer:ApplicationsofDemultiplexers
are:
3.Demultiplexerisusedtoconnectasingle
sourcetomultipledestinations.
4.Serialtoparallelconverter-Aserialto
parallelconverterisusedforreconstructing
paralleldatafromincomingserialdata
stream.
150RNB Global University, Bikaner.Course Code -19004000

151. Multiplexer & De-multiplexer
De-Multiplexer:
151RNB Global University, Bikaner.Course Code -19004000

152. Multiplier & Dividers
Multiplicationofbinarynumbersisperformed
inthesamewayasindecimalnumbers–
partialproduct:themultiplicandismultipliedby
eachbitofthemultiplierstartingfromtheleast
significantbit.
152RNB Global University, Bikaner.Course Code -19004000

153. Multiplier & Dividers
Multiplicationoftwobits=A*B(AND)0*0=
00*1=01*0=01*1=1.
153RNB Global University, Bikaner.Course Code -19004000

154. Multiplier & Dividers
154RNB Global University, Bikaner.Course Code -19004000

155. Multiplier & Dividers
Todesigna4-bitbinarynumberdividerwhich
dividesfourbitsby5(101inbinary).
Itcanbeeasilysolvedusingitstruthtableand
K-map.
Weneedstoconsiderthequotient.Soinorder
towritethetruthtableyouneedonlytwo
outputvariables.Thisisbecausethe
maximumnumberthatcanberepresented
using4bitsis15(1111),whichwhendivided
by5yieldsquotient3(0011).
155RNB Global University, Bikaner.Course Code -19004000

156. Multiplier & Dividers
156RNB Global University, Bikaner.Course Code -19004000

157. Multiplier & Dividers
A3toA0representtheinputinbinary.F1and
F0representstheoutputinbinary.
Thistableiseasilyobtainedsincenumbers0
to4upondivisionwith5gives0quotient.5to
9yields1.10to14yields2andsoon.
NowyoucandrawK-mapsforF1andF0.
157RNB Global University, Bikaner.Course Code -19004000

158. Decoder -Encoder
Encoders:Anencoderisacombinational
circuitthatperformstheinverseoperationofa
decoder.
Ifadeviceoutputcodehasfewerbitsthanthe
inputcodehas,thedeviceisusuallycalledan
encoder.e.g.2
n
-to-n,priorityencoders.
Thesimplestencoderisa2
n
-to-nbinary
encoder,whereithasonlyoneof2
n
inputs=1
andtheoutputisthen-bitbinarynumber
correspondingtotheactiveinput.
ItcanbebuiltfromORgates.
158RNB Global University, Bikaner.Course Code -19004000

159. Decoder -Encoder
Encoders:4to2Encoder
159RNB Global University, Bikaner.Course Code -19004000

160. Decoder -Encoder
Encoders:OctaltoBinaryEncoder
Octal-to-Binarytake8inputsandprovides3
outputs,thusdoingtheoppositeofwhatthe3-
to-8decoderdoes.
Atanyonetime,onlyoneinputlinehasa
valueof1.
Thefigurebelowshowsthetruthtableofan
Octal-to-binaryencoder:
160RNB Global University, Bikaner.Course Code -19004000

161. Decoder -Encoder
Encoders:OctaltoBinaryEncoder
161RNB Global University, Bikaner.Course Code -19004000
IoI1I2I3I4I5I6I7Y2Y1Y0
1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 1 1
0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0 1
0 0 0 0 0 0 1 0 1 1 0
0 0 0 0 0 0 0 1 1 1 1

162. Decoder -Encoder
Encoders:OctaltoBinaryEncoder
Foran8-to-3binaryencoderwithinputsI0-I7
thelogicexpressionsoftheoutputsY0-Y2are:
Y0=I1+I3+I5+I7
Y1=I2+I3+I6+I7
Y2=I4+I5+I6+I7
162RNB Global University, Bikaner.Course Code -19004000

163. Decoder -Encoder
Encoders:OctaltoBinaryEncoder
Basedontheaboveequations,wecandraw
thecircuitasshownbelow
163RNB Global University, Bikaner.Course Code -19004000

164. Decoder -Encoder
Decoder:Acombinationalcircuitthatconverts
binaryinformationfromninputlinestoa
maximumof2nuniqueoutputlines.
n-to-m-linedecoders:generatem(=2nor
fewer)mintermsofninputvariablesAn-to-2n
decodertakesann-bitinputandproduces2n
outputs.Theninputsrepresentabinary
numberthatdetermineswhichofthe2n
outputsisuniquelytrue.
164RNB Global University, Bikaner.Course Code -19004000

165. Decoder -Encoder
Decoder:
A2-to-4decoderoperatesaccordingtothe
followingtruthtable.–The2-bitinputiscalled
S1S0,andthefouroutputsareQ0-Q3.–Ifthe
inputisthebinarynumberi,thenoutputQiis
uniquelytrue.
Forinstance,iftheinputS1S0=10(decimal
2),thenoutputQ2istrue,andQ0,Q1,Q3are
allfalse.
165RNB Global University, Bikaner.Course Code -19004000

166. Decoder -Encoder
Decoder:
Thiscircuit“decodes”abinarynumberintoa
“one-of-four”code.
Followthedesignproceduresfromlasttime!
Wehaveatruthtable,sowecanwrite
equationsforeachofthefouroutputs(Q0-
Q3),basedonthetwoinputs(S0-S1).
166RNB Global University, Bikaner.Course Code -19004000

167. Decoder -Encoder
Decoder:
Inthiscasethere’snotmuchtobesimplified.
Herearetheequations:
Q0=S1’S0’
Q1=S1’S0
Q2=S1S0’
Q3=S1S0
167RNB Global University, Bikaner.Course Code -19004000

168. Decoder -Encoder
Decoder:
168RNB Global University, Bikaner.Course Code -19004000

169. Decoder -Encoder
Decoder:Manydeviceshaveanadditional
enableinput,whichisusedto“activate”or
“deactivate”thedevice.•Foradecoder,
–EN=1activatesthedecoder,soitbehaves
asspecifiedearlier.Exactlyoneoftheoutputs
willbe1.
–EN=0“deactivates”thedecoder.By
convention,thatmeansallofthedecoder’s
outputsare0.
Wecanincludethisadditionalinputinthe
decoder’struthtable:
169RNB Global University, Bikaner.Course Code -19004000

170. Decoder -Encoder
Decoder:
170RNB Global University, Bikaner.Course Code -19004000

171. Decoder -Encoder
Decoder:3to8decoder
171RNB Global University, Bikaner.Course Code -19004000

172. Decoder -Encoder
Decoder:3to8decoder
172RNB Global University, Bikaner.Course Code -19004000

173. Decoder -Encoder
COMPARATOR :Comparator compares
binarynumbers.
Logiccomparing2bits:aandb
173RNB Global University, Bikaner.Course Code -19004000

174. Decoder -Encoder
COMPARATOR : Digitalor Binary
Comparators aremade up from
standardAND,NORandNOTgatesthat
comparethedigitalsignalspresentattheir
inputterminalsandproduceanoutput
dependingupontheconditionofthoseinputs.
Forexample,alongwithbeingabletoaddand
subtractbinarynumbersweneedtobeableto
comparethemanddeterminewhetherthe
valueofinputAisgreaterthan,smallerthanor
equaltothevalueatinputBetc.
174RNB Global University, Bikaner.Course Code -19004000

175. Decoder -Encoder
COMPARATOR :Thedigitalcomparator
accomplishesthisusingseverallogicgates
thatoperateontheprinciplesofBoolean
Algebra.
TherearetwomaintypesofDigital
Comparatoravailableandtheseare.
1.IdentityComparator–anIdentity
Comparatorisadigitalcomparatorwithonly
oneoutputterminalforwhenA=B,eitherA=
B=1(HIGH)orA=B=0(LOW).
175RNB Global University, Bikaner.Course Code -19004000

176. Decoder -Encoder
COMPARATOR :2. Magnitude
Comparator–aMagnitudeComparatorisa
digitalcomparatorwhichhasthreeoutput
terminals,oneeachforequality,A=Bgreater
than,A>BandlessthanA<B
ThepurposeofaDigitalComparatoristo
compareasetofvariablesorunknown
numbers,forexampleA(A1,A2,A3,….An,
etc)againstthatofaconstantorunknown
valuesuchasB(B1,B2,B3,….Bn,etc)and
produceanoutputconditionorflagdepending
upontheresultofthecomparison.
176RNB Global University, Bikaner.Course Code -19004000

177. Decoder -Encoder
COMPARATOR :Forexample,amagnitude
comparatoroftwo1-bits,(AandB)inputs
wouldproducethefollowingthreeoutput
conditionswhencomparedtoeachother.
A>B,A=B,A<B
Whichmeans:AisgreaterthanB,Aisequal
toB,orAislessthanB
Thisisusefulifwewanttocomparetwo
variablesandwanttoproduceanoutputwhen
anyoftheabovethreeconditionsare
achieved.
177RNB Global University, Bikaner.Course Code -19004000

178. Decoder -Encoder
COMPARATOR :
178RNB Global University, Bikaner.Course Code -19004000

179. Decoder -Encoder
COMPARATOR :Thentheoperationofa1-bit
digitalcomparatorisgiveninthefollowing
TruthTable.
179RNB Global University, Bikaner.Course Code -19004000

180. Decoder -Encoder
CodeConversion:Binary-to-Gray
Belowtableshowsnatural-binarynumbers
(upto4-bit)andcorrespondinggraycodes.
180RNB Global University, Bikaner.Course Code -19004000

181. Decoder -Encoder
CodeConversion:Binary-to-Gray
Lookingatgray-code(G3G2G1G0),wefind
thatanytwosubsequentnumbersdifferinonly
onebit-change.
Thesametableisusedastruth-tablefor
designingalogiccircuitrythatconvertsagiven
4-bitnaturalbinarynumberintograynumber.
Forthiscircuit,B3B2B1B0areinputswhile
G3G2G1G0areoutputs.
181RNB Global University, Bikaner.Course Code -19004000

182. Decoder -Encoder
CodeConversion:Binary-to-Gray
182RNB Global University, Bikaner.Course Code -19004000

183. Decoder -Encoder
CodeConversion:Binary-to-Gray
183RNB Global University, Bikaner.Course Code -19004000

184. Decoder -Encoder
CodeConversion:Binary-to-Gray
Sothat’sasimplethreeEX-ORgatecircuit
thatconvertsa4-bitinputbinarynumberinto
itsequivalent4-bitgraycode.Itcanbe
extendedtoconvertmorethan4-bitbinary
numbers.
184RNB Global University, Bikaner.Course Code -19004000

185. Decoder -Encoder
CodeConversion:Gray-to-binary
Oncetheconvertedcode(nowinGrayform)is
processed,wewanttheprocesseddataback
inbinaryrepresentation.Soweneeda
converterthatwouldperformreverse
operationtothatofearlierconverter.Thiswe
callaGray-to-Binaryconverter.
Thedesignagainstartsfromtruth-table:.
185RNB Global University, Bikaner.Course Code -19004000

186. Decoder -Encoder
CodeConversion:Gray-to–binary
186RNB Global University, Bikaner.Course Code -19004000

187. Decoder -Encoder
CodeConversion:Gray-to–binary
187RNB Global University, Bikaner.Course Code -19004000

188. Decoder -Encoder
CodeConversion:Gray-to–binary
188RNB Global University, Bikaner.Course Code -19004000

189. ROM & Programmable Logic
Thenextthreecombinationalcomponentswe
willstudyare:ROM,PLA,andPAL.
ROM'sPLA'sandPAL'sarestorage
Components.
Amoreprecisedefinitionis:acombinational
componentisacircuitthatdoesn'thave
memoryofpastinputs.(Theoutputsofa
combinationalcomponentarecompletely
determinedbythecurrentinputs.)
189RNB Global University, Bikaner.Course Code -19004000

190. ROM & Programmable Logic
ROM:AROMisacombinationalcomponent
forstoringdata.Thedatamightbeatruth
tableorthedatamightbethecontrolwordsfor
amicroprogrammedCPU.(Controlwordsina
microprogrammedCPUinterpretthemacro
instructionsunderstoodbytheCPU.)
AROMcanbeprogrammedatthefactoryor
inthefield.
Thefollowingimageshowsthegenericformof
aROM:
190RNB Global University, Bikaner.Course Code -19004000

191. ROM & Programmable Logic
ROM:(x=log
2n<=>2
x
=n)
191RNB Global University, Bikaner.Course Code -19004000

192. ROM & Programmable Logic
ROM: An n x m ROM can store the truth table
for m functions defined on log
2n variables:
192RNB Global University, Bikaner.Course Code -19004000

193. ROM & Programmable Logic
ROM:Example:Implementthefollowing
functionsinaROM:
F
0=A
F
1=A'B'+AB
SinceaROMstoresthecompletetruthtable
ofafunction(oryoucouldsaythataROM
decodeseverymintermofafunction)
Thefirststepistoexpresseachfunctionasa
truthtable.
193RNB Global University, Bikaner.Course Code -19004000

194. ROM & Programmable Logic
ROM:
For the discussion that follows it may be
helpful to keep in mind the canonical form of
the function also:
F
0= AB' + AB
F
1= A'B' + AB
194RNB Global University, Bikaner.Course Code -19004000

195. ROM & Programmable Logic
ROM:
WeuseaspecialnotationtoshowtheROM
implementationofafunction:
195RNB Global University, Bikaner.Course Code -19004000

196. ROM & Programmable Logic
ROM:
Theimageaboveshowshowa4x3ROMcan
beusedtoimplementthetwofunctionsF
0and
F
1.(Note,thereisroomintheROMfor3
functionsoftwovariables.F
2isn'tused.
196RNB Global University, Bikaner.Course Code -19004000

197. ROM & Programmable Logic
ROM:
ROMsprogrammedatthefactoryarecalled
maskROMSbecauseduringfabricationthe
circuitpatternsaredeterminedbyamask.
Thereareseveraldifferenttypesoffield
programmableROMS:
PROM(ProgrammableRead-OnlyMemory)-This
isthetypethatwasdiscussedabove.Connections
arefusedandburnedinthefieldwithaPROM
programmer.
197RNB Global University, Bikaner.Course Code -19004000

198. ROM & Programmable Logic
ROM:
EPROM (ErasableProgrammableRead-Only
Memory)-ThistypeofROMcanbere-writtenby
shininganultravioletlightthroughawindowonthe
IC.
EEPROM (ElectricallyErasableProgrammable
Read-OnlyMemory)-Ratherthanultravioletlight
anextrahighvoltageisusedtore-writethe
contentsofthistypeofROM.
FlashMemory-Insteadofrequiringextrahigh
voltagesflashmemorydevicesworkwithregular
devicevoltages.
198RNB Global University, Bikaner.Course Code -19004000

199. ROM & Programmable Logic
ProgrammableLogic:Aprogrammablelogic
deviceworkslikeaROMbutisamoreefficient
solutionforimplementingsparse(Matrixinwhichnon
zeroelementsarelessthannoofzeros)output
functions(Notallmintermsaredecoded).
Therearetwotypesofprogrammablelogicdevices:
1.PLA (Programmable Logic Array)
2.PAL (Programmable Array Logic)
199RNB Global University, Bikaner.Course Code -19004000

200. ROM & Programmable Logic
ProgrammableArrayLogic(PAL):
PALisaprogrammablelogicdevicethathas
ProgrammableANDarray&fixedORarray.
TheadvantageofPAListhatwecangenerateonly
therequiredproducttermsofBooleanfunctioninstead
ofgeneratingallthemintermsbyusingprogrammable
ANDgates.
TheblockdiagramofPALisshowninthefollowing
figure.
200RNB Global University, Bikaner.Course Code -19004000

201. ROM & Programmable Logic
ProgrammableArrayLogic(PAL):
Here,theinputsofANDgatesareprogrammable.
ThatmeanseachANDgatehasbothnormaland
complementedinputsofvariables.
So,basedontherequirement,wecanprogramanyof
thoseinputs.So,wecangenerateonlythe
requiredproducttermsbyusingtheseANDgates.
theinputsofORgatesarenotofprogrammabletype.
So,thenumberofinputstoeachORgatewillbeof
fixedtype.Hence,applythoserequiredproductterms
toeachORgateasinputs.
Therefore,theoutputsofPALwillbeintheform
ofsumofproductsform.
201RNB Global University, Bikaner.Course Code -19004000

202. ROM & Programmable Logic
ProgrammableArrayLogic(PAL):
Example:LetusimplementthefollowingBoolean
functionsusingPAL.
A=XY+XZ′
A=XY′+YZ′
Thegiventwofunctionsareinsumofproductsform.
TherearetwoproducttermspresentineachBoolean
function.So,werequirefourprogrammableAND
gates&twofixedORgatesforproducingthosetwo
functions.
ThecorrespondingPALisshowninthefollowing
figure.
202RNB Global University, Bikaner.Course Code -19004000

203. ROM & Programmable Logic
ProgrammableArrayLogic(PAL):
Example:
203RNB Global University, Bikaner.Course Code -19004000

204. ROM & Programmable Logic
ProgrammableArrayLogic(PAL):
Example:
TheprogrammableANDgateshavetheaccessof
bothnormalandcomplementedinputsofvariables.In
theabovefigure,theinputsX,X′,Y,Y′,Z&Z′,are
availableattheinputsofeachANDgate.
So,programonlytherequiredliteralsinorderto
generateoneproducttermbyeachANDgate.The
symbol‘X’isusedforprogrammableconnections.
Thesymbol‘X’isusedforprogrammableconnections.
204RNB Global University, Bikaner.Course Code -19004000

205. ROM & Programmable Logic
ProgrammableArrayLogic(PAL):
Example:
Here,theinputsofORgatesareoffixedtype.So,the
necessaryproducttermsareconnectedtoinputsof
eachORgate.
SothattheORgatesproducetherespectiveBoolean
functions.
Thesymbol‘.’isusedforfixedconnections.
205RNB Global University, Bikaner.Course Code -19004000

206. ROM & Programmable Logic
ProgrammableLogicArray(PLA):
PLAisaprogrammablelogicdevicethathas
bothProgrammable AND array&
ProgrammableORarray.Hence,itisthemost
flexiblePLD.
TheblockdiagramofPLAisshowninthe
followingfigure.
206RNB Global University, Bikaner.Course Code -19004000

207. ROM & Programmable Logic
ProgrammableLogicArray(PLA):
Here,theinputsofANDgatesareprogrammable.
ThatmeanseachANDgatehasbothnormaland
complementedinputsofvariables.
Basedontherequirement,wecanprogramanyof
thoseinputs.So,wecangenerateonlythe
requiredproducttermsbyusingtheseANDgates.
TheinputsofORgatesarealsoprogrammable.So,
wecanprogramanynumberofrequiredproduct
terms,sincealltheoutputsofANDgatesareapplied
asinputstoeachORgate.Therefore,theoutputsof
PALwillbeintheformofsumofproductsform.
207RNB Global University, Bikaner.Course Code -19004000

208. ROM & Programmable Logic
ProgrammableLogicArray(PLA):
Example-
LetusimplementthefollowingBoolean
functionsusingPLA.
A=XY+XZ′
B=XY′+YZ+XZ′
Thegiventwofunctionsareinsumofproductsform.
Thenumberofproducttermspresentinthegiven
BooleanfunctionsA&Baretwoandthree
respectively.Oneproductterm,Z′XZ′Xiscommonin
eachfunction.
208RNB Global University, Bikaner.Course Code -19004000

209. ROM & Programmable Logic
ProgrammableLogicArray(PLA):
werequirefourprogrammableANDgates&two
programmableORgatesforproducingthosetwo
functions.ThecorrespondingPLAisshowninthe
followingfigure.
209RNB Global University, Bikaner.Course Code -19004000

210. ROM & Programmable Logic
ProgrammableLogicArray(PLA):
TheprogrammableANDgateshavetheaccessof
bothnormalandcomplementedinputsofvariables.In
theabovefigure,theinputsX,X′,Y,Y′,Z&Z′,are
availableattheinputsofeachANDgate.So,program
onlytherequiredliteralsinordertogenerateone
producttermbyeachANDgate.
Alltheseproducttermsareavailableattheinputsof
eachprogrammableORgate.But,onlyprogramthe
requiredproducttermsinordertoproducethe
respectiveBooleanfunctionsbyeachORgate.The
symbol‘X’isusedforprogrammableconnections.
210RNB Global University, Bikaner.Course Code -19004000

211. FPGA -Field Programmable Gate
Arrays
FieldProgrammableGateArrays(FPGAs)are
semiconductordevicesthatarebasedaroundamatrix
ofconfigurablelogicblocks(CLBs)connectedvia
programmableinterconnects.
FPGAscanbereprogrammedtodesiredapplicationor
functionalityrequirementsaftermanufacturing.
ThisfeaturedistinguishesFPGAsfromApplication
SpecificIntegratedCircuits(ASICs),whicharecustom
manufacturedforspecificdesigntasks.
211RNB Global University, Bikaner.Course Code -19004000

212. FPGA -Field Programmable Gate
Arrays
Field-programmablegatearrays(FPGAs)are
reprogrammablesiliconchips.RossFreeman,the
cofounderofXilinx,inventedthefirstFPGAin1985.
FPGAchipadoptionacrossallindustriesisdrivenby
thefactthatFPGAscombinethebestpartsof
application-specificintegratedcircuits(ASICs)and
processor-basedsystems.
FPGAsprovidehardware-timedspeedandreliability,
buttheydonotrequirehighvolumestojustifythe
largeupfrontexpenseofcustomASICdesign.
Reprogrammablesiliconalsohasthesameflexibility
ofsoftwarerunningonaprocessor-basedsystem,but
itisnotlimitedbythenumberofprocessingcores
available. 212RNB Global University, Bikaner.Course Code -19004000

213. FPGA -Field Programmable Gate
Arrays
Althoughone-timeprogrammable(OTP)FPGAsare
available,thedominanttypesareSRAMbasedwhich
canbereprogrammedasthedesignevolves.
ApplicationsofFPGAs:
1.Aerospace&Defence-Radiation-tolerantFPGAs
alongwithintellectualpropertyforimageprocessing,
waveformgeneration,andpartialreconfigurationfor
SDRs(SpecialDrawingRights).
213RNB Global University, Bikaner.Course Code -19004000

214. FPGA -Field Programmable Gate
Arrays
ApplicationsofFPGAs:
2.ASICPrototyping-ASICprototypingwithFPGAs
enablesfastandaccurateSoC(SystemonChip)
systemmodelingandverificationofembedded
software
3.Automotive-AutomotivesiliconandIPsolutionsfor
gatewayanddriverassistancesystems,comfort,
convenience,andin-vehicleinfotainment.
4.ConsumerElectronics-Cost-effectivesolutions
enablingnextgeneration,full-featuredconsumer
applications,suchasconvergedhandsets,digitalflat
paneldisplays,informationappliances,home
networking,andresidentialsettopboxes.
214RNB Global University, Bikaner.Course Code -19004000

215. FPGA -Field Programmable Gate
Arrays
ApplicationsofFPGAs:
5.DataCenter-Designedforhigh-bandwidth,low-
latencyservers,networking,andstorageapplications
tobringhighervalueintoclouddeployments.
6.HighPerformanceComputingandDataStorage-
SolutionsforNetworkAttachedStorage(NAS),
StorageAreaNetwork(SAN),servers,andstorage
appliances.
7.Industrialhigherdegreesofflexibility,fastertime-to-
market,andloweroverallnon-recurringengineering
costs(NRE)forawiderangeofapplicationssuchas
industrialimagingandsurveillance,industrial
automation,andmedicalimagingequipment.
215RNB Global University, Bikaner.Course Code -19004000

216. FPGA -Field Programmable Gate
Arrays
ApplicationsofFPGAs:
8.Medical-Fordiagnostic,monitoring,andtherapy
applications.
9.Security-offerssolutionsthatmeettheevolving
needsofsecurityapplications,fromaccesscontrolto
surveillanceandsafetysystems.
10.WiredCommunications-End-to-endsolutionsforthe
Reprogrammable NetworkingLinecardPacket
Processing,Framer/MAC,serialbackplanes,and
more.
216RNB Global University, Bikaner.Course Code -19004000

217. TTL IC
Transistor–transistorlogic(TTL)isaclassofdigital
circuitsbuiltfrombipolarjunctiontransistors(BJTs)
andresistors.
Itiscalledtransistor–transistorlogicbecause
transistorsperformboththelogicfunction(e.g.,AND)
andtheamplifyingfunction(comparewithresistor–
transistorlogic(RTL)anddiode–transistorlogic(DTL).
TTLintegratedcircuits(ICs)werewidelyusedin
applicationssuchascomputers,industrialcontrols,
testequipmentandinstrumentation,consumer
electronics,andsynthesizers.
217RNB Global University, Bikaner.Course Code -19004000

218. Quine McCluskey Tabulation Method
TheQuineMcCluskeytabulationmethodisavery
usefulandconvenienttoolforsimplificationofBoolean
functionsforlargenumbersofvariables.
AsweknowthattheKarnaughmapmethodisavery
usefulandconvenienttoolforsimplificationofBoolean
functionsaslongasthenumberofvariablesdoesnot
exceedfour.
Butforcaseoflargenumberofvariables,the
visualizationandselectionofpatternsofadjacentcells
intheKarnaughmapbecomescomplicatedandtoo
muchdifficult.
ForthosecasesQuineMcCluskeytabulationmethod
takesvitalroletosimplifytheBooleanexpression.
218RNB Global University, Bikaner.Course Code -19004000

219. Quine McCluskey Tabulation Method
TheQuineMcCluskeytabulationmethodisaspecific
step-by-stepproceduretoachieveguaranteed,
simplifiedstandardformofexpressionforafunction.
Nowtakeanexampletounderstandtheprocess.Let
we have a Boolean expressionF=
(0,1,2,3,5,7,8,10,14,15)andwehavetominimizethat
byQuineMcCluskeytabulationmethod.
219RNB Global University, Bikaner.Course Code -19004000

220. Quine McCluskey Tabulation Method
Tostartwithwehavetomaketableandkeptallthe
numbersinsamegroupwhosebinarynumbers
containingequal1s.Like1,2,8(0001,0010,1000)are
insamegroupbecauseallhasequal1sintheirbinary
number.Seeinbelowtable.
220RNB Global University, Bikaner.Course Code -19004000

221. Quine McCluskey Tabulation Method
Wehavetoaddanothercolumntorightsideofthat
tablenaming1
st
Nowbetweentwogroupsdepending
uponnumberof1s,wehavetofindsimilarnumber
withonlyonepositionchangeto0to1.
Seethebinarynumberof1(0001)fromfirstgroupand
3(0011)fromsecondgroup.Boththenumberare
similaronlysecondbitpositionfromLSBchange0to
1.Soinnewcolumnweshouldwrite(1,3)00-1(in
placeofnumberchangeweput“–“onthat).Inthis
waywehavetocheckentiretableandmakenew
columnaccordingly.
221RNB Global University, Bikaner.Course Code -19004000

222. Quine McCluskey Tabulation Method
222RNB Global University, Bikaner.Course Code -19004000

223. Quine McCluskey Tabulation Method
Nowwehavetoagainaddanothercolumntoright
sideofthattablenaming2
nd
Nowbetweentwogroups
from1
st
column,wehavetofindsimilarnumberwith
onlyonepositionchangeto0to1.
Seethebinarynumberof(0,1)(000-)and(2,3)(001-).
Boththenumbersaresimilaronlysecondbitposition
fromLSBchange0to1.Soinnewcolumnweshould
write(0,1,2,3)00–(inplaceofnumberchangeweput
“–“onthat).Inthiswaywehavetocheckentiretable
andmakenewcolumnaccordingly.
223RNB Global University, Bikaner.Course Code -19004000

224. Quine McCluskey Tabulation Method
224RNB Global University, Bikaner.Course Code -19004000

225. Quine McCluskey Tabulation Method
Mostofwecompletednowwehavetomark
whatarethosecombinationweusedin
2
nd
Likeforfirstone(0,1,2,3),weused0,1and
2,3combinationfrom1
st
column.
Nowmakethefinaltableforgettingthe
simplifiedBooleanexpression.Nowquestion
ishowitpossible?Wehavetomakeatable
withallcombinationof2
nd
columnandunused
portionof1
st
225RNB Global University, Bikaner.Course Code -19004000

226. Quine McCluskey Tabulation Method
226RNB Global University, Bikaner.Course Code -19004000

227. Quine McCluskey Tabulation Method
227RNB Global University, Bikaner.Course Code -19004000

228. Quine McCluskey Tabulation Method
Wecankeeponecrossinanyonecolumn.So
wehavetocutsomerawwhichwasmost
benefitedentirelytomakeonecrossatone
column.Butkeepmindthatweshouldnotcut
thoserawwhichcangiveascrossatsingle
column.
228RNB Global University, Bikaner.Course Code -19004000

229. Quine McCluskey Tabulation Method
229RNB Global University, Bikaner.Course Code -19004000

230. Quine McCluskey Tabulation Method
NowwecangetthesimplifiedBoolean
expressionfromabovetableandit’s
correspond2
nd
columnvalue.Wehavetotake
uncutrowwithits2
nd
columnvalueand
convertitwithABCDvariable.Likewhereyou
find0takecomplementvalue,1for
uncomplementvalueand“–“fornovariable.
230RNB Global University, Bikaner.Course Code -19004000

231. Quine McCluskey Tabulation Method
0,8,2,10(-0 –0)=B^D^
1,3,5,7(0 ––1) = A^D
14,15 (1 1 1 -)=ABC
So answer will be F =B^D^+A^D+ABC
231RNB Global University, Bikaner.Course Code -19004000

232. Quine McCluskey Tabulation Method
Example-Letussimplifythefollowing
Boolean
Function,f(W,X,Y,Z)=∑m(2,6,8,9,10,11,14,15)
usingQuine-McClukeytabularmethod.
232RNB Global University, Bikaner.Course Code -19004000

233. Quine McCluskey Tabulation Method
Example-
233RNB Global University, Bikaner.Course Code -19004000
Group Minterm W X Y Z
GA1 2 0 0 1 0
8 1 0 0 0
GA2 6 0 1 1 0
9 1 0 0 1
10 1 0 1 0
GA 11 1 0 1 1
14 1 1 1 0
GA4 15 1 1 1 1

234. Quine McCluskey Tabulation Method
Example-
234RNB Global University, Bikaner.Course Code -19004000
GroupMinterm W X Y Z
GB1 2,6 0 - 1 0
2,10 - 0 0 0
8,9 1 0 0 -
8,10 1 0 - 1
GB2 6,14 - 1 1 0
9,11 1 0 - 1
10,11 1 0 1 -
10,14 1 - 1 0
GB3 11,15 1 - 1 1
14,15 1 1 1 -

235. Quine McCluskey Tabulation Method
Example-
235RNB Global University, Bikaner.Course Code -19004000
Group Minterm W X Y Z
GB1 2,6,10,14 - - 1 0
2,10,6,14 - - 1 0
8,9,10,11 1 0 - -
8,10,9,11 1 0 - -
GB2 10,11,14,15 1 - 1 -
10,14,11,15 1 - 1 -

236. Quine McCluskey Tabulation Method
Example-
236RNB Global University, Bikaner.Course Code -19004000
Group Minterm W X Y Z
GB1 2,6,10,14 - - 1 0
8,9,10,11 1 0 - -
GB2 10,11,14,15 1 - 1 -

237. Quine McCluskey Tabulation Method
Example-
237RNB Global University, Bikaner.Course Code -19004000
Min
terms
/
Prime
Implic
ants
2 6 8 9 10 11 14 15
YZ’ 1 1 1 1
WX’ 1 1 1 1
WY 1 1 1 1

238. Quine McCluskey Tabulation Method
Example-
238RNB Global University, Bikaner.Course Code -19004000
Min
terms
/
Prime
Implic
ants
2 6 8 9 10 11 14 15
YZ’ 1 1 1 1
WX’ 1 1 1 1
WY 1 1 1 1

239. Quine McCluskey Tabulation Method
Example-Letussimplifythefollowing
Boolean.
f(W,X,Y,Z)=YZ’+WX’+WY.
239RNB Global University, Bikaner.Course Code -19004000

240. Quine McCluskey Tabulation Method
Example-Letussimplifythefollowing.
F(a,b,c,d)=Ʃ(0,5,8,9,10,11,14,15)
240RNB Global University, Bikaner.Course Code -19004000

241. Quine McCluskey Tabulation Method
Example-Letussimplifythefollowing.
F(a,b,c,d)=Ʃ(0,5,8,9,10,11,14,15)
Ans–AB’+AC+B’C’D’+A’BC’D
241RNB Global University, Bikaner.Course Code -19004000

242. Reviews
SimplificationofBooleanfunctionbyK-Map.
SimplificationofBooleanfunctionbyQ.M.
Adder–Half,Full,BCD,HighSpeed.
Subtractor,Multiplier,dividers.
ALU,CodeConversion–Encoder,Decoder.
Comparators,Multiplexers,Demultiplexers.
ImplementationusingICs.
242RNB Global University, Bikaner.Course Code -19004000

243. Thank You!
RNB Global University, Bikaner. 243
Course Code -19004000