Integer Multiplication with Overflow Detection or Saturation.
AbstractHigh-speed multiplication is frequently used in general-purpose and application-specific computer systems. These systems often support integer multiplication, where two $n$-bit integers are multiplied to produce a $2n$-bit product. To prevent growth in word length, processors typically return the $n$ least significant bits of the product and a flag that indicates whether or not overflow has occurred. Alternatively, some processors saturate results that overflow to the most positive or most negative representable number. This paper presents efficient methods for performing unsigned or two's complement integer multiplication with overflow detection or saturation. These methods have significantly less area and delay than conventional methods for integer multiplication with overflow detection or saturation.
Introduction
1.1 Multiplication
Multiplication is an essential arithmetic operation for general purpose computers
and digital signal processors. High-performance systems support parallel multiplication
in hardware. Various high-speed parallel multipliers have been proposed and
realized. Most parallel multiplier designs can be divided into two classes; array
multipliers and tree multipliers. Array multipliers consist of an array of similar cells
that generate and accumulate the partial products [3]. Tree multipliers generate all
partial products in parallel, use a tree of counters to reduce the partial products
to sum and carry vectors and then sum these vectors, using a fast carry-propagate
adder. Several methods have been developed for reducing the partial products [1],
[2],
The regular structure of array multipliers facilitates their implementation in
VLSI technology. The delay of array multipliers, however, is proportional to the
operand length. On the other hand, tree multipliers offer a delay proportional
to the logarithm of the operand length. The main drawback of tree multipliers is
their irregular interconnection structure, which makes them difficult to implement in
VLSI. Thus, tree multipliers are preferred for high performance systems, while array
multipliers are preferred for systems requiring less area. New implementations and
optimizations of parallel multipliers are still active research areas [5]. More detail
descriptions of array and tree multipliers are given in the next chapter.
1.2 Overflow
To avoid grow in word length, most instruction set architectures and high-level languages
require that arithmetic operation return results with the same length as their
input operands. If the result of an integer arithmetic operation on n-bit numbers
cannot be represented by n bits, overflow occurs and needs to be detected. For
integer multiplication, the method for overflow detection also depends on whether
the operands are signed or unsigned integers. For unsigned multiplication, overflow
only occurs if the result is larger than the largest unsigned n-bit number. For signed
integer multiplication overflow also occur if the result is smaller than the minimum
representable n-bit number. For two's complement multiplication there is also a
difference between fractional and integer overflow detection. Since overflow only
occurs for two's complement fractional numbers when \Gamma1 is multiplied by \Gamma1, it is
easy to detect overflow when multiplying two's complement fractions.
It is an important design issue in computer architecture is to decide what to do
when overflow occurs. Typically, overflow results in an overflow flag being set. This
overflow flag can then be used to signal an arithmetic exception [9].
1.3 Saturation
In most general purpose processors, overflow is handled by setting an exception
flag. More recent implementations for digital signal processing and multimedia
applications saturate results that overflow to the most positive or most negative
representable number [11], [12]. For two's complement integers this is \Gamma2
negative numbers and 2 positive numbers. For unsigned integers, results
that are too large saturate to 2
1.4 Thesis Overview
Previous studies have focussed on overflow detection in two's complement addition
[13], multi-operand addition [14], fractional arithmetic operations [10] and generalized
signed-digit arithmetic[15]. This thesis presents efficient techniques for integer
multiplication with overflow detection or saturation. Most existing computers detect
overflow in integer multiplication by a computing 2n-bit product and then testing
the most significant bits to see if overflow has occurred. The methods proposed in
this thesis only calculate n or n bits of the product. This leads to a significant
reduction in area and delay.
Chapter 2 presents array multipliers, tree multipliers, and conventional methods
for overflow detection. Chapter 3 introduces new methods for overflow detection and
saturation for unsigned integer multiplication. Chapter 4 focuses on overflow detection
and saturation for two's complement integer multiplication. Chapter 5 presents
the component counts and area and delay estimates for unsigned and two's complement
parallel multipliers that use either the conventional or the proposed methods
for overflow detection. Chapter 6 discusses future work and gives conclusions.
Chapter 2
Previous Research
2.1 Unsigned Parallel Multipliers
Multiplication of two n-bit unsigned numbers is shown in Figure 2.1, where
Multiplication produces a 2n-bit product. If the n least significant bits are
used for the result, then overflow occurs when the actual product uses more than n
bits. In other words, overflow occurs when the product is greater or equal to 2 n .
With conventional methods, overflow is detected after the 2n-bit result is pro-
duced. This is done by simply logically ORing together the n most significant bits,
a n-2
a n-1 n-2
a n-1
a n-2 n-2
a n-1 a n-2b b 1
a n-1 a n-2b b 0

Figure

