Apparatus and method for expediting subtraction procedures in a carry/save adder multiplication unit

Claim 2

A multiplier unit capable of implementing a modified Booth algorithm, said multiplier unit comprising: a multiplier storage means for storing a multiplier operand; a multiplicand storage means for storing a multiplicand operand; a plurality of sequential carry/save adder means coupled to said multiplicand storage means and a next previous carry/save adder stage, each carry/save adder means for performing a processing operation on said multiplicand operand and combining an internal operand resulting from said processing operation with a processed operand from a next previous carry/save adder stage, wherein said processed operand is shifted a preestablished amount between said next previous carry/save adder stage and said carry/save adder stage; a plurality of encoding means coupled to said multiplier operand storage means and responsive to said multiplier operand for applying control signals to an associated carry/save adder means, said control signals determining said processing operation of said associated carry/save adder means, each of said plurality of encoding means generating a positive logic signal when said control signals result in a subtraction processing operation in said associated carry/save adder means, wherein said positive logic signal is entered in a first carry/save adder stage at a predetermined position and combined with said multiplicand operand in said first carry/save adder means, and combining means for combining signals from a last carry/save adder means.

Claim 3

The multiplier unit of claim 1 wherein said predetermined position is a position of least significant bit position of a carry/save adder means receiving control signals associated with said positive logic signal prior to shifting said processed operand during transfer between carry/save adder stages.

Claim 4

The multiplier unit of claim 2 wherein said control signals causing a subtraction processing operation by said carry/save adder means result in a 1's complement processing operation.

Claim 5

The multiplier unit fo claim 3 wherein said positive logic signal is a logic signal for causing said 1's complement processing operation to provide a 2's complement processing operation.

Claim 6

The multiplier unit of claim 4 further comprising a plurality of least significant cells, each of said least significant cells associated with a one of said carry/save adder means, said each least significant cell receiving signals from a least significant bit position cell of a next prior carry/save adder means, wherein said predetermined position is determined by a position of an associated least significant cell.

Claim 9

The method of implementing a modified Booth's algorithm in a multiplier unit of claim 6 wherein said adding said positive logic signal step and said performing a 1's complement step provide a two's complement operation.

Claim 10

The method of implementing a modified Booth's algorithm in a multiplier unit of claim 7 wherein said recoding step includes a step of providing said control signals in response to selected multiplier operand bit position signals.

Claim 11

The method of implementing a modified Booth's algorithm of claim 8 wherein said adding said positive logic signal step includes a step of entering said positive logic signal in a bit position of said first carry/save adder stage equivalent to the least significant position of said carry/save adder stage performing said 1's complement processing operation prior to shifting of processed operands.

Claim 12

The method of implementing a modified Booth's algorithm of claim 8 further including a step of entering said positive logic signal in a carry/save adder unit associated with said predetermined bit position in said first carry/save adder stage by means of a terminal selected from a SUM signal input terminal and a CARRY signal input terminal of said carry/save adder unit.

Claim 13

Apparatus for executing a multiplication operation using a modified Booth's algorithm, said apparatus comprising: first storage means for storing a multiplier operand; second storage means for storing a multiplicand operand; an ordered plurality of carry/save adder stages, wherein each of said carry/save adder stages receives said multiplicand operand, said each carry/save adder stages including an array of carry/save adder cells, said each carry/save adder stage performing a one of a sequence of processing operations on said multiplicand operand, said each carry/save adder stage combining a processed multiplicand operand and an output operand from a next prior carry/save adder stage, each of said output operands shifted a preestablished number of bit positions when applied to a next sequential carry/save adder stage; a plurality of encoding means, each of said encoding means coupled to a carry/save adder stage and coupled to said first storage means, said encoding means applying control signals to said coupled carry/save adder stage, said control signals determining said processing operation on said multiplicand operand entered in said coupled carry/save adder stage, wherein said control signals are determined by selected signal groups of said multiplier operand, said encoding means applying a logic signal with a selected position of a first carry/save adder stage in response to preselected multiplier operand signal groups, said preselected signal groups identifying a subtraction operation by said coupled carry/save adder stage on said multiplicand operand; and combining means for combining signals from a last carry/save adder stage to provide a resulting operand.

Claim 14

Apparatus for executing a multiplication operation using a modified Booth's algorithm, said apparatus comprising: first storage means for storing a multiplier operand; second storage means for storing a multiplicand operand; an ordered plurality of carry/save adder stages, wherein each of said carry/save adder stages receives said multiplicand operand, said each carry/save adder stages including an array of carry/save adder cells, said each carry/save adder stage performing a one of a sequence of processing operations on said multiplicand operand, said each carry/save adder stage combining a processed multiplicand operand and an output operand from a next prior carry/save adder stage, each of said output operands shifted a preestablished number of bit positions when applied to a next sequential carry/save adder stage; a plurality of encoding means, each of said encoding means coupled to a carry/save adder stage and coupled to said first storage means, said encoding means applying control signals to said coupled carry/save adder stage, said control signals determining said processing operation on said multiplicand operand entered in said coupled carry/save adder stage, wherein said control signals are determined by selected signal groups of said multiplier operand, said encoding means applying a logic signal with a selected position of a first carry/save adder stage in response to preselected multiplier operand signal groups, said preselected signal groups identifying a subtraction operation by said coupled carry/save adder stage on said multiplicand operand; and combining means for combining signals from a last carry/save adder stage to provide a resulting operand.

Claim 15

The apparatus for executing a multiplication operation of claim 11 wherein said preselected multiplier operand signal groups cause a 1's complement processing operation to be performed by a coupled carry/save adder stage.

Claim 16

The apparatus for executing a multiplication operation of claim 12 wherein combining said logic signal in said first carry/save adder unit converts said 1's complement multiplicand processing operation to a 2's complement multiplicand processing operation.

Claim 17

The apparatus for executing a multiplication operation of claim 13 wherein said selected position is determined by a least significant bit position of a carry/save adder stage prior to shifting of output operands between said carry/save adder stages.

Claim 18

The apparatus for executing a multiplication operation of claim 14 wherein output signals from a carry/save adder stage include a SUM signal and a CARRY signal associated with each bit position.

Claim 19

The apparatus for executing a multiplication operation of claim 15 further comprising a least significant cell associated with each carry/save adder stage; said least significant cell combining shifted SUM signals from a least significant bit position of a next prior carry/save adder stage, at least one shifted CARRY signal from said next previous carry/save adder stage, and an overflow signal from a next previous least significant cell.

Claim 20

The apparatus for executing a multiplication operation of claim 16 wherein said apparatus implements a two bit retirement Booth's algorithm, a SUM signal being shifted by two less significant positions from a one carry/save adder stage to a next consecutive carry/save adder stage, wherein a CARRY signal is shifted by one less significant position from said one carry/save adder stage to said second carry/save adder stage.

Claim 21

The apparatus for executing a multiplication operation of claim 17 wherein said least significant cells are two bit adder units.

Claim 22

The apparatus for executing a multiplication operation of claim 18 further comprising combination means for combining signals from a last carry/save adder stage and a last least significant cell into a final result operand.

Claim 23

The apparatus for executing a multiplication operation of claim 19 wherein said encoding means is responsive to preestablished three bit signals of said multiplier operand.