IEEE TRANSACTIONS ON COMPUTERS, VOL. C-22, NO.

12, DECEMBER 1973 1045

A Two's Coreent Parallel Array

CRu lt r M I
CHARLES R. BAUGH, MEMBER,4' S D Wk O *LEY, MEMBER, IEEE

Abstract-An algorithm for high-speed, two's complement, m-bit by lowing the product to be formed using array addition tech-
n-bit parallel array multiplication is described. The two's complement niques. In conventional two's complement multiplication there
multiplication is converted to an equivalent parallel array addition are partial product bits with negative, as well as positive, signs.
problem in which each partial product bit is the AND of a multiplier bit
and a multiplicand bit, and the signs of all the partial product bits are In binary multiplication the n + m-bit product P = (Pn+m -1 '
positive. Pn+m -2' ---, Po) is formed by multiplying the m-bit multi-
Index Terms-Array multiplier, binary multiplication, high-perfor-
plicand Y = (Ym -I ,Ym -2, * *, Yo) by the n-bit multiplier X =
mance multiplication, parallel multiplier, two's complement multiplica- (xn i , -, xo). This multiplication is usually depicted as
tion. shown in Fig. 1. The AND of each multiplier bit and each
multiplicand bit is formed to produce the partial product bits.
The partial products are then summed to form the product.
M s ULTIPLICATION is often an essential function in The difficulty in two's complement multiplication lies with
digital systems. For example, it is a necessary operation the signs of the multiplicand and the multiplier. Let Y, be the
in digital filtering and Fourier transform processing. With the value of the multiplicand Y, and X, the value of the multiplier
advent of high-speed semiconductor memory, an increasing X. For two's complement representation X, and Y, are
mismatch between memory access and multiplication time has given by
arisen. Consequently, there exists considerable interest in
parallel array multipliers. Most of this interest has centered m -2
around two's complement multipliers, since the two's com- Yv =-Ym 12m-l + yi2 (1 a)
plement representation of numbers is used almost universally. i=o
Two's complement representation adds complexity to the n -2
multiplication algorithm because the sign of the number is em- XV = -x,1 2'~-+ £ xi2'. (lb)
bedded in the number itself. This is in contrast to sign- i=o
magnitude representation where the sign and the number can
be separated and multiplication is much simpler. The value P, of the product P is
With the advent of medium-scale integration, the fabrication
of parallel array multipliers has become economically more m +n -2
feasible. Several companies now offer modules that can be Pv =-Pm+n-l2m+n+l + ; pi2'= YvXv
interconnected to form parallel array multipliers. For sign- i=O
magnitude multiplication, Fairchild offers a 2 X 4-bit multi- m-2 \ n-2
plier [1], Hughes an 8 X 8-bit multiplier (2], and Texas = Vm -1 2m + E Yi21)
xn2 £ -1+ xj21)
Instruments a 4 X 4-bit multiplier [3]. For two's complement
multiplication, a 2 X 4-bit multiplier is available from Ad- n-2 m-2
vanced Micro Devices [4]. There have been at least two cus- =Xn -1Ym -1 2m +n -2 + £ E xi.yi2'i
tom circuit designs for two's complement multipliers. Pezaris i=0 j=0
designed three circuits for implementing a 17 X 17-bit multi-
plier [5], while Hampel et al. used a single circuit for n X m-bit m=-2 n-2

multiplication [6]. Both designs were for high-speed multipli- i=o

Xn-l 2£
yi2 n-I +i + Ym-lxi2m
i=o.
E -"+
(2) .

cation. All commercial multipliers, except for the Advanced

Micro Devices circuit, use conventional algorithms for imple- When forming P by adding the partial products, the sign of the
menting the multiplication. partial product bits must be considered. In particular, the
In this paper an algorithm for parallel two's complement signs of
x_1 for i= 0, - -, m- 2 and Ym_-xi for i=0,
multiplication is described. The algorithm's principle advantage * *, n - 2 are yi negative. By rewriting the partial product bits as
is that the signs of all the partial product bits are positive, al- shown in Fig. 2, all the partial product bits with negative
signs are placed in the last two rows. The product is formed by
Manuscript received March 8, 1973; revised June 28, 1973. A sum- adding the first n - 2 partial product rows and subtracting the
mary of this paper was presented as a Short Note at COMPCON 73, last two rows.
the 7th Annual IEEE Computer Society International Conference,
February 28, 1973. Instead of subtracting the partial products that have negative
The authors are with Bell Laboratories, Holmdel, N.J. 07733. signs, the negation of the partial products can be added. The

