Apparatus and Method for Expediting Subtraction Procedures in a Carry/Save Adder Multiplication Unit

This application is related to the following U.S. Patent Application.

APPARATUS AND METHOD FOR PERFORMING A SHIFT OPERATION IN A MULTIPLIER ARRAY; invented by Gilbert M. Wolrich, Edward J. McLellan and Robert A. J. Yodlowski; having Ser. No. 050,749; filed on May 15, 1987; and assigned to the assignee of the present U.S. Patent Application.

1. Field of the Invention

This invention relates generally to data processing systems and, more particularly, to execution of the multiplication procedure by a data processing system.

2. Description of the Related Art

Data processing systems typically employ an array of carry/save adders to execute the multiplication procedure. A block diagram of apparatus used in performing this multiplication procedure is shown in FIG. 1. Register 101 contains the multiplicand operand, while register 102 contains the multiplier operand. For this exemplary apparatus, the operands are assumed to be 8 bits in length. The multiplication apparatus includes a first carry/save adder stage 111, a second carry/save adder stage 112, a third carry/save adder stage 113 and a fourth carry/save adder stage 114. In the exemplary apparatus illustrated in FIG. 1, a shift of two bit positions is assumed between each carry/save adder stage (i.e., a two bit retirement algorithm is used). Each carry/save adder stage includes a multiplicity of carry/save adder cells, in the present example 8 carry/save adder cells are used in each stage.

