CSE205:DIGITALLOGIC

DESIGN
Dr.TanzimaHashem
AssistantProfessor
CSE,BUET
TEXTBOOK
DigitalDesign(4thEdition)
M.MorrisMano
MichaelD.Ciletti

OtherBooks:
DigitalFundamentalsbyThomasL.Floyd
DigitalDesignbyE.L.JohnsonandM.AKarim
DigitalLogicandComputerDesignbyM.
MorrisMano
DIGITALSYSTEMS
Whystudydigitallogicdesign
Todesignlargedigitalsystemswithaeasier
andmathematicallysoundabstraction

DigitalSystems
Example:digitalcameras,digitaltelephones,
digitaltelevision,digitalcomputers
Usedincommunication,businesstransactions,
trafficcontrol,spaceguidance,medical
treatment,weathermonitoring,theInternet
ANALOGVS.DIGITAL
AnalogSystem
Thephysicalquantitiesorsignalsmayvary
continuouslyoveraspecifiedrange.
Ex:voltageonawirecreatedbyamicrophone
Digitalsystem

Thephysicalquantitiesorsignalscanassume
onlydiscretevalues.
Ex:buttonpressedinakeypad
TECHNOLOGYCHANGE

Old New
TELEPHONETECHNOLOGY
CHANGE

Old New
DIGITALSYSTEMS
Advantages
Programmable
GreaterAccuracy
Cheapelectroniccircuits
BINARYLOGIC
Inadigitalsystem,allsignalstakeondiscrete
values.
Alsoreferredasstates

Mostmoderndigitalsystemsoperateon2discrete
states
Binarylogicsystem
Dealswithbinaryvariablesandasetof

logicaloperations
BINARYLOGIC
Werepresentthetwostatesofbinaryvariableas
Trueandfalse
1and0
HighandLow

Threebasiclogicoperations
AND:x.y=zorxy=z
OR:x+y=z
NOT:x=z
TRUTHTABLE
Atruthtableisatableofallpossiblecombinations
ofthevariablesshowingtherelationbetweenthe
valuesthatthevariablesmaytakeandtheresult
oftheoperation.
LOGICGATES
Logicgatesareelectroniccircuitsthatoperateon
oneormoreinputsignalstoproduceanOutput
signal.
LOGICGATES
GATEIMPLEMENTATIONOFA
FUNCTION
BOOLEANFUNCTION
ABooleanfunctioncanberepresentedinatruth
table.

f(x,y,z)=(x+yz)
LOGICGATES
NUMBERSYSTEMS
ConsistsofTWOThings:
ABASEorRADIXValue
ASETofDIGITS
Digitsaresymbolsrepresentingallvaluesless

thantheradixvalue.
ExampleistheCommonDecimalSystem:

RADIX(BASE)=10
DigitSet={0,1,2,3,4,5,6,7,8,9}
DECIMALNUMBERSYSTEMS
Consider:5032.21
(5032.21)10 5 (10) 3 0 (10) 2 3 (10)1 2 (10) 0 2 (10) 1 1 (10) 2
5000 0 30 2 0.2 0.01
OtherNotation:(5032.21)10

Ingeneral,anumberexpressedinabaser system
hascoefficientsmultipliedbypowersofr:

anrn+an1rn1++a1r1+a0+a1r-1+a2r2 ++amrm
OTHERNUMBERSYSTEMS
Binary
Radix=(2)10
DigitSet={0,1}
Octal

Radix=(8)10
DigitSet={0,1,2,3,4,5,6,7}
Hexadecimal

Radix=(16)10
DigitSet={0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}
BINARYNUMBERSYSTEMS
Binary
Radix=(2)10
DigitSet={0,1}

BinarytoDecimal:
(1101 .01) 2 1 23 1 2 2 0 21 1 20 0 2 1 1 2 2
(13.25)10
BINARYTODECIMAL:PRACTICE
a) 01102=? 610

b) 110102=? 2610

c) 01101012=? 5310

d) 110100112=? 21110
OCTALNUMBERSYSTEMS
Octal
Radix=(8)10
DigitSet={0,1,2,3,4,5,6,7}

OctaltoDecimal:
(15.2)8 1 81 5 80 2 81
(13.25)10
HEXADECIMALNUMBERSYSTEMS
Hexadecimal
Radix=(16)10
DigitSet={0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}

HexadecimaltoDecimal:
( D.4)16 D (16) 0 4 (16) 1
(13.25)10
 DECIMAL(INTEGER)TOBINARY
