SSE3061: Digital System Design

Lecture 10.

Tae Hee Han: than@skku.edu

Semiconductor Systems Engineering
Sungkyunkwan University

Agenda
 Computer Arithmetic II
 Multiplication

2
Basic Concept of Multiplication

multiplicand 11012 (1310)

multiplier × 10112 (1110)

1101

1101
Partial products 0000
1101

10001111 (14310)

 Product of 2 n-bit numbers is a 2n-bit number

 sum of n n-bit partial products
 Unsigned

Combinational Multiplier: Accumulation of Partial Products

A3 A2 A1 A0

B3 B2 B1 B0

A3 B0 A2 B0 A1 B0 A0 B0

A3 B1 A2 B1 A1 B1 A0 B1

A3 B2 A2 B2 A1 B2 A0 B2

A3 B3 A2 B3 A1 B3 A0 B3

S7 S6 S5 S4 S3 S2 S1 S0

4
Array Multiplier
Generates all n partial products simultaneously.
b3 0 b2 0 b1 0 b0 0
Each row: n-bit adder with AND gates
a0

0
P0
a1

0
P1
a2

0
P2
a3

0
P3

P7 P6 P5 P4
What is the critical path?
5

“Shift-and-Add” Multiplier
 Sums each partial
product, one at a time
P B
n-bit shift registers
 In binary, each partial
product is shifted
+ versions of A or 0

n-bit
0 0
adder 1
Control Algorithm:
A
n-bit register 1. P ← 0, A ← multiplicand, B ← multiplier
2. If LSB of B==1 then add A to P else add 0
 Cost ∝ n, Τ = n clock cycles
3. Shift [P][B] right 1
 What is the critical path for
determining the min clock period? 4. Repeat steps 2 & 3 (n−1) times.
5. [P][B] has product.

6
Combinational Multiplier
 Use an array of AND gates to generate the partial
products in parallel
multiplicand
1 1 0 LSB
LSB
1

multiplier 1 1 0
1

1 1 0
0

0 0 0

1 0 0 1 0
7

Combinational Multiplier: Adding Partial Products

X3 X2 X1 X0 Y0

X3 X2 X1 X0 Y1 Z
0

HA FA FA HA

X3 X2 X1 X0 Y2
Z1

FA FA FA HA

X3 X2 X1 X0 Y3
Z2

FA FA FA HA

Z7 Z6 Z5 Z4 Z3
8
Combinational Multiplier: Critical Path(s)

Carry-Save Adder: the Idea

 When adding k n-bit numbers, don’t need to optimize the carry
chain of each of the rows
 Below is the old-style ripple-adder

HA FA FA HA

FA FA FA HA

FA FA FA HA

10
Carry-Save Addition
 Speeding up multiplication is a
 Example: sum three numbers,
matter of speeding up the summing
of the partial products 310 = 0011, 210 = 0010, 310 = 0011

 “Carry-save” addition can help

310 0011
 Carry-save addition passes (saves)
+ 210 0010 carry-save add
the carries to the output, rather than
propagating them c 0100 = 410
s 0001 = 110
carry-save add
310 0011
c 0010 = 210
carry-propagate add s 0110 = 610
1000 = 810
 In general, carry-save addition takes in 3 numbers and produces 2
 Whereas carry-propagate takes 2 and produces 1
 With this technique, we can avoid carry propagation until final addition
11

Carry-Save Circuits

CSA
FA FA FA FA FA FA FA FA 0

x2
c sc sc sc sc sc sc sc sc
CSA
 When adding sets of numbers, x1
carry-save can be used on all but CSA
the final sum x0
CSA
 Standard adder (carry propagate)
is used for final sum
CPA

12
Carry-Save Adder: Structure
 Postpone the “carry propagation” operation to the last stage

Delay = N⋅tcarry +
tAND + HA HA HA HA
tmerge

HA FA FA FA

CSA HA FA FA FA

