DLD Chapter-4.pdf

Combinational Logic Circuit

1. 4.1
Under graduate (2016)
GirmaAdam (M.Tech)
Chapter Four
Combinational
logiccircuits

2. 4.2
Topics discussed in this section:
Cont’d..
Introduction
Adders
Subtractors
Binary code conversion
Magnitude comparator
Decoders
Encoders
Multiplexers and Multiplexer tree

3. 4.3
Introduction
Basically the digital Circuits are divided in to two broad
categories
Combinational Circuits
Sequential Circuits
A Combinational circuits consists of logical gates whose output
at any time are depending on the present combination of inputs.
A block diagram of a combinational circuit is as shown below

4. 4.4
Cont’d..
The design of combinational circuits starts from the outline of
the problem and ends in a logical circuit diagram, or set Boolean
functions from which the logic diagram can be obtained.
The procedure involves the following steps:-
The problem is stated
The number of both input and output variables required are
determined
Both input and output variables are assigned letter symbols
Te truth table that defines the required relationships
between input and outputs are derived.

5. 4.5
Cont’d..
The simplified Boolean function for each output is obtained.
Thelogicdiagramisdrawn.
Apracticaldesignmethodhavetoconsiderthefollowing
requirements:-
1.Minimumnumberofgates
2.Minimumnumberofinputstothegates
3.Minimumpropagationdelay
4.Minimumnumberofinterconnection
5.HighSpeedofprocessing
6.LessComplexity

6. 4.6
ADDERS
Themostbasicarithmeticoperationistheadditionoftwobinarydigits.
Thissimpleadditionconsistoffourpossibleelementaryoperations
ACombinationalcircuitsthatperformstheadditionoftwobitsis
calledaHalf-adder.
ACombinationalcircuitsthatperformstheadditionofthree
bits(twosignificantbitsandapreviouscarry)iscalledFull-adder.

7. 4.7
Half-adder
The half-adder can be used to add together the two least
significant bits A and B of two numbers, where there is no input
carry.
The block diagram of a half-adder is shown below

8. 4.8
Cont,d..
Formulateatruthtabletoidentifyexactlythefunctionofthe
half-adder.
ThesimplifiedBooleanfunctionsforthetwooutputscanbe
obtaineddirectlyfromthetruthtable.
ThesimplifiedexpressionsforSandCare:-

9. 4.9
Cont’d..

10. 4.10
Full-adder
A half-adder has only two inputs and there is no provision to add
a carry coming from the lower order bits when multibit addition is
performed.
For this purpose, a third input terminal is added and this circuits
(full -adder) is used to add An,Bn,Cn-1.
where
Anand Bnare the n
th
order bits of the number Aand Brespectively.
Cn-1is the carry generated from the addition of (n-1) the order bits

11. 4.11
Cont,d..
The truth table of full-adder and the k-map for simplification of
outputs Snand Cnare given below

12. 4.12
Cont’d..
ThisimplementationusesthefollowingBooleanexpressions

13. 4.13
Cont’d...
TheSnoutputfromthesecondhalf-adderistheexclusive-OR
ofCn-1andtheoutputofthefirsthalf-adder,giving
Carry

14. 4.14
Cont’d...

15. 4.15
Full-adder from half-adders

16. 4.16
Parallel adder
Twoormorefull-addersareconnectedtoformparallelbinary
adders.
Thecarryoutputsignalfromonestagepropagatestothecarry
inputofthenextstage

17. 4.17
Cont,d..
Example.1:-Determinethesumgeneratedbythe3-bitparallel
adderandshowtheintermediatecarrierswhenthebinary
number101and011arebeingadded?
Solution

18. 4.18
A 4-bit parallel binary adder
Exercise1:-Showhowadderscanbeconnectedtoforman8-
bitparalleladder,andshowtheoutputbitsforthefollowing
inputbinarynumbers?10111001and10011110