Authorized licensed use limited to: INDIAN INSTITUTE OF TECHNOLOGY ROORKEE. Downloaded on March 17,2021 at 05:21:27 UTC from IEEE Xplore. Restrictions apply.
 l1046 IEEE TRANSACTIONS ON COMPUTERS, DECEMBER 1973

Ym-i * * Y4 Y3 Y2 YI YO
Xn.1 . . . X2 Xi xO
XOym-I 0 , , X0 y4 xOy3 x0Y2 x0y1 xoyo
XIYm-i XiYm-2 - . Xi Y4 X1Y3 X1Y2 XiY1 XiYO
X2Ym-i X2Ym-2 . . X
x2y4 X2Y3 X2y2 X2Yj X2Yo

. *
0
Xn_2y2 Xn-2Y1 Xn-2YO
Xn-iYm-i * * * Xn 1Y2 Xn IYI Xn-IYO
Pmin-I Pmtn-2 Pmi Pm Pm-i
Pn+I Pn Pn-I Pn-2 P3 P2 p1 PO
Fig. 1. Conventional two's complement m X n-bit multiplication.

Ym-1 0 .
Y4 Y3 Y2 Y1 YO
Xn-1 * * * X2 Xi XO

oYm-2 * xAy4 XOy3 XOY2 XOYI xoyO

Xi1 Ym-2 0
Kly4 X1y3 X1Y2 x1y1 X1YO
X
2 Ym-2 * * X2y4 X2y3 X2y2 X2y1 X2yO
0

Xn iYm-i 0
Xn-2Ym-2 * * * xn-2y4 Xn-2y3 Xn 2Y2 Xn-2YI Xn-2Yo
0 0
Xn-lYm-2 Xn-lYm-3*- * Xn-iy4xn-lY3 Xn-ly2 Xn-IYI Xn-iYO
0 0 X n 2ym i X n-3ym-1 Oym
Pn+m-1 Pntm-2 Pnim-3 Pn*m-4 ***m-1@@Pn+3 Pn+2 9n+I Pn Pn-1 Pn-2 .. P3 P2 P1 PO
Fig. 2. Positive/negative segregation of partial product bits.

value of the negation of a two's complement number Z= is replaced by

