GatesandLogic: FromswitchestoTransistors, LogicGatesandLogicCircuits
HakimWeatherspoon CS3410,Spring2013 ComputerScience CornellUniversity
See:P&HAppendixC.2andC.3(Also,seeC.0andC.1)
GoalsforToday
FromSwitchestoLogicGatestoLogicCircuits LogicGates
Fromswitches TruthTables
LogicCircuits
IdentityLaws FromTruthTablestoCircuits(SumofProducts)
LogicCircuitMinimization
AlgebraicManipulations TruthTables(Karnaugh Maps)
Transistors(electronicswitch)
Aswitch
Actsasaconductor or insulator
Canbeusedtobuild amazingthings
TheBombeusedtobreaktheGerman EnigmamachineduringWorldWarII
BasicBuildingBlocks:SwitchestoLogicGates
+
Either(OR)
A
TruthTable
A B Light OFF OFF OFF ON
ON ON
OFF ON
Both(AND)
+
A B
Light
OFF OFF OFF ON ON ON OFF ON
BasicBuildingBlocks:SwitchestoLogicGates
Either(OR)
A
TruthTable
A B Light OFF OFF OFF ON ON ON OFF ON
OR
B
Both(AND)
A
A B Light
AND
B
OFF OFF OFF ON ON ON OFF ON
BasicBuildingBlocks:SwitchestoLogicGates
Either(OR)
A
TruthTable
A 0 0 1 1 B 0 1 0 1 Light
OR
B
0=OFF 1=ON
Both(AND)
A
A 0 0 1 1 B 0 1 0 1 Light
AND
B
BasicBuildingBlocks:SwitchestoLogicGates
OR
B
George Boole,(1815-1864)
Didyouknow?
AND
B
GeorgeBooleInventoroftheidea oflogicgates.Hewasbornin Lincoln,Englandandhewastheson ofashoemakerinalowclassfamily.
Takeaway
Binary(twosymbols:trueandfalse)isthebasisof LogicDesign
BuildingFunctions:LogicGates
NOT:
A Out
In
A B Out
AND: A
B
0 0 0 1 1 0 1 1
0 0 0 1
OR:
A B
A B Out 0 0 0 1 1 0 1 1 0 1 1 1
LogicGates
digitalcircuitthateitherallowsasignaltopassthroughitornot. Usedtobuildlogicfunctions Therearesevenbasiclogicgates: AND,OR,NOT, NAND (notAND),NOR (notOR),XOR,andXNOR (notXOR)[later]
BuildingFunctions:LogicGates
NOT:
A Out 1 0
In
0 1
A B Out
AND: A
B
0 0 0 1 1 0 1 1
0 0 0 1
OR:
A B
A B Out 0 0 0 1 1 0 1 1 0 1 1 1
LogicGates
digitalcircuitthateitherallowsasignaltopassthroughitornot. Usedtobuildlogicfunctions Therearesevenbasiclogicgates: AND,OR,NOT, NAND (notAND),NOR (notOR),XOR,andXNOR (notXOR)[later]
BuildingFunctions:LogicGates
NOT:
A Out 1 0 A B Out
In
0 1
A B Out
AND: A
B
0 0 0 1 1 0 1 1
0 0 0 1
NAND: NOR:
A B
0 0 0 1 1 0 1 1
1 1 1 0
OR:
A B
A B Out 0 0 0 1 1 0 1 1 0 1 1 1
A B
A B Out 0 0 0 1 1 0 1 1 1 0 0 0
LogicGates
digitalcircuitthateitherallowsasignaltopassthroughitornot. Usedtobuildlogicfunctions Therearesevenbasiclogicgates: AND,OR,NOT, NAND (notAND),NOR (notOR),XOR,andXNOR (notXOR)[later]
Activity#1.A:LogicGates
Fillinthetruthtable,giventhefollowingLogic CircuitmadefromLogicAND,OR,andNOTgates. Whatdoesthelogiccircuitdo?
Out
a b Out
Activity#1:LogicGates
Fillinthetruthtable,giventhefollowingLogic CircuitmadefromLogicAND,OR,andNOTgates. Whatdoesthelogiccircuitdo?
a 0 0 0 0 1 1 1 1
b 0 0 1 1 0 0 1 1
d 0 1 0 1 0 1 0 1
Out
a d Out
GoalsforToday
FromSwitchestoLogicGatestoLogicCircuits LogicGates
Fromswitches TruthTables
LogicCircuits
IdentityLaws FromTruthTablestoCircuits(SumofProducts)
LogicCircuitMinimization
AlgebraicManipulations TruthTables(Karnaugh Maps)
Transistors(electronicswitch)
NextGoal
GivenaLogicfunction,createaLogicCircuitthat implementstheLogicFunction and,withtheminimumnumberoflogicgates Fewergates:Acheaper($$$)circuit!
LogicGates
NOT: AND: OR: XOR:
A L B ogic Equations
A Out 1 0
In
0 1
A B Out
A B
0 0 0 1 1 0 1 1
0 0 0 1
A B
A B Out 0 0 0 1 1 0 1 1 0 1 1 1
A B Out 0 0 0 1 1 0 0 1 1
1 1=0 0 Constants:true=1,false Variables:a,b,out, Operators(above):AND,OR,NOT,etc.
LogicGates
NOT: AND: OR: XOR:
A L B ogic Equations
A Out 1 0 A B Out
In
0 1
A B Out
A B
0 0 0 1 1 0 1 1
0 0 0 1
NAND: NOR:
A B
0 0 0 1 1 0 1 1
1 1 1 0
A B
A B Out 0 0 0 1 1 0 1 1 0 1 1 1
A B
A B Out 0 0 0 1 1 0 1 0 0 0
XNOR:
A B
1 1
A B Out 0 0 0 1 1 0 0 1 1
A B Out 0 0 0 1 1 0 1 1 1 0 0 1
1 1=0 0 Constants:true=1,false Variables:a,b,out, Operators(above):AND,OR,NOT,etc.
LogicEquations
NOT:
out= =!a=a
AND: OR:
out=ab=a&b=a b out=a+b=a|b=a b out=a b=ab +b
XOR:
LogicEquations
Constants:true=1,false=0 Variables:a,b,out, Operators(above):AND,OR,NOT,etc.
LogicEquations
NOT:
out= =!a=a
AND: OR:
out=ab=a&b=a b out=a+b=a|b=a b out=a b=ab +b
NAND: NOR:
out=a b =!(a&b)= (a b) b =!(a|b)= (a b)
out=a
XOR:
XNOR:
out=a b =ab +ab
LogicEquations
Constants:true=1,false=0 Variables:a,b,out, Operators(above):AND,OR,NOT, . etc.
Identities
Identitiesusefulformanipulatinglogicequations
Foroptimization&easeofimplementation
a+0= a+1= a+=
a0= a1= a=
Identities
Identitiesusefulformanipulatinglogicequations
Foroptimization&easeofimplementation
= = a+ab = a(b+c)= =
LogicManipulation
functions:gatestruthtablesequations Example:(a+b)(a+c)=a+bc
a 0 0 0 0 1 1 1 1 b 0 0 1 1 0 0 1 1 c 0 1 0 1 0 1 0 1
Takeaway
Binary(twosymbols:trueandfalse)isthebasisof LogicDesign MorethanoneLogicCircuitcanimplementsame Logicfunction.UseAlgebra(Identities)orTruth Tablestoshowequivalence.
NextGoal
Howtostandardizeminimizinglogiccircuits?
LogicMinimization
Howtoimplementadesiredlogicfunction? a 0 0 0 0 1 1 1 1 b 0 0 1 1 0 0 1 1 c out 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0
LogicMinimization
Howtoimplementadesiredlogicfunction? a 0 0 0 0 1 1 1 1 b 0 0 1 1 0 0 1 1 c out minterm 1) Writeminterms 0 0 abc 2) sumofproducts: 1 1 abc ORofallmintermswhereout=1 0 0 abc 1 1 abc 0 0 abc 1 1 abc 0 0 abc 1 0 abc
KarnaughMaps
Howdoesonefindthemostefficientequation? Manipulatealgebraicallyuntil? UseKarnaughmaps(optimizevisually) Useasoftwareoptimizer Forlargecircuits Decomposition&reuseofbuildingblocks
MinimizationwithKarnaugh maps(1)
a 0 0 0 0 1 1 1 1
b 0 0 1 1 0 0 1 1
c 0 1 0 1 0 1 0 1
out 0 1 0 1 1 1 0 0
Sum of minterms yields?
out =
MinimizationwithKarnaugh maps(2)
a 0 0 0 0 1 1 1 1
b 0 0 1 1 0 0 1 1
c 0 1 0 1 0 1 0 1
out 0 1 0 1 1 1 0 0
Sum of minterms yields?
out =
Karnaugh maps identify which inputs are (ir)relevant to the output
1 1
ab 00 011110 0 1
0 1
0 1
0 0
MinimizationwithKarnaugh maps(2)
a 0 0 0 0 1 1 1 1
b 0 0 1 1 0 0 1 1
c 0 1 0 1 0 1 0 1
out 0 1 0 1 1 1 0 0
Sum of minterms yields?
out =
Karnaugh map minimization
Cover all 1s Group adjacent blocks of 2n 1s that yield a rectangular shape Encode the common features of the rectangle
out = ab + ac
ab 00 01 0 1 11 10
0 1
0 1
0 0
1 1
Karnaugh MinimizationTricks(1)
c ab 00 01 1110 0 1 c 0 1 ab 00 01 1110
0 0
1 0
1 1
1 0
Minterms can overlap
out =
1 0
1 0
1 1
1 0
Minterms can span 2, 4, 8 or more cells
out =
KarnaughMinimizationTricks(2)
ab cd 00 01 11 10 ab cd 00 01 11 10 00 011110 00 01 1110
0 1 1 0
0 0 0 0
0 0 0 0
0 1 1 0
Themapwrapsaround
out=
1 0 0 1
0 0 0 0
0 0 0 0
1 0 0 1
out=
KarnaughMinimizationTricks(3)
ab cd 00 01 11 10 ab cd 00 01 11 10 00 011110 00 011110
0 1 1 0
0 x x 0
0 x x 0
0 x 1 0
Dontcarevaluescanbe interpretedindividuallyin whateverwayisconvenient
assumeallxs=1 out=
1 0 0 1
0 x x 0
0 x x 0
x 0 0 1
assumemiddlexs=0 assume4th columnx=1 out=
Multiplexer
Amultiplexerselects betweenmultipleinputs
d
a 0 0 0 0 1 1 1 1 b 0 0 1 1 0 0 1 1 d 0 1 0 1 0 1 0 1 out
a b
out=a,ifd=0 out=b,ifd=1
Buildtruthtable Minimizediagram Derivelogicdiagram
Takeaway
Binary(twosymbols:trueandfalse)isthebasisof LogicDesign MorethanoneLogicCircuitcanimplementsame Logicfunction.UseAlgebra(Identities)orTruth Tablestoshowequivalence. Anylogicfunctioncanbeimplementedassumof products.Karnaugh Mapsminimizenumberofgates.
GoalsforToday
FromTransistorstoGatestoLogicCircuits LogicGates
Fromtransistors TruthTables
LogicCircuits
IdentityLaws FromTruthTablestoCircuits(SumofProducts)
LogicCircuitMinimization
AlgebraicManipulations TruthTables(Karnaugh Maps)
Transistors(electronicswitch)
NMOSandPMOSTransistors
NMOS Transistor
VD VG VD = 0V VG = VSupply VG = 0 V
PMOSTransistor
Vsupply Vsupply VS = Vsupply VG VG = VSupply
Vsupply
VG = 0 V VD = Vsupply Closedswitch WhenVG =0V
VS = 0 V Closedswitch WhenVG =Vsupply
VD
Connect source to drain when VG = Vsupply N-channel transistor
Connectsourcetodrain whenVG =0V Pchanneltransistor
VS:voltageatthesource VD:voltageatthedrain Vsupply:maxvoltage(akaalogical1) (ground):minvoltage(akaalogical0)
NMOSandPMOSTransistors
NMOS Transistor
D G D= 0 G= 1 G= 0 G
PMOSTransistor
Vsupply Vsupply S = Vsupply G= 1 G= 0
Vsupply
S = 0V Closedswitch WhenVG =Vsupply
D= 1 Closedswitch WhenVG =0V
Connect source to drain when gate = 1 N-channel transistor
Connectsourcetodrain whengate=0 Pchanneltransistor
VS:voltageatthesource VD:voltageatthedrain Vsupply:maxvoltage(akaalogical1) (ground):minvoltage(akaalogical0)
Inverter
Vdd =hi A out A=0
Function: NOT Called an inverter Symbol:
in out
Vss =gnd
A 0 1
Out 1 0
Useful for taking the inverse of an input
CMOS: complementary-symmetry metaloxide semiconductor
Truth table
NANDGate
Vdd A B out B Vdd
Function: NAND Symbol:
a b out
A 0 1 0 1
B out 0 1 0 1 1 1 1 0
Vss
NORGate
Vdd A B out A Vss B Vss
Function: NOR Symbol:
a b out
A 0 1 0 1
B out 0 1 0 0 1 0 1 0
BuildingFunctions(Revisited)
NOT: AND: OR:
NANDandNORareuniversal
CanimplementanyfunctionwithNANDorjustNORgates usefulformanufacturing
BuildingFunctions(Revisited)
NOT: AND: OR:
a
a b
a b
NANDandNORareuniversal
CanimplementanyfunctionwithNANDorjustNORgates usefulformanufacturing
LogicGates
Onecanbuygatesseparately
ex.74xxxseriesof integratedcircuits cost~$1perchip,mostly forpackagingandtesting
Cumbersome,butpossibleto builddevicesusinggatesput togethermanually
ThenandNow
http://www.theregister.co.uk/2010/02/03/intel_westmere_ep_preview/
Thefirsttransistor
An Intel Westmere
1.17 billion transistors 240 square millimeters Six processing cores
onaworkbenchat AT&TBellLabsin1947 Bardeen,Brattain,andShockley
Summary
Mostmoderndevicesaremadefrombillionsofon/off switchescalledtransistors
Wewillbuildaprocessorinthiscourse! Transistorsmadefromsemiconductormaterials:
MOSFET MetalOxideSemiconductorFieldEffectTransistor NMOS,PMOS NegativeMOSandPositiveMOS CMOS ComplimentaryMOSmadefromPMOSandNMOStransistors
Transistorsusedtomakelogicgatesandlogiccircuits
Wecannowimplementanylogiccircuit
Candoitefficiently,usingKarnaugh mapstofindtheminimal termsrequired CanuseeitherNANDorNORgatestoimplementthelogic circuit CanuseP andNtransistorstoimplementNANDorNORgates
BigPicture:Abstraction
Hidecomplexitythroughsimpleabstractions
Simplicity
Boxdiagramrepresentsinputsandoutputs
Complexity
HidesunderlyingP andNtransistorsandatomic interactions
Vdd in out a d
out
Vss
b a d b
in
out
out
