Transcript Combinational circuit design - Computer Science and Engineering

Digital Design
Debdeep Mukhopadhyay
Associate Professor
Dept of Computer Science and Engineering
NYU Shanghai and IIT Kharagpur
1
Logical Design
2
Design with Basic Logic Gates
Logic gates: perform logical operations on input signals
Positive (negative) logic polarity: constant 1 (0) denotes a high voltage and
constant 0 a low (high) voltage
Synchronous circuits: driven by a clock that produces a train of equally
spaced pulses
Asynchronous circuits: are almost free-running and do not depend on a
clock; controlled by initiation and completion signals
Fanout: number of gate inputs driven by the output of a single gate
Fanin: bound on the number of inputs a gate can have
Propagation delay: time to propagate a signal through a gate
3
Analysis of Combinational Circuits
Circuit analysis: determine the Boolean function that describes the circuit
• Done by tracing the output of each gate, starting from circuit inputs and
continuing towards each circuit output
Example: a multi-level realization of a full binary adder
C B A
AB
AB + (A + B)C
C0
A+B
(A + B)C
(A + B + C)[AB + C(A + B)]
A+B+C
C0 = AB + (A + B)C
= AB + AC + BC
S = (A + B + C)[AB + (A + B)C]’ + ABC
= (A + B + C)(A’ + B’)(A’ + C’)(B’ + C’)
+ ABC
= AB’C’ + A’BC’ + A’B’C + ABC
= A +B +C
S
ABC
4
Simple Design Problems
Parallel parity-bit generator: produces output value 1 if and only if an odd
number of its inputs have value 1
z
z
y
x
xy
0
00
01
11
10
0
1
0
1
P
1
1
0
1
0
P = x’y’z + x’yz’ + xy’z’ + xyz
(a) Map.
(b) Implementation.
5
Simple Design Problems (Contd.)
Serial-to-parallel converter: distributes a sequence of binary digits on a
serial input to a set of different outputs, as specified by external
control signals
C2
C1
L1
L2
L3
x
L4
6
Logic Design with Integrated Circuits
Small scale integration (SSI): integrated circuit packages containing a few
gates; e.g., AND, OR, NOT, NAND, NOR, XOR
Medium scale integration (MSI): packages containing up to about 100
gates; e.g., code converters, adders
Large scale integration (LSI): packages containing thousands of gates;
arithmetic unit
Very large scale integration (VLSI): packages with millions of gates
7
Comparators
n-bit comparator: compares the magnitude of two numbers X and Y, and
has three outputs f1, f2, and f3
• f1 = 1 iff X > Y
• f2 = 1 iff X = Y
• f3 = 1 iff X < Y
x1x2
y1y2
y1 y2
x1 x2
00
01
11
10
00
2
1
1
1
01
3
2
1
1
11
3
3
2
3
10
3
3
1
2
2-bit comparator
f1
f2
f3
(b) Map for f1, f2, and f3.
(a) Block diagram.
x1
y1
f1 = x1x2y2’ + x2y1’y2’ + x1y1’
= (x1 + y1’)x2y2’ + x1y1’
f2 = x1’x2’y1’y2’ + x1’x2y1’y2 +
x1x2’y1y2’ + x1x2y1y2
= x1’y1’(x2’y2’ + x2y2) +
x1y1(x2’y2’ + x2y2)
= (x1’y1’ + x1y1)(x2’y2’ + x2y2)
f3 = x2’y1y2 + x1’x2’y2 + x1’y1
= x2’y2(y1 + x1’) + x1’y1
f1
x2
y2
x1
y1
8
(c) Circuit for f1.
4-bit/12-bit Comparators
Four-bit comparator: 11 inputs (four for X, four for Y, and three connected
to outputs f1, f2 and f3 of the preceding stage)
12-bit comparator:
x1 x4
f1
f2
f3
y1 y4
>
=
<
>
=
<
Inputs from
preceding
stage
(a) A 4-bit comparator.
x1 x4
f1
f2
f3
>
=
<
y1 y4
>
=
<
x5 x8
>
=
<
y5 y8
>
=
<
x9 x12
>
=
<
y9 y12
>
=
<
0
1
0
(b) A 12-bit comparator.
9
Data Selectors
Multiplexer: electronic switch that connects one of n inputs to the output
Data selector: application of multiplexer
• n data input lines, D0, D1, …, Dn-1
• m select digit inputs s0, s1, …, sm-1
• 1 output
Select number
s2
Data inputs
Select
number
s2 D7 D6 D5 D4 D3 D2 D1 D0
s1
s0
s1
s0
Data inputs
D7
D6
D5
D4
D3
D2
D1
D0 Enable
Enable
z
(a) Block diagram.
z
z
(b) Logic diagram.
10
Implementing Switching Functions with
Data Selectors
Data selectors: can implement arbitrary switching functions
Example: implementing two-variable functions
D1
D0
Enable
z = sD1 + s D0
s
If s = A, B = D0, and
B = D1, then z = A + B.
If s = A, D0 = 1, and
D1 = B , then z = A + B.
z
11
Implementing Switching Functions with
Data Selectors (Contd.)
To implement an n-variable function: a data selector with n-1 select inputs
and 2n-1 data inputs
Implementing three-variable functions:
z = s2’s1’D0 + s2’s1D1 + s2s1’D2 + s2s1D3
Example: s1 = A, s2 = B, D0 = C, D1 = 1, D2 = 0, D3 = C’
z = A’B’C + AB’ + ABC’
= AC’ + B’C
General case: Assign n-1 variables to the select inputs and last variable
and constants 0 and 1 to the data inputs such that desired
function results
12
Realize Y=AC’+B’C using MUX only
• Make A, B as select lines.
–
–
–
–
A,B=0,0 => Y=0
A,B=0,1 => Y=0
A,B=1,0 => Y=C’+C=1
A,B=1,1 => Y=C’
A
0
0
1
0
1
2
C’
3
B
Y
13
Priority Encoders
Priority encoder: n input lines and log2n output lines
• Input lines represent units that may request service
• When inputs pi and pj, such that i > j, request service simultaneously, line
pi has priority over line pj
• Encoder produces a binary output code indicating which of the input lines
requesting service has the highest priority
Example: Eight-input, three-output priority encoder
Enable
p0
p1
p2
p3
p4
Input lines
Outputs
p0 p1 p2 p3 p4 p5 p6 p7 z4 z2 z1
z1
Priority
encoder
p5
p6
p7
z2
z4
z0
(a) Block diagram.
1 0 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0
1 0 0 0
1 0 0
0
0
0
0
0
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 0 1 0 1
1 0 1 1 0
1 1 1 1
(b) Truth table.
z4 = p4p5’p6’p7’ + p5p6’p7’ + p6p7’ + p7 = p4 + p5 + p6 + p7
z2 = p2p3’p4’p5’p6’p7’ + p3p4’p5’p6’p7’ + p6p7’ + p7 = p2p4’p5’ + p3p4’p5’ + p6 + p7
z1 = p1p2’p3’p4’p5’p6’p7’ + p3p4’p5’p6’p7’ + p5p6’p7’ + p7 = p1p2’p4’p6’ + p3p4’p6’ + p5p6’ + p7
14
Priority Encoders (Contd.)
p0
p1
p2
z1
p3
p4
p5
z2
p6
z4
p7
Request
indicator
Enable
z0
(c) Logic diagram.
15
Decoders
Decoders with n inputs and 2n outputs: for any input combination, only one
output is 1
Useful for:
•
•
•
•
Routing input data to a specified output line, e.g., in addressing memory
Basic building blocks for implementing arbitrary switching functions
Code conversion
Data distribution
Example: 2-to-4- decoder
w
x
f0 = w x
f1 = w x
f2 = wx
16
f3 = wx
Decoders with Enable Line
Decoders with n inputs and 2n outputs: for any input combination, only one
output is 1
Useful for:
•
•
•
•
Routing input data to a specified output line, e.g., in addressing memory
Basic building blocks for implementing arbitrary switching functions
Code conversion
Data distribution
Example: 2-to-4- decoder
E
w
x
f0 = w x
f1 = w x
f2 = wx
17
f3 = wx
4-16 decoder using 3-8 decoder with
Enable
x
y
z
3-8 Decoder
D0-D7
E
w
3-8 Decoder
D8-D15
E
Usefulness of Enable to
expand circuits.
18
Decoders (Contd.)
Example: 4-to-16 decoder made of two 2-to-4 decoders and a gateswitching matrix
f0
f1
f2
f3
f4
f5
f6
f7
f8
f9
f10
f11
f12
f13
f14
f15
f0
f1
w
x
2-to-4
f2
f3
f1
f2
f0
f3
2-to-4
y z
19
Decimal Decoder
BCD-to-decimal: Decoder which converts from BCD to decimal. Example
w
z
y
x
of 4-9 Decoder.
w
x
y
z
Decimal
decoder
Enable
f0
f1
f2
f3
f4
f5
f6
f7
f8
f9
(a) Block diagram.
f0
wx
00 01 11
yz
00 f0 f4
10
f1
f8
f2
01 f1
f5
11 f3
f7
f3
10 f2
f6
f4
f9
(b) Map.
f5
f6
f7
f8
f9
Enable
(c) Logic diagram.
20
Decimal Decoder (Contd.)
Alternative Implementation using a partial-gate matrix:
y z
y z
y z
y z
w
x
f3
f2
f1
f0
f7
f6
f5
f4
f9
f8
w
x
w
x
21
Implementing Arbitrary Switching
Functions
Example: Realize a distinct minterm at each output
A
B
C
D
Enable
4-to-16
line
decoder
f0
f1
f5
f9
f = (1,5,9,15)
f15
22
Demultiplexers
Demultiplexers: decoder with1 data input and n address inputs
• Directs input to any one of the 2n outputs
Data input
n-bit address
Enable
C2
n
C1
2 outputs
Example: A 4-output demultiplexer
L1
L2
L3
23
x
L4
Seven-segment Display
Seven-segment display: BCD to seven-segment decoder and seven LEDs
x1
x2
x3
x4
A
B
C
BCD to
7-segment D
E
decoder
F
G
A
F
G
B
C
E
D
Seven-segment pattern and code:
A = x1 + x2’x4’ + x2x4 + x3x4
B = x2’ + x3’x4’ + x3x4
C = x2 + x3’ + x4
D = x2’x4’ + x2’x3 + x3x4’ + x2x3’x4
E = x2’x4’ + x3x4’
F = x1 + x2x3’ + x2x4’ + x3’x4’
G = x1 + x2’x3 + x2x3’ + x3x4’
24
Sine Generators
Combinational sine generators: for fast and repeated evaluation of sine
• Input: angle in radians converted to binary
• Output: sine in binary
Angle x
sin( x)
x1 x2 x3 x4 z1 z2 z3 z4
0
0
0
0
0
0
0
0
0
0
1
1
0 1
0 1
1
1
1
1
1
1
1
1
0 0 0 0
0 1 0 0
1 0 0 1
1 1 1 0
0 0 1 0
0 1 1 1
1 0 1 1
1 1 1 1
0 0 1 1
0
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
0 0
1 1
1 0
0 0
1 1
0 1
1 0
1 1
1 1
1 1 1
1 1 0
1 0 1
0 1 1
0 0 0
1 1 0
x1
x2
x3
x4
Sine
generator
(b) Block diagram.
z1
z2
z3
z4
sin( x)
z1 = x1’x2 + x1x2’ + x2x3’ + x1’x3x4
z2 = x1x2’ + x3x4’ + x1’x2x4
z3 = x3x4’ + x2x3 + x2x4’ +
x2’x3’x4 + x1x4’
z4 = x2’x3’x4 + x2x3’x4’ + x1x2’x3’ +
x1x3x4 + x1’x2x4
1 1 0 0
1 1 1 0 0 1 1
25
(a) Truth table.
NAND/NOR Circuits
Switching algebra: not directly applicable to NAND/NOR logic
A
B
(AB)
A
B
(c)
(a)
A
B
A+B
(b)
(A + B)
A
B
AB
(d)
NAND and NOR gate symbols
26
Analysis of NAND/NOR Networks
Example: circles (inversions) at both ends of a line cancel each other
A
B
C
5
3
4
D
E
F
T = A + (B + C )(D + EF )
B+C
[(B + C )(D + EF )]
2
D + EF
1
(EF )
(a) NAND-logic circuit.
A
B
C
T = A + (B + C )(D + EF )
B+C
(B + C )(D + EF )
D
E
F
D + EF
EF
(b) Logically equivalent AND-OR circuit.
27
Synthesis of NAND/NOR Networks
Example: Realize T = w(y+z) + xy’z’
y
z
w
1
2
[w(y + z)]
y+z
4
x
y
z
3
T = w(y + z) + xy z
(xy z )
(a) First realization.
y
z
1
y+z
w
2
[w(y + z)]
4
y
z
x
3
(y z )
yz
T = w(y + z) + xy z
3
(xy z )
(b) Realization with two-input gates.
28
Design of High-speed Adders
Full adder: performs binary addition of three binary digits
• Inputs: arguments A and B and carry-in C
• Outputs: sum S and carry-out C0
Example:
Truth table, block diagram and expressions:
A B C S C0
0
0
0
0
1
1
0
0
1
1
1
1
0
1
1
0
0
1
0
1
0
1
0
1
0
0
1
0
1
1
A
B
C
FA
S
S = A’B’C + A’BC’ + AB’C’ + ABC
= A +B +C
C0 = A’BC + ABC’ + AB’C + ABC
= AB + AC + BC
C0
(b) Block diagram.
1 0 1 0 1
1 0 0 1 0
(a) Truth table for S and C0.
29
Ripple-carry Adder
Ripple-carry adder: Stages of full adders
• Cf: forced carry
• C0(n-1): overflow carry
An-1Bn-1 C
n-1
FAn-1
C0(n-1)
A1 B1 C
1
A0 B0 C
f
FA1
FA0
C01
Sn-1
S1
S0
Si = Ai + Bi + Ci
C0i = AiBi + AiCi + BiCi
Time required:
• Time per full adder: 2 units
• Time for ripple-carry adder: 2n units
30
Carry-lookahead Adder
Carry-lookahead adder: several stages simultaneously examined and their
carries generated in parallel
• Generate signal Di = AiBi
• Propagate signal Ti = Ai + Bi
• Thus, C0i = Di + TiCi
To generate carries in parallel: convert recursive form to nonrecursive
C0i = Di + TiCi
Ci = C0(i-1)
C0i = Di + Ti(Di-1 + Ti-1Ci-1)
= Di + TiDi-1 + TiTi-1(Di-2 + Ti-2Ci-2)
= Di + TiDi-1 + TiTi-1Di-2 + TiTi-1Ti-2Ci-2
……..
...
C0i = Di + TiDi-1 + TiTi-1Di-2 + … + TiTi-1Ti-2…T0Cf
Thus, C0i = 1 if it has been generated in the ith stage or originated in a
preceding stage and propagated to all subsequent stages
31
Carry-lookahead Adder (Contd.)
Implementation of lookahead for the complete adder impractical:
• Divide the n stages into groups
• Full carry lookahead within group
• Ripple carry between groups
Example: Three-digit adder group with full carry lookahead
S2
S1
A2 B2
S0
A1 B1
D1
T1
D0
T1
T0
Cf
A0 B0
C01
SN2
A
B
C2
SN1
A
B
C1
SN0
A0
B0
Cg1 = C02
CN1
CN0
C01
C00
C00
(CN0)
(CN1)
Cf
CN2
Cf
T0
D0
D2
T2
D1
T2
T1
D0
T2
T1
T0
Cf
Cg1 = C02
(a) Block diagram of initial three-stage group
Time taken:
• 4 time units for Cg1
• Only 2 time units for Cg2 and other
group carries
Di = AiBi
Ti = Ai + Bi
(CN2)
(b) The carry networks
32
30-bit Adder
Example: divide n stages into groups of three stages
• Time taken: 4 + 2n/3 time units
• 50% additional hardware for a threefold speedup
Cg10
S29
S27
S5
S3
S2
S0
SN29
SN27
SN5
SN3
SN2
SN0
Bi
Ai
CN29
CN27
Bi
Cg9
Cg2
CN5
Bi
Ai
CN3
Cg1
CN2
Ai
Cf
CN0
33
Metal-oxide Semiconductor (MOS)
Transistors and Gates
Complementary metal-oxide semiconductor (CMOS): currently the
dominant technology
• Two types of transistors: nMOS and pMOS
a
b
a
x
(a) nMOS transistor
a
a
b
(d) pMOS transistor
x=1
b
a
a
x=0
x=1
x
b
b
(b) nMOS operation
a
x
x=0
(c) nMOS model
b
a
x
b
b
(e) pMOS operation
(f) pMOS model
x
a
a
b
a
x=0
x=1
b
a
x
b
b
x
(g) Complementary
switch
(h) Complementary
switch operation
(i) Complementary
switch model
34
Transmission Function of a Network
Network
x
y
a
a
y
x
x
a
Transmission function
b
Tab = x + y
b
Tab = xy
b
Tab = x
CMOS inverter and its transmission functions:
1 (Vdd)
1
x
x
f
f
x
0 (Vss)
0
35
CMOS NAND/NOR Gates
1 (Vdd)
1
x
x
y
f
f
x
y
y
0 (Vss)
0
(a) CMOS NAND gate and its transmission functions.
1
1 (Vdd)
x
x
y
y
f
f
x
0 (Vss)
y
0
(b) CMOS NOR gate and its transmission functions.
36
Analysis of Series-parallel Networks
Algebra of MOS networks: isomorphic to switching algebra
Example: Find the transmission function of the network and its
complementary switch based and complex gate CMOS implementations
w
y
z
y
z
a
x
w
x
b
w
y
z
1 (Vdd)
x
pMOS network
x
w
y
y
w
z
(a) Tab = x [(y z + z y)w + w + y + x z ].
a
1
w
y
z
x
w
x
y
Tab
b
z
w
x
(b) Tab = x (w + y + z ).
c
Tab
y
z
x
y
nMOS network
z
d
(c) Tcd = Tab = x + w yz.
z
Complementary
switch based
0 (Vss)
Complex
gate
37
Analysis of Non-series-parallel Networks
Obtaining the transmission function:
• Tie sets: minimal paths between two terminals
• Cut sets: minimal sets of branches, when open, ensure no transmission
between the two terminals
x
w
i
j
v
y
z
(a) Tie sets. Tij = wx + wvz + yvx + yz.
x
w
i
j
v
y
z
(b) Cut sets. Tij = (w + y)(w + v + z)(x + v + y)(x + z).
38
Synthesis of MOS Networks
Sneak paths in non-series-parallel networks: undesired paths that may
change the transmission function
• Occur because of bilateral nature of MOS transistors
Example: Design a minimal network with BCD inputs that produces a 1
whenever the input is 3 or a multiple of 3
wx
00 01 11
yz
00
01
10
1
w
z
11 1
10
x
y
x
y
1
z
(b) Series-parallel realization of T.
(a) Map for T = wz + xyz + x yz.
w
z
x
y
Sneak path: z’xx’w – OK since it has no effect on the transmission function
z
x
(c) Minimal realization of T.
39
Synthesis of MOS Networks (Contd.)
Example: Design a minimal network to realize T(w,x,y,z) = (0,3,13,14,15)
wx
00 01 11
yz
00 1
01
1
11 1
1
10
1
10
y
x
w
w
z
y
z
y
z
x
(b) Series-parallel realization of T.
(a) Map for T = wxy + wxz
+ w x y z + w x yz.
y
w
w
x
z
y
z
z
y
x
(c) An alternative series-parallel realization of T.
w
x
y
y
w
z
y
x
z
(d) A minimum realization of T.
40
41
42