(Zk...1,* , zo) with value Z, is 1 1 Xn-2Ym-1 Xn-3Ym-1 XoYm-I
k -2
k with a "1" added in the Pm-i column. Following these sub-
-Zu = 1- Zk-12 + E Ti2i (3)
stitutions, all partial product bits can be treated in exactly the
i=O
same manner with respect to the sign.
where Ei is the complement of zi. Therefore, the subtraction The substitution of (5) for (4) in Fig. 2 results in nonuni-
of formity with regard to partial product bits since some partial
m -2 product bits are the NAND of a multiplier bit and multiplicand
2n-1 -( -
2m +O 2m`1 +
n lyi2' (4) bit, while others are formed with an AND. To simplify this
i=O situation, the following equivalences are used. Note that (5)
can be replaced with the addition of has the value
m -2 \
for xn-i =0
2n-1 - 1 2m
- + I 2m-1
* + 1 + ;E X_jyj2') (5)
i=O = 1.
Thus the partial product row of Fig. 2 containing
0 0 Xn-lYm-2 Xn_lYm-3 *-. Xn-iYo (6)
is replaced by From (6) it follows that (5) can be rewritten as
m-2
1 1 Xn1lYm-2 Xn-lYm-3 .... Xn-IYO 2n-1 y2m +2m-l +x 12m-1 +Xni + E Xn-2').
i=O
with a "1" added to the Pn-1 column. Similarly, the row
containing (7)
0 0 Xn 2Ym_l X.3 XoYm-I Therefore, (5) is equivalent to (7). Since the next to the

Authorized licensed use limited to: INDIAN INSTITUTE OF TECHNOLOGY ROORKEE. Downloaded on March 17,2021 at 05:21:27 UTC from IEEE Xplore. Restrictions apply.
 BAUGH AND WOOLEY: MULTIPLICATION ALGORITHM 1047

Ym-1 y4 y3 y2 y1 YO

Xn-i * . . X2 Xi XO
XoYm-2 K0y2 xoy1 50Y0
xymm2 *
~~~X1y2 51y1 x1y0

X2YM-2 * * ~~x2Y1 x2Y0

5n,iym.t 0 Xn-2ymr-2 xfl.2y2 Xnl-2y1 xn,.2y0

xn-I Xn-iym 2 Xn-1ym-3 X.-1Y-2 Xn.1;y1 Kn.;Y_0
Ym.i Kfl.2Ym.1 Xn-3Ymi,,, or-

Ym-i Xn-1

Pn+mr- Pnm-2 Pn+m-3 Pn+m-4 . . . Pm -I* * * Pn+1 PR Pn-1 Pn-2 ..P3 P2 P1 PO

Fig. 3. Algorithm with all positive partial product bits.

last row of partial product bits in Fig. 2 is of the form given in [2] "Bipolar LSI 8-bit ,multiplier H1002MC," Hughes Aircraft Co.,
500 Superior Ave., Newport Beach, Calif.
(5), (7) is substituted for this row. By making a similar substi- [31 "TTL/MSI SN74284-5 and SN54284-5 4-bit by 4-bit parallel
tution for the last row of partial product bits and by adding binary multipliers," Texas Instruments, Inc., P.O. Box 5012,
Dallas, Tex.
constants, the partial product bits of Fig. 3 are obtained. [4] "TTL/MSI AM2505 4-bit by 2-bit 2's complement multiplier,"
The principle characteristic of the partial product bits in Advanced Micro Devices, 901 Thompson Place, Sunnyvale, Calif.
Fig. 3 is uniformity. The two advantages of this uniformity [5] S. D. Pezaris, "A 40-ns 17-bit by 17-bit array multiplier," IEEE
Trans. Comput., vol. C-20, pp. 442-447, Apr. 1971.
are as follows. [6] D. Hampel, J. B. Lerch, and K. J. Prost, "Development of high-
speed integrated circuits, digital multipliers and sample and hold
1) The partial product bits are obtained by forming the gates; Final report," Air Force Avionics Lab., Contract AFAL-TR-
71395, Mar. 1972.
AND of a multiplier bit and a multiplicand bit.
2) Every partial product bit has a positive coefficient.
Therefore, the product is formed with only the AND function
and the ADD function. No subtraction is necessary, nor is the
NAND function needed to form xiy3. Charles R. Baugh (S'65-M'70) received the B.S.
In a circuit implementation of the above algorithm, separate degree in electrical engineering from Michigan
State University, East Lansing, in 1965, the M.S.
AND gates are not needed to form the nm partial product bits. degree in electrical engineering, and the Ph.D.
Both Pezaris [51 and Hampel et al. [6] have designed circuits degree in computer science, both from the
that readily incorporate the AND operation into the addition University of llinois,Urbana,in 1967 and 1970,
respectively.
circuits. Also, the five extra partial product bits of the al- X l l||; j He joined Bell Laboratories, Holndel, N.J., in
gorithm, xn l, xn-l, Ymn-I, Yin-I, and "1", can be included 1970. His current research interests are switch-
ing theory and digital signal processing.
in a circuit implementation without increasing the total propa- Dr. Baugh is a member of Eta Kappa Nu and
gation delay of the two's complement multiplication. Sigma Xi.
A disadvantage of the proposed algorithm is the need for the
complements of each multiplier and multiplicand bit in form-
ing the partial product bits. However, for a number of reasons,
this is not a major concem. Since high-speed multiplication is Bruce A. Wooley (S'64-M'70) was born in
desired, current-mode (emitter-coupled) logic would most Milwaukee, Wis., on October 14, 1943. He re-

likely be used to implement the algorithm; with this logic both ceived the B.S., M.S., and Ph.D. degrees
electrical engineering from the University
in
of
the output and its complement are available. In addition, the California, Berkeley, in 1966, 1968, and 1970,
multiplier would probably be connected to a bus and driven respectively.
from bus-receiving gates or a bus register; consequently, the At the University of California he held ap-

complements of the multiplicand and multiplier bits would be pointments

Assistant
as

Professor
Acting Instructor

in the Department
and Acting
of Elec-

readily available. Furthermore, since the fan-out requirements trical Engineering and Computer Sciences. He
for the multiplicand and multiplier bits are high, special driving employed by Motorola Semiconductor
was
Products Division, Phoenix, Ariz., and Bell Laboratories, Allentown,
gates would be needed even if the multiplier was not connected Pa., during the summers of 1966 and 1968, respectively. Since 1970
to a bus; such driving gates would provide complemented he has been a Member of the Technical Staff at Bell Laboratories,
signals. Holmdel, N.J. His current research interests include the realization of
functional integrated circuits for communication systems and the
REFERENCES computer-aided design of integrated circuits.
Dr. Wooley is a member of Sigma Xi, Tau Beta Pi, and Eta Kappa Nu.
[1] "TTL/MSI 9344 binary (4-bit by 2-bit) full multiplier," Fairchild In 1966 he received the University Medal from the University of Cali-
Semiconductors, 313 Fairchild Drive, Mountain View, Calif. fornia, Berkeley. He was the IEEE Fortescue Fellow for 1966-1967.

Authorized licensed use limited to: INDIAN INSTITUTE OF TECHNOLOGY ROORKEE. Downloaded on March 17,2021 at 05:21:27 UTC from IEEE Xplore. Restrictions apply.