Topic 2

Basic Logic Gates

1
 Electronic Switch – Transistors
control
input
• Transistors are the basis of binary
digital circuits “off”

– Transistors operate at 2 values

source output
H / L or input
control
On / Off or input
“on”
1/0
source output
input
• Evolution of electronic switches
– 1930s: Relays
– 1940s: Vacuum tubes
– 1950s: Discrete transistor
– 1960s: Integrated circuits (ICs) discrete
• Initially just a few transistors on transistor
IC
relay vacuum tube
IC
• Then tens, thousands, millions...
2
 Moore’s Law
• IC capacity doubling about every 18 months
for several decades
– Known as “Moore’s Law” named after
Gordon Moore, co-founder of Intel
• Predicted in 1965 predicted that
components per IC would double roughly
every 18 months or so
– For a particular number of transistors, the
IC shrinks by half every 18 months
• Enables incredibly powerful computation
in incredibly tiny devices
– Today’s ICs hold billions of transistors
• The first Pentium processor (early 1990s)
had only 3 million

An Intel Pentium processor IC

having millions of transistors
3
 CMOS Transistor

• CMOS – Complementary Metal-Oxide-Semiconductor

• Transistors with CMOS technology
nMOS
AApositive
positive …attracts
...attracts electrons
electrons here,
here, 1 0
voltage here...
here… turning
turning the
the channel
channel gate
betweensource
between source and
and drain
drain
into a conductor.
into a conductor.

gate conducts does not

oxide ICpackage
package conduct
IC
source drain

pMOS
1 0
gate

(a) IC
IC

does not conducts

Silicon -- not quite a conductor or insulator: Semiconductor conduct

4
 AND Logic
0

X Y Z = XY
x y
0 0 0
Z
y
0 1 0
1 0 0
x
1 1 1
1
Truth Table
• Definition of AND operation
Z=X•Y means Z = 1 if and only if both X = 1 and Y = 1;

Variable AND operator

2-input AND gate
5
 Truth Table
• Truth table creates the relationship between the inputs and outputs
– Must include all the inputs to the device in the left columns
– Must include all the outputs of the device in the right columns
– The behavior of the circuit is implied by the table Inputs Outputs

I1 I1 I2 I3 O1 O2
O1
Digital 0 0 0 ? ?
Inputs I2 Outputs
Circuit 0 0 1 ? ?
O2
I3 0 1 0 ? ?
0 1 1 ? ?
Number of
combinations is 2N; 1 0 0 ? ?
N is the number of 1 0 1 ? ?
the inputs
1 1 0 ? ?
1 1 1 ? ?

6
 Example of Truth Table

a b F a b c F a b c d F
0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 1
1 0 0 1 0 0 0 1 0
1 1 0 1 1 0 0 1 1
1 0 0 0 1 0 0
(a)
1 0 1 0 1 0 1
1 1 0 0 1 1 0
1 1 1 0 1 1 1
1 0 0 0
(b) 1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
(c)

7
 OR Logic
0
X Y Z=X+Y
y
0 0 0
x 0 1 1
Z
1 0 1
x y
1 1 1
1 Truth Table
• Definition of OR operation
Z = X + Y means Z = 1 if either X=1 or Y=1, or both;

OR operator

2-input OR gate

8
 NOT Logic
1
X Z = X’
0 1
x Z
1 0

0 Truth Table
• Definition of NOT operation
Z = X’ or Z = X means Z = 0 if X = 1; Z = 1 if X = 0; Z is the complement of X

NOT operator

NOT gate/Inverter

9
 Logic Gates

• “Logic gates” are better digital circuit building blocks than

switches (transistors)
10
 Logics in Human Language

• Motion-in-dark example
– a: signal from motion sensor, b: signal from light sensor
– Human/programming language: Turn on lamp (F=1) if
motion sensed (a) and no light (not b)
– Logic Equation: F = a AND NOT(b) = ab’
– Logic circuit: implementation of equation using logic gates
11
 Example: Seat Belt Warning Light System
• Design circuit for warning
light
• Sensors
– s: seat belt fastened
– k: key inserted
– p: person in seat k Seat Belt Indicator

• Function description p w

– Light on if person in seat,

and seat belt not fastened, s
and key inserted
• Logic equation
w = p AND NOT(s) AND k
12
 Example: Implement Logic Equation with
