Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Binary Multiplication and Division Utilizing a Three Input Adder

IP.com Disclosure Number: IPCOM000078360D
Original Publication Date: 1972-Dec-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 4 page(s) / 28K

Publishing Venue

IBM

Related People

Jackson, RT: AUTHOR [+3]

Abstract

Binary multiplication and division cam be rapidly performed through the use of a three-input adder having input registers REG1, REG2 and shifting gates S1, S2, S3. Binary Multiplication.

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 37% of the total text.

Page 1 of 4

Binary Multiplication and Division Utilizing a Three Input Adder

Binary multiplication and division cam be rapidly performed through the use of a three-input adder having input registers REG1, REG2 and shifting gates S1, S2, S3. Binary Multiplication.

Multiplication is accomplished four bits at a time, utilizing even multiples of the multiplicand from 0 to 16. These multiples are supplied by REG2 through S2 and S3. Partial products are stored in REG1 and, on each iteration, supplied to the adder through S1.

The multiplier is divided into four-bit groups, extra zeros being added to the high-order end of necessary. Only one addition or subtraction will be made for each group and, using the bits in the group as a reference, this addition or subtraction will consist of from two to sixteen times the multiplicand with only even multiples being utilized. These multiples may be obtained by shifting the position of entry of the multiplicand into the adder one, two, three or four positions left from the reference position. The last cycle of the multiplication may require special handling. Rules for this will be considered after the general rules have been developed.

The general rule is that, following any addition or subtraction, the resulting partial product will be either correct or larger than it should be by an amount equal to one times the multiplicand. Thus, if the high-order group of bits of the multiplier is 0000 or 0010, the multiplicand would be multiplied by zero or two and added, which gives a correct partial product. If the high-order group of bits is 0001 or 0011, the multiplicand is multiplied by two or four, not one or three, and added. This gives a partial product that is larger than it should be, and the next add cycle must correct for this.

Following the addition, the partial product is shifted left four positions. This multiplies it by sixteen, which means that it may now be larger than it should be by sixteen times the multiplicand. This may be corrected during the next addition by subtracting the difference between sixteen and the desired shift.

Thus, if a group ends in 0, the resulting partial product will be correct and the following operation will be an addition. If a group ends in a 1, the resulting partial product will be too large, and the following operation will be a subtraction.

It can now be seen that the operation to be performed for any group of bits of the multiplier may be determined, by examining that group of bits plus the low- order bit of the next higher order group. If the bit of the higher order group is a 0, an addition will result; if it is 1, a subtraction will result. If the low-order bit of a group is considered to have a value of 1 and the high-order bit a value of 16, then the multiple called for by a group is the numerical value of the group if that value is even and one greater if it is odd. If the operation is an addition, this multiple of the multiplicand is used. If the operation is a su...