Transcript Transistors and Logic II

Computer Organization and Design
Transistors & Logic - II
Montek Singh
Wed, Oct 16, 2013
Lecture 10
Today’s Topics
 Synthesis using standard gates
 Truth tables
 Universal gates: NAND and NOR
 Gates with more than 2 inputs
 Sum-of-Products
 DeMorgan’s Law
2
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
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:
(same idea holds for AND and OR gates)
A
B
tpd = 1
C
(latency)
And we want an N-input XOR:
A3
A4
AN
A2
A1
N ) -- WORST CASE.
tpd (latency)= 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 (“SOP”)


“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
Y  C B A  C BA  CBA  CBA
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
Let’s do some practice examples
On whiteboard
Next Class
 Arithmetic circuits