Vector merging stage

HA FA FA HA

13

Carry-Save Adder: Details

2-input AND gate

H Half-Adder

F Full-Adder

A3 A2 A1 A0

× B3 B2 B1 B0
A3 B0 A2 B0 A1 B0 A0 B0
H H H
A3 B1 A2 B1 A1 B1 A0 B1

A3 B2 A2 B2 A1 B2 A0 B2
F F F
A3 B3 A2 B3 A1 B3 A0 B3

F F F

S7 S6 S5 S4 S3 S2 S1 S0 F F H

S7 S6 S5 S4 S3 S2 S1 S0

14
Array Mult. using Carry-Save Addition
b3 0 b2 0 b1 0 b0 0

a0 bj sum in
0 0 0
0
0 ai
P0
a1
0
0
P1 FA
a2 carry carry
0
out in
0
P2
a3 sum out
0

P3

1
Fast carry-propagate adder
0 (e.g., carry-select adder,
carry-lookahead adder)
P7 P6 P5 P4

15

Another Representation
Sum In X Cin Building block: Full Adder + AND
Y
FA
A B
CO CI
S

Cout Sum Out A3 A2 A1 A0

B0
A3 B0 A2 B0 A1 B0 A0 B0
C C C C
S S S S
B1
A3 B1 A2 B1 A1 B1 A0 B1
C C C C
S S S S
B2
A3 B2 A2 B2 A1 B2 A0 B2
C C C C
S S S S
B3
A3 B3 A2 B3 A1 B3 A0 B3
C
S S S S
Add P7 P6 P5 P4 P3 P2 P1 P0

CPA 4 × 4 array of building blocks

16
Carry-Save Addition
CSA is associative and commutative. For example:
(((X0 + X1) + X2 ) + X3 ) = ((X0 + X1) +( X2 + X3 ))

• A balanced tree can be used to

reduce the logic delay

• This structure is the basis of the

Wallace Tree Multiplier

• Partial products are summed with

the CSA tree. Fast CPA (ex: CLA)
is used for final sum.

• Multiplier delay ∝ log3/2N + log2N

17

Signed Multiplication
 So far, we have dealt with unsigned integer multiplication
 Version 1 of Signed Multiplication
 Convert multiplier and multiplicand into positive numbers
 If negative, then obtain the 2's complement and remember the sign
 Perform unsigned multiplication
 Compute the sign of the product
 If (product sign < 0) then obtain the 2's complement of the
product  Need one more step

 Efficient Version:
 Using almost same hardware for unsigned multiplication
 No additional step of 2’s complement of the final result
18
Multiplying Signed Numbers
 Coding of the numbers
 Signed-magnitude  trivial
 2’s complement?
 2’s complement
 Multiplier positive, Multiplicand +/− :
 Sign extend the partial products when adding up
 Example:

0 1 0 1 +5 × 1 0 1 1 −5 ×
0 0 1 1 +3 0 0 1 1 +3
0 1 0 1 1 1 1 1 0 1 1
0 1 0 1 1 1 1 0 1 1
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 +15 1 1 1 0 0 0 1 −15

19

Multiplying Signed Numbers (cont.)

 2’s complement (cont.)
 Multiplier negative, Multiplicand +/− :
 Ad-hoc solution: convert negative Multiplier to positive, do the multiplication,
negate the result
 Example:

1 01 1 −5 × 1 0 1 1 −5 ×
1 1 01 −3 0 0 1 1 +3
1 1 1 1 0 1 1
1 1 1 0 1 1
0 0 0 0 0
000 0
1 1 1 0 001 −15

0001 1 1 1 +15
20
Multiplying Signed Numbers: Efficient Method
 Using almost the same architecture, we can do signed mult. w/o negating the result
 Idea: “What if we had negated the multiplier?”

