High-radix multiplier-divider
AssigneeKing Fahd University of Petroleum and Minerals
InventorsAlaaeldin Amin, Muhammad Waleed Shinwari
Life of this patent
Estimating the term…
Abstract
The high-radix multiplier-divider provides a system and method utilizing an SRT digit recurrence algorithm that provides for simultaneous multiplication and division using a single recurrence relation. When A, B, D and Q are fractions (e.g., Q=0·q−1 q−2 . . . q−n), then the algorithm provides for computing S = AB D to yield a w-bit quotient Q and w-bit remainder R by: (1) determining the next quotient digit q−j using a quotient digit selection function; (2) generating the product q−jD; and (3) performing the triple addition of rRj-1, (−q−jD) and b - ( j - 1 ) ( A r ) where R0=b−1Ar−1. The recurrence relation may be implemented with carry-save adders for computation using bitwise logical operators (AND, OR, XOR).
Claims7
A high-radix multiplier-divider for performing simultaneous multiplication and division in radix r of a multiplicand A=0·a−1a−2 . . . a−n, a multiplier B=0·b−1b−2 . . . b−n, and a divisor D=0·d−1d−2 . . . d−n so that
- (
- AB
- D
- )
- where AB<D, comprising:
- a plurality of registers for storing the multiplicand, the multiplier, the divisor, a quotient, and a remainder, wherein the multiplicand is an input value;
- a first data switch having a first input receiving the multiplicand right-shifted by one digit (m-bits), a second input for sequentially receiving bits from the multiplier register corresponding to digits of the multiplier from the most significant digit to the least significant digit, and an output for outputting b−j−1Ar−1 where j is a counter of the multiplier digits;
- a digital lookup table having a first input for receiving a truncated shifted partial remainder, a second input for receiving a truncated divisor, and an output for outputting a quotient digit corresponding to the truncated shifted partial remainder and truncated partial divisor, the output being stored in the quotient register and left-shifted by the radix;
- a second data switch having a first input connected to the output of the digital lookup table, a second input receiving the divisor, and an output for outputting the product of the quotient digit and the divisor;
- and
- an addition module having inputs for receiving the output of the first data switch and the 2's complement output of the second data switch, the addition module being configured for recursively adding the inputs for each digit of the multiplier and outputting the truncated partial remainder at each iteration for input to the digital lookup table.
A computer software product that includes a non-transitory storage medium readable by a processor, the non-transitory storage medium having stored thereon a set of instructions for performing high-radix multiplication and division of fractions in radix r including a multiplicand A=0·a−1a−2 . . . a−n, a multiplier B=0·b−1b−2 . . . bn, and a divisor D=0·d−1d−2 . . . d−n so that
- (
- AB
- D
- )
- where AB<D, the instructions comprising:
- (a) a first set of instructions which, when loaded into main memory and executed by the processor, causes the processor to receive an input value of the multiplicand and initialize a partial remainder to equal b−1Ar−1;
- (b) a second set of instructions which, when loaded into main memory and executed by the processor, causes the processor to initialize an iteration counter j=1;
- (c) a third set of instructions which, when loaded into main memory and executed by the processor, causes the processor to initialize a quotient register to equal 0;
- (d) a fourth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to shift the quotient register left by the radix;
- (e) a fifth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to look up a quotient digit in a digital lookup table using the partial remainder and the divisor D;
- (f) a sixth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to store the quotient digit in the quotient register's least significant bits;
- (g) a seventh set of instructions which, when loaded into main memory and executed by the processor, causes the processor to shift the partial remainder left by the radix;
- (h) an eighth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to set the partial remainder equal to the shifted partial remainder minus the product of the quotient digit and the divisor plus the quantity b−j−1Ar−1;
- (i) a ninth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to increment the counter j by one;
- (j) a tenth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to repeat the fourth set of instructions through the ninth set of instructions by a number of iterations equal to the number of bits in the quotient register divided by Log2 r;
- (k) an eleventh set of instructions which, when loaded into main memory and executed by the processor, causes the processor to subtract one from the quotient register and adding the divisor to the partial remainder when the partial remainder of the eighth set of instructions is negative;
- and
- (l) a twelfth set of instructions which, when loaded into main memory and executed by the processor, causes the processor to set the quotient equal to the quotient register and the remainder equal to the partial remainder.
Dependencies are inferred from the claim text.