DividethenumberbytheBase(=2)
Taketheremainder(either0or1)asacoefficient

Takethequotientandrepeatthedivision

Example:(13)10
Quotient Remainder Coefficient
13/2=6 1a0=1
6 /2=3 0a1=0
3 /2=1 1a2=1
1 /2=0 1a3=1
Answer: (13)10 = (a3 a2 a1 a0)2 = (1101)2

MSB LSB
DECIMALTOBINARY:PRACTICE
a) 1310=? 11012

b) 2210=? 101102

c) 4310=? 1010112

d) 15810=? 100111102
 DECIMAL(FRACTION)TOBINARY
MultiplythenumberbytheBase(=2)
Taketheinteger(either0or1)asacoefficient

Taketheresultantfractionandrepeatthedivision

Example:(0.625)10
Integer Fraction Coefficient
0.625 *2=1 . 25 a1=1
0.25 *2=0 . 5a2=0
0.5 *2=1 . 0a3=1

Answer: (0.625)10 = (0.a-1 a-2 a-3)2 = (0.101)2

MSB LSB
DECIMALTOOCTALCONVERSION
Example:(175)10
Quotient Remainder Coefficient
175 /8=21 7a0=7
21 /8=2 5a1=5
2 /8=0 2a2=2
Answer: (175)10 = (a2 a1 a0)8 = (257)8

Example:(0.3125)10
Integer Fraction Coefficient
0.3125 *8=2 . 5 a1=2
0.5 *8=4 . 0a2=4
Answer: (0.3125)10 = (0.a-1 a-2 a-3)8 = (0.24)8
 BINARYOCTALCONVERSION
8=23 Octal Binary
Eachgroupof3bitsrepresentsan
0 000
octaldigit
Assume Zeros 1 001
Example:
2 010
( 1 0 1 1 0 . 0 1 )2
3 011

4 100

5 101
( 2 6 . 2 )8
6 110
Worksbothways(Binaryto 7 111
Octal&OctaltoBinary)
 BINARYHEXADECIMAL
CONVERSION
16=24 Hex Binary
Eachgroupof4bitsrepresentsa 0 0000
1 0001
hexadecimaldigit 2 0010
3 0011
Assume Zeros
Example: 4 0100
5 0101
6 0110
( 1 0 1 1 0 . 0 1 )2 7 0111
8 1000
9 1001
A 1010
B 1011
(1 6 . 4 )16 C 1100
D 1101
E 1110
Worksbothways(Binaryto F 1111
Hex&HextoBinary)
OCTALHEXADECIMAL
CONVERSION
ConverttoBinaryasanintermediatestep
Example:
( 2 6 . 2 )8

Assume Zeros Assume Zeros

( 0 1 0 1 1 0 . 0 1 0 )2

(1 6 . 4 )16

Worksbothways(OctaltoHex&HextoOctal)
BINARYADDITION

1 1 1 1 1 1
1 1 1 1 0 1 =61
+ 1 0 1 1 1 =23

1 0 1 0 1 0 0 =84

(2)10
BINARYSUBTRACTION

1 2 =(10)2
0 2 2 0 0 2
1 0 0 1 1 0 1 =77
1 0 1 1 1 =23

0 1 1 0 1 1 0 =54
BINARYMULTIPLICATION

1 0 1 1 1
x 1 0 1 0
0 0 0 0 0
1 0 1 1 1
0 0 0 0 0
1 0 1 1 1

1 1 1 0 0 1 1 0
COMPLEMENTS

Theyareusedtosimplifythesubtractionoperation
Twotypes(foreachbasersystem)

Diminishingradixcomplement(r1scomplement)
Radixcomplement(rscomplement)

ForndigitnumberN

(r 1) N
n
r1scomplement

r Nn rscomplement

33
DIMINISHEDRADIXCOMPLEMENT
Examplefor6digitdecimalnumbers:
9scomplementis(rn1)N=(1061)N=
999999N
9scomplementof546700:
999999546700=453299
Examplefor7digitbinarynumbers:

1scomplementis(rn1)N=(271)N=
1111111N
1scomplementof1011000:
11111111011000=0100111
RADIXCOMPLEMENT
Ther'scomplementofanndigitnumberNinbase
risdefinedasrnNforN0andas0forN=0.

Ther'scomplementcanalsobeobtainedbyadding
1tothe(r1)'scomplement,since
rnN=[(rn1)N]+1.

DecimalNumber:10nN
Example:10scomplementof246700is753300
RADIXCOMPLEMENT(BINARY
NUMBER)
Take1scomplementthenadd1
OR
Toggleallbitstotheleftofthefirst1fromthe
right
Example:

