Gates and Logic:
From Transistors to Logic Gates and
Logic Circuits
Prof. Hakim Weatherspoon
CS 3410
Computer Science
Cornell University
The slides are the product of many rounds of teaching CS 3410 by
Professors Weatherspoon, Bala, Bracy, and Sirer.
Goals for Today
• From Switches to Logic Gates to Logic Circuits
• Logic Gates
From switches
Truth Tables
• Logic Circuits
Identity Laws
From Truth Tables to Circuits (Sum of Products)
• Logic Circuit Minimization
Algebraic Manipulations
Truth Tables (Karnaugh Maps)
• Transistors (electronic switch)
A switch
• Acts as a conductor or
insulator
• Can be used to build
amazing things…
The Bombe used to break the German
Enigma machine during World War II
Basic Building Blocks: Switches to Logic Gates
• Either (OR)
Truth Table
A A B Light
-
OR
OFF OFF
OFF ON
B ON OFF
ON ON
• Both (AND)
A - A B Light
OFF OFF
AND OFF ON
B ON OFF
ON ON
Basic Building Blocks: Switches to Logic Gates
• Either (OR)
Truth Table
A A B Light
-
OR 0 = OFF
0 0
0 1 1 = ON
B 1 0
1 1
• Both (AND)
A - A B Light
0 0
AND 0 1
B 1 0
1 1
Basic Building Blocks: Switches to Logic Gates
OR
B
George Boole,(1815-1864)
A • Did you know?
• George Boole Inventor of the idea
AND of logic gates. He was born in
B Lincoln, England and he was the son
of a shoemaker in a low class family.
Takeaway
• Binary (two symbols: true and false) is the basis
of Logic Design
Building Functions: Logic Gates
• NOT: A Out
A 0 1
1 0
• AND: A B Out A B Out
A
0 0
0 1
0
0
NAND: A
0 0
0 1
1
1
B 1 0 0 B 1 0 1
• OR: 1 1 1 1 1 0
A B Out NOR: A B Out
A A
0 0 0 0 0 1
B 0 1 1 B 0 1 0
1 0 1 1 0 0
1 1 1 1 1 0
• Logic Gates
digital circuit that either allows a signal to pass through it or not.
Used to build logic functions
There are seven basic logic gates:
AND, OR, NOT,
NAND (not AND), NOR (not OR), XOR, and XNOR (not XOR) [later]
Goals for Today
• From Switches to Logic Gates to Logic Circuits
• Logic Gates
From switches
Truth Tables
• Logic Circuits
Identity Laws
From Truth Tables to Circuits (Sum of Products)
• Logic Circuit Minimization
Algebraic Manipulations
Truth Tables (Karnaugh Maps)
• Transistors (electronic switch)
Next Goal
• Given a Logic function, create a Logic Circuit that
implements the Logic Function…
• …and, with the minimum number of logic gates
• Fewer gates: A cheaper ($$$) circuit!
Logic Gates
NOT:
A Out
0 1
A
1 0
A B Out A B Out
AND: A
0 0
0 1
0
0
NAND: A
0 0
0 1
1
1
B 1 0 0 B 1 0 1
1 1 1 1 1 0
OR: A B Out NOR: A B Out
A A
0 0 0 0 0 1
B 0 1 1 B 0 1 0
1 0 1 1 0 0
XOR: 1 1 1
XNOR:
1 1 0
A B Out A B Out
A 0 0 0 A 0 0 1
0 1 1 0 1 0
B B
1 0 1 1 0 0
1 1 0 1 1 1
Logic Implementation
• How to implement a desired logic function?
a b c out
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 0
Logic Implementation
• How to implement a desired logic function?
a b c out minterm 1) Write minterms
0 0 0 0 a b c 2) sum of products:
0 0 1 1 a b c • OR of all minterms where out=1
0 1 0 0 abc
0 1 1 1 abc
1 0 0 0 abc
1 0 1 1 abc
1 1 0 0 abc
1 1 1 0 abc
Logic Equations
• NOT:
out = ā = !a = ¬a
• AND: NAND:
out = a ∙ b = a & b = a ∧ b • out = a · b = !(a & b) = ¬ (a ∧ b)
• OR: NOR:
out = a + b = a | b = a ∨ b • out = a + b = !(a | b) = ¬ (a ∨ b)
• XOR: XNOR:
out = a ⊕ b = ab� + āb • out = a ⊕ b = ab + ab
• Logic Equations
Constants: true = 1, false = 0
Variables: a, b, out, …
Operators (above): AND, OR, NOT, etc.
• .
Identities
Identities useful for manipulating logic equations
– For optimization & ease of implementation
a+0=
a+1=
a+ā=
a∙0 =
a∙1 =
a∙ā =
Identities
Identities useful for manipulating logic equations
– For optimization & ease of implementation
(a + b) =
(a � b) =
a+ab =
a(b+c) =
a(b + c) =
Goals for Today
• From Switches to Logic Gates to Logic Circuits
• Logic Gates
From switches
Truth Tables
• Logic Circuits
From Truth Tables to Circuits (Sum of Products)
Identity Laws
• Logic Circuit Minimization – why?
Algebraic Manipulations
Truth Tables (Karnaugh Maps)
• Transistors (electronic switch)
Checking Equality w/Truth Tables
circuits ↔ truth tables ↔ equations
Example: (a+b)(a+c) = a + bc
a b c
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Takeaway
• Binary (two symbols: true and false) is the basis
of Logic Design
• More than one Logic Circuit can implement same
Logic function. Use Algebra (Identities) or Truth
Tables to show equivalence.
Goals for Today
• From Switches to Logic Gates to Logic Circuits
• Logic Gates
From switches
Truth Tables
• Logic Circuits
From Truth Tables to Circuits (Sum of Products)
Identity Laws
• Logic Circuit Minimization
Algebraic Manipulations
Truth Tables (Karnaugh Maps)
• Transistors (electronic switch)
Next Goal
• How to standardize minimizing logic circuits?
Karnaugh Maps
How does one find the most efficient equation?
– Manipulate algebraically until…?
– Use Karnaugh Maps (optimize visually)
– Use a software optimizer
For large circuits
– Decomposition & reuse of building blocks
Minimization with Karnaugh maps (1)
Sum of minterms yields
�
out = abc + a�bc + abc + abc
a b c out
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 0
Minimization with Karnaugh maps (2)
Sum of minterms yields
�
out = abc + a�bc + abc + abc
a b c out
0 0 0 0
0 0 1 1
0 1 0 0 Karnaugh map minimization
0 1 1 1
Cover all 1’s
1 0 0 1
1 0 1 1 Group adjacent blocks of 2n
1 1 0 0 1’s that yield a rectangular
1 1 1 0
shape
ab
c 00 01 11 10 Encode the common features
of the rectangle
0 0 0 0 1
out = ab� + a�c
1 1 1 0 1
Karnaugh Minimization Tricks (1)
ab
c 00 01 11 10
Minterms can overlap
0 0 1 1 1
out = b�c + a�c + ab
1 0 0 1 0
ab
c 00 01 11 10
0 1 1 1 1 Minterms can span 2, 4, 8
1 0 0 1 0
or more cells
out = c� + ab
Karnaugh Minimization Tricks (2)
ab
cd 00 01 11 10
00 0 0 0 0 • The map wraps around
01 1 0 0 1 out =
11 1 0 0 1
10
0 0 0 0
ab
cd 00 01 11 10
00 1 0 0 1 out =
01 0 0 0 0
11 0 0 0 0
10
1 0 0 1
Karnaugh Minimization Tricks (3)
ab
cd 00 01 11 10
00 0 0 0 0 • “Don’t care” values can be
01 1 x x x interpreted individually in
11 1 x x 1 whatever way is convenient
10
0 0 0 0 assume all x’s = 1
out =
ab
cd 00 01 11 10
assume middle x’s = 0
00 1 0 0 x assume 4th column x = 1
01 0 x x 0 out =
11 0 x x 0
10
1 0 0 1
Minimization with K-Maps
ab
c 00 01 11 10 (1) Circle the 1’s (see below)
0 0 0 0 1 (2) Each circle is a logical
component of the final equation
1 1 1 0 1
= ab� + a� c
Rules:
• Use fewest circles necessary to cover all 1’s
• Circles must cover only 1’s
• Circles span rectangles of size power of 2 (1, 2, 4, 8…)
• Circles should be as large as possible (all circles of 1?)
• Circles may wrap around edges of K-Map
• 1 may be circled multiple times if that means fewer
circles
29
Multiplexer
• A multiplexer selects
a between multiple inputs
b out = a, if d = 0
out = b, if d = 1
d
a b d out • Build truth table
• Minimize diagram
0 0 0
0 0 1
0 1 0 • Derive logic diagram
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Takeaway
• Binary (two symbols: true and false) is the basis of Logic
Design
• More than one Logic Circuit can implement same Logic
function. Use Algebra (Identities) or Truth Tables to
show equivalence.
• Any logic function can be implemented as “sum of
products”. Karnaugh Maps minimize number of gates.
Goals for Today
• From Transistors to Gates to Logic Circuits
• Logic Gates
From transistors
Truth Tables
• Logic Circuits
From Truth Tables to Circuits (Sum of Products)
Identity Laws
• Logic Circuit Minimization
Algebraic Manipulations
Truth Tables (Karnaugh Maps)
• Transistors (electronic switch)
Silicon Valley & the Semiconductor Industry
• Transistors:
• Youtube video “How does a transistor work”
https://www.youtube.com/watch?v=IcrBqCFLHIY
• Break: show some Transistor, Fab, Wafer photos
33
Transistors 101
Source Gate Drain Source Gate Drain
—
Insulator Insulator
- + + + + + + + + - - + + + + -
+ + channel created
+ + P-type
- + + + - - - + + + - - + + + - +- - + ++ -
P-type - P-type P-type - P-type
- N-type - - N-type -
- - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
Off On
N-Type Silicon: negative free-carriers (electrons)
P-Type Silicon: positive free-carriers (holes)
P-Transistor: negative charge on gate generates electric field that
creates a (+ charged) p-channel connecting source & drain
N-Transistor: works the opposite way
Metal-Oxide Semiconductor (Gate-Insulator-Silicon)
• Complementary MOS = CMOS technology uses both p- & n-type
transistors
34
CMOS Notation
N-type Off/Open On/Closed
0 1
gate
P-type
Off/Open On/Closed
1 0
gate
Gate input controls whether current can flow
between the other two terminals or not.
Hint: the “o” bubble of the p-type tells you that
this gate wants a 0 to be turned on
35
2-Transistor Combination: NOT
• Logic gates are constructed by combining transistors
in complementary arrangements
• Combine p&n transistors to make a NOT gate:
CMOS Inverter :
power source (1) power source (1) power source (1)
p-gate — p-gate + p-gate
closes stays open
0 1 1 0
input output
n-gate
n-gate n-gate
— + closes
stays open
ground (0) ground (0) ground (0)
36
Inverter
Vsupply (aka logic 1) Function: NOT
Symbol:
in out
in out
(ground is logic 0)
Truth Table:
In Out
0 1
1 0
37
NOR Gate
Vsupply
Function: NOR
A Symbol:
B a out
b
out
A B
Truth Table:
A B out
0 0 1
0 1 0
1 0 0
1 1 0
38
Building Functions (Revisited)
• NOT: a
a
• AND:
b
• OR: a
b
• NAND and NOR are universal
Can implement any function with NAND or just NOR gates
useful for manufacturing
Logic Gates
• One can buy gates
separately
ex. 74xxx series of
integrated circuits
cost ~$1 per chip, mostly
for packaging and testing
• Cumbersome, but possible
to build devices using
gates put together
manually
Then and Now
http://techguru3d.com/4th-gen-intel-haswell-processors-architecture-and-lineup/
• The first transistor • Intel Haswell
• One workbench at AT&T Bell Labs • 1.4 billion transistors, 22nm
• 1947 • 177 square millimeters
• Bardeen, Brattain, and Shockley • Four processing cores
41
https://en.wikipedia.org/wiki/Transistor_count
Then and Now
https://www.computershopper.com/computex-2015/performance-preview-desktop-broadwell-at-computex-2015
• The first transistor • Intel Broadwell
• One workbench at AT&T Bell Labs • 7.2 billion transistors, 14nm
• 1947 • 456 square millimeters
• Bardeen, Brattain, and Shockley • Up to 22 processing cores
42
https://en.wikipedia.org/wiki/Transistor_count
Big Picture: Abstraction
• Hide complexity through simple abstractions
Simplicity
• Box diagram represents inputs and outputs
Complexity
• Hides underlying NMOS- and PMOS-transistors and atomic
interactions
Vdd a
in out d out
Vss b
a
d out
in out 43
b
Summary
• Most modern devices made of billions of transistors
You will build a processor in this course!
Modern transistors made from semiconductor materials
Transistors used to make logic gates and logic circuits
• We can now implement any logic circuit
Use P- & N-transistors to implement NAND/NOR gates
Use NAND or NOR gates to implement the logic circuit
Efficiently: use K-maps to find required minimal terms
44