Multiplicand M 0 1 01 = +5 ×
Multiplier 1 α 1 101 = −3
 Consider α as positive magnitude (forget about the 2’s complement convention for now)
 It means α = 5.
 We want to use computation: α ⋅ M
 By negating 1 α to get 0 β , then computed β ⋅ M and negated it

negate
1 1 0 1 = −3 0 0 1 1 = +3
α β
21

Multiplying Signed Numbers: Efficient Method

 The negation process
k−1 k−2 . . . 1 0 k−1 k−2 . . . 1 0
1 α = − 0 β
negate
1 α = 2k−1 + α

− 1 α = 2k – 1 α
= 2k − (2k−1 + α) = 2k – 2k−1 − α
= (2k − 2k−1) − α = 2k−1 − α
= 0 β  β= 2k−1 − α
22
Multiplying Signed Numbers: Efficient Method
Our interpretation
Machine’s understanding

k−1 k−2 . . . 1 0 k−1 k−2 . . . 1 0

1 α = − 0 β β= 2k−1 − α
3 2 1 0 3 2 1 0
1 1 0 1 = − 0 0 1 1 3 = 23 − 5
 We used to compute: −(β ⋅ M)
− β ⋅ M = − (2k−1 − α ) ⋅ M = −2k−1 ⋅ M + α ⋅ M

Subtract the multiplicand for the last bit

Normal mult for the first k−1 bits

23

Multiplying Signed Numbers: Example

Normal mult
0 1 0 1 +5 ×
for the first k−1 bits 1 1 0 1 −3
0 1 0 1
0 0 0 0
Use a subtractor
0 1 0 1
for the last 1 0 1 1 (−5)
partial product
1 1 1 0 0 0 1 −15

24
Summary: Signed Multiplier
Signed Multiplication:
Remember for 2’s complement numbers; the MSB has negative weight:

𝑋= 𝑥 2 −𝑥 2

e.g.: −610 = 110102 = 0⋅20 + 1⋅21 + 0⋅22 + 1⋅23 − 1⋅24

= 0 + 2 + 0 + 8 − 16 = −6
 Therefore, for multiplication:
a) subtract final partial product
b) sign-extend partial products
 Modifications to unsigned multiplication:
a) adder/subtractor
b) sign-extender

25

Summary: Signed Multiplication

multiplicand 1101 (−3)

multiplier × 1011 (−5)
11111101 +(−3) Note: 2’s complement &
+ 11111010 +(−6) sign extension
+ 00000000
− 1 1101000 −(−24)
00001111 (15)

26
Signed Array Multiplier

b3 0 b2 0 b1 0 b0 0

a0

0
Implicit
Sign P0
a1 We can specify
extension
this as ‘1’ for
0
accounting 2’s
P1 complement
a2 adder for the
subtractor
0
P2
a3
Subtractor − − − −
0
P3

P7 P6 P5 P4

27

Multiplication in Verilog
 You can use the “∗” operator to multiply two numbers:
wire [9:0] a, b;
wire [19:0] result = a * b; // unsigned multiplication!

 However, we cannot guarantee the efficiency of the synthesized result in

terms of speed and area.
 Therefore, a structural description is recommended for the multiplier.
 If you want Verilog to treat your operands as signed 2’s
complement numbers, add the keyword signed to your wire or
reg declaration:
wire signed [9:0] a, b;
wire signed [19:0] result = a * b; // signed multiplication!

28
Summary
 2’s complement number systems
 Algebraic and corresponding bit manipulations
 Overflow detection
 Significance of “sign bit” : 2n−1
 Carry lookahead is form a parallel prefix
 Time / Space tradeoffs
 Bit serial adder
 Binary Multiplication algorithm
 Array multiplier
 Serial multiply (with bit parallel adder)
 Signed multiplication
 Sign extend multiplicand
 Sign bit of multiplier treated as subtract

29

Announcements
 Homework #6 (Due: Next Week)
 Textbook Problems: 4.1, 4.3, 4.8, 4.11, 4.14

30