Browse Prior Art Database

Parallel Multiplier

IP.com Disclosure Number: IPCOM000049371D
Original Publication Date: 1982-Apr-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 3 page(s) / 87K

Publishing Venue

IBM

Related People

Beraud, JP: AUTHOR [+2]

Abstract

This article describes a method of multiplying two 12-bit numbers, which combines the booth algorithm with 6-bit adders, with actual gain in computational speed and multiplier design complexity.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 59% of the total text.

Page 1 of 3

Parallel Multiplier

This article describes a method of multiplying two 12-bit numbers, which combines the booth algorithm with 6-bit adders, with actual gain in computational speed and multiplier design complexity.

The implementation of the multiplier is illustrated in Fig. 1 in which the two numbers X and Y to be multiplied are given in the 2 radix-representation system by x(11) x (10)... x(1) x(0) and y(11) y(10) y(1) y(0), respectively. Number Y is decoded in accordance with the well-known Booth algorithm, as illustrated in the following table. y(i+1) y(i) y(i-1) code

0 0 0 add 0

0 0 1 add X

0 1 0 add X

0 1 1 add 2 X

1 0 0 subtract 2 X

1 0 1 subtract X

1 1 0 subtract X

1 1 1 add 0

The Booth decode device has six outputs which drive six shift/ complement devices SC1-SC6, respectively. The output which drives SC1 carries the result of the decoding of the couple of bits y(1) y(0) (i = 0 in the table). The output which drives SC2 carries the result of the decoding of the group of bits y(3) y(2) y(1) (i = 1 in the table), and so on. Each of the devices SC1-SC6 has an input which receives X and two outputs S (shift) and C (complement). The operation of a shift/complement device is illustrated in Fig. 2. For example, if the result of Booth decoding is: add X (+X), output C is 0 and output S provides serially the following bit stream: x11 x10...x(1) x(0) x(0).

If the result of Booth decoding is: subtract 2X (-2X), output C is 1 and output S provides serially the following bit stream: x(11)x(10)... x(1) x(0) 1.

The outputs S from SC1-SC6 are serially loaded into 13-bit shift registers SRl-SR6, respectively.

The rest of the multiplier consists of three rows of adders. The first row comprises from right to left one 2-bit adder, one 3-bit adder, two 3-bit adders, and sixteen 6-bit adders. The second row comprises one 2-bit adder, one 3-bit adder, one 2-bit adder, and sixteen 3-bit adders. The third row comprises three 2-bit adders and eighteen 3-bit adders.

The least significant bit in SR1 (right hand in the figure) and output C from SC1 are added in 2-bit adder 10 whose sum output provides the least significant bit of the multiplier output. The second bit in SR1 and the carry output from 2-bit adder 10 are added in 2-bit adder 50 whose sum output provides the second bit

1

Page 2 of 3

of the multiplier output. The...