Transcript 3-input NAND gate

CPEN 315 - Digital System Design
Combinational Logic Design
Chapter 3
© Logic and Computer Design Fundamentals, 4rd Ed., Mano
© 2008 Pearson Prentice Hall
Design Concepts and Automation
• A top-down design proceeds from an abstract, high-level
specification to a more and more detailed design by
decomposition and successive refinement
• A bottom-up design starts with detailed primitive blocks
and combines them into larger and more complex
functional blocks
• Designs usually proceed from both directions
simultaneously
– Top-down design answers: What are we building?
– Bottom-up design answers: How do we build it?
• Top-down controls complexity while bottom-up focuses
on the details
Design Example
X0
X1
X2
X3
X4
X5
X6
X7
X8
9-Input
odd
function
ZO
(a) Symbol for circuit
X0
A0
X1
A1
X2
A2
X3
A0
3-Input
odd B O
function
X5
3-Input
A 1 odd B O
function
A2
X6
A0
X7
A1
X8
A2
X4
A0
A1
A2
3-Input
odd B
O
function
3-Input
odd B O
function
(b) Circuit as interconnected 3-input odd
function blocks
A0
A1
BO
A2
(c) 3-input odd function circuit as
interconnected exclusive-OR
blocks
(d) Exclusive-OR block as interconnected
NANDs
ZO
Reusable Functions and CAD
• Whenever possible, we try to decompose a complex
design into common, reusable function blocks
• These blocks are
– verified and well-documented
– placed in libraries for future use
• Representative Computer-Aided Design Tools:
–
–
–
–
Schematic Capture
Logic Simulators
Timing Verifiers
Hardware Description Languages
• Verilog and VHDL
– Logic Synthesizers
– Integrated Circuit Layout
Integrated Circuits
• Integrated circuit (informally, a “chip”) is a
semiconductor crystal (most often silicon)
containing the electronic components for the digital
gates and storage elements which are
interconnected on the chip.
• Terminology - Levels of chip integration
–
–
–
–
SSI (small-scale integrated) - fewer than 10 gates
MSI (medium-scale integrated) - 10 to 100 gates
LSI (large-scale integrated) - 100 to thousands of gates
VLSI (very large-scale integrated) - thousands to 100s of
millions of gates
– ULSI (Ultra large-scale integration) – 100 million to
billion(s)
Combinational Circuits
• A combinational logic circuit has:
– A set of m Boolean inputs,
– A set of n Boolean outputs, and
– n switching functions, each mapping the 2m input
combinations to an output such that the current output
depends only on the current input values
• A block diagram:
m Boolean Inputs
Combinatorial
Logic
Circuit
n Boolean Outputs
Simplification with
Don’t care conditions
There are applications in which the function is not
specified for certain input combinations:
- Input combinations never occur
- Input combinations are expected to occur but we simply
don’t care what the outputs are in response to the input
combinations.
These conditions can be used on a map to provide further
simplification of the function.
Simplification with
Don’t care conditions (example)
F ( A, B, C, D)   m(1,3,7,11,15)
d ( A, B, C, D)   m(0,2,5)
F ( A, B, C, D)   m(1,3,7,11,15)
x
x
x
F  CD  A' B'
F  CD  A' B'
x
x
x
F  CD  A' D
Multi-Level Circuit Optimization
Multi-Level circuits can reduce the cost of Combinational
Logic Circuits.
G  ABC  ABD  E  ACF  ADF
Gate-Input Cost = 17
Multi-Level Circuit Optimization
(continued)
G  ABC  ABD  E  ACF  ADF
G  AB(C  D)  E  A(C  D) F
Gate-Input Cost = 13
Multi-Level Circuit Optimization
(continued)
G  ABC  ABD  E  ACF  ADF
G  ( AB  AF )(C  D)  E
Gate-Input Cost = 11
Multi-Level Circuit Optimization
(continued)
G  ABC  ABD  E  ACF  ADF
G  ( AB  AF )(C  D)  E
G  A( B  F )(C  D)  E
Gate-Input Cost = 9
Is the signal delay reduced or increased?
High-Impedance Outputs
Tri-State Buffer
Transmission Gate
Transmission Gate Logic
Technology Parameters
• Specific gate implementation technologies are
characterized by the following parameters:
– Fan-in – the number of inputs available on a gate
– Fan-out – the number of standard loads driven by a gate
output
– Cost – The cost of a gate is proportional to the chip area
occupied by the gate
– Logic Levels – the signal value ranges for 1 and 0 on the
inputs and 1 and 0 on the outputs (see Figure 1-1)
– Noise Margin – the maximum external noise voltage
superimposed on a normal input value that will not cause an
undesirable change in the circuit output
– Propagation Delay – the time for a change on an input of a
gate to propagate to the output.
– Power Dissipation – the amount of power drawn from the
power supply and consumed by the gate
Propagation Delay
in Chapter 6
• Propagation delay is the time for a change on an input
of a gate to propagate to the output.
• Delay is usually measured at the 50% point with
respect to the H and L output voltage levels.
• High-to-low (tPHL) and low-to-high (tPLH) output signal
changes may have different propagation delays.
• High-to-low (HL) and low-to-high (LH) transitions are
defined with respect to the output, not the input.
• An HL input transition causes:
– an LH output transition if the gate inverts and
– an HL output transition if the gate does not invert.
Propagation Delay (continued)
•
•
•
•
A logic gate always takes some time to change states
tPLH is the delay time before output changes from low to high
tPHL is the delay time before output changes from high to low
both tPLH & tPLH are measured between the 50% points on the
input and output transitions
50%
INPUT
OUTPUT
tPHL
tpd = max (tPHL, tPLH)
tPLH
Propagation Delay (continued)
1.5 ns
OUT (volts)
IN (volts)
• Find tPHL, tPLH and tpd for the signals given
t (ns)
1.0 ns per division
Fan-out and Delay
• The fan-out loading a gate’s output affects the
gate’s propagation delay (input-to-output)
• Example:
– One realistic equation for tpd for a NAND
gate with 4 inputs is:
tpd = 0.07 + 0.021 SL ns
– SL is the number of standard loads the gate
is driving.
– Assume SL = 4.5, tpd = 0.165 ns
Fan-out and Delay - example
• A 4-input NAND gate is attached to the inputs of the
following gates with a given number of standard loads
representing their inputs:
– 4-input NOR gate (0.8 standard load)
– 3-input NAND gate (1.00 standard load)
tpd = 0.07 + 0.021 SL ns (4-input NAND gate)
– What is the total tpd? 0.11 ns
Note that in modern high-speed designs, the
portion of gate delay due to wiring capacitance is
often significant.
Fan-in
• For high-speed technologies fan-in, the number
of inputs to a gate is often restricted to no more
than 4 or 5.
• Problem: Implement a 7-input NAND gate
using NAND gates with 4 inputs.
Cost
• In an integrated circuit:
– The cost of a gate is proportional to the chip
area occupied by the gate
– The gate area is roughly proportional to the
number and size of the transistors and the
amount of wiring connecting them
• If the actual chip area occupied by the gate is
known, it is a far more accurate measure.
Speed-Power Product
• Speed (propagation delay) and power consumption are the
two most important performance parameters of a digital IC.
• A simple means for measuring and comparing the overall
performance of an IC family is the speed-power product
(the smaller, the better).
• For example, an IC has
– an average propagation delay of 10 ns and
– an average power dissipation of 5 mW.
– What is the speed-power product ? 50 pico joules
Design Procedure
1. Specification
–
Write a specification for the circuit if one is not
already available
Formulation
2.
–
Derive a truth table or initial Boolean equations that
define the required relationships between the inputs
and outputs, if not in the specification
3. Optimization
–
–
Apply 2-level and multiple-level optimization
Draw a logic diagram or provide a netlist for the
resulting circuit using ANDs, ORs, and inverters
Design Procedure
4. Technology Mapping
–
Map the logic diagram or netlist to the implementation
technology selected
Verification
5.
–
Verify the correctness of the final design
Design Example
1. Specification
– BCD to Excess-3 code converter
– Transforms BCD code for the decimal digits to Excess-3
code for the decimal digits
– BCD code words for digits 0 through 9: 4-bit patterns 0000
to 1001, respectively
– Excess-3 code words for digits 0 through 9: 4-bit patterns
consisting of 3 (binary 0011) added to each BCD code
word
– Implementation:
• multiple-level circuit
• NAND gates (including inverters)
Design Example (continued)
2. Formulation
–
–
–
–
Conversion of 4-bit codes can be most easily
formulated by a truth table
Variables
Input BCD
Output Excess-3
- BCD:
ABCD
WXYZ
A,B,C,D
0000
0011
0001
0100
Variables
0010
0101
- Excess-3
0011
0110
W,X,Y,Z
0100
0111
0101
1000
Don’t Cares
0110
1001
- BCD 1010
0111
1010
to 1111
1000
1011
1001
1011
Design Example (continued)
3. Optimization z
a. 2-level using
K-maps
A
W = A + BC + BD
X = BC + B D + BC D
Y = CD + C D
Z=D
x
C
1
y
1
0
1
3
4
5
7
1
X
X
12
13
8
9
X
X
1
B
1
4
5
A
X
X
12
13
8
9
1
1
0
4
5
7
6
4
1
1
10
3
1
X
13
1
X
C
2
8
B
14
11
w
3
A
X
D
1
12
6
X
0
X
7
15
1
10
C
X
2
X
D
1
3
1
X
14
11
0
1
6
15
1
1
2
1
X
C
X
15
X
9
11
D
B
X
14
10
X
1
7
X
13
1
8
1
5
12
A
X
1
2
6
X
15
X
9
11
D
14
X
10
B
Design Example (continued)
3. Optimization (continued)
b. Multiple-level using transformations
W = A + BC + BD
X = B C + BD + B CD
Y = CD + C D
Z= D
–
G = 7 + 10 + 6 + 0 = 23
Perform extraction, finding factor:
T1 = C + D
W = A + BT1
X = B T1 + B CD
Y = CD + C D
Z= D
G = 2 + 1 + 4 + 7 + 6 + 0 = 19
Design Example (continued)
3. Optimization (continued)
b. Multiple-level using transformations
T1 = C + D
W = A + BT1
X = B T1 + BCD
Y = CD + C D
Z =D
G = 19
– An additional extraction not shown in the text since it uses a
Boolean transformation: (CD = C + D = T1 ):
W = A + BT1
X = B T1 + B T1
Y = CD + T1
Z= D
G = 2 +1 + 4 + 6 + 4 + 0 = 16
Design Example (continued)
4. Technology Mapping
•
Mapping with a library containing inverters and 2-input NAND,
2-input NOR, and 2-2 AOI gates
A
A
W
B
X
W
B
X
C
C
D
Y
D
Y
Z
Z
Technology Mapping
• Chip design styles
• Cells and cell libraries
• Mapping Techniques
–
–
–
–
NAND gates
NOR gates
Multiple gate types
Programmable logic devices
• The subject of Chapter 3 - Part 2
Chip Design Styles
• Full custom - the entire design of the chip down to the
smallest detail of the layout is performed
– Expensive
– Justifiable only for dense, fast chips with high sales
volume
• Standard cell - blocks have been design ahead of time or
as part of previous designs
– Intermediate cost
– Less density and speed compared to full custom
• Gate array - regular patterns of gate transistors that can be
used in many designs built into chip
– Lowest cost
– Less density compared to full custom and standard cell
Cell Libraries
• Cell - a pre-designed primitive block
• Cell library - a collection of cells available for
design using a particular implementation
technology
• Cell characterization - a detailed specification of
a cell for use by a designer - often based on actual
cell design and fabrication and measured values
• Cells are used for gate array, standard cell, and in
some cases, full custom chip design
Example Cell Library
Typical
Input-toOutput
Delay
Normalized
Area
Typical
Input
Load
Inverter
1.00
1.00
0.04
0.012
+
x SL
2NAND
1.25
1.00
0.05
+ 0.014 x SL
2NOR
1.25
1.00
0.06
+ 0.018 x SL
2-2 AOI
2.25
0.95
0.07
+ 0.019 x SL
Cell
Name
Cell
Schematic
Basic
Function
Templates
Mapping to NAND gates
• Assumptions:
– Gate loading and delay are ignored
– Cell library contains an inverter and n-input NAND
gates, n = 2, 3, …
– An AND, OR, inverter schematic for the circuit is
available
• The mapping is accomplished by:
– Replacing AND and OR symbols,
– Pushing inverters through circuit fan-out points, and
– Canceling inverter pairs
NAND Mapping Algorithm (Example)
NOR Mapping Example
A
A
B
B
1
F
C
C
D
E
(a)
A
2
X
F
3
D
E
(b)
B
C
F
D
E
(c)
Verification
• Verification - show that the final circuit designed
implements the original specification
• Simple specifications are:
– truth tables
– Boolean equations
– HDL code
• If the above result from formulation and are not
the original specification, it is critical that the
formulation process be flawless for the
verification to be valid!
Basic Verification Methods
• Manual Logic Analysis
– Find the truth table or Boolean equations for the final circuit
– Compare the final circuit truth table with the specified truth table,
or
– Show that the Boolean equations for the final circuit are equal to
the specified Boolean equations
• Simulation
– Simulate the final circuit (or its netlist, possibly written as an
HDL) and the specified truth table, equations, or HDL description
using test input values that fully validate correctness.
– The obvious test for a combinational circuit is application of all
possible “care” input combinations from the specification
Verification Example: Simulation
• Enter BCD-to-Excess-3 Code Converter Circuit Schematic
Verification Example: Simulation
• Enter waveform that applies all possible input combinations:
INPUTS
A
B
C
D
0
50 ns
100 ns