2.1: Multiplication of A and B.
such that
where V is one if overflow occurs and + denotes logical OR. Although calculating
2n product bits and then detecting overflow leads to unnecessary area and delay,
most computers that provide integer multiplication with overflow detection use this
approach. If the system requires saturation, the saturated least significant product
bits are computed as
which sets the product to 2 n\Gamma1 when overflow occurs.
2.1.1 Unsigned Array Multipliers
In general, array multipliers are slower than tree multipliers. In spite of this speed
disadvantage, however, array multipliers are often used due their regular layout, low
area, and simplified design.
A block diagram of an unsigned 8 by 8 array multiplier is shown in Figure 2.2.
Each diagonal in Figure 2.2 corresponds to a column in the multiplication matrix,
in

Figure

2.1. A modified half adder (MHA) is a half adder with an AND gate,
and a modified full adder (MFA) is a full adder with an AND gate. The AND gates
generate the partial products. Full adders and half adders add the generated partial
products. Sum outputs are connected diagonally and carry outputs are connected
vertically. The last row of adders, which are connected from left to right, generates
the n-most significant product bits . The critical path through this multiplier is
shown with dashed lines. Since almost half of the latency is due to the bottom row
of adders, this row may be replaced by a fast carry-propagate adder. Although this
decreases the overall delay, it has a negative impact on the design's regularity. An
n by n unsigned array multiplier uses n 2 AND gates, (n HAs.
The conventional method for overflow detection requires the n most significant
product bits to be calculated. These product bits are then OR'ed together to produce
the overflow flag, as shown in Figure 2.2. The conventional method for saturating
multiplication is accomplished by ORing V with p 0 to p n\Gamma1 , as shown in

Figure

2.3.
AND AND AND AND AND
AND AND
AND
AND
AND
AND
AND
AND MHA MHA
MHA MHA MHA MHA MHA
MFA MFA MFA MFA MFA MFA MFA
MFA
MFA
MFA
MFA
MFA
MFA
MFA
MFA
MFA
MFA
MFA MFA MFA MFA MFA
MFA
MFA
MFA
MFA
MFA MFA MFA MFA
MFA
MFA
MFA
MFA MFA MFA
MFA
AND
MFA
MFA
FA
c s
FA
c s
FA
c s
AND
MFAa 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
MFA
MFA
HA
c s
FA
c s
FA
c s
FA
c s

Figure

2.2: Unsigned Array Multiplier with Conventional Overflow Detection.
AND
AND
AND
AND
AND
MHA MHA MHA MHA
MHA MHA MHA
MFA MFA MFA MFA MFA MFA MFA
MFA
MFA
MFA
MFA
MFA
MFA
MFA
AND
MFA
MFA
MFA MFA MFA MFA MFA
MFA
MFA
MFA
MFA
MFA MFA MFA
MFA
MFA
MFA
MFA MFA MFA
MFA
MFA
MFA
MFA
MFA
FA
c s
FA
AND
AND
AND
AND
MFA
FA
AND
AND
AND
AND
a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c
c
c
c
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
MFA
MFA
HA
c
FA
c s
FA
c s
FA
c s

Figure

2.3: Unsigned Array Multiplier with Conventional Saturation.
2.1.2 Unsigned Tree Multipliers
Tree multipliers have three main parts; partial product generation, partial product
reduction, and final carry-propagate addition. Various reduction schemes have been
developed over the years. Two of the most well-known methods for multiplier tree
designs are those proposed by Wallace [2] and Dadda [1]. Wallace's strategy combines
three rows of partial product bits using (3; 2) and (2; 2) counters to produce
two rows. Dadda's strategy leads to a simpler counter tree but requires a larger
final carry-propagate adder. There are hybrid approaches between these two methods
that offers cost and speed trade-offs for VLSI implementations. These reduction
schemes differs in the number and placement of counters in the tree and the size
of the final carry propagate adder. The tree multipliers presented in this thesis use
Dadda's method, since it allows component counts to easily be determined based on
n. Since our overflow detection method does not depend on the reduction strategy,
similar savings are expected for other tree multipliers.

Figure

2.4 shows a dot diagram of an 8 by 8 unsigned array multiplier. Dot
diagrams are often used to illustrate reduction strategies in tree multipliers [2].
With this technique, a dot represents a partial product bit, a plain diagonal line
represents a full adder and a crossed diagonal line represents a half adder. The
two bottom rows of the dot diagram corresponds to sum and carry vectors that are
combined using the final carry-propagate adder to produce the product.
Dadda multipliers require n 2 AND gates, (n and a
Figure

2.4: Dadda Reduction Scheme.
CPA. The number of stages, based on n; is shown in Table 2.1.
For example a 24 by 24 Dadda multiplier requires seven reduction stages. The
worst case delay path is equal to the delay of partial product generation, plus the
delay for the reduction stages, plus the delay for the final carry-propagate addition.
With the conventional method, overflow is detected with a tree of (n \Gamma 1) 2-input
gates. The delay of the tree of OR gates is equivalent to dlog 2 ne 2-input OR
gates, as shown in Figure 2.5.
Range of n s
43

Table

2.1: Number of Stages s for n-Bit Dadda Tree Multipliers.V101214
pp

Figure

2.5: Tree of 2-input OR Gates for
2.2 Two's Complement Multipliers
Two's complement numbers A and B and their product P have the values
where
\Gammab
a
a
overflow occurs when
Multiplication of two's complement numbers generates signed partial products as
shown in Figure 2.6. Since a negative
weights, they should be subtracted, rather than added. This makes the design
difficult to implement because it requires adder and subtracter cells. Consequently,
several techniques have been proposed to handle partial products with negative
and positive weight, such as the Baugh-Wooley Algorithm[6] and its variations [7],
[8] and, Booth's Algorithm [16]. The Baugh-Wooley algorithm provides a method
a 1 a 0
- a
- a a 0
a 1
a 0 n-1
x
a n-1
a a

Figure

2.6: Two's Complement Multiplication Matrix.
for modifying the partial product matrix, so that all the partial product bits have
positive weights. This algorithm and its modified form are often used to perform
two's complement multiplication.b b 1
a n-1
a
a
a 1 b n-2 a
a
a n-2
a n-1 n-2
bn-1a n-2 n-2
a

Figure

2.7: Modified Two's Complement Multiplication Matrix.
Two's complement multiplication is often realized using a variation of the Baugh-
Wooley algorithm called the Complemented Partial Product Word Correction Al-
gorithm. With this implementation, partial product bits containing a
but not both, are complemented and ones are added to columns n and 2n \Gamma 1. This
is equivalent to taking the two's complement of the two negative terms in Equation
2.5. The multiplication matrix for this implementation is shown in Figure 2.7.
2.2.1 Two's Complement Array Multipliers
The design of an array multiplier that uses the Complemented Partial Product Word
Correction Algorithm and conventional overflow detection is shown in Figure 2.8.
The design shown in this figure is similar to the unsigned array multiplier design in

Figure

2.2. AND gates in the left-most column are replaced by NAND gates and
the last row of MFAs are replaced by Negating Modified Full Adders (NMFA). The
specialized half adder (SHA) in the bottom right corner is a half adder that takes
the sum and carry bits of the previous row and adds them with '1'. This cell has
approximately the same area and delay as a regular half adder. The last product
bit p 2n\Gamma1 is inverted to add the one in column 2n \Gamma 1. Inverting p 2n\Gamma1 has the same
effect as adding one in column 2n \Gamma 1, because the carry out from this column is
ignored.
In

Figure

2.8, the bottom two rows of cells, consisting of n XOR gates and
gates, are dedicated to overflow detection. The XOR gates identify whether
differs from any of the more significant product bits p n to outputs
from the XOR gates are combined to determine if the overflow flag V should be set.
The logic equation for the overflow detection flag is
AND
MHA MHA MHA MHA MHA
MHA
MFA MFA
AND
MFA MFA MFA MFA
MHA
MFA
MFA
MFA
MFA
MFA
MFA
AND
MFA MFA MFA MFA MFA
MFA
MFA
MFA
MFA MFA
MFA MFA
MFA
MFA MFA MFA
MFA
MFA
MFA
MFA
AND
MFA
MFA
bb AND
AND
a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
FA
c s
FA
c s
FA
c s
AND
AND NMFA NMFA NMFA NMFA NMFA NMFA NMFA
FA
c s
FA
c s
FA
c s

Figure

2.8: Two's Complement Array Multiplication with Conventional Overflow
Detection.
Saturating multiplication is implemented by adding an n-bit 2-to-1 multiplexer,
as shown in Figure 2.9. For two's complement multiplication, if the product over-
flows, the saturated product is determined from the sign bits of A and B. If
and a negative overflow has occurred and the product saturates
to \Gamma2 On the other hand, if positive overflow has
occurred and the product saturates to 2 then overflow has not
MFA
MFA
MFA
MFA
MFA MFA
MFA
MFA
MFA
MFA MFA
MFA
MFA
MFA
MFA MFA
MFA
MFA
MFA
MFA
MFA
MFA
AND
MFA
c
MFA
c
c s
c
c s
MFA
MFA
MFA
MFA
MFA
MFA
MFA
MFA
MHA
MHA
MHA
MFA
c
s
MHA
MHA
MHA
c
AND
ANDpAND
AND
AND
a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0
c
c
c
c
c
c
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c
c
c
c
c
c
c
FA
c s
FA
c s
FA
c s
AND
NMFA NMFA NMFA NMFA NMFA
FA
c s
FA
c FA
c s
MFA
MFA
n-bit
Mux
XAND

Figure

2.9: Conventional Two's Complement Saturation.
occurred and the saturated product is the n least significant bits. If
the saturated product
2.2.2 Two's Complement Tree Multipliers
Several techniques are available for implementing two's complement multiplier trees
[4], [8].

Figure

2.7 shows the dot diagram of an 8 by 8 two's complement multiplier
tree that uses the Complemented Partial Product Algorithm [8] and Dadda's reduction
method [1]. Similar to the two's complement array multiplier, (2n \Gamma 2) of the
partial product bits are inverted and ones are added to columns n and (2n \Gamma 1): Although
it seems that the heights of these two columns are increased by adding ones,
this does not effect adversely the design, because the most significant product bit is
simply inverted and a SHA adds one in the column n. In Figure 2.10, a dot with a
line above it indicates a complemented partial product bit and the circled half adder
in column 8 is a (SHA) specialized half adder. An n by n two's complement Dadda
tree multiplier has
FAs, and a (2n \Gamma 2) bit CPA.
Conventional techniques for overflow detection and saturation for two's complement
tree multipliers are similar to the techniques used for two's complement array
multipliers. The only difference is that tree multipliers tend to use a tree of OR
gates, rather than a linear array of OR gates, when computing the overflow flag.
Figure

2.10: Two's Complement Dadda Tree Multiplier.
Chapter 3
Overflow Detection and
Saturation for Unsigned Integer
Multiplication
3.1 General Design Approach
Instead of computing all 2n bits of the product, the methods proposed in this thesis
only compute the n least significant product bits and have separate overflow detection
logic, as shown in Figure 3.1. Carries into column n are also used in the
overflow detection circuit.
The main idea behind the proposed unsigned overflow detection methods is that
overflow occurs if any of the partial product bits in column n to (2n \Gamma 2) are '1' or any
OVERFLOW
DETECTION
RESULT
OPERAND A OPERAND B
n by n
MULTIPLIER

Figure

3.1: Block Diagram for Unsigned Multiplication Overflow Detection.
of the carries into column n are '1'. Consequently, these ones can be detected without
adding the partial products. The logic equation for unsigned overflow detection is
a
In this expression, V is the overflow flag, c i is the i th carry into column n, bit summations
corresponds to logical ORs and bit multiplications corresponds to logical
ANDs.
3.2 Unsigned Array Multipliers with Overflow Detection
or Saturation

Figure

3.2. shows an 8 by 8 multiplication matrix to demonstrate how the partial
product bits are used to detect overflow with the proposed method.
PARTIAL PRODUCTS USED FOR OVERFLOW DETECTION
a b 0
a
a b 0
a a
a b 0
a b
a b
a b
a b
a b
a b
a b 1357 a 0 b 1111a b
a b
a b
a b
a b
a b
a b 1357 a 0 b 2222a b
a b
a b
a b
a b
a b
a b 1357
a b
a b
a b
a b
a ba
a b 1357
a b
a b
a b
a b
a b
a b
a b 1357
a b
a b
a b
a b
a b
a b
a b 1357
a b
a b
a b
a b
a b
a b
a b 1357 a 0 b
a
a
a
a
a

Figure

3.2: 8 by 8 Unsigned Multiplication Matrix.
Using Equation 3.1, with
Common terms in the logic equation for overflow detection are used to reduce the
hardware needed to detect overflow. An overflow detection circuit constructed using
AND and OR gates is shown in the Figure 3.3 for an 8 by 8 unsigned multiplication.
For an n by n multiplier, the three gates in the dashed lines are replicated
times. These three gates are combined to form an overflow detection (OVD) cell.
Overflow is detected using the following iterative equations.
is a temporary OR bit with an initial value of
and v i is a temporary overflow bit with an initial value . The
are shown in Figure 3.3.
An OVD cell takes a inputs and generates
outputs. Each OVD cell contains one AND gate, one 2-input OR gate, and one 3-
input To form an unsigned multiplier with the proposed overflow detection
method, these cells are combined with an unsigned array multiplier from which the
cells used to compute p n to p 2n\Gamma1 have been removed. This is shown in Figure 3.4
for an 8 by 8 unsigned array multiplier.
b246 a
a
a
a
a
aa 7b
c c

Figure

3.3: Proposed Overflow Detection Logic for
An n-bit unsigned array multiplier that uses the proposed method for overflow
detection requires (n 2
FAs. This corresponds to (n
gates than the conventional
method.
The worst case delay path is indicated by the dashed line in Figure 3.4. Since a
MFA has longer delay than an OVD cell, the unsigned multiplier with the proposed
overflow detection logic has a delay approximately half as long as the unsigned
multiplier with conventional overflow detection, shown in Figure 3.3.
Unsigned saturating multiplication using the proposed method is performed by
ORing the overflow bit with n least significant product bits, as shown in Figure 3.5.
If the overflow bit is '1' this produces a product with n ones, which corresponds to
the maximum representable unsigned number; otherwise the product is not changed.
This requires n more OR gates and the worst case delay increases by one
delay.
AND AND AND AND AND
AND MHA MHA MHA MHA MHA MHA
MFA MFA MFA
MHA
MFA MFA
MFA MFA MFA MFA MFA
MFA MFA MFA MFA
MFA MFA MFA
MFA
AND
MFAo 7v
AND
AND
a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
MFA
OVD
OVD
OVD
OVD
OVD
cccc
OVD
c

Figure

3.4: Unsigned Array Multipliers with Proposed Overflow Detection Logic.
MFA MFA MFA MFA
MFA MFA
MFA
MFA MFA
MFA MFA MFA MFA
MFA
MFA
MFA
MFA
MFA
MFA
MHA
MHA
MHA
MHA
MHA
MHA
MHA
AND
AND
AND
AND
a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
MFA
OVD
OVD
OVD
OVD
OVD
cccc
OVD
c
AND
AND
AND
AND
AND

Figure

3.5: Unsigned Array Multipliers with Proposed Saturation Logic.
3.3 Unsigned Tree Multipliers with Overflow Detection
or Saturation.
For unsigned tree multipliers, the technique of using an array of OVD cells with
linear delay does not work well, since the OVD cells would significantly increase the
multipliers' worst case delay path. Instead, all n 2 partial product bits are generated
and a tree of OR gates is used to determine if any of the partial product bits in
columns n to 2n\Gamma1 or any carries into column n are one. This method is shown for an
8 by 8 multiplier in Figure 3.6, where the symbol 'o' denotes the output of a 2-input
gate. Although this method requires more hardware for overflow detection than
the unsigned array multiplier, the overflow detection logic has logarithmic delay and
no longer contributes significantly to the critical path. An n by n unsigned array
multiplier that uses this method has (n 2
HAs, and (n FAs. Since the delay of the OR gates for overflow detection
is less than the delay of the partial product reduction stages, the worst case delay
is equal to the delay of partial product generation, plus partial product reduction,
plus an (n \Gamma 1)-bit carry-propagate addition plus one OR gate delay to include the
final carry out. Saturating multiplication is performed with the same method that
is used by the array multiplier. The overflow bit is OR'ed with the n least significant
bits of the product.
Figure

Unsigned Tree Multiplier with Proposed Overflow Detection Logic.
Chapter 4
Overflow and Saturation
Detection for Two's Complement
Integer Multiplication
4.1 General Approach
The proposed method for overflow detection in two's complement multiplication
detects the number of consecutive bits that are equal to the sign bit. Essentially,
this method counts the number of leading zeros if the operand is positive and the
number of leading ones if the operand is negative. For example, 11100101 has three
leading ones and 00001001 has four leading zeros. This method works because the
number of leading zeros or ones indicates the magnitude of the operand; operands
with more leading zeros or ones have smaller magnitudes and therefore are less likely
to cause overflow. The main issue is to determine how many of leading zeros and
leading ones are needed to guarantee that overflow will occur or that overflow will
not occur. A block diagram that shows the proposed approach is shown in Figure
4.1.
The analysis for two's complement multiplication has three cases depending on
the operands' signs; both operands positive, both operands negative, or one positive
and the other negative. Overflow regions for these three cases are discussed in the
following sections.
Case 1: Both Operands are Positive
Let ZA denote the number of leading zeros of operand A and ZB denote the number
of leading zeros of operand B. Since both operands are positive n-bit integers, they
have at least one and at most n leading zeros, which can be expressed as
The ranges for operand A and operand B in terms of the number of the leading
zeros are expressed as
OVERFLOW
DETECTION
OPERAND A OPERAND B
MULTIPLIER
n by n

Figure

4.1: Block Diagram of The Proposed Method for Two's Complement Multiplication
with Overflow Detection.
Overflow occurs for Case 1 when overflow does not occur
when . Based on (4.2) the range of P is
Using (4.3), overflow is guaranteed to occur when
To determine the number of leading zeros in A and B that guarantee overflow, (4.4)
is rewritten as
Taking the base 2 logarithm of both sides gives
or equivalently,
Thus, if A and B together have less than n leading zeros, overflow must occur.
Similarly, overflow is guaranteed not to occur when
To determine the number of leading zeros in A and B that guarantee overflow does
not occur, Equation 4.8 is rewritten as
since \Gamma2 n\GammaZ A - \Gamma1 and \Gamma2 n\GammaZ B - \Gamma1,
Consequently, overflow is guaranteed not to occur if
Taking the base 2 logarithm of both sides gives
or equivalently
Using
which is always true since ZA - 1 and ZB - 1. Therefore, 4.13 can be rewritten as
Thus, overflow is guaranteed not to occur if A and B together have more than n
leading zeros.
cannot be directly determined whether or not overflow
has occurred only by examining the number of leading zeros. Rewriting (4.3) for
This problem however can be solved by further analyzing what happens when ZA
n. The results obtained so far are summarized in Figure 4.2.
overflow no overflow
undetermined

Figure

4.2: Overflow Regions for ZA
To Determine whether or not overflow occurs when is necessary to
calculate how many product bits are needed to represent the result when ZA
n. Then by using the most significant product bits and the sign bits of the operands
the overflow flag is set. If n is even, the maximum product is
or equivalently
If n is odd the maximum product is
or equivalently
Thus, when ZA can always be represented with n bits and overflow can
be determined simply by examining the sign bit p n\Gamma1 . If p
Otherwise, overflow does not occur.
4.1.2 Case 2: Both Operands are Negative
Let I A denote the number of leading ones of operand A and I B denote the number
leading zeros of operand B. Since both operands are negative n-bit integers, they
have at least one and at most n leading ones. This can be expressed as
The ranges for A and B in terms of leading ones are expressed as
\Gamma2 n\GammaI A - A - \Gamma(1
Overflow occurs for Case 2 when overflow does not occur
when . Based on (4.22) the range of P is
Using (4.23), overflow is guaranteed to occur when
To determine the number of leading ones in A and B that guarantee overflow occurs
(4.24) is rewritten as
since
values that satisfy
also satisfy (4.25), Taking the base 2 logarithm of both sides of (4.27) gives
I A
Thus, for negative integers overflow occurs when operands have less than
leading ones.
Using (4.23) overflow is guaranteed not to occur when
Taking the base 2 logarithm of both sides of Equation 4.29 gives
Thus, overflow is guaranteed not to occur when A and B together have more than
leading ones.
When cannot be directly determined if overflow has
occurred. This is seen by using in (4.23), which gives
similarly when
The results so far are shown in Figure 4.3.
undetermined no overflow
overflow

Figure

4.3: Overflow Regions for I A
When I A is even, the maximum result is
when n is odd, the maximum product is
can be represented using only n bits,
except when occurs
when
4.1.3 Case 3: When The Signs of The Operands Differ
Let I A denote the number of leading ones in operand A and ZB denote the number
of leading zeros in operand B. Negative operand A has at least one and at most n
leading zeros and positive operand B has at least one and at most n leading ones.
This can be expressed as
The ranges for A and B in terms of leading ones and zeros are
\Gamma2 n\GammaI A - A - \Gamma(1
Overflow occurs for Case 3 when P - \Gamma2 and does not occur when P - \Gamma2
Based on (4.36) the range of P is
Using Equation 4.37, overflow is guaranteed to occur when
or equivalently
For I A +ZB , (4.39) is always true, since 2
Using 4.37 overflow is guaranteed not to occur when
\Gamma2
or equivalently
For
in this range.
When cannot be determined whether or not overflow occurred
since for
The

Figure

4.4 shows graphically the results obtained so far for Case 3.
overflow no overflow
undetermined

Figure

4.4: Overflow Regions for I A + ZB .
When I A is even, the minimum negative number is
and when is n is odd it is
For both cases, the product can be represented using only by n bits. Therefore,
overflow occurs if p
So far, the proposed method has been explained mathematically. In the next
section implementations of the overflow logic are presented.
4.1.4 Overflow Detection Logic
To allow positive and negative operands to use the same hardware for detecting
leading zeros or ones, the sign bits are XNOR'ed with the remaining bits.
This takes gates and is expressed logically as
A logic design that detects (n \Gamma 1) or fewer leading zeros or leading ones includes
gates. These AND gates are used to compute
Y
ba (n\Gammak)\Gamma2 (4.47)
Y
For 3: A preliminary overflow flag is generated, using x(i) and y(i)
as
where bit products correspond to logical ANDs, and bit summations correspond to
logical ORs. This equation is implemented by using (n \Gamma 2) 2-input NOR gates and
gates. V 1 is one when the total number of leading zeros and
leading ones is less than n: In this case, overflow is guaranteed to occur. Additional
logic is used to detect overflow for the undetermined regions for Cases 1-3.
For Case 1 (when a
is detected as
For Case 2 when a
neither A nor B is zero, or the n least significant bits are zero.
For Case 3, (when
neither A nor B is zero. This is detected as
Logic Equations 4.50 through 4.54 can be realized by 9 2-input AND gates, 4
inverters and (n gates. The final overflow flag V is generated by OR'ing all
of the previous flags.
The overflow detection circuit requires, (2n \Gamma
gates, and four
inverters. An overflow detection circuit for an 8-bit two's complement multiplier is
shown in Figures 4.5 and 4.6.
bb
a 7 a 7 a 7 a 7 a 7
a 7 a a 7 a a a a

Figure

4.5: The Logic for V 1 for 8-bit Multiplication.
a 7y
aN LEAST SIGNIFICANT
a
z

Figure

Detection Logic for 8-bit Two's Complement Multiplication.
4.1.5 An Alternative Method
An alternative method for detecting overflow in the undetermined case is, instead
of generating product bits, have the multiplier generate
product bits and detect the undetermined cases by checking if p n \Phi p
approach is shown in Figure 4.7. This approach works since for the undetermined
cases we have the following situations;
only when overflow occurs.
(2) Case 2: overflow occurs. The one
exception is when generated and then p
(3) Case 3: only when overflow occurs. For all three
cases, overflow can be detected as
4.2 Two's Complement Array Multipliers with Overflow
Detection or Saturation
The proposed method for overflow detection for array multipliers requires half as
much hardware as the conventional method. An 8-bit two's complement multiplier
n by n
MULTIPLIER
OPERAND A
DETECTION
Figure

4.7: Block Diagram of the Proposed Alternative Method for Two's Complement
Multiplication with Overflow Detection.
with the proposed method for overflow detection is shown in Figure 4.8. The X2A
cell contains one 2-input XOR gate and one 2-input AND gate, and each X3A cell
contains one 3-input XOR gate and one 2-input AND gate, an X3NA contains two
2-input XOR gate and one 2-input NAND gate.
A two's complemented array multiplier with the proposed overflow detection logic
3-input XOR gates, one 2-input XOR gate and four inverters.
The delay for this multiplier is approximately equal to the delay of (n \Gamma
plus four 2-input OR gates, plus three 3-input AND gates. The actual delay may
differ according to various design decisions and the technology used.
OVERFLOW DETECTION
MFA MFA MFA MFA
MFA MFA
MFA
MFA
MFA
b 7b MFA
a 7
a 5 a 3 a 1 aa 4
MFAa 7 a 6 a 5
4 a 3 a 2
a
MFA
MFA
MFA
MHA
MHA
a
MHA
a a
MHA
MHA
MHA
AND
AND
AND
AND
AND
AND
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
c s
NAND AND
s
s
s
s
s
s
s

Figure

4.8: Overflow Detection Logic for 8-bit Two's Complement Multiplication.
Two's complement saturating multiplication is performed by using the V and
t flags. These flags are used as inputs to an n-bit 2-to-1 multiplexer as shown
in

Figure

4.9. When negative overflow occurs, the result is saturated to \Gamma2
positive overflow occurs, result is saturated to 2
Adding saturation logic to the array multiplier with overflow detection only requires
the addition of an inverter and an n-bit 2-to-1 multiplexor. Since V and t are
already generated by the overflow detection logic, they do not require any additional
hardware. The delay increases just by the delay of a 2-to-1 multiplexer plus the delay
of an inverter.
OVERFLOW DETECTION
AND
c s
c s
c
c
c
MFA 6
c
s
s7s
s
MFAb 432
a 7
MFA
MFA
a 5 a 4 a
a 2 a 1
a 7 a 6
MFA
MFA
MFA
MFA
MFA
MFA
MFAb
MFA
MFAMFA
MHA
MHA
MHA
MHA
MHA
AND
AND
AND
AND
AND
c s
c s
c s
c s
c s
c s
c s
c s
NAND AND
MFA
n-bit
Mux
s
s
s
s
s
s
a 6 a 5 a 4 a 3 a 2 a 1 a 07 5 4 2
Figure

4.9: Saturating Two's Complement Array Multiplication.
4.3 Two's Complement Tree Multipliers with Overflow
Detection or Saturation
The alternative method is used for tree multipliers. For this method (n+1) bits of the
product are computed. V 1 is computed the approach same as the first method and
then the overflow flag is generated by using the logic equation
as explained in Section 4.1.5.
Since the detection circuit is independent of the multiplication process, only n+1
of the partial product bits needs to be generated. Consequently, the AND gates and
counters that generate and reduce the partial product bits after column n of the
multiplication matrix are no longer needed. The size of the carry-propagate adder is
reduced to n bits since only the least significant product bits are used. These
reductions are independent of the strategy used to design the tree multiplier. The
reduction scheme of a Dadda multiplier that uses the alternative method is shown
in

Figure

4.10. A diagonal line with an x at the bottom is an 3 input XOR gate and
a diagonal with a tilda on it and an x at the bottom represents a 2-input XNOR
gate. The X's are used to denote that a carry output is not required.
If the worst case delay is the main constraint of the custom design, the alternative
design method should be considered to implement the overflow detection logic. A
two's complement Dadda multiplier with proposed overflow detection has (n
gates and one n-bit CPA. The worst case delay of the multiplier is also less than the
conventional technique. With the alternative method,the worst case delay equals
the delay of the reduction stages, plus the delay of the n
adder, plus one 2-input OR gate, plus, one 2-input XOR gate, plus one 2-input AND
gate.
Two's complement saturating multiplication logic for the Dadda tree multiplier
is similar to the logic for the array multiplier. An n-bit 2-to-1 multiplexer and an
inverter are added as shown in Figure 4.9, except the partial product bits p n\Gamma2 to
are not connected to the overflow detection logic. The control signals t and V for
the 2-to-1 multiplexer are generated by the detection logic. The delay increases by
just the delay of the inverter plus the delay of the 2-to-1 multiplexer.
Figure

4.10: Dadda Dot Product Scheme after Proposed Overflow Detection.
Chapter 5
Results
5.1 Area and Delay Estimates
Theoretical component counts and worst case delays are given for various multipliers
in

Tables

5.1, 5.2 and table 5.3. In these tables, U and S denotes unsigned and
signed, A and T denote array and tree multiplier, and P and C denote proposed
and conventional. Table 5.1 and Table 5.2 gives the number of each component and
the size of the CPA based on operand length n. Table 5.3 gives the number of each
type of component on the worst case delay path. The proposed methods reduce the
number of AND gates and FAs for array multipliers and reduce the number of AND
gates and FAs, and the size of the CPAs for tree multipliers. The proposed methods
also reduces the delays of the array and tree multiplier, since the most significant
product bits are no longer calculated.
Multiplier Number of Components
Type INV AND NAND OR2 NOR OR3

Table

5.1: Component Counts for n-bit Multipliers with Overflow Detection I.
Multiplier Number of Components
Type XOR XNOR HA FA CPA

Table

5.2: Component Counts for n-bit Multipliers with Overflow Detection II.
Multiplier Number of Components on Worst Case Delay Path
Type INV AND OR2 XOR HA FA CPA

Table

5.3: Worst Case Delay for n-bit Multipliers with Overflow Detection.

Table

5.4: Unsigned Array Multipliers with Overflow Detection.
It is possible to reduce the amount of logic required to implement the detection
circuit even further. The proposed method uses a straight forward implementation
of the logic equations and structures presented in the previous chapters. Synthesis
tools are used to further optimize the design. Consequently, the values shown in

Table

5.1, 5.2, and Table 5.3 should be considered to be worst case values, before
further optimization is performed.
Gate level VHDL code for various sizes of array and Dadda tree multipliers were
generated for the conventional and proposed methods for overflow detection. The
VHDL code was synthesized and optimized for area using LSI Logic's 0.6 micron
gate array library and the Leonardo Synthesis tool from Exemplar logic.
The synthesis tool was set to a nominal operating voltage of 5.0 volts and a temperature
of 25 ffi C. Area estimates are reported in equivalent gates and delay estimates
are reported in nanoseconds.

Table

5.4 gives area and delay estimates for unsigned array multiplier. Compared
to the multipliers that use conventional overflow detection, the proposed multipliers
have between 50% and 53% less area and between 41% and 42% less delay. These

Table

5.5: Unsigned Dadda Tree Multipliers with Overflow Detection.
Conventional Proposed Reduction
n Area Delay Area Delay Area Delay

Table

Signed Array Multipliers with Overflow Detection.
gains are mainly due to the reductions in the area and the delay of FAs used to
generate the n most significant product bits.

Table

5.5 gives area and delay estimates for unsigned Dadda tree multipliers.
Compared to multipliers that use conventional overflow detection method, multipliers
that use the proposed method have approximately 47% less area and between
23% and 28% less delay. These improvements are due to the reducing the number
of FAs and reducing the size of the final carry-propagate adder from (2n \Gamma 2) to

Table

5.6 gives area and delay estimates for two's complement array multipliers.
Compared to the multipliers that use the conventional method, multipliers that use
the proposed method require between 38% and 47% less area and between 41% and

Table

5.7: Signed Dadda Tree Multipliers with Overflow Detection.

Table

5.7 gives area and delay estimates for two's complement Dadda tree mul-
tipliers. Compared to the multipliers that use the conventional method, multipliers
that use the proposed method have between 35% and 44% less area and between
24% to 32% less delay.
Chapter 6
Conclusions and Future Research
6.1 Conclusions
The overflow detection and saturation methods presented in this thesis significantly
reduce the area and delay of array and tree multipliers. For the multiplier sizes
examined, the area is reduced by about 50% for unsigned multipliers when compared
with conventional methods. The proposed methods also do not change the regularity
of the multiplier structure. For the two's complement multipliers, the proposed
methods are completely independent of the multipliers' internal structure. This
feature provides designers increased flexibility, since they can add overflow detection
logic without effecting their original design. Reduction in the multiplier hardware
will also lead to reduced power dissipation. The proposed methods reduce the delay
of array multipliers by about 40% to 50%.
6.2 Future Research
This thesis separately presented overflow detection and saturation methods for unsigned
and two's complement parallel multipliers. An important next step is to
develop a single multiplier structure that can perform both unsigned and two's
complement integer multiplication with overflow detection or saturation based on
an input control signal. Another area for future research is to investigate techniques
for further reducing the area for overflow detection in multiplier trees, without significantly
impacting the delay. This research may be able to take advantage of a hybrid
structure that has less delay than linear overflow detection structures and less area
than overflow detection trees. Another research area is to investigate reductions in
power dissipation due to the proposed techniques. It is anticipated that a significant
reduction in power dissipation can be achieved due to the reduction in multiplier
hardware. Methods similar to the proposed methods can be also used for other
arithmetic operations that needs overflow detection, such as multiply-accumulate
and squaring.



--R

" Some Schemes for Parellel Multipliers,"
"Suggestion for a Fast Multiplier,"
"A 40 ns 17-bit Array Multiplier,"
"Parallel Reduced Area Multipliers,"
"A reduction Scheme to Optimize The Wallace Multiplier,"
"A Two's Complement Parallel Array Multiplication Algorithm,"
"Comments on A Two's Complement Parallel Array Multiplication Algorithm,"
"Synthesis and Comparision of Two's Complement Parallel Multipliers,"
"Computer Architecture a Quantative Approach, Second Edi- tion,"
"Parallel Saturating Fractional Arithmetic Units,"
"Fixed-point Overflow Exception Detection,"
"Programmable High-performance IIR Filter Chip,"
"Overflow Indication In Two's Complement Arith- metic,"
"Overflow Detection in Multioperand Addition,"
"Zero, Sign, and Overflow Detection Schemes For Generalized Signed Arithmetic"
"A Signed Binary Multiplication Technique,"
--TR

--CTR
Eyas El-Qawasmeh , Ahmed Dalalah, Revisiting integer multiplication overflow, Proceedings of the 4th WSEAS International Conference on Software Engineering, Parallel & Distributed Systems, p.1-14, February 13-15, 2005, Salzburg, Austria
Eyas El-Qawasmeh , Ahmed Dalalah, Revisiting integer multiplication overflow, Proceedings of the 4th WSEAS International Conference on Software Engineering, Parallel & Distributed Systems, p.1-14, February 13-15, 2005, Salzburg, Austria
integer;computer arithmetic;saturation;two's complement;tree multipliers;array multipliers;unsigned;overflow