19. 4.19
Subtractors
Half-Subtractor:-alogicalcircuitforthesubtractionofB
fromA,whereAandBare1-bitnumbersisreferredtoasa
half-Subtractor.
Thetruthtableofhalf-Subtractoris:-
HereAandBaretwoinputsandD(difference)andC(borrow)
arethetwooutputs

20. 4.20
Cont’d...
Fromthetruthtable,thelogicalexpressionforDandCare
obtained
Thelogicaldiagramofhalf-Subtractorusinggatesisshown
below

21. 4.21
Cont’d..
Full-Subtractor:-Justlikeafull-adderwerequireafull-
Subtractorforperformingmultibitsubtraction,
Afull-Subtractorwillhavethreeinputs,An,BnandCn-1(borrow
fromthepreviousstage)andtwooutputsDn(difference)and
Cn(borrow).
ThetruthtableofFull-subtractoris:-

22. 4.22
Cont’d..
Inputs Outputs
An Bn Cn1 Dn Cn
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
1 0 0 1 0
1 0 1 0 0
1 1 0 0 0
1 1 1 1 1
The truth table of full-Subtractor and the k-map for simplification of
outputs Dnand Cnare given below

23. 4.23
Cont’d..
ThisimplementationusesthefollowingBooleanexpressions

24. 4.24
Cont’d..
Thefull–SubtractorlogicCircuitdiagram

25. 4.25
Binary Subtractor using 2’s complement
TheSubtrcationA–Bcanbedonebytakingthe2’s
complementofBandaddingittoAbecauseA-B=A+(-B)=
A+2’sB.
Itmeansifweusetheinverterstomake1’scomplementofB
(connectingeachBitoaninverter)andthenadd1tothe
leastsignificantbit(bysettingcarryC0to1)ofbinary
adder,thenwecanmakeabinarysubtractor.

26. 4.26
4 bit 2’s complement Subtractor

27. 4.27
BinaryConversion
Theavailabilityofalargevarietyofcodesforthesame
discreteelementsofinformationresultsintheuseofdifferent
codesbydifferentdigitalsystems.
Itissometimesnecessarytousetheoutputofonesystemas
inputtoanother,atthisconditionaconversioncircuitis
insertedbetweenthetwosystems,ifeachusesdifferentcodes
forthesameinformation.
Thusacodeconverterisacircuitthatmakesthetwosystems
compatibleeventhougheachsystemusesadifferentbinary
code.

28. 4.28
Cont’d..
Thedesignprocedureofcodeconverterswillbeillustratedby
meansofaspecificexamples:-
1.BinarytoGraycodeconverter
Thetruthtableofa4-bitbinarytograycodeconverterisgiven
below:-
Binary codes Gray codes
B3 B2 B1 B0 G3 G2 G1 G0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 1
0 0 1 1 0 0 1 0

29. 4.29
Cont’d..
Binary codes Gray codes
B3 B2 B1 B0 G3 G2 G1 G0
0 1 0 0 0 1 1 0
0 1 0 1 0 1 1 1
0 1 1 0 0 1 0 1
0 1 1 1 0 1 0 0
1 0 0 0 1 1 0 0
1 0 0 1 1 1 0 1
1 0 1 0 1 1 1 1
1 0 1 1 1 1 1 0
1 1 0 0 1 0 1 0
1 1 0 1 1 0 1 1
1 1 1 0 1 0 0 1
1 1 1 1 1 0 0 0

30. 4.30
Cont’d..

31. 4.31
Cont’d..
ThisimplementationusesthefollowingBooleanexpressions

32. 4.32
Cont’d..
2.GraytoBinarycodeconverter
Thetruthtableofa4-bitGraytobinarycodeconverterisgiven
below:-
Gray codes Binary codes
G3 G2 G1 G0 B3 B2 B1 B0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 0
0 0 1 0 0 0 1 1

