Transcript Transistors and Logic Gates

Chapter 3
Digital Logic
Structures
Basic Logic Gates
3-2
Basic Relations of Boolean Algebra
+ = OR
= AND
‘ = NOT
x+0=x
x+1=1
x+x=x
x + x’ = 1
x + y = y + x (Commutative)
x + (y+z) = (x+y)+z (Associative)
x(y+z’) = xy + xz (Distributive)
(x+y)’ = x’ y’ (DeMorgan)
(x’)’ = x
x0 = 0
x1 = x
xx = x
xx’ = 0
xy = yx (Commutative)
x(yz) = (xy)z (Associative)
x+yz = (x+y)(x+z) (Distributive)
(xy)’ = x’+y’ (DeMorgan)
3-3
DeMorgan’s Law
not(A and B) = (not A) or (not B)
A and B  A or B
=
not(A or B) = (not A) and (not B)
A or B  A and B
=
3-4
More than 2 Inputs?
AND/OR can take any number of inputs.
• AND = 1 if all inputs are 1.
• OR = 1 if any input is 1.
• Similar for NAND/NOR.
Can implement with multiple two-input gates,
or with single CMOS circuit.
3-5
Summary
MOS transistors are used as switches to implement
logic functions.
• n-type: connect to GND, turn on (with 1) to pull down to 0
• p-type: connect to +2.9V, turn on (with 0) to pull up to 1
Basic gates: NOT, NOR, NAND
• Logic functions are usually expressed with AND, OR, and NOT
DeMorgan's Law
• Convert AND to OR (and vice versa)
by inverting inputs and output
3-6
Building Functions from Logic Gates
Combinational Logic Circuit
• output depends only on the current inputs
• stateless
Sequential Logic Circuit
• output depends on the sequence of inputs (past and present)
• stores information (state) from past inputs
We'll first look at some useful combinational circuits,
then show how to use sequential circuits to store
information.
3-7
Decoder
n inputs, 2n outputs
• exactly one output is 1 for each possible input pattern
2-bit
decoder
3-8
Multiplexer (MUX)
n-bit selector and 2n inputs, one output
• output equals one of the inputs, depending on selector
4-to-1 MUX
3-9
Mux (cont.)
A
B
C
D
S0
S1
• In general, a MUX has
2n data inputs
n select (or control) lines
and 1 output.
• It behaves like a channel selector.
Out  A. S0 . S1  B. S0 .S1  C.S0 . S1  D.S0 .S1
A
B
C
Ou
t
D
S[1:0]
A 4-to-1 MUX:
Out takes the value of A,B, C or D
depending on the value of S (00, 01, 10, 11)
Out
3-10
Adder
Half Adder
• 2 inputs
• 2 outputs: sum and carry
ai
0
0
1
1
bi
0
1
0
1
ci+1
0
0
0
1
si
0
1
1
0
Half-adder truth table
Full Adder
•
•
•
•
•
performs the addition in column i
3 inputs: ai, bi and ci
2 outputs: si and ci+1
ci is the carry in from bit position i-1
ci+1 is the carry out to bit position i+1
a n 1 a n 2 ... a1 a 0
 b n 1 b n 2 ... b1 b 0
 cn 1 cn 2 ... c1 0
s n 1 s n 2 ... s1 s 0
3-11
Full Adder
Add two bits and carry-in,
produce one-bit sum and carry-out.
A B Cin S Cout
0 0
0
0
0
0 0
1
1
0
0 1
0
1
0
0 1
1
0
1
1 0
0
1
0
1 0
1
0
1
1 1
0
0
1
1 1
1
1
1
3-12
Full Adder (cont)
si  ai  bi  ci
ci 1  ai .bi  ci .( ai  bi )
where
 is exclusive OR
. is the AND operation
 is the OR operation
- verify that this corresponds to the gate-level implementation.
3-13
Four-bit Adder
1010
0101
+ 1101
10010
Cin
A
B
S
3-14
Logical Completeness
Can implement ANY truth table with AND, OR, NOT.
A
B
C
D
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
0
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
0
1. AND combinations
that yield a "1" in the
truth table.
2. OR the results
of the AND gates.
3-15