Transcript Transistors and Logic

Computer Organization and Design
Transistors & Logic - II
Montek Singh
Wed, Oct 17, 2012
Lecture 11
Today’s Topics
 Implementing digital logic
 transistor-level circuits
 gate-level circuits
2
From Transistors… to Gates!
 Logic Gate recipe:
 use complementary arrangements of PFETs and NFETs
 called CMOS (“complementary metal-oxide semiconductor”)
 at any time: either “pullup” active, or “pulldown”, never
both!
VDD
We’ll use
p-type here
pullup: make this connection
when VIN is near 0 so that VOUT = VDD
VIN
VOUT
pulldown: make this connection
when VIN is near VDD so that VOUT = 0
Gnd
and, n-type
here
CMOS Inverter
“0”
“1”
Vout
Valid “1”
Vin
Vout
Invalid
“1”
Valid “0”
A
inverter
Y
Vin
Only a narrow
range of input
voltages result in
“invalid” output
values. (This
diagram is greatly
exaggerated)
“0”
CMOS Complements
A
A
conducts when A is high
A
conducts when A is low
A
Series N connections:
B
B
Parallel P connections:
conducts when A is high
and B is high: A.B
conducts when A is low
or B is low: A+B = A.B
A
A
B
Parallel N connections:
conducts when A is high
or B is high: A+B
B
Series P connections:
conducts when A is low
and B is low: A.B = A+B
A Two Input Logic Gate
What function does
this gate compute?
A
B
0
0
1
1
A B C
0
1
0
1
Here’s Another…
B
A
What function does
this gate compute?
0
0
1
1
A B C
0
1
0
1
CMOS Gates Like to Invert
Observation: CMOS gates tend
to be inverting!
 One or more “0” inputs are
B
necessary to generate a “1”
output
 One or more “1” inputs are
necessary to generate a “0”
output
 Why?
A
General CMOS Gate Recipe
Step 1. Figure out pulldown network
that does what you want (i.e the set of
conditions where the output is ‘0’)
e.g., F = A*(B+C)
Step 2. Walk the hierarchy replacing
nfets with pfets, series subnets with
parallel subnets, and parallel subnets
with series subnets
Step 3. Combine pfet pullup network
from Step 2 with nfet pulldown
network from Step 1 to form fullycomplementary CMOS gate.
A
B
C
B
A
C
B
A
C
A
B
C
One Last Exercise
 Lets construct a gate to compute:
 F = A+BC = NOT(OR(A,AND(B,C)))
Vdd
A
 Step 1: Draw the pull-down network
 Step 2: The complementary pull-up
B
C
network
F
A
B
C
One Last Exercise
 Lets construct a gate to compute:
 F = A+BC = NOT(OR(A,AND(B,C)))
A
 Step 1: Draw the pull-down network
 Step 2: The complementary pull-up
network
 Step 3: Combine and Verify
Vdd
B
C
F
A B C F
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1
1
1
0
0
0
0
0
A
B
C
Now We’re Ready to Design Stuff!
 We need to start somewhere
 usually it’s the functional specification
A
B
C
If C is 1 then
copy B to Y,
otherwise copy
A to Y
Y
If you are like most engineers you’d rather
see a table, or formula than parse a logic
puzzle. The fact is, any combinational
function can be expressed as a table.
These “truth tables” are a concise
description of the combinational system’s
function. Conversely, any computation
performed by a combinational system can
expressed as a truth table.
Truth Table
C
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
A
0
1
0
1
0
1
0
1
Y
0
1
0
1
0
0
1
1
A Slight Diversion
 Are we sure we have all the gates we need?
 How many two-input gates are there?
AND
OR
AB Y
AB Y
00
01
10
11
00
01
10
11
0
0
0
1
0
1
1
1
NAND
NOR
AB Y
AB Y
00
01
10
11
00
01
10
11
1
1
1
0
1
0
0
0
 All of these have 2-inputs (no surprise)
 … 2 inputs have 4 possible values
2
 How many possible patterns for 4 outputs are there? ___
4
 Generalizing, for N inputs, there are 2(2^N) gates
There Are Only So Many Gates
 There are only 16 possible 2-input gates
 … some we know already, others are just silly