33. 4.33
Cont’d..
Gray codes Binary codes
G3 G2 G1 G0 B3 B2 B1 B0
0 1 1 0 0 1 0 0
0 1 1 1 0 1 0 1
0 1 0 1 0 1 1 0
0 1 0 0 0 1 1 1
1 1 0 0 1 0 0 0
1 1 1 1 1 0 0 1
1 1 1 0 1 0 1 0
1 0 1 0 1 0 1 1
1 0 1 1 1 1 0 0
1 0 1 1 1 1 0 1
1 0 0 1 1 1 1 0
1 0 0 0 1 1 1 1

34. 4.34
Cont’d..

35. 4.35
Cont’d..
ThisimplementationusesthefollowingBooleanexpressions
andlogicdiagram

36. 4.36
Cont’d..
Exercise
1.Convertthebinarynumber0101toGraycodewith
exclusive–ORgates
2.ConverttheGraycode1011tobinarywith
exclusive–ORgates
Solution

37. 4.37
Magnitude comparator
Amagnitudecomparatorisacombinationalcircuitthatcompares
twonumbersAandB,anddeterminestheirrelativemagnitudes.
Theoutcomeofthecomparisonisspecifiedbythreebinary
variablesthatindicatewhetherA>B,A=BorA<B.
Exclusive-ORgatecanbeusedasabasiccomparator
1.Equality
Exclusive-ORgateas1-bitcomparator

38. 4.38
Cont’d..
Exclusive-OR gate as 2-bit comparator
The output is 1 when Ao=Bo and A1=B1,

39. 4.39
Cont’d..
Exclusive-OR gate as 4-bit comparator
Detects one of three conditions
Only one output will be High at any one time
-A greater than B (A > B)
-A equal to B (A = B)
-A less than B (A < B)

40. 4.40
Cont’d..
Thetwonumberswillbeequalifallpairsofsignificantdigits
areequal,thatis,A3=B3,A2=B2,A1=B1andA0=B0.
TodetermineaninequalityofbinarynumberAandB,starting
fromthemostsignificantpositionineachnumber.Thefollowing
conditionarepossible
1. If A3= 1 and B3= 0 , number A > B
2. If A3= 0 and B3= 1, number A <B
3. If A3= B3, then you must examine the next lower bit
position for an inequality.
The comparison continues until a pair of unequal digits is reached.

41. 4.41
Cont’d..
Example:-Applyeachofthefollowingsetsofbinarynumbersto
thecomparatorcircuitanddeterminetheoutputbyfollowingthe
logicallevelsthroughthecircuit
a)10and10 b)11and10
Solution

42. 4.42
Cont’d..
Example:-DeterminetheA=B,A>BandA<Boutputsforthe
inputnumbersshownonthecomparatorcircuit?
Solution
ThenumberAisgreaterthanB,A>Boutputishighandthe
otheroutputarelow

43. 4.43
Designing Comparators Functionally
Onebitcomparator

44. 4.44
Cont’d..
Designacomparatorfor2bitbinarynumbersA
(A1A0)andB(B1B0)wedothefollowingsteps:
Fora2-bitcomparatorwehavefourinputsA1A0andB1B0and
threeoutput
1.E(is1iftwonumbersareequal)
2.G(is1whenA>B)and
3.L(is1whenA<B)
Thecircuit,forcomparingtwon-Bitnumbers,has2ninputs&
2
2n
entriesinthetruthtable.
For2-Bitnumbers,4-inputs&16-rowsinthetruthtable.

45. 4.45
Cont’d..
TruthTableof2-BitMagnitudeComparator

46. 4.46
Cont’d..

47. 4.47
Cont’d..

48. 4.48
Cont’d..

49. 4.49
Cont’d..

50. 4.50
Combined

51. 4.51
Decoder
Adecoderisacombinationallogiccircuitthatacceptsasetof
inputsthatrepresentsabinarynumberandactivatesonlythe
outputthatcorrespondstotheinputnumber.
Initsgeneralform,adecoderhasninputlinestohandlenbits
andformoneto2
n
outputlinestoindicatethepresenceofone
ormoren-bitcombinations.
Thedecoderpresentedherearecalledn-to-mlinedecoders
wherem≤2
n
.
ThegeneralBlockdiagramofaDecodercircuit

