Transcript Gates and Combinational Logic

Transistors and Logic - II
1)
2)
3)
A
Gates
Truth-table SOP Realizations
Multiplexer Logic
B
Comp 411 – Fall 2010
10/18/10
L09 – Transistors and Logic 1
CMOS Gates Like to Invert
OBSERVATION: CMOS gates tend to be
inverting!
Precisely, one or more “0” inputs are
necessary to generate a “1” output, and
one or more “1” inputs are necessary to
generate a “0” output. Why?
B
A
Comp 411 – Fall 2010
10/18/10
L09 – Transistors and Logic 2
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.
Comp 411 – Fall 2010
10/18/10
A
B
C
B
A
C
B
A
But isn’t it
hard to wire
it all up?
C
A
B
C
L09 – Transistors and Logic 3
One Last Exercise
Lets construct a gate to compute:
F = A+BC = NOT(OR(A,AND(B,C)))
Step 1: The pull-down network
Step 2: The complementary pull-up
network
Vdd
A
B
C
F
A
B
C
Comp 411 – Fall 2010
10/18/10
L09 – Transistors and Logic 4
One Last Exercise
Lets construct a gate to compute:
F = A+BC = NOT(OR(A,AND(B,C)))
A B C F
Step 1: The pull-down network
1 Step 2: The complementary pull-up B
1 1
network
A
0 1 Step 3: Combine and Verify
1 0
00
1 0
00
1 0
0 0 0
0 0
0 1
0 1
1 0
1 0
1 1
1 1
Comp 411 – Fall 2010
10/18/10
Vdd
A
C
F
B
C
L09 – Transistors and Logic 5
Now We’re Ready to Design Stuff!
We need to start somewhere -- usually it’s the functional
specification
Argh… I’m tired of word games
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.
Comp 411 – Fall 2010
10/18/10
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
L09 – Transistors and Logic 6
Where Do We Start?
We have a bag of gates.
We want to
build a computer.
What do we do?
Did I mention we
have gates?
A
B
We need
… a systematic approach for designing logic
Comp 411 – Fall 2010
10/18/10
L09 – Transistors and Logic 7
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
Hum… all of these have 2-inputs (no surprise)
… 2 inputs have 4 possible values
24
How many possible patterns for 4 outputs are there? ___
2N
Generalizing, there are 2 , N-input gates!
Comp 411 – Fall 2010
10/18/10
L09 – Transistors and Logic 8
There Are Only So Many Gates
How many of
these gates
can be
implemented
using a single
CMOS gate?
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
Do we need all of these gates?
Nope. After all, we describe them all using AND, OR, and NOT.
Comp 411 – Fall 2010
10/18/10
L09 – Transistors and Logic 9
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
0
1
1
0
A
B
Y
A
B
y
Y
How many different gates do we really need?
Comp 411 – Fall 2010
10/18/10
L09 – Transistors and Logic 10
One Will Do!
NANDs and NORs are universal
=
=
=
=
=
=
Ah!, but what if we want more than 2-inputs
Comp 411 – Fall 2010
10/18/10
L09 – Transistors and Logic 11
Stupid Gate Tricks
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
A
0
0
1
1
B
0
1
0
1
C
0
1
1
0
output = 1
iff number of 1s
input is ODD
(“ODD PARITY”)
N ) -- WORST CASE.
tpd = O( ___
Can we compute N-input XOR faster?
Comp 411 – Fall 2010
10/18/10
L09 – Transistors and Logic 12
I Think That I Shall Never See
a Gate Lovely as a ...
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( _______
Comp 411 – Fall 2010
10/18/10
L09 – Transistors and Logic 13
Here’s a Design Approach
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
-it’s systematic!
-it works!
-it’s easy!
-we get to go home!
Comp 411 – Fall 2010
1) Write out our functional spec as a
truth table
2) Write down a Boolean expression for
every ‘1’ in the output
Y  C B A  C BA  CBA  CBA
3) Wire up the gates, call it a day, and
go home!
This approach will always give us logic
expressions in a particular form:
SUM-OF-PRODUCTS
10/18/10
L09 – Transistors and Logic 14
Straightforward Synthesis
We can implement
SUM-OF-PRODUCTS
with just three levels of
logic.
A
B
C
A
B
C
INVERTERS/AND/OR
Y
A
B
C
A
B
C
Comp 411 – Fall 2010
10/18/10
L09 – Transistors and Logic 15
Useful Gate Structures
NAND-NAND
AB=A+B
“Pushing Bubbles”
C
C
A
Y
B
DeMorgan’s Laws
NOR-NOR

A
Y
B
xyz  x  y  z
AB=A+B
C
C
A
Y
B

A
Y
B
x  y  xy
Comp 411 – Fall 2010
10/18/10
L09 – Transistors and Logic 16
An Interesting 3-Input Gate
Based on C, select the A or B input to be
copied to the output Y.
Truth Table
A
B
C
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
Comp 411 – Fall 2010
0
B
1
C
10/18/10
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
Gate
symbol
L09 – Transistors and Logic 17
MUX Shortcuts
A 4-bit wide Mux
A 4-input Mux
(implemented as
a tree)
I0
I1
I2
I3
0
0
11S
0
0
11S
0
0
11S
S0
Y
A
B
C
D
S
0
1
2
3
Y
A0 0
0
B0 11
S
Y0
A1
B1
Y1
0
0
11S
A2 0
0
B2 11
S
Y2
Y0-3
S
A3
0
0
B3 1
1S
S1
A0-3
B0-3
Y3
S
Comp 411 – Fall 2010
10/18/10
L09 – Transistors and Logic 18
Mux Logic Synthesis
Consider implementation of some arbitrary
Boolean function, F(A,B)
... using a MULTIPLEXER
as the only circuit element:
A
0
0
0
0
1
1
1
1
Comp 411 – Fall 2010
Full-Adder
Carry Out Logic
0
0
0
1
0
1
1
1
A,B,Cin
B Cin Cout
0 0 0
0 1 0
1 0 0
1 1 1
0 0 0
0 1 1
1 0 1
1 1 1
10/18/10
0
1
2
3
4
5
6
7
Cout
L09 – Transistors and Logic 19