10110000 10110000
01001111
+1

01010000 01 010000
SUBTRACTIONWITHCOMPLEMENTS
MN
AddMtorscomplementofN
Sum=M+(rnN)=MN+rn

IfM>N,Sumwillhaveanendcarryrn,
discardit
IfM<N,Sumwillnothaveanendcarryand
Sum=rn(NM)(rscomplementofNM)

SoMN=(rscomplementofSum)
SUBTRACTIONWITHCOMPLEMENTS

654385623
65438
10scomplementof05623+94377
159815
Discardendcarry105100000
Answer59815
SUBTRACTIONWITHCOMPLEMENTS

562365438
05623
10scomplementof65438+34562
40185 Thereisno
endcarry.

Therefore,theansweris:
(10'scomplementof40185)=59815.

39
 SUBTRACTIONWITHCOMPLEMENTS

1011001010011111
10110010
2scomplementof10011111 +01100001
100010011
Discardendcarry2^8100000000
Answer00010011

BinarySystems 40
 SUBTRACTIONWITHCOMPLEMENTS

1001111110110010
10011111
2scomplementof10110010+01001110
11101101 Thereisno
endcarry.

Therefore,theansweris
YX=(2'scomplementof11101101)=
00010011.

BinarySystems 41
SUBTRACTIONWITHCOMPLEMENTS
Subtractionofunsignednumberscanalsobedone
bymeansofthe(r1)'scomplement.
Rememberthatthe(r1)'scomplementisone
lessthenther'scomplement.
1011001010011111
10110010
1scomplementof10011111 +01100000
100010010
Endaroundcarry+1
Answer00010011
 SUBTRACTIONWITHCOMPLEMENTS

1001111110110010
10011111
1scomplementof10110010+01001101
11101100 Thereisno
endcarry.

Therefore,theansweris
YX=(1'scomplementof11101100)=00010011.

BinarySystems 43
SIGNEDBINARYNUMBERS
Torepresentnegativeintegers,weneedanotation
fornegativevalues.
Itiscustomarytorepresentthesignwithabit
placedintheleftmostpositionofthenumbersince
binarydigits.
Theconventionistomakethesignbit0for
positiveand1fornegative.
Example:
SIGNEDBINARYNUMBERS
ARITHMETICADDITION
Discard

+500000101 511111011
+1100001011 +1100001011
+1600010000 +6100000110

+500000101 511111011
1111110101 1111110101
611111010 16111110000
Discard
SIGNEDBINARYNUMBERS
ARITHMETICSUBTRACTION
In2scomplementform:
1. Takethe2scomplementofthesubtrahend(includingthe
signbit)andaddittotheminuend(includingsignbit).
2. Acarryoutofsignbitpositionisdiscarded.

(A) ( B) (A) (B)

(6)(13)
Example: (1111101011110011)
(11111010+00001101)
00000111(+7)
BINARYCODE:BCDCODE
Anumberwithkdecimal
digitswillrequire4kbits
inBCD.

AdecimalnumberinBCD
isthesameasits
equivalentbinarynumber
onlywhenthenumberis
between0and9..
BINARYCODE:BCDCODE

BCDAddition
BINARYCODE:BCDCODE
Example:
Considertheadditionof184+576=760in
BCD:
BINARYCODE:BCDCODE

DecimalArithmetic:(+375)+(240)=+135
BINARYCODES
OTHERDECIMALCODES
BINARYCODE:GRAYCODE
BINARYCODES:ASCIICHARACTER
CODE
BINARYCODES:ASCIICHARACTER
CODE
AmericanStandardCodeforInformation
Interchange(RefertoTable1.7)
Apopularcodeusedtorepresentinformationsent
ascharacterbaseddata.
Ituses7bitstorepresent:

94Graphicprintingcharacters.
34Nonprintingcharacters.
Somenonprintingcharactersareusedfortext
format(e.g.BS=Backspace,CR=carriagereturn).
Othernonprintingcharactersareusedforrecord
markingandflowcontrol(e.g.STXandETXstart
andendtextareas).
BINARYCODES:ERRORDETECTING
CODE
Todetecterrorsindatacommunicationand
processing,aneighthbitissometimesaddedtothe
ASCIIcharactertoindicateitsparity.
Aparitybitisanextrabitincludedwithamessage
tomakethetotalnumberof1'seitherevenorodd.
Example:

Considerthefollowingtwocharactersandtheir
evenandoddparity: