Mixed size radix recoded multiplier

Claim 2

A multiplier using at least two of a plurality of predetermined recoding algorithms and providing a product of first and second input operands, said multiplier recoding a predetermined one of the input operands by using at least two sets of bits of predetermined differing set size to group the predetermined input operand into a plurality of groups of bits, each group of bits having a bit size corresponding to one of first or second set sizes, said multiplier forming special product terms by creating integer multiples of the first operand, said special product terms being required by the multiplier to form partial product terms by using bits associated with the second set size and also forming at least one partial product term by using bits associated with the first set size, said first and second set sizes having differing integer values, said partial product terms being added to provide the product.

Claim 3

The multiplier of claim 1 wherein the first set size is less than said second set size.

Claim 4

The multiplier of claim 1 wherein one of said predetermined recoding algorithms is Booth's algorithm.

Claim 5

The multiplier of claim 1 wherein one of said predetermined recoding algorithms is modified Booth's algorithm.

Claim 6

The multiplier of claim 1 wherein said multiplier is an array multiplier having a single row of adders for forming the partial product terms associated with the first set size of the recoded operand, and a rank ordered row of adders for forming partial product terms coupled to each of a predetermined plurality of recoders having the second radix size, said rows of adders successively forming partial product terms beginning with the single row of adders and ending with a highest rank ordered row of adders which are coupled to the recoders having the second set size in order to generate said product of the first and second input operands.

Claim 7

The multiplier of claim 1 wherein the first set size is three and the second set size is five.

Claim 10

The method of claim 7 wherein the first set size is three and the second set size is five.

Claim 11

The method of claim 8 wherein one of the two predetermined recoding algorithms is Booth's algorithm.

Claim 12

The method of claim 7 wherein one of the two predetermined recoding algorithms is modified Booth's algorithm.

Claim 13

A recoded multiplier having differing recoding sets of bits for multiplying first and second input operands, comprising: first recoding means having a first recoding set size for receiving a first portion of the first input operand and recoding said first input operand in accordance with a first predetermined recoding algorithm; second recoding means having a second recoding set size larger than the first recoding set size and for receiving a second portion of the first input operand and recoding said first input operand in accordance with a second predetermined recoding algorithm; first logic means coupled to the first recoding means for providing partial product operands in response to the first recoding means; second logic means coupled to the second recoding means for providing partial product operands in response to the second recoding means; first adder means coupled to the first and second logic means, said first adder means selectively adding partial product operands provided by the first and second logic means with predetermined multiples of the second input operand to provide an output product; and second adder means coupled to the first adder means for receiving the second input operand and forming predetermined integer multiples of the second input operand for use by the first adder means while said first recoding means recodes the first portion of the first input operand, thereby optimizing computation time of the multiplier.

Claim 14

A recoded multiplier having differing recoding sets of bits for multiplying first and second input operands, comprising: first recoding means having a first recoding set size for receiving a first portion of the first input operand and recoding said first input operand in accordance with a first predetermined recoding algorithm; second recoding means having a second recoding set size larger than the first recoding set size and for receiving a second portion of the first input operand and recoding said first input operand in accordance with a second predetermined recoding algorithm; first logic means coupled to the first recoding means for providing partial product operands in response to the first recoding means; second logic means coupled to the second recoding means for providing partial product operands in response to the second recoding means; first adder means coupled to the first and second logic means, said first adder means selectively adding partial product operands provided by the first and second logic means with predetermined multiples of the second input operand to provide an output product; and second adder means coupled to the first adder means for receiving the second input operand and forming predetermined integer multiples of the second input operand for use by the first adder means while said first recoding means recodes the first portion of the first input operand, thereby optimizing computation time of the multiplier.

Claim 15

The recoded multiplier of claim 11 wherein either said first or said second predetermined recoding algorithm is Booth's algorithm.

Claim 16

The recoded multiplier of claim 11 wherein either said first or said second predetermined recoding algorithm is modified Booth's algorithm.

Claim 17

The recoded multiplier of claim 11 wherein the first recoding set size is three and the second recoding set size is five.

Claim 18

The recoded multiplier of claim 11 wherein said second recoding set size is larger than said first recoding set size.