Logic Gates
• Q: Implement the following equation with logic gates:
F = a AND NOT( b OR NOT(c) )

b
a
Class
F b
a
F
c
Derivation c

• Precedence of Logic Operations

NOT > AND > OR

13
 From Logic Equation to Logic Circuit

• There exists a correspondence between a Logic Equation and

its logic circuit.

Variables + Constant binary values + Logic operators  Logic Equation

Signals + Power Supplies + Logic gates  Logic Circuit

• Logic Circuit:
A net of logic gates.

14
 Logic Equation and Logic Circuit

• F = x OR (NOT y AND Z) = x + y’・z = x + y’z

F = x + y’z

output expression
of inputs

x
y’
y
Class y’z F = x + y’z

z
Derivation
15
 Build Truth Table
• F = x + y’z
x 0 F = 0 + 0’• 0

y
0 y’=1 Class
y’z=0 F=0 or =0+1•0
=0+0
z 0
Derivation =0

• Truth table x y z y’ y’z F

0 0 0 1 0 0
0 0 1 ? ? ?
0 1 0 ? ? ?
0 1 1 ? ? ?
1 0 0 ? ? ?
1 0 1 ? ? ?
1 1 0 ? ? ?
1 1 1 ? ? ?
16
 Build Truth Table
• F = x + y’z
x 0 F = 0 + 0’• 1
0 1 1 or =0+1•1
y 1 =0+1
z 1 =1

• Truth table x y z y’ y’z F

0 0 0 1 0 0
0 0 1 1 1 1
0 1 0 ? ? ?
0 1 1 ? ? ?
1 0 0 ? ? ?
1 0 1 ? ? ?
1 1 0 ? ? ?
1 1 1 ? ? ?
17
 Build Truth Table
• F = x + y’z
x 0 F = 0 + 1’• 0
1 0 0 or =0+0•0
y 0 =0+0
z 0 =0

• Truth table x y z y’ y’z F

0 0 0 1 0 0
0 0 1 1 1 1
0 1 0 0 0 0
0 1 1 ? ? ?
1 0 0 ? ? ?
1 0 1 ? ? ?
1 1 0 ? ? ?
1 1 1 ? ? ?
18
 Build Truth Table
• F = x + y’z
x 0 F = 0 + 1’• 1
1 0 0 or =0+0•1
y 0 =0+0
z 1 =0

• Truth table x y z y’ y’z F

0 0 0 1 0 0
0 0 1 1 1 1
0 1 0 0 0 0
0 1 1 0 0 0
1 0 0 ? ? ?
1 0 1 ? ? ?
1 1 0 ? ? ?
1 1 1 ? ? ?
19
 Build Truth Table
• F = x + y’z
x 1 F = 1 + 0’• 0
0 1 1 or =1+1•0
y 0 =1+0
z 0 =1

• Truth table x y z y’ y’z F

0 0 0 1 0 0
0 0 1 1 1 1
0 1 0 0 0 0
0 1 1 0 0 0
1 0 0 1 0 1
1 0 1 ? ? ?
1 1 0 ? ? ?
1 1 1 ? ? ?
20
 Build Truth Table
• F = x + y’z
x 1 F = 1 + 0’• 1
0 1 1 or =1+1•1
y 1 =1+1
z 1 =1

• Truth table x y z y’ y’z F

0 0 0 1 0 0
0 0 1 1 1 1
0 1 0 0 0 0
0 1 1 0 0 0
1 0 0 1 0 1
1 0 1 1 1 1
1 1 0 ? ? ?
1 1 1 ? ? ?
21
 Build Truth Table
• F = x + y’z
x 1 F = 1 + 1’• 0
1 0 1 or =1+0•0
y 0 =1+0
z 0 =1

• Truth table x y z y’ y’z F

0 0 0 1 0 0
0 0 1 1 1 1
0 1 0 0 0 0
0 1 1 0 0 0
1 0 0 1 0 1
1 0 1 1 1 1
1 1 0 0 0 1
1 1 1 ? ? ?
22
 Build Truth Table
• F = x + y’z
x 1 F = 1 + 1’• 1
1 0 1 or =1+0•1
y 0 =1+0
z 1 =1

• Truth table x y z y’ y’z F