I
N
P
U
T
AB
Z
E
R
O
A A
N >
D B
00
01
10
11
0
0
0
0
0
0
0
1
0
0
1
0
A
B
>
A
0
0
1
1
0
1
0
0
B
X
O
R
N
O O
R R
X
N
O
R
0
1
0
1
0
1
1
0
0
1
1
1
1
0
0
1
1
0
0
0
N
N
O A O B
T <= T <=
‘B’ B ‘A’ A
N
A
N
D
O
N
E
1
0
1
0
1
1
1
0
1
1
1
1
1
0
1
1
1
1
0
0
1
1
0
1
How many of
these gates can
actually be
implemented
using a single
CMOS gate?
 Do we need all of these gates?
 Nope. We describe them all using AND, OR, and NOT.
We Can Make Most Gates Out of Others
B>A
A
B
XOR
AB Y
AB Y
00
01
10
11
00
01
10
11
0
1
0
0
y
0
1
1
0
A
B
Y
A
B
Y
 How many different gates do we really need?
One Will Do!
 NANDs and NORs are universal
 one can make any circuit out of just NANDs, or just NORs!
=
=
=
=
=
=
 Ah! But what if we want more than 2-inputs?
Gate Trees
Suppose we have some 2-input XOR gates:
A
B
tpd = 1
C
And we want an N-input XOR:
A3
A4
AN
A2
A1
N ) -- WORST CASE.
tpd = O( ___
Can we compute N-input XOR faster?
A
0
0
1
1
B
0
1
0
1
C
0
1
1
0
output = 1
iff number of 1s
in input is ODD
(“ODD PARITY”)
Gate Trees
A2
A1
A3
A4
AN
log2N
2
22
21
log N ) levels...
N-input TREE has O( ______
log N ) gate delays.
Signal propagation takes O( _______
Design Approach: Sum-of-Products
Three steps:
Write functional spec as a truth table
2. Write down a Boolean expression for
every ‘1’ in the output
1.
Y  C B A  C BA  CBA  CBA
3.
Wire up the gates!
 This approach will always give us
logic expressions in a particular
form:

SUM-OF-PRODUCTS


SUM actually means OR
PRODUCT actually means AND
Truth Table
C
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
A
0
1
0
1
0
1
0
1
Y
0
1
0
1
0
0
1
1
Straightforward Synthesis
 We can implement SUM-OF-PRODUCTS…
 …with just three levels of logic
 INVERTERS/AND/OR
A
B
C
A
B
C
A
B
C
A
B
C
Y
Notations
 Symbols and Boolean operators:
x × y, xy, x Ù y, AND(x, y), x AND y
x + y, x Ú y, OR(x, y), x OR y
x, x', Øx, NOT(x), INV(x)
x × y, x Ù y, xy, NAND(x, y), x NAND y
x + y, x Ú y, NOR(x, y), x NOR y
x Å y, XOR(x, y), x XOR y
x Å y, x Å y, XNOR(x, y), x XNOR y
DeMorgan’s Laws
 Change ANDs into ORs and vice-versa
x+y = x ×y
x×y = x + y
Useful Gate Structures
 NAND-NAND
AB=A+B
“Pushing Bubbles”
C
C
A
B
DeMorgan’s Laws
CA + AB + BC
Y

A
Y
B
xyz  x  y  z
AB=A+B
 NOR-NOR
C
C
A
Y
B

A
Y
B
x  y  xy
An Interesting 3-Input Gate: Multiplexer
 Based on C, select the A or B input to be copied to
the output Y.
A
B
C
Truth Table
If C is 1 then
copy B to Y,
otherwise copy
A to Y
C
0
0
0
0
1
1
1
1
Y
2-input Multiplexer
A
B
C
Y
A
“schematic”
diagram
B
C
0
1
Gate
symbol
B
0
0
1
1
0
0
1
1
A
0
1
0
1
0
1
0
1
Y
0
1
0
1
0
0
1
1
Multiplexer (MUX) Shortcuts
A 4-bit wide 2-input Mux
A 4-input Mux
(implemented as a tree)
I0
I1
0
0
1S
1
I2
I3
0
0
1S
1
0
0
1S
1
S0
S1
Y
A
B
C
D
S
0
1
2
3
Y
A0
B0
0
0
1S
1
Y0
A1
B1
0
0
1S
1
Y1
A2
B2
0
0
1S
1
A3
B3
0
0
1S
1
Y2
Y3
S
A0-3
B0-3
S
Y0-3
Next
 Arithmetic Circuits