52. 4.52
Cont’d..
#Thereare2
N
possibleinputcombinations,fromA
0toA
N1.
ForeachoftheseinputcombinationsonlyoneoftheMoutputs
willbeactiveHIGH(1),alltheotheroutputsareLOW(0).

53. 4.53
Cont’d..
Thebasicbinaryfunction
Ifanactive-LOWoutput(74138,oneoftheoutputwilllowand
therestwillbehigh)isrequiredforeachdecodednumber,the
entiredecodercanbeimplementedwith
1.NANDgates
2.Inverters
Ifanactive-HIGHoutput(74139,oneoftheoutputwillhigh
andtherestwillbelow)isrequiredforeachdecodednumber,
theentiredecodercanbeimplementedwith
•ANDgates
•Inverters

54. 4.54
Cont’d..
Example:1Decodinglogicforthebinarycode1001withan
active-HIGHoutput.
Solution

55. 4.55
Decoder with Enable Line
Decodersusuallyhaveanenableline,
Enablingpermitsaninputsignaltopassthroughtoanoutput
Disablingblocksaninputsignalfrompassingthroughtoan
output,replacingitwithafixedvalue.
Ifenable=0,decoderisoff.Itmeansalloutputlinesare
zero
Ifenable=1,decoderisonanddependingoninput,the
correspondingoutputlineis1,allotherlinesare0

56. 4.56
Cont’d..
Example.2:2-to-4linedecoder(withenableinput)-active
Lowoutput
Solution

57. 4.57
Cont’d..
Forexampleifthenumberofinputisn=3thenumberofoutput
linescanbem=2
3
.Itisalsoknownas1of8becauseoneoutput
lineisselectedoutof8availablelines:
Thedecoderpresentedherearecalledn-to-mlinedecoders
wherem≤2
n

58. 4.58
Cont’d..
Theirpurposeistogeneratethe2
n
orlessmintermsofninput
variables.
Considerthe3-to-8linedecoder,thethreeinputsare
decodedintoeightoutputs,eachoutputrepresentingoneofthe
mintermsofthe3-inputvariables.

59. 4.59
Cont’d..
Thetruthtableofa3-to-8linedecoder

60. 4.60
Cont’d..

61. 4.61
Cont’d…
Thisbinaryportaddressisdecodedandtheappropriate
decoderoutputisactivatedtoenabletheI/Oport.

62. 4.62
BCD-to-Decimal Decoder
Theelementsofinformationinthiscasearethetendecimal
digitsrepresentedbytheBCDcode.
Thecodeitselfhasfourbits
Thiswillgivesa4-to-10lineBCD–to-decimaldecoder.

63. 4.63
Cont’d..
ThetruthtableofBCD–to-Decimaldecoder
inputs outputs
A3A2A1A0D0D1D2D3D4D5D6D7D8D9
00001000000000
00010100000000
00100010000000
00110001000000
01000000100000
01010000010000
01100000001000
01110000000100
10000000000010
10010000000001

64. 4.64
Cont’d..

65. 4.65
BCD-7segment decoders/drivers
Mostdigitalequipmenthassomemeansfordisplayinginformation
inaformthatcanbeunderstoodbytheuser.Thisinformationis
oftennumericaldatabutalsobealphanumeric.
Oneofthesimplestandmostpopularmethodsfordisplaying
numericaldigitsusesa7-segmentconfigurationtoformdigital
characters0to9andsometimesthehexcharactersAtoF

66. 4.66
Cont’d..
Onecommonarrangementsuseslight-emittingdiodes(LED's)for
eachsegment.BycontrollingthecurrentthrougheachLED,some
segmentswillbelightandotherswillbedarksothatdesired
characterpatternwillbegenerated.
Therearetwotypesof7segmentLEDdisplays;
A)common-anode
B)commoncathode

67. 4.67
Cont’d..
Incommonanode,theanodeofalloftheLEDsaretiedtogetherto
positiveofthepowersupply(V
cc)asshown

68. 4.68
Cont’d..

69. 4.69
Cont’d..
Example:1

70. 4.70
Cont’d..

71. 4.71
Cont’d..
Incommoncathode,thecathodeofalloftheLEDsaretiedtogether
topositiveofthepowersupply(V
cc)asshown

72. 4.72
Cont’d..

73. 4.73
Cont’d..

74. 4.74
Cont’d..

75. 4.75
Cont’d..
a = A + B D + C + B' D'
b = C' D' + C D + B'
c = B + C' + D
d = B' D' + C D' + B C' D + B' C + A
e = B' D' + C D’
f = A + C' D' + B D' + B C'
g = A + C D' + B C' + B' C

76. 4.76
Cont’d..

77. 4.77
Cont’d..

78. 4.78
Cont’d..
Example.1.DesignandimplementalogicdiagramforaBoolean
functiongivenbyatruthtablebelowusinga3-to-8decoder
Truthtable:
Solution
Minterms:
F=m(3,5,6,7)
Implementationusingdecoder:
A B C F
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
0
1
2
3
4
5
6
7
A
B
C
2
1
0
F
Indicate MSB, LSB

79. 4.79
Cont’d..
Example.2.CanyoudesignandimplementaBooleanFunctiongiven
belowusinga2-to-4decoderwithenableinputandanOR
gate?
Solution
Yes,Usinga2-to-4decoderwithenableinputandanORgate:
F=C(AB+A’B’)
F=C(AB+A’B’) = ABC+ A’B’C
EN

80. 4.80
Cont’d..
Example.3.a7-segmentdecoderdrivesthedisplayinfigure
below.Ifthewaveformsgivenbelowareappliedasinput,
determinethesequenceofdigitsthatappearsonthedisplay
?
Solution

81. 4.81
Encoder
Anencoderisacombinationallogiccircuitthatessentially
performsa‘’reverse’’processofdecoderfunction.
Encoderscanencodevarioussymbolsandalphabetic
characters.
Theprocessofconvertingfromfamiliarsymbolsornumber
toacodedformatiscalledencoding.
Anencoderacceptsanactivelevelononeofitsinputs
representingadigit,suchasadecimaloroctalandconverts
ittoacodedoutput,suchasBCDorBinary

82. 4.82
Cont’d..

83. 4.83
Decimal-to-BCD encoder
Adecimal-to-BCDencoder
•Inputs:10bitscorrespondingtodecimaldigits0
through9,(D
0,…,D
9)
•Outputs:4bitswithBCDcodes
•Function:IfinputbitDiisa1,thentheoutput(A
3,A
2,
A
1,A
0)istheBCDcodefori,

84. 4.84
Cont’d..

85. 4.85
Cont’d..
A3=D8+D9
A2=D4+D5+D6+D7
A1=D2+D3+D6+D7
A0=D1+D3+D5+D7+D9
The Boolean Equation can be :-

86. 4.86
Multiplexer & Multiplexer tree
Itisacombinationalcircuitthatselectsbinaryinformation
fromoneoftheinputlinesanddirectsittoasingleoutputline
Usuallythereare2
n
inputlinesandnselectionlineswhosebit
combinationsdeterminewhichinputlineisselected
Dependinguponthedigitalcodeappliedattheselectorinputs
oneoutofndatasourceisselectedandtransmittedtoasingle
outputchannel.

87. 4.87
Cont’d..

88. 4.88
Cont’d..
MUX Types
2-to-1 (1 select line)
4-to-1 (2 select lines)
8-to-1 (3 select lines)
16-to-1 (4 select lines)

89. 4.89
Typical Application of a MUX

90. 4.90
Cont’d..

91. 4.91
Cont’d..
Forexamplefor2-to-1multiplexer
1.ifselectionSiszerothenI
0hasthepathtooutputand
2.ifSisoneI
1hasthepathtooutput

92. 4.92
Cont’d..
Truthtablefor2-to-1multiplexer
For4-to-1multiplexer

