Computer Architecture Homework

Please use the textbook attached to find the answers and please cite the text and any sources. Please answer every question fully with detail.

Question 1
[10 points]
Majority function has an output value of 1 if there are more 1s than 0s on its inputs. The output is 0 otherwise.
Design a three-input majority function.
Question 2
[10 points]
Find a function to detect an error in the representation of a decimal digit in BCD. In other words, write an
equation with value 1 when the inputs are any one of the six unused bit combinations in the BCD code,
and value 0 otherwise
Question 3
[10 points]
Design a 4-input priority encoder with inputs and outputs as in Table 3-6, but with the truth table
representing the case in which input D has the highest priority and input D the lowest priority.
0
Question 4
3
[10 points]
Construct a 15–to–1-line multiplexer with two 8–to–1-line multiplexers. Interconnect the two multiplexers
and label the inputs such that any added logic required to have selection codes 0000 through 1110 is
minimized.
Question 5
[10 points]
Implement the Boolean function F(A, B, C, D) = Σm(1, 3, 4, 11, 12, 13, 14, 15) with a 4–to–1-line
multiplexer and external gates. Connect inputs A and B to the selection lines. The input requirements for
the four data lines will be a function of the variables C and D. The values of these variables are obtained
by expressing F as a function of C and D for each of the four cases when AB = 00, 01, 10, and 11.These
functions must be implemented with external gates.
Question 7
[10 points]
Given standard boolean function F(x,y,z) = x’y’z + x’yz’ + xy’z’. You should not simplify the
function.
a. Create the truth table.
[4 points]
b. Implement F by means of an 8-to-1 multiplexer.
[3 points]
a. Implement F by means of a 3-to-8 decoder.
[3 points]
Question 8
[10 points]
Consider designing a combinational circuit that implements the following function:
F(x)
-x;
x is even
x-1;
x is odd
Where x and F(x) are each 3-bit 2’s complement integers.
a. Draw the truth table for this function.
[4 points]
b. Write the Boolean equations for the output functions in canonical form. [6 points]
Chapter 3 Part 2
• Functions and functional blocks
• Rudimentary logic functions
• Selecting
• Decoding
• Encoding
• Implementing Combinational Functions
Using:
– Decoders and OR gates
– Multiplexers (and inverter)
2
Rudimentary Logic Functions
• Functions of a single variable X
• Can be used on the
inputs to functional
blocks
4
Multiple-bit Rudimentary Functions
• Multi-bit Examples:
A
1
0
A
•
•
•
•
•
F3
F2
F1
F0
A
1
0
A
2
1
3
0
4
F
4
2:1
F
(c)
2
F(2:1)
3
(a)
(b)
F(3), F(1:0)
4 3,1:0
A wide line is used to represent
F
a bus which is a vector signal
(d)
In (b) of the example, F = (F3, F2, F1, F0) is a bus.
The bus can be split into individual bits as shown in (b)
Sets of bits can be split from the bus as shown in (c)
for bits 2 and 1 of F.
The sets of bits need not be continuous as shown in (d) for bits 3, 1,
and 0 of F.
5
Selecting
• Selecting of data or information is a critical
function in digital systems and computers
• Circuits that perform selecting have:
– A set of information inputs from which the selection is
made
– A single output
– A set of control lines for making the selection
• Logic circuits that perform selecting are called
multiplexers
• Selecting can also be done by three-state logic
6
or transmission gates
Enabling Function
• Enabling permits an input signal to pass through
to an output
• Disabling blocks an input signal from passing
through to an output, replacing it with a fixed
value
• The value on the output when it is disable can
be Hi-Z (as for three-state buffers and
transmission gates), 0 , or 1 (see next slide)
18
Enabling
•When disabled, 0 output
•When disabled, 1 output
X
EN
F
(a)
X
F
EN
(b)
19
Decoder: Definition
• N inputs, 2N outputs
• One-hot outputs: only one output HIGH at once
2:4
Decoder
A1
A0
A1
0
0
1
1
A0
0
1
0
1
Y3
0
0
0
1
11
10
01
00
Y3
Y2
Y1
Y0
Y2
0
0
1
0
Y1
0
1
0
0
Y0
1
0
0
0
1
Decoding
• Decoding – the conversion of an n-bit input
code to an m-bit output code with
n £ m £ 2n such that each valid code word
produces a unique output code
• Circuits that perform decoding are called
decoders
• Here, functional blocks for decoding are
– called n-to-m line decoders, where m £ 2n,
and
– generate 2n (or fewer) minterms for the n 20
input variables
Decoder Examples
• 1-to-2-Line Decoder
• 2-to-4-Line Decoder
21
Decoder with Enable
• In general, attach m-enabling circuits to the outputs
• See truth table below for function
– Note use of X’s to denote both 0 and 1
– Combination containing two X’s represent four binary combinations
• Alternatively, can be viewed as distributing value of signal
EN
EN to 1 of 4 outputs
A
• In this case, called a
A
demultiplexer
D
1
0
0
EN A 1 A 0
D0 D1 D2 D3
0
1
1
1
1
0
1
0
0
0
X
0
0
1
1
X
0
1
0
1
(a)
0
0
1
0
0
0
0
0
1
0
D1
0
0
0
0
1
D2
D3
(b)
25
Decoder: Logic Diagram
yi = mi En
En
y0 = 1 if (I2, I1, I0 ) = (0,0,0) & En = 1
I0’
I1’
I2’
y0
I0’
I1’
I2
y1
.
.
I0
I1
I2
y7
y7 = I2I1I0En
3
Decoder Application: universal set {Decoder, OR}
Example: Implement functions f1(a,b,c) = Sm(1,2,4)
f2(a,b,c) = Sm(2,3), and f3(a,b,c) = Sm(0,5,6)
with a 3-input decoder and OR gates.
y1
y2
y4
En
c
I0
b
I1
a
I2
0
1
2
3
4
5
6
7
y0
y1
.
.
f1
y2
y3
f2
y7
y0
y5
y6
f3
4
Decoders
• OR minterms
A
B
2:4
Decoder
11
10
01
00
Y = AB + AB
= A  B
Minterm
AB
AB
AB
AB
Y
5
Tree of Decoders
Implement a 4-24 decoder with 3-23 decoders.
d
c
b
I0
I1
I2
I0
I1
I2
0
1
2
3
4
5
6
7
y0
y1
0
1
2
3
4
5
6
7
y8
y9
y7
y15
a
6
Tree of Decoders
Implement a 6-26 decoder with 3-23 decoders.
En
En
y0
I2, I1, I0
D0
y8
I5, I4, I3
I2, I1, I0
y7
D1
y15
…
…
y56
I2, I1, I0
D7
y63
7
Encoding
• Encoding – the opposite of decoding – the
conversion of an m-bit input code to a n-bit output
code with n £ m £ 2n such that each valid code
word produces a unique output code
• Circuits that perform encoding are called encoders
• An encoder has 2n (or fewer) input lines and n
output lines which generate the binary code
corresponding to the input values
• Typically, an encoder converts a code containing
exactly one bit that is 1 to a binary code corresponding to the position in which the 1 appears.
26
Encoder Example
• A decimal-to-BCD encoder
– Inputs: 10 bits corresponding to decimal
digits 0 through 9, (D0, …, D9)
– Outputs: 4 bits with BCD codes
– Function: If input bit Di is a 1, then the
output (A3, A2, A1, A0) is the BCD code for i,
• The truth table could be formed, but
alternatively, the equations for each of
the four outputs can be obtained directly.
27
Truth Table (continued)
28
Priority Encoder
• If more than one input value is 1, then the
encoder just designed does not work.
• One encoder that can accept all possible
combinations of input values and produce a
meaningful result is a priority encoder.
• Among the 1s that appear, it selects the most
significant input position (or the least
significant input position) containing a 1 and
responds with the corresponding binary code
for that position.
29
Priority Encoder Example
• Priority encoder with 5 inputs (D4, D3, D2, D1, D0) – highest priority to
most significant 1 present – Code outputs A2, A1, A0 and V where V
indicates at least one 1 present.
No. of Minterms/Row
Inputs
D4
D3 D2
D1
D0
A2
A1
A0
V
1
0
0
0
0
0
X
X
X
0
1
0
0
0
0
1
0
0
0
1
2
0
0
0
1
X
0
0
1
1
4
0
0
1
X
X
0
1
0
1
8
0
1
X
X
X
0
1
1
1
Outputs
16
1
X
X
X
X
1
0
0
1
• Xs in input part of table represent 0 or 1; thus table entries correspond
to product terms instead of minterms. The column on the left shows
that all 32 minterms are present in the product terms in the table
Interrupt handling
30
Priority Encoder Example (continued)
31
Multiplexer (Mux): Definition
• Selects between one of N inputs to
connect to the output.
• log2N-bit select input – control input
S
• Example:
2:1 Mux
S
0
0
0
0
1
1
1
1
D1
0
0
1
1
0
0
1
1
D0
0
D1
1
D0
0
1
0
1
0
1
0
1
Y
0
1
0
1
0
0
1
1
Y
S
0
1
Y
D0
D1
8
2-to-1-Line Multiplexer
• Since 2 = 21, n = 1
• The single selection variable S has two values:
– S = 0 selects input I0
– S = 1 selects input I1
• The equation:
Y = S I0 + SI1
• The circuit:
Enabling
Circuits
Decoder
I0
Y
S
I1
8
Multiplexer Definition: Example
En
D0
0
D1
1
D2
2
D3
3
If D0 = 0 and S1S0 = 00 => y = 0
If D0 = 1 and S1S0 = 00 => y = 1
y
S1 S0
9
Multiplexer: Logic Diagram
• Logic gates
– Sum-of-products form
Y
S
D0 D1
00
01
11
10
0
0
0
1
1
1
0
1
1
0
Y = D 0S + D1S
D0
S
D1
Y
10
Multiplexer Application
• Mux for a Boolean function with
truth table as input
A
B
Y
0
0
1
1
0
1
0
1
0
0
0
1
Y = AB
AB
00
01
10
Y
11
11
Multiplexer: Application
Y = AB
A
0
0
1
1
B
0
1
0
1
Y
0
0
0
1
A
Y
0
0
1
A
0
Y
B
B
1
12
Multiplexer Application: universal set {Mux}
Example 1: Given f (a,b,c) = Sm (0,1,7) + Sd(2), implement
with an 8-input Mux.
En
Id
a
b c
f
0
1
2
3
4
5
6
7
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
1
1
0
0
0
0
1
0
1
0
1
0
1
0
1
1
1
0
0
0
0
0
1
0
1
2
3
4
5
6
7
y
S2 S1 S0
a b c
13
Multiplexer Application
Example 2: Given f (a,b,c) = Sm (0,1,7) + Sd(2), implement
with 4-input Muxes.
En
a b
0
0
1
1
0
1
0
1
c=0 c=1
1
0
0
1
0
0
1
D (c)
D0 (c) =1
D1 (c) =0
D2 (c) =0
D3 (c) =c
1
0
0
1
0
2
c
3
y
S1 S0
a b
14
Multiplexer Application
Example 3: Given f (a,b,c) = Sm (0,1,7) + Sd(2), implement
with 2-input Muxes.
a
00 01 10 11
D (b,c)
0
1
1
0
D0 (b,c)
D1 (b,c)
1
0
0
0
1
En
En b’
D0 (b,c) = b’
c
1
–
1
0
0
y
D1 (b,c) = bc
c
0
0
0
0
0
1
c
1
b
1
a
b
b
D1 (b,c)
b
c=0 c=1
0
1
0
0
0
1
l1(0) = 0
l1(c) = c
15
Example
Given standard boolean function F(x,y,z) = x’yz + x’yz’ + xy’z’. You should not simplify the function.
a. Create the truth table.
b. Implement F by means of an 8-to-1 multiplexer.
c. Implement F by means of a 3-to-8 decoder.
16
Example
Given standard boolean function F(x,y,z) = x’yz + x’yz’ + xy’z’. You should not simplify the function.
a. Create the truth table.
b. Implement F by means of an 8-to-1 multiplexer.
c. Implement F by means of a 3-to-8 decoder.
17
Q 3-8
• Design a combinational circuit that accept
a 3-bit number and generates a 6-bit
binary number output equal to the square
of the input number
32
Answer
33
Weekly Exercises
• 3-2
• 3-8
• 3-13
• 3-16
• 3-30
• 3-35
• 3-36
• 3-39
• 3-42
• 3-47
34
Logic and Computer Design Fundamentals
Chapter 3 – Combinational
Logic Design
Part 1 – Implementation Technology and Logic
Design
Charles Kime & Thomas Kaminski
© 2004 Pearson Education, Inc.
Terms of Use
(Hyperlinks are active in View Show mode)
Overview
▪ Part 1 – Implementation Technology and Logic Design
• Design Concepts and Automation
▪ Fundamental concepts of design and computer-aided design techniques
• The Design Space
▪ Technology parameters for gates, positive and negative logic and design
tradeoffs
• Design Procedure
▪ The major design steps: specification, formulation, optimization,
technology mapping, and verification
• Technology Mapping
▪ From AND, OR, and NOT to other gate types
• Verification
▪ Does the designed circuit meet the specifications?
▪ Part 2 – Programmable Implementation Technologies
• Read-Only Memories, Programmable Logic Arrays, Programmable
Array Logic
▪ Technology mapping to programmable logic devices
Chapter 3 – Part 1
2
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
Chapter 3 – Part 1
3
Hierarchical Design
▪ To control the complexity of the function mapping inputs to
outputs:
• Decompose the function into smaller pieces called blocks
• Decompose each block’s function into smaller blocks, repeating as
necessary until all blocks are small enough
• Any block not decomposed is called a primitive block
• The collection of all blocks including the decomposed ones is a
hierarchy
▪ Example: 9-input parity tree (see next slide)
•
•
•
•
•
Top Level: 9 inputs, one output
2nd Level: Four 3-bit odd parity trees in two levels
3rd Level: Two 2-bit exclusive-OR functions
Primitives: Four 2-input NAND gates
Design requires 4 X 2 X 4 = 32 2-input NAND gates
Chapter 3 – Part 1
4
Hierarchy for Parity Tree 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
ZO
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
Chapter 3 – Part 1
5
Propagation Delay
▪ 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.
Chapter 3 – Part 1
6
Propagation Delay (continued)
▪ Propagation delays measured at the midpoint
between the L and H values
▪ What is the expression for the tPHL delay for:
• a string of n identical buffers?
• a string of n identical inverters?
Chapter 3 – Part 1
7
Propagation Delay Example
OUT (volts)
IN (volts)
▪ Find tPHL, tPLH and tpd for the signals given
t (ns)
1.0 ns per division
Chapter 3 – Part 1
8
Delay Models
▪ Transport delay – a change in the output in
response to a change on the inputs occurs after
a fixed specified delay
▪ Inertial delay – similar to transport delay,
except that if the input changes such that the
output is to change twice in a time interval less
than the rejection time, the output changes do
not occur. Models typical electronic circuit
behavior, namely, rejects narrow “pulses” on
the outputs
Chapter 3 – Part 1
9
Delay Model Example
A
B
A B:
No Delay
(ND)
Transport
Delay (TD)
a b
c d e
Inertial
Delay (ID)
0
2
4
6
8
10
12
14
16 Time (ns)
Propagation Delay = 2.0 ns Rejection Time = 1 .0 ns
Chapter 3 – Part 1
10
Fan-out
Chapter 3 – Part 1
11
Fan-out
▪ Fan-out can be defined in terms of a
standard load
• Example: 1 standard load equals the load
contributed by the input of 1 inverter.
• Transition time -the time required for the
gate output to change from H to L, tHL, or
from L to H, tLH
• The maximum fan-out that can be driven by
a gate is the number of standard loads the
gate can drive without exceeding its specified
maximum transition time
Chapter 3 – Part 1
12
Fan-out and Delay
▪ The fan-out loading a gate’s output
affects the gate’s propagation delay
▪ 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, i. e., its fan-out in standard loads
• For SL = 4.5, tpd = 0.165 ns
Chapter 3 – Part 1
13
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
• Ignoring the wiring area, the gate area is roughly
proportional to the gate input count
• So gate input count is a rough measure of gate cost
▪ If the actual chip layout area occupied by the
gate is known, it is a far more accurate measure
Chapter 3 – Part 1
14
Design Procedure
1. Specification
•
Write a specification for the circuit if one is not
already available
2. Formulation
•
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
Chapter 3 – Part 1
15
Design Procedure
4. Technology Mapping
•
Map the logic diagram or netlist to the
implementation technology selected
5. Verification
•
Verify the correctness of the final design
Chapter 3 – Part 1
16
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)
Chapter 3 – Part 1
17
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
ABCD
WXYZ
– BCD:
0000
0011
A,B,C,D
0001
0100
Variables
0010
0101
– Excess-3
0011
0110
0100
0111
W,X,Y,Z
0101
1000
Don’t Cares
0110
1001
– BCD 1010
0111
1010
to 1111
1000
1011
11 01 10 10
1001
Chapter 3 – Part 1
18
Design Example (continued)
z
C
1
1
0
1
3
4
5
7
1
1
X
X
13
8
9
X
15
1
B
14
X
1
4
5
X
12
13
8
9
1
10
C
1
1
1
3
2
4
5
7
6
A
X
X
15
1
8
X
9
11
D
15
B
14
X
11
10
C
0
1
1
13
X
X
1
12
6
w
0
X
7
D
x
X
2
X
D
1
3
1
X
A
X
11
0
1
6
X
12
1
2
1
A
C
y
14
X
10
B
4
X
A
1
12
1
8
7
X
13
11
Chapter 3 – D
Part 1
B
6
X
15
X
9
2
1
5
X
1
3
14
X
10
19
Design Example (continued)
3. Optimization z
a. 2-level using
K-maps
A
W = A + BC + BD
X = B C + B D + BC D
Y = CD + CD
Z=D
x
C
1
1
0
1
3
4
5
7
C
y
1
1
1
X
X
13
8
9
X
15
1
B
14
X
1
4
5
X
12
13
8
9
1
10
1
1
1
3
2
4
5
7
6
A
X
X
15
1
8
X
9
11
D
15
B
14
X
11
10
C
0
1
1
13
X
X
1
12
6
w
0
X
7
D
C
X
2
X
D
1
3
1
X
A
X
11
0
1
6
X
12
1
2
14
X
10
B
4
X
A
1
12
1
8
7
X
13
11
Chapter 3 – D
Part 1
B
6
X
15
X
9
2
1
5
X
1
3
14
X
10
20
Design Example (continued)
3. Optimization (continued)
b. Multiple-level using transformations
W = A + BC + BD
X = B C + B D + BC D
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 + BCD
Y = CD + C D
Z= D
G = 2 + 1 + 4 + 7 + 6 + 0 = 19
Chapter 3 – Part 1
21
Design Example (continued)
3. Optimization (continued)
b. Multiple-level using transformations
T1 = C + D
W = A + BT1
X = B T1 + B CD
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!
Chapter 3 – Part 1
22
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
W
B
C
D
X
B
X
C
Y
D
Y
Z
Z
Chapter 3 – Part 1
23
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
Chapter 3 – Part 1
24
NAND Mapping Algorithm
1. Replace ANDs and ORs:
.
.
.
.
.
.
.
.
.
.
.
.
2. Repeat the following pair of actions until there
is at most one inverter between :
a. A circuit input or driving NAND gate output, and
b. The attached NAND gate inputs.
.
.
.
.
.
.
Chapter 3 – Part 1
25
NAND Mapping Example
Chapter 3 – Part 1
26
Mapping to NOR gates
▪ Assumptions:
• Gate loading and delay are ignored
• Cell library contains an inverter and n-input NOR
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
Chapter 3 – Part 1
27
NOR Mapping Algorithm
1. Replace ANDs and ORs:
.
.
.
.
.
.
.
.
.
.
.
.
2. Repeat the following pair of actions until there
is at most one inverter between :
a. A circuit input or driving NAND gate output, and
b. The attached NAND gate inputs.
.
.
.
.
.
.
Chapter 3 – Part 1
28
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)
Chapter 3 – Part 1
29
Terms of Use
▪ © 2004 by Pearson Education,Inc. All rights reserved.
▪ The following terms of use apply in addition to the standard Pearson
Education Legal Notice.
▪ Permission is given to incorporate these materials into classroom
presentations and handouts only to instructors adopting Logic and
Computer Design Fundamentals as the course text.
▪ Permission is granted to the instructors adopting the book to post these
materials on a protected website or protected ftp site in original or
modified form. All other website or ftp postings, including those
offering the materials for a fee, are prohibited.
▪ You may not remove or in any way alter this Terms of Use notice or
any trademark, copyright, or other proprietary notice, including the
copyright watermark on each slide.
▪ Return to Title Page
Chapter 3 – Part 1
30
Arithmetic Functions and
Circuits, Chapter 3
Professor CK Cheng CSE Dept. UC San Diego
1
Representation
1’s Complement
For a negative number, we take the positive
number and complement every bit.
2’s Complement
For a negative number, we do 1s
complement and plus one.
(bn-1, bn-2, …, b0): -bn-12n-1+ sumi> 2 = 00110
– Ex: 11001 >> 2 = 11110
– Ex: 11001 >
Y2
10
2
A3:0 4
S1:0
01
11
4
Y3:0
00
S1:0
01
Y1
10
11
00
01
10
S1:0
Y0
11
25
Exercise
• Implement 2-bit incrementer
• Implement 2-bit decrementer
• Implement 2-bit incrementer/decrementer
26
Optional
27
32-bit CLA with 4-bit blocks
B31:28 A31:28
Cout
B27:24 A27:24
B7:4 A7:4
4-bit CLA C28 4-bit CLA C24
Block
Block
S31:28
C8 4-bit CLA C4 4-bit CLA
Block
Block
S27:24
B3
A3
B3:0 A3:0
S7:4
B2
A2
C3
B1
A1
C2
S3:0
B0
A0
C1
+
+
+
+
S3
S2
S1
S0
G3:0
Cin
Cin
G3
P3
G2
P2
G1
P1
G0
P3:0
Cout
Cin
P3
P2
P1
P0
28
Carry-Lookahead Adder Delay
• Delay of an N-bit carry-lookahead adder with k-bit
blocks:
tCLA = tpg + tpg_block + (N/k – 1)tAND_OR + ktFA
where
– tpg :
delay of the column generate and propagate gates
– tpg_block : delay of the block generate and propagate gates
– tAND_OR : delay from Cin to Cout of the final AND/OR gate
in the k-bit CLA block
• An N-bit carry-lookahead adder is generally much
faster than a ripple-carry adder for N > 16
29
Prefix Adder
• Computes the carry in (Ci-1) for each of the
columns as fast as possible and then computes the
sum:
Si = (Ai  Bi)  Ci
• Computes G and P for 1-bit, then 2-bit blocks, then
4-bit blocks, then 8-bit blocks, etc. until the carry in
(generate signal) is known for each column
• Has log2N stages
30
Prefix Adder
• A carry in is produced by being either generated in a
column or propagated from a previous column.
• Define column -1 to hold Cin, so G-1 = Cin, P-1 = 0
• Then, the carry in to col. i = the carry out of col. i-1:
Ci-1 = Gi-1:-1
Gi-1:-1 is the generate signal spanning columns i-1 to -1.
There will be a carry out of column i-1 (Ci-1) if the block
spanning columns i-1 through -1 generates a carry.
• Thus, we rewrite the sum equation:Si = (Ai  Bi)  Gi-1:-1
• Goal: Compute G0:-1, G1:-1, G2:-1, G3:-1, G4:-1, G5:-1, …
(These are called the prefixes)
31
Prefix Adder
• The generate and propagate signals for a block
spanning bits i:j are:
Gi:j = Gi:k + Pi:k Gk-1:j
Pi:j = Pi:kPk-1:j
• In words, these prefixes describe that:
– A block will generate a carry if the upper part (i:k)
generates a carry or if the upper part propagates a carry
generated in the lower part (k-1:j)
– A block will propagate a carry if both the upper and
lower parts propagate the carry.
32
Prefix Adder Schematic
15
14
13
14:13
12
11
12:11
13:7
10:7
12:7
14
13
12
Legend
8
7
11
10
6
8:7
9:7
9:-1
8:-1
9
5
6:5
11:7
14:-1 13:-1 12:-1 11:-1 10:-1
15
9
10:9
14:11 13:11
14:7
10
4
3
4:3
6:3
5:3
6:-1
5:-1
2
1
2:1
-1
0:-1
2:-1
4:-1
0
1:-1
3:-1
7:-1
8
7
6
5
4
3
2
i
1
0
i
i:j
Ai Bi
Pi:i
Pi:k Pk-1:jGi:k
Gk-1:j
Gi-1:-1 Ai Bi
Gi:i
Pi:j
Gi:j
Si
33
Carry Save Adder
Fast and low power addition for multiple
additions
• A Redundant Number System
• Save the Partial Solution for Multiple
Additions
• One Bit Propagation for Each Addition
34
Carry Save Adder: A Redundant Number System
• For each digit, we have two bits
– (0,0) (0,1) (1,0) (1,1)
• Weight 0 (0,0)
• Weight 1 (0,1) (1,0)
• Weight 2 (1,1)
35
Carry Save Adder: A Simple Example
Weight
32
16
8
4
2
1
n1
0
0
1
0
0
1
n2
0
1
1
1
1
0
n3
0
1
1
1
0
1
n4
0
0
1
0
1
1
36
Carry Save Adder: A Simple Example
Weight
64
32
16
8
4
2
1
n1
0
0
0
1
1
0
1
n2
0
0
1
1
1
1
0
n3
0
0
1
1
1
0
1
n4
0
0
0
1
1
1
1
n1
00
00
00
10
10
00
10
n2
0
0
1
1
1
1
0
A=n1+n2 00
00
11
01
00
10
10
n3
0
0
1
1
1
0
1
B=A+n3
00
01
11
00
10
11
00
n4
0
0
0
1
1
1
1
C=B+n4
00
10
11
11
01
10
10
Sum
1
0
1
0
1
1
1
37
Carry Save Adder: One Digit Logic Diagram
Addend in two bit Addend in one bit
A
B
Full Adder Cin
Full Adder
Cout
Sum
Carry out form digit i-1
Carry out to digit i+1 Sum in two bits
• For digit i, the addition of addend in two bits and addend
in one bit produces the carry out and sum.
• The sum and the carry out from digit i-1 become the two
bit output at digit i.
38
Carry Save Adder: Three Digit Logic Diagram
Addend in two bit Addend in two bit Addend in two bit
Addend in one bit Addend in one bit Addend in one bit
A B
A B
A B
Full Adder
Full Adder
Full Adder
Full
Cin
Adder
Cout
Full
Cin
Adder
Cout
Sum
Sum
Sum
Cout to digit i+2
Cout to digit i+1
Full
Cin
Adder
Cout
Cout form digit i-1
Sum in two bits Sum in two bits
Cout form digit i-2
Sum in two bits
• For digit i, the addition of addend in two bits and addend
in one bit produces the carry out and sum.
• The sum and the carry out from digit i-1 become the two
bit output at digit i.
39
Carry Save Adder
Procedure of carry save addition system
1. Convert the first addend to the redundant number
system
2. For intermediate solution, perform carry save
addition.
3. Split the redundant number into two numbers.
4. Perform the addition on the two numbers to general
the solution.
40
Prefix Adder Delay
• The delay of an N-bit prefix adder is:
tPA = tpg + log2N(tpg_prefix ) + tXOR
where
– tpg is the delay of the column generate and propagate gates
(AND or OR gate)
– tpg_prefix is the delay of the black prefix cell (AND-OR
gate)
41
Adder Delay Comparisons
• Compare the delay of 32-bit ripple-carry, carrylookahead, and prefix adders. The carry-lookahead
adder has 4-bit blocks. Assume that each two-input
gate delay is 100 ps and the full adder delay is 300
ps.
42
Adder Delay Comparisons
• Compare the delay of 32-bit ripple-carry, carrylookahead, and prefix adders. The carry-lookahead
adder has 4-bit blocks. Assume that each two-input
gate delay is 100 ps and the full adder delay is 300 ps.
tripple = NtFA = 32(300 ps) = 9.6 ns
tCLA
tPA
= tpg + tpg_block + (N/k – 1)tAND_OR + ktFA
= [100 + 600 + (7)200 + 4(300)] ps
= 3.3 ns
= tpg + log2N(tpg_prefix ) + tXOR
= [100 + log232(200) + 100] ps
= 1.2 ns
43
Barrel Shifter
shift
x
0 1 0 1 0 1
s0
O or 1 shift
s1
O or 2 shift
0 1 0 1 0 1 0 1 0 1
s2
O or 4 shift
y
0 1 0 1 0 1 0 1 0 1 0 1
Shifters as Multipliers and
Dividers
• A left shift by N bits multiplies a number by 2N
– Ex: 00001 > 2 = 00010 (8 ÷ 22 = 2)
– Ex: 10000 >>> 2 = 11100 (-16 ÷ 22 = -4)
45
Carry-Lookahead Adder (optional)
• Compress the logic levels of Cout
• Some definitions:
– Generate (Gi) and propagate (Pi) signals for each column:
• A column will generate a carry out if Ai AND Bi are both 1.
Gi = Ai Bi
• A column will propagate a carry in to the carry out if Ai OR Bi is 1.
Pi = Ai + Bi
• The carry out of a column (Ci ) is:
Ci+1 = Ai Bi + (Ai + Bi )Ci = Gi + Pi Ci
46
Carry Look Ahead Adder
C1 = a0b0 + (a0+b0)c0 = g0 + p0c0
C2 = a1b1 + (a1+b1)c1 = g1 + p1c1 = g1 + p1g0 + p1p0c0
C3 = a2b2 + (a2+b2)c2 = g2 + p2c2 = g2 + p2g1 + p2p1g0 + p2p1p0c0
C4 = a3b3 + (a3+b3)c3 = g3 + p3c3 = g3 + p3g2 + p3p2g1 + p3p2p1g0 + p3p2p1p0c0
qi = aibi
pi = ai + bi
a3 b3
a 2 b2
g3
g2
p3
p2
a 1 b1
g1
p1
a 0 b0
g0
p0
c0
c4
c3
c2
c1
47
Carry-Lookahead Addition
• Step 1: compute generate (G) and propagate (P)
signals for columns (single bits)
• Step 2: compute G and P for k-bit blocks
• Step 3: Cin propagates through each k-bit
propagate/generate block
48
Multipliers (optional)
• Steps of multiplication for both decimal and
binary numbers:
– Partial products are formed by multiplying a single
digit of the multiplier with the entire multiplicand
– Shifted partial products are summed to form the
result
Decimal
230
x
42
460
+ 920
9660
Binary
multiplicand
multiplier
partial
products
result
230 x 42 = 9660
0101
x 0111
0101
0101
0101
+ 0000
0100011
5 x 7 = 35
49
4 x 4 Multiplier
A3
A2
B0
B1
A B
4
4
x
x
A2
A1
A0
B3
B2
B1
B0
A0
0
0
B2
A3B0 A2B0 A1B0 A0B0
0
A3B1 A2B1 A1B1 A0B1
8
P
A3
A1
B3
A3B2 A2B2 A1B2 A0B2
A3B3 A2B3 A1B3 A0B3
+
P7
P6
P5
P4
P3
P2
P1
0
P0
P7
P6
P5
P4
P3
P2
P1
50
P0
Division Algorithm
• Q = A/B
• R: remainder
• D: difference
R=A
for i = N-1 to 0
D=R-B
if D < 0 then Qi = 0, R’ = R else Qi = 1, R’ = D R = 2R’ // R < B // R  B 51 4 x 4 Divider 52 Logic and Computer Design Fundamentals Chapter 2 – Combinational Logic Circuits Part 3 – Additional Gates and Circuits Charles Kime & Thomas Kaminski © 2004 Pearson Education, Inc. Terms of Use (Hyperlinks are active in View Show mode) Overview § Part 1 – Gate Circuits and Boolean Equations • Binary Logic and Gates • Boolean Algebra • Standard Forms § Part 2 – Circuit Optimization • Two-Level Optimization • Map Manipulation § Part 3 – Additional Gates and Circuits • Other Gate Types • Exclusive-OR Operator and Gates • High-Impedance Outputs Chapter 2 - Part 3 2 Other Gate Types § Why? • Implementation feasibility and low cost • Power in implementing Boolean functions • Convenient conceptual representation § Gate classifications • Primitive gate - a gate that can be described using a single primitive operation type (AND or OR) plus an optional inversion(s). • Complex gate - a gate that requires more than one primitive operation type for its description § Primitive gates will be covered first Chapter 2 - Part 3 3 Buffer § A buffer is a gate with the function F = X: X F § In terms of Boolean function, a buffer is the same as a connection! § So why use it? • A buffer is an electronic amplifier used to improve circuit voltage levels and increase the speed of circuit operation. Chapter 2 - Part 3 4 NAND Gate § The basic NAND gate has the following symbol, illustrated for three inputs: • AND-Invert (NAND) X Y Z F( X , Y , Z ) = X × Y × Z § NAND represents NOT AND, i. e., the AND function with a NOT applied. The symbol shown is an AND-Invert. The small circle (“bubble”) represents the invert function. Chapter 2 - Part 3 5 NAND Gates (continued) § Applying DeMorgan's Law gives Invert-OR (NAND) X Y Z F( X , Y , Z ) = X + Y + Z § This NAND symbol is called Invert-OR, since inputs are inverted and then ORed together. § AND-Invert and Invert-OR both represent the NAND gate. Having both makes visualization of circuit function easier. § A NAND gate with one input degenerates to an inverter. Chapter 2 - Part 3 6 Transistor NAND Gate Chapter 2 - Part 3 7 NAND Gates (continued) § The NAND gate is the natural implementation for the simplest and fastest electronic circuits § Universal gate - a gate type that can implement any Boolean function. § The NAND gate is a universal gate as shown in Figure 2-4 of the text. § NAND usually does not have a operation symbol defined since • the NAND operation is not associative, and • we have difficulty dealing with non-associative mathematics! Chapter 2 - Part 3 8 NOR Gate § The basic NOR gate has the following symbol, illustrated for three inputs: • OR-Invert (NOR) X Y Z F(X, Y, Z) = X +Y+ Z § NOR represents NOT - OR, i. e., the OR function with a NOT applied. The symbol shown is an OR-Invert. The small circle (“bubble”) represents the invert function. Chapter 2 - Part 3 9 NOR Gate (continued) § Applying DeMorgan's Law gives Invert-AND (NOR) X Y Z § This NOR symbol is called Invert-AND, since inputs are inverted and then ANDed together. § OR-Invert and Invert-AND both represent the NOR gate. Having both makes visualization of circuit function easier. § A NOR gate with one input degenerates to an inverter. Chapter 2 - Part 3 10 NOR Gate (continued) § The NOR gate is another natural implementation for the simplest and fastest electronic circuits § The NOR gate is a universal gate § NOR usually does not have a defined operation symbol since • the NOR operation is not associative, and • we have difficulty dealing with non-associative mathematics! Chapter 2 - Part 3 11 Transistor NOR Gate Chapter 2 - Part 3 12 NAND Flash & NOR Flash Chapter 2 - Part 3 13 A Flash Memory Cell (floating-gate transistor) Chapter 2 - Part 3 14 Exclusive OR/ Exclusive NOR § The eXclusive OR (XOR) function is an important Boolean function used extensively in logic circuits. § The XOR function may be; • implemented directly as an electronic circuit (truly a gate) or • implemented by interconnecting other gate types (used as a convenient representation) § The eXclusive NOR function is the complement of the XOR function § By our definition, XOR and XNOR gates are complex gates. Chapter 2 - Part 3 15 Exclusive OR/ Exclusive NOR § Uses for the XOR and XNORs gate include: • Adders/subtractors/multipliers • Counters/incrementers/decrementers • Parity generators/checkers § Definitions • The XOR function is: X Å Y = X Y + X Y • The eXclusive NOR (XNOR) function, otherwise known as equivalence is: X Å Y = X Y + X Y § Strictly speaking, XOR and XNOR gates do not exist for more than two inputs. Instead, they are replaced by odd and even functions. Chapter 2 - Part 3 16 Truth Tables for XOR/XNOR Because it is defined as X Y + X’ Y’ that equals 1 if § Operator Rules: XORX is equivalent XNOR and only if X = Y implying to Y. X Y XÅY X 0 0 1 1 0 1 0 1 0 0 1 1 0 1 1 0 Y (XÅY) or X ºY 0 1 1 0 0 0 1 1 § The XOR function means: X OR Y, but NOT BOTH § Why is the XNOR function also known as the equivalence function, denoted by the operator º? Chapter 2 - Part 3 17 The three-variable XOR is equal to 1 if only one XOR/XNOR (Continued) variable is equal to 1 or if all three variables are equal to 1. With three or more variables an odd § The XOR function can be extended to 3 or more number of variables equal ittois called 1. Therefore, variables. For moremust than 2be variables, an odd function modulo 2 sum (Mod 2 sum), not an XOR: it’s called oddorfunction. Why? X Å YÅ Z = XYZ+ XYZ+ XYZ+ XYZ § The complement of the odd function is the even function. § The XOR identities: XÅ0 = X X Å1 = X XÅX =0 XÅX =1 XÅY = YÅX ( X Å Y) Å Z = X Å ( Y Å Z ) = X Å Y Å Z Chapter 2 - Part 3 18 Symbols For XOR and XNOR § XOR symbol: § XNOR symbol: § Symbols exist only for two inputs Chapter 2 - Part 3 19 XOR Implementations § The simple SOP implementation uses the following structure: X X Y Y § A NAND only implementation is: X X Y Y Chapter 2 - Part 3 20 Odd and Even Functions § The odd and even functions on a K-map form “checkerboard” patterns. § The 1s of an odd function correspond to minterms having an index with an odd number of 1s. § The 1s of an even function correspond to minterms having an index with an even number of 1s. § Implementation of odd and even functions for greater than 4 variables as a two-level circuit is difficult, so we use “trees” made up of : • 2-input XOR or XNORs • 3- or 4-input odd or even functions Chapter 2 - Part 3 21 Example: Odd Function Implementation § Design a 3-input odd function F = X + Y + Z with 2-input XOR gates § Factoring, F = (X + Y) + Z § The circuit: X Y Z F Chapter 2 - Part 3 22 Example: Even Function Implementation § Design a 4-input even function F = W + X+ Y + Z with 2-input XOR and XNOR gates § Factoring, F = (W + X) + (Y + Z) § The circuit: W X F Y Z Chapter 2 - Part 3 23 Hi-Impedance Outputs § Logic gates introduced thus far • have 1 and 0 output values, • cannot have their outputs connected together, and • transmit signals on connections in only one direction. § Three-state logic adds a third logic value, HiImpedance (Hi-Z), giving three states: 0, 1, and Hi-Z on the outputs. § The presence of a Hi-Z state makes a gate output as described above behave quite differently: • “1 and 0” become “1, 0, and Hi-Z” • “cannot” becomes “can,” and • “only one” becomes “two” Chapter 2 - Part 3 24 Hi-Impedance Outputs (continued) § What is a Hi-Z value? • • • § The Hi-Z value behaves as an open circuit This means that, looking back into the circuit, the output appears to be disconnected. It is as if a switch between the internal circuitry and the output has been opened. Hi-Z may appear on the output of any gate, but we restrict gates to: • • a 3-state buffer, or a transmission gate, each of which has one data input and one control input. Chapter 2 - Part 3 25 The 3-State Buffer § For the symbol and truth table, IN is the data input, and EN, the control input. § For EN = 0, regardless of the value on IN (denoted by X), the output value is Hi-Z. § For EN = 1, the output value follows the input value. § Variations: • Data input, IN, can be inverted • Control input, EN, can be inverted by addition of “bubbles” to signals. Symbol IN OUT EN Truth Table EN 0 1 1 IN X 0 1 OUT Hi-Z 0 1 Chapter 2 - Part 3 26 Resolving 3-State Values on a Connection § Connection of two 3-state buffer Resolution Table outputs, B1 and B0, to a wire, OUT § Assumption: Buffer data inputs B1 B0 OUT can take on any combination of values 0 and 1 0 Hi-Z 0 § Resulting Rule: At least one buffer 1 Hi-Z 1 output value must be Hi-Z. Why? § How many valid buffer output Hi-Z 0 0 combinations exist? § What is the rule for n 3-state Hi-Z 1 1 buffers connected to wire, OUT? Hi-Z Hi-Z Hi-Z § How many valid buffer output combinations exist? Chapter 2 - Part 3 27 Answers to last slide § One buffer output Hi-Z? Because any data combinations including (0,1) and (1,0) can occur. If one of these combinations occurs, and no buffers are Hi-Z, then high currents can occur, destroying or damaging the circuit. § Valid buffer output combinations? 5 § Rule for n 3-state buffers? n-1 buffer outputs must be HiZ. § Valid buffer output combinations? Each of the n-buffers can have a 0 or 1 output with all others at Hi-Z. Also all buffers can be Hi-Z. So there are 2n + 1 valid combinations. Chapter 2 - Part 3 28 3-State Logic Circuit § Data Selection Function: If s = 0, OL = IN0, else OL = IN1 § Performing data selection with 3-state buffers: EN0 IN0 EN1 IN1 OL 0 0 1 1 0 X X 0 1 X 1 1 0 0 0 0 1 X X X 0 1 0 1 X IN0 S EN0 OL IN1 EN1 § Since EN0 = S and EN1 = S, one of the two buffer outputs is always Hi-Z plus the last row of the table never occurs. Chapter 2 - Part 3 29 MUX using Tri-State Buffers Chapter 2 - Part 3 30 Terms of Use § © 2004 by Pearson Education,Inc. All rights reserved. § The following terms of use apply in addition to the standard Pearson Education Legal Notice. § Permission is given to incorporate these materials into classroom presentations and handouts only to instructors adopting Logic and Computer Design Fundamentals as the course text. § Permission is granted to the instructors adopting the book to post these materials on a protected website or protected ftp site in original or modified form. All other website or ftp postings, including those offering the materials for a fee, are prohibited. § You may not remove or in any way alter this Terms of Use notice or any trademark, copyright, or other proprietary notice, including the copyright watermark on each slide. § Return to Title Page Chapter 2 - Part 3 31