0 0 0 1 0 0
0 0 1 1 1 1
0 1 0 0 0 0
0 1 1 0 0 0
1 0 0 1 0 1
1 0 1 1 1 1
1 1 0 0 0 1
1 1 1 0 0 1
23
 Build A Truth Table: Another Approach
a b F a b c F a b c d F
0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 1
1 0 0 1 0 0 0 1 0
1 1 0 1 1 0 0 1 1
1 0 0 0 1 0 0
(a)
1 0 1 0 1 0 1
1 1 0 0 1 1 0
1 1 1 0 1 1 1
1 0 0 0
(b) 1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1 a b c F
1 1 1 0 0 0 0 0
• Q: Use truth table to 1 1 1 1 0 0 1 0

define function F(a,b,c) (c) Class

0
0
1
1
0
1
0
0

that is 1 only when abc is Derivation

1 0 0 0
1 0 1 1
5 or greater in binary 1 1 0 1
1 1 1 1
24
 Representations of I/O Relationship:
Equation, Truth Table, & Circuit
• Another example: G = x’y’z + x’yz + xy’

x y z G
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

Gate Implementation Truth Table

25
Timing Diagram: Another Representations of
I/O Relationship
• Timing diagram of one signal shows the response to
changes on a signal in voltage levels with time

X 0 1 1 0 0

26
 Timing Diagrams for Gates

xy F
0 0 0
X 0 1 1 0 0
0 1 0
1 0 0
1 1 1 Y 0 0 1 1 0

x+y F Class
0 0
0 1
0
1
X•Y Derivation
0 0 1 0 0

1 0 1
X+Y 0 1 1 1 0
1 1 1

x F
0 1 X’ 1 0 0 1 1
1 0

27
 More Gates
1 1
NAND NOR XOR XNOR NAND NOR
x x x
F F x y
y y
F y
x y F x y F x y F x y F x F
0 0 1 0 0 1 0 0 0 0 0 1
0 1 1 0 1 0 0 1 1 0 1 0 x y
y
1 0 1 1 0 0 1 0 1 1 0 0
1 1 0 1 1 0 1 1 0 1 1 1 0 0

• NAND: Opposite of AND (“NOT AND”) • AND in CMOS: NAND with NOT
• NOR: Opposite of OR (“NOT OR”)
• OR in CMOS: NOR with NOT
• XOR (): outputs 1 when inputs have odd
number of 1’s • So NAND/NOR more common
• XNOR: Opposite of XOR (“NOT XOR”)

28
 Recall Overflow Detection Method 2
• Simpler method: Detect difference between carry-in to sign bit and carry-
out from sign bit
• overflow = c4  c3 (overflow = 1, if c4 ≠ c3)

0 1 1 1 1 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 0 0 0

+ 0 0 0 1 + 1 0 0 0 + 0 1 1 1

1 0 0 0 0 1 1 1 1 1 1 1
overflow overflow no overflow
(a) (b) (c)

29
 Gates with Multiple Inputs
• AND and OR gates may have more than two inputs
• Three-input AND gate responds with logic 1 output if and only if all
three inputs are logic 1 (may be generalized)
• Four-input OR gate responds with logic 1 if any input is logic 1; its
output becomes 0 if and only if all inputs are logic 0 (may be
generalized)

A
A
B
B F = ABC Z = A+B+C+D
C
C C

3-input AND gate 4-input OR gate

30
 Some Circuit Drawing Conventions

no yes
x
F
y

no yes

ok

not ok

31
 Integrated Circuit
• Integrated Circuit (IC) – chip
– Contains logic components and/or devices for constructing digital circuits
• Integration Levels
– Small-Scale Integration (SSI)
• Fewer than 10 gates
– Medium-Scale Integration (MSI)
• 10 to 1000 gates
– Large-Scale Integration (LSI)
• Thousands of gates
– Very Large-Scale Integration (VLSI)
• Millions of gates
– Ultra Large-Scale Integration (ULSI)
• Billions of gates

– … https://www.sparkpi.co.uk/evolution-of-the-integrated-
circuit-board-infographic-2/
32
 Integrated Circuit

• TTL – Transistor-Transistor Logic

• ECL – Emitter-Coupled Logic
• MOS – Metal-Oxide Semiconductor
• CMOS – Complementary MOS

Chip placed on breadboard

33