93. 4.93
Cont’d..
Truthtablefor4-to-1multiplexer
Derivethelogicalexpressionfortheoutputintermsofthe
datainputandtheselectline
-TheoutputisequaltoDoonlyifS1=0andSo=0:Y=DoS1So
-TheoutputisequaltoD1onlyifS1=0andSo=1:Y=D1S1So
-TheoutputisequaltoD2onlyifS1=1andSo=0:Y=D2S1So
-TheoutputisequaltoD3onlyifS1=1andSo=1:Y=D3S1So

94. 4.94
Cont’d..
TheBooleanexpressionoftheinputselected(y)
Thelogicdiagramof4-to-1multiplexer

95. 4.95
Cont’d..
Example.1.thedatainputanddata-selectwaveformsinfigure
belowareappliedtothe4-to-1multiplexer.Determinetheoutput
waveforminrelationtotheinputs?
Solution

96. 4.96
Multiplexer tree
Pindiagramandlogicalsymbolforthe74LS1518-inputdata
selector/multiplexer.
ALOWontheEnableinputallowstheselectedinputdatatopass
throughtotheoutput.AHIGHontheEnableinputpreventsdata
fromgoingthroughtotheoutput;i.e,itdisablesthemultiplexer.

97. 4.97
Cont’d..
Example.1.Design16:1multiplexerusing8:1multiplexer?
Solution
Exercise.1.Design32:1multiplexerusing8:1and4:1multiplexer?

98. 4.98
Boolean function Implementation
Themultiplexingfunctioncanconvenientlybeusedasalogic
elementinthedesignofcombinationalcircuits.
Forusingthemultiplexerasalogicelement,eitherthetruth
tableoroneofthestandardformsoflogicalexpressionmustbe
available.
Thedesignprocedureisgivenbelow
1.Identifythedecimalnumbercorrespondingtoeachminterminthe
expression.
2.Theinputlinescorrespondingtothesenumbersaretobeconnectedto
logic1level.
3.Allotherinputlinesaretobeconnectedtologicolevel.
4.Theinputsaretobeappliedtoselectinputs

99. 4.99
Cont’d..
Example.1.Implementthelogicfunctionspecifiedintruthtable
belowbyusinga74LS1518-inputdataselector/multiplexer.
Comparethismethodwithadiscretelogicgateimplementation
SolutionY=Σm(1,3,5,6)

100. 4.100
Cont’d..

101. 4.101
Cont’d..
AnothermethodforimplementingBooleanfunctionisusing
multiplexer
FordoingthatassumeBooleanfunctionhasnvariables.We
havetousemultiplexerwithn-1selectionlinesand
1-firstn-1variablesoffunctionisusedfordatainput
2-theremainingsinglevariable(namedz)isusedfordata
input.
Eachdatainputcanbez,z’,1or0.Fromtruthtablewe
havetofindtherelationofFandztobeabletodesign
inputlines.

102. 4.102
Cont’d..
Example.1.:f(A,B,C,D)=∑(1,3,4,11,12,13,14,15)
Solution

103. 4.103
Cont’d..
Example.2.:Implementthelogicfunctionintruthtable
belowbyusing74LS1518-inputdataselector/multiplexer.
Comparethismethodwithadiscretelogicgate?

104. 4.104
Cont’d..
Solution

105. 4.105
Demultiplexer
Ademultiplexerbasicallyreversethemultiplexingfunction.It
takesdigitalinformationfromonelineanddistributesittoagiven
numberofoutputs.Forthisreasonthedemultiplexerisalsoknow
asdatadistributor.

106. 4.106
Cont’d..
DEMUX Types
1-to-2 (1 select line)
1-to-4 (2 select lines)
1-to-8 (3 select lines)
1-to-16 (4 select lines)

107. 4.107
Typical Application of a DEMUX

108. 4.108
Cont’d..
Forexamplefor1-to-4De-Multiplexer(DEMUX)

109. 4.109
Cont’d..
Example.1.Theserialdata-inputwaveform(datain)anddata-
selectinputs(SoandS1)areasshownbelow.Determinethedata-
outputwaveformsforthe1-to-4demultiplexer?
Solution