Referring now to FIG. 2, (for the modified Booth's 2 bit retirement algorithm) each carry/save adder cell 20 has a CARRY(n+1) signal from the prior carry/save adder stage, a SUM(n+2) signal from the prior carry/save adder stage and a MULTIPLICAND(n) signal applied thereto and, in response to control signals, provides a SUM(n) signal and a CARRY(n) signal. (Each carry/save adder cell is associated with a multiplicand bit position n.)

Referring again to FIG. 1, each multiplicand register 101 cell is applied to a corresponding carry/save adder cell in each of the carry/save adder stages. In FIG. 1, this coupling is illustrated for the 7.sup.th bit position of multiplicand register 101 which is coupled to the 7.sup.th bit position carry/save adder cell of the first carry/save adder stage 111, the 7.sup.th bit position carry/save adder cell of the second carry/save adder stage 112, the 7.sup.th bit position carry/save adder cell of the third carry/save adder stage 113 and the 7.sup.th bit position carry/save adder cell of the fourth carry/save adder stage 114. In the illustrative example of FIG. 1, the two bit position shift between the carry/save adder stages in indicated in FIG. 1 by the application of the SUM (S) signal from carry/save adder cell bit position 5 to the carry/save adder cell bit position 3 of the next succeeding carry/save adder stage and by the application of the CARRY (C) signal from carry/save adder cell bit position 5 to the carry/save adder cell at bit position 4 of the next succeeding carry/save adder stage (i.e., from carry/save adder stage 111 to carry/save adder stage 112, etc.).

The two position shifting of signals between the carry/save adder stages is the result of using a procedure generally referred to as the modified Booth 2 bit retirement algorithm. In this procedure, a plurality (2 bits in the present example) of remaining least significant multiplier operand bits multiply the multiplicand operand in a single operation (i.e., are retired in a single operation). This operation is performed by encoding (or recoding the two multiplier bits into appropriate control signals in encoding apparatus 141, 142, 143 and 144, each encoding apparatus being associated with a carry/save adder stage (111, 112, 113 and 114 respectively). (As will be known to those familiar with the modified Booth algorithm, the remaining three least significant bits are used to determine the control signals even though only the two least significant bits are retired.) Referring to FIG. 3, the relationship between the three multiplier bits and the operation of the carry/save adder cell resulting from the control signals is illustrated. Of particular importance to the present invention is the requirement of the subtraction operation for certain multiplier operand signal groups. In order to implement the subtraction operation with the carry/save adder cells, the 2's complement subtraction algorithm is used. When the encoding apparatus 141 to 144 determines that a subtraction operation is to be performed in the associated carry/save adder logic (111 through 114 respectively), a 1's complement signal group is formed from the multiplicand operand and the logic signal, to complete the 2's complement of the multiplicand operand, is applied to the least significant bit position associated with the multiplicand operand.

Referring once again to FIG. 1, the shifting operation causes a portion of the operand field to be removed therefrom. To insure the accuracy of the multiplication procedure, least significant cells 151, 152, 153 and 154 are used to process signals, otherwise removed from the operand field, but which can contribute to the result. In the preferred embodiment, the least significant cell is a two bit adder cell. The least significant cell receives the SUM signals from the 0.sup.th and 1.sup.st carry/save adder stage bit positions from the prior carry/save adder stage, the CARRY signal from the 0.sup.th bit position from the prior carry/save adder stage, the overflow signal from the preceding least significant cell and the logic signal needed to provide the 1's complement signal group, generated on the fly in the preferred embodiment, into a 2's complement signal for the prior carry/save adder stage. In the shifting of the signals from the carry/save adder stage, the least significant bit position associated with the multiplicand register is entered into the least significant cell and the application of the 2's complement logic signal thereto is equivalent to applying the 2's complement logic signal to the least significant position of the next preceding carry/save adder stage. The signals from the fourth carry/save adder stage 114 and the fifth least significant cell 154 are applied to the carry/sum combining network 130 wherein an 8 bit result operand is formed. (Least significant bit cell 150 is shown with dotted lines in FIG. 1 because all of the input signals thereto are zero.)

The multiplier circuit of FIG. 1 has several advantages. Only in carry/sum combining network 130 are the CARRY signals and the SUM signals combined into a single operand with the potentially slow carry propagation process. The use of the modified Booth algorithm reduces the number of operations performed on the operand and reduces the number of elements to implement the multiplication operation. However, the multiplication process has the limitation of potentially requiring the processing of five input signals by the least significant cell.

A need has therefore been felt for accelerating the potentially slowest portion of the multiplication procedure, which is the combination of signals in the least significant cell associated with each carry/save stage.

It is an object of the present invention to provide an improved data processing system.

It is a feature of the present invention to provide an improved technique for execution of the multiplication operation in a data processing system.

It is a further feature of the present invention to apply the logic signal(s) required to convert a 1's complement operand (or operand) into a 2's complement operand in an initial carry/save adder stage.

It is a still further feature of the present invention to accelerate the multiplication operation by reducing the number of signals processed by a least significant cell associated with a carry/save adder stage.

The aforementioned and other features are accomplished, according to the present invention, by a multiplication unit implemented by a plurality of carry/save adder stages and executing the multiplication procedure through the use of the modified Booth algorithm. When the encoded multiplier bits indicate a subtraction operation is required, the single logic "1" signal needed to convert a 1's complement signal group derived from the multiplicand operand into a 2's complement signal group in order to execute the subtraction operation by means of addition operation is entered, for all subtraction operations, into the first carry/save adder stage at the appropriate bit positions. The appropriate bit positions are determined by the position where the logic signals would be entered in the least significant cell, account being taken to the position shifts between equivalent positions in the first carry/save adder stage cell and the least significant cells. For the first carry/save adder stage, both the input CARRY signal terminals and the input SUM signal terminals are unused and can be used to enter the 2's complement signal(s) into the first carry/save adder stage.

These and other features of the present invention will be understood upon reading of the following description along with the drawings.

FIG. 1 is a block diagram illustrating the apparatus used in executing a multiplication procedure.

FIG. 2 is a diagram illustrating the signals applied to and derived from a carry/save adder cell.

FIG. 3 is a table of multiplier bit groups and the corresponding operations for the carry/save adder stages for the modified Booth's 2 bit retirement algorithm.

FIG. 4 is a block diagram of selected elements of FIG. 1 indicating how the additional logic "1" signal required for the completion of the 2's complement of the multiplicand operand is entered in the multiplication unit according to the prior art.

FIG. 5 is a block diagram of selected elements of FIG. 1 illustrating how the additional logic "1" signal required to complete the 2's complement of the mulitplicand operand is entered in the multiplier unit according to the present invention.

FIG. 6 illustrates portions of an example of modified Booth's algorithm multiplication according to the prior art and according to the present invention.

FIG. 1, FIG. 2 and FIG. 3 have been discussed with reference to the related art.

Referring next to FIG. 4, the technique for entering the additional logic "1" signal required to complete the 2's complement of the multiplicand operand according to the prior art is illustrated. The encoding apparatus, in response to associated signals from the multiplier operand, determines what operation is to be performed on the multiplicand operand by the associated carry/save adder stage. When this operation is a subtraction of one or two times the multiplicand operand, then the carry/save adder stages generate a 1's complement of the multiplicand operand (by inverting the logic input signals to the carry/save adder cells) and adds the 1's complement signal group to the SUM and CARRY signals. Because the correct subtraction procedure requires that 2's complement signal group be used, the additional logic "1" signal required for generation of the 2's complement signal group is added to the least significant bit position of the associated least significant cell (i.e., the least significant cell position into which the signal in the least significant carry/save adder stage of the next preceding carry/save adder stage will be shifted). When the associated bit group from the multiplier operand requires a subtraction of one times or two times the multiplicand operand, each encoding apparatus 141, 142, 143 and 144 applies a positive signal to the input terminals of the least significant bit position of the least significant cell 151, 152, 153 and 154, respectively. As will be clear, entry in this location is equivalent to entry in the least significant carry/save array position of the signal associated with the least significant bit position of the multiplicand operand. As was discussed with reference to FIG. 1, this logic "1" signal is a fifth signal that can be applied to the least significant bit cell.

Referring next to FIG. 5, the entry of the logic "1" signal to complete the 2's complement of the multiplicand operand according to the present invention is illustrated. As in the implementation in FIG. 4, the presence of specified groups of multiplier operand signals causes the encoding apparatus 141, 142, 143 and 144 to provide a positive output signal when the recoding requires a times one or "times two" subtraction operation. The positive output signals are applied to appropriate unused terminals of the first carry/save adder stage, both the CARRY signal input terminals and the SUM signal input terminals being unused. The particular carry/save adder cell to which the logic "1" signal is added is the cell associated with the least significant bit of each recoded signal group. As illustrated in FIG. 5, the positive signal from the encoding apparatus 141 is applied to the 0.sup.th cell of the first carry/save adder stage 111. A positive signal from encoding apparatus 142 is applied to the 2.sup.nd cell of the first carry/save adder stage, a positive signal from encoding apparatus 143 is applied to the 4.sup.th cell and a positive signal from encoding apparatus 144 is applied to the 6.sup.th cell of first carry/save adder stage 111. As will be clear, the position at which the logic "1" signal is entered in the first carry/save adder circuit is the corresponding position to where the signals are entered in the least significant bit cell.

Referring next to FIG. 6, a partial comparison of the use of the modified Booth's algorithm multiplication according to the prior art and according to the present invention is shown. The multiplier operand (0.10101011) is recoded as 1.(-1) (-1) (-1) (-1) (somewhat differently than illustrated in FIG. 1). The input signals to the first carry/save adder stage 111 (CSA) for the two techniques demonstrates that the present invention enters the 2's complement signals into the stage by means of the SUM (S) input terminals. The first carry/save adder stage 111 used in conjunction with the prior art receives only the (1's) complement signals of the multiplicand operand. Least significant cell 151 receives signals from the first carry/save adder stage 111 and the 2's complement signal resulting from the presence of the first recorded (-1) group of multiplier operand. In the present invention, the 2's complement signal has already been entered, thereby reducing the number of signals applied to the least significant cell. The remaining carry/save adder and least significant cell signals can be determined in a similar manner. The signals for only two carry/save adder stages is shown, however, the remaining signals can be determined in an analogous manner. The signals applied to the carry/sum combining network (CPA) 130 are identical, whether the technique of the prior art or the technique of the present invention is used.

The present invention accelerates the multiplication procedure by eliminating one input signal to the least significant cell associated with each carry/save adder stage that is required when the multiplier unit must execute a subtraction operation in response to selected multiplier bit groups used in recoding (encoding) the multiplier operand for use with the modified Booth algorithm. Instead of adding the appropriate logic "1" signal needed to complete the multiplicand operand's 2's complement of the multiplicand operand to the associated least significant cell, the present invention enters all of the 2's complement additional logic "1" signals to the first carry/save adder stage. Because the CARRY signal and SUM signal input terminals are not used by the first carry/save adder stage, these input terminals are available for signal entry. Entry of the logic "1" signals in this manner reduces the number of input signals to each least significant cell by one, thereby expediting the multiplication procedure.

Because the carry/save adder stage implementation of the multiplication operation uses addition operations, and because the addition operation is commutative, the insertion of logic signals to convert a 1's complement operand to a 2's complement operand provides the same result whether the logic signals ae inserted in the first carry/save adder unit or in the least significant bit cell. This equality can be demonstrated by working through the example begun in FIG. 6. The only requirement is that the position of insertion in the operand be equivalent in either circumstance.

The foregoing description is included to illustrate the operation of the preferred embodiment and is not meant to limit the scope of the invention. The scope of the invention is to be limited only by the following claims. From the foregoing description, many variations will be apparent to those skilled in the art that would yet be encompassed by the spirit and scope of the invention.