Multiplication Control System

This invention relates to a multiplication control system for multiplying a binary-coded multiplier and a binary-coded multiplicand.

The multiplication between binary-coded numbers is carried out by repeating an "add" operation a plurality of times, and the number of bits of the resultant product becomes larger than the numbers of bits of the multiplier and the multiplicand. In general, therefore, a "multiply" instruction requires an instruction executing period of time which is several times longer than that of an "add" or "subtract" instruction. At present, increasing use is being made of "multiply" instructions, not only in electronic computers for science, but also in electronic computers for business, and a variety of inconveniences have occurred due to the long time required for executing binary multiplication operations. Although various multiplication systems have heretofore been proposed, any of them has the disadvantage that the processing time is long. By way of example, a method of multiplication is known wherein the multiplier is processed a bit at a time. If the bit is "1," it is added to a multiplicand, while if the bit is "0," nothing is added. The resultant bit and the multiplier are shifted one digit. This operation is sequentially repeated for the respective bits. According to such a multiplication system, all the bits of the multiplier and the multiplicand must be sequentially processed in this manner. Therefore, the processing time remains fixed whatever the contents of the multiplier and the multiplicand may be. Disadvantageously, even when the number of significant bits is small, a long time for multiplication is required.

It is accordingly an object of this invention to provide a multiplication control system in which the multiply operation is executed for only significant bits of either a multiplier or a multiplicand, whereby the processing time is shortened. In accordance with the invention there is provided a multiplication control system wherein the number of digits in the digits of the multiplier or multiplicand which require operations is detected, the number of recursive or repetitive multiplication operations of a multiplying circuit is determined on the basis of the detected number of digits and a predetermined constant, and the "multiply" operations are executed in the multiplying circuit in accordance with the number of recursive operations required.

FIG. 1 is a block diagram showing the arrangement of multiplication control apparatus according to one embodiment of the invention;

FIG. 2 is a diagram showing an example of the bit construction of a multiplier;

FIG. 3 is a block circuit diagram showing the details of the multiplying circuit 10 in FIG. 1;

FIG. 4 is a flow chart for explaining the operation of the circuits shown in FIG. 1 and FIG. 3; and

FIG. 5 is a block diagram showing another example of a circuit for detecting the number of significant digits in an operand processed in the circuit of FIG. 1.

In an embodiment to be described hereunder, a multiplication system is provided in which the n-bit check system, n being 3, is employed. Assuming that both a multiplier (MPR) and a multiplicand (MCD) are 36-bit signed binary numbers represented respectively as follows:

Expressed as a general formula, ##EQU1## As apparent from the above equation, there are twelve addition terms, and the highest order term is 2.sup.33. Therefore, the multiplication result or product to be evaluated is obtained by repeating the operations in the parentheses of the respective addition terms and the operations of shifting the operated results to 3-bit higher digits (equivalent to multiplying by 2.sup.3) twelve times.

Likewise, ##EQU2## Accordingly, the range of binary data in which both the multiplier (MPR) and the multiplicant (MCD) can be expressed becomes as follows:

Further, the range of values of the product (PRD)=MPR.times.MDC is:

Therefore, a PRD of 72 bits results from the multiplication of two 36 bit terms.

Referring now to FIG. 1, a multiplying circuit 10 receives an MPR 11 and an MCD 12. The multiplying circuit 10 repeatedly executes the respective operations of the twelve addition terms and the 3-bit shiftings until it is stopped by an output signal 15 from a zero detector 14 which detects that the content of a recursive or repetitive control counter 13 is zero. The number of iterations of the operations and the shiftings is determined from the number of significant bits in all the bits of the MPR 11 or the MCD 12. In the example of FIG. 1, the MPR 11 is used to determine the number of iterations. More specifically, the MPR 11 is supplied to a leading O/1 decoder 16. The leading 0/1 decoder 16 provides as a decoded leading signal DLS 17 the number of bits in MPR 11 immediately following bit b.sub.0 which have the same value as the sign bit b.sub.0.

The leading 0/1 decoder 16 has a circuit arrangement which carries out the decoding functions indicated in Table 1.

That is, the decoder circuit provides an output indicating the number of consecutive bits immediately to the right of the sign bit which have the same value as the sign bit. Since such a decoder circuit can be readily realized by combining gate circuits, it need not be explained in further detail for the purposes of this description.

In the specific example of the bit construction of an MPR shown in FIG. 2, twenty-nine bits from bit 1 to bit 29 have the same value ("0") as the sign bit 0. Accordingly, the content of the DLS 17 indicates "29". When this value "29" is divided with a (.div.3) divider 18, a value of "9" is obtained at a output 19 as the resultant quotient. This output is entered into a (.times.3) multiplier 20, and a value of:

([A]: Gaussian symbol, signifying a value of maximum integer which is not greater than A)

is transmitted to a shift circuit 22 as an output 21 indicative of a shift count. In the present example, the output 21 indicates the value of "27." When output 23 from the multiplying circuit 10 enters the shift circuit 22, it is shifted towards lower digits with sign augmentation by the value "27" of the shift count of the output 21, and a final multiplication result is provided on output line 24.

The output from (.div.3) divider 18 is also transmitted to an arithmetic unit ALU 25. Upon command of a function (FUNC) signal 27, the ALU 25 performs a subtraction in which the value of the output from (.div.3) divider 18 is subtracted from the value of the output from the recursive control counter RCNT 13 one line 26. The result on line 28 is returned to a selector 29. As a constant, a value of, e.g., "11" is externally entered into the selector 29 through an input line 30. An output 31 from the selector 29 is entered into the recursive control counter RCNT 13. The RCNT 13 has its contents subjected to "minus 1" (subtracted by one) by a count-down signal 32 which is delivered from the multiplying circuit 10 each time one multiplication is completed. The output 26 of the RCNT 13 is entered into the zero detector 14. In consequence, the output 15 which commands the twelve recursive operations of the multiplying circuit 10 and the shifting corresponding to 3 bits as stated previously is delivered.

Referring to FIG. 2, the principle of operation of the multiplication control will be described in detail. The multiplication based on the 3-bit check system of this embodiment is carried out in such a manner that the multiplier b=b.sub.0 b.sub.1 . . . b.sub.n is separated every 3 bits from the most significant digit. The multiples of the MCD given in Table 1 are determined by the 4 bits in the respective parentheses of Eq. (1), that is, the 4 bits consisting of the 3 bits (b.sub.3i,b.sub.3i+1, b.sub.3i+2) and the subsequent b.sub.3i+3. There are 2.sup.4 or 16 values which are represented by the 4 bits (b.sub.3i through b.sub.3i+3). Among them, the values whose leading bits b.sub.3i are "0" number 8, and the values whose leading bits b.sub.3i are "1" number 8. The remaining 3 bits (b.sub.3i+1 through b.sub.3i+3) are arranged as regards the cases where the leading bits are "0" and "1" respectively, in the following Table 2:

The multiples of the MCD determined by Table 2 are multiplied by the MPR b, and these products are termed partial products PPR's. By sequentially adding the partial products PPR's, the product PRD is obtained.

FIG. 2 serves to explain the operating procedures of the MPR. The multiplying operation of, e.g., "101011" (indicative of "43" in the decimal number) as based on the 3-bit check system is performed as described hereunder.

First of all, the PPR is made zero. By the first operation,

is obtained. In the first operation, the value "3" which corresponds to the second-last value "110" in the column of the leading bit b.sub.3i =0 in Table 2 is selected for the binary number "0110," and the operation (3.times.MCD) in the above equation is executed. (b.sub.36 =0) Initial value of RMPR.sub.36 =0.

By the second operations, there is obtained.

Likewise, the value "-3" which corresponds to the third value "010" in the column of b.sub.3i =1 in Table 2 is selected for the binary number "1010", and the operation (-21.times. MCD) in the above equation is executed.

By the third operation, there is obtained:

Likewise, the value "+1" which corresponds to the second value "001" in the column of b.sub.3i =0 in Table 2 is selected for the binary number "0001," and the operation (43.times.MCD) in the above equation is executed.

All the fourth to twelfth operations become:

The prior art multiplication system requires the step of adding "0" in the fourth to twelfth operations in the above operating procedure. In contrast, this embodiment does not execute the fourth to twelfth operations and can enhance the processing speed.

More specifically, as illustrated in FIG. 1, the bit contents of the MPR is checked and the number of consecutive bits having the same value as the "0" bit and immediately following it is detected by means of the leading 0/1 decoder 16. In the example shown in FIG. 2, "0's" continue from bit 0 to bit 29 as described previously. Therefore, the content of the output DLS 17 of the leading 0/1 decoder 16 indicates the value "29." The divider 18 having received this output DLS 17 conducts the operation of 29.div. 3, and delivers the value "9" to the output 19 as the resultant quotient. On the other hand, the constant input value "11" is introduced into the RCNT 13 through the selector 29 as the recursive control constant in advance, and it is further introduced into the ALU 25. The ALU 25 conducts the operation of 11-9=2 on the basis of the FUNCT signal 27, and the resulting value " 2" is set in the RCNT 13 via the output line 28 and the selector 29. This value of the RCNT 13 is counted down by the signal 32, and is detected by the zero detector 14. Here, the number of times of the recursive operations of the set value "2" becomes "3" (2, 1, 0), and the recursive operation command is transmitted from the output 15 to the multiplying circuit 10. In the multiplying circuit 10, the first to third operations are executed by a procedure to be described below.

The results produced by the multiplying circuit 10 is set in the shift circuit 22, and the shifting is executed. In this shifting, the value "9" of the output 19 of the divider 18 is entered into the (.times.3) multiplier 20, the operation of 9.times.3=27 is performed in the multiplier 20, and the shift value "27" is given to the shift circuit 22 by the output 21. In the circuit 22, the partial product PPR produced through the third operation as obtained from the output 23 is shifted towards lower digits sign augmentation by 27 bits as if the fourth to twelfth operations had been executed. The value of the final product of this result is obtained from output 24.

Referring now to FIGS. 3 and 4, the construction and the operation of the multiplying circuit 10 shown in FIG. 1 will be described.

FIG. 3 is a block diagram showing an embodiment of the multiplying circuit 10. The multiplying circuit illustrated in the figure is constructed of a register 51 which stores MCD,2.times.MCD, 3.times.MCD and 4.times.MCD prepared from the multiplicand MCD; a register 52 which calculates the partial product PPR; an adder circuit 53 which executes addition or subtraction between the value of the partial product PPR generated by register 52 and the multiple value of the MCD selected from the register 51 or which transmits the value of the partial product PPR as it is (i.e., which executes the "0" addition); a control circuit 54 which designates the address for selecting the multiple value of the MCD in register 51 and controls the operation of addition, subtraction or "0" addition in adder circuit 53; a selector 55; a register 56 which receives data from the selector 55; and a bus 57 which delivers a product PRD' formed in the register 56 and the register 52 in a multiplying operation (this product is data which has not yet been subjected to the shifting processing in the shift circuit 22 shown in FIG. 1).

In the multiplying circuit 10, the multiple values of the multiplicand MCD to be stored in the register 51, i.e., 1.times.MDC, 2.times.MCD, 3.times.MCD and 4.times.MCD are obtained as follows. 2.times.MCD is calculated by adding the MCD to 1.times.MCD, 3.times.MCD is determined by adding the MCD to 2.times.MCD, and 4.times.MCD is calculated by adding the MCD to 3.times.MCD. However, the respective multiples of the MCD may be formed in any manner desired. As apparent from the above, the bit length of the register 51 should be at least 2 bits greater than the multiplicand MCD. In FIG. 3, therefore, the register 51 has a bit length of 38 bits with sign augmentation if necessary (bit 0 to bit 37) to accommodate the 36 bit MCD considered in the present embodiment.

The selector 55 selects the multiplier MPR bit 0 to bit 36 (MPR bit 36 initial value is "0" in the example shown) externally supplied, or data obtained in such a way that the multiplier MPR is shifted rightwards by 3 bits each time a multiplication is executed and that the lower 3 bits (bit 35 to bit 37) of the adder circuit 53 are transmitted to the higher 3 bits having been emptied by the right shifting, each time of multiplication. The selector 55 supplies the selected MPR data of the register RMPR 56.

Further, an initial value of "0" is set into the register 52 for the partial product PPR. The produced by the adder circuit 53, i.e., the data at bits 0 to 34 is transmitted to the bit 3 to bit 37 positions of register 52 in order to be used as the partial product PPR in the subsequent operation. In that part of the register 52 which has become empty owing to the transmitting operation, each bit 0-2 of PPR register 52 is set equal to the value of bit 0 of the adder circuit 53 for the sign augmentation. When the multiplying circuit has completed the operations of the number of times of multiplication already explained, the 72 bits of data formed by concatenating bits 2-37 from PPR registers 52 with bits 0-35 from the MPR register 56 are transmitted from the output bus 57 to the shift circuit 22 in FIG. 1 in order to form the result to be product determined.

A specific example of operation of the above multiplying circuit will now be described. The explanation will be made of an actual multiplication employing concrete numerical values. To this end, the operation for a multiplier MPR having a decimal value of 43 will be referred to, and the multiplicand MCD will be assumed to have a value of 8.

(Example)

At this time,

is to be obtained.

The left-digit in each binary number is the sign bit. In each case this bit is 0 because MPR, MCD are both positive.

In this case, the respective multiple values of the multiplicand MCD to be entered in the register 51 in FIG. 3 are given in Table 3:

Here, let's confirm again the multiplication at the time when the multiplier MPR=43. It is confirmed that this multiplication can obtain the product by the three operations in all.

The first operation is: (PPR.sub.0 =0 by initially set)

Thus, the addition between the initial value of the register 52 and the and the value of 3.times.MCD of the register 51 is executed by the adder circuit 53. At this time, the control circuit 54 addresses 3.times.MCD of the register 51 because RMPR register 56 bit 33-36 is "0110" and controls the adder circuit 53 so as to carry out the 0 addition.

Accordingly, ##STR3## is executed in the adder circuit 53. Thus, 3.times.MCD= PPR.sub.1 is obtained. The result A.sub.1 and 3 bit sign augmentation is the partial product of the next operation and is set in the register 52. On the other hand, the result B.sub.1 forms part of the product, and the product of the last 3 bits which are not changed is obtained at once in the operation of the 3-bit check system adopted in the foregoing. The value of B.sub.1 is set in the register 56 through the selector 55. The state of the register 56 at this time becomes: ##STR4##

The second operation is:

This signifies that -3.times.MCD.times.2.sup.3 =-24MCD is added to 3.times.MCD determined in the first operation. At this time, accordingly, the control circuit 54 addresses -3.times.MCD of the register 51 because RMPR register 56 bit 33-36 is "1010" and controls the adder circuit 53 so as to execute the subtraction. The second operation is confirmed to be:

[A]: Gaussian symbol

Let's confirm the value of the register 52 after the first operation. In the register 52, the data at the bit 0-34 of the adder circuit 53 (i.e., the result A.sub.1 and 3 bits sign augmentation of the first operation) is set. This signifies that the partial product PPR.sub.1 obtained by the first operation is shifted rightwwards by 3 bits and is set.

Accordingly, the second operation simply subtracts the value of 3.times.MCD of the register 51 from the value of the register 52, whereby the partial product PPR.sub.2 is obtained. This operation is indicated as follows: ##STR5## 3.times.MCD-24MCD=-21.times.MCD= PPR.sub.2 is obtained from the adder circuit 53. As in the first operation, the result A.sub.2 and 3 bits sign augmentation is the partial product of the next operation and is set in the register 52. Similarly, the result B.sub.2 forms part of the product, and this product of 3 bits is set in the register 56 through the selector 55. The state of the register 56 at this time becomes: ##EQU3##

The third operation is:

This operation signifies that (1.times.MCD).times.2.sup.6 =64 MCD is added to the partial product -21 MCD obtained in the second operation. The control circuit 54 at this time accordingly addresses 1.times.MCD of the register 51 and controls the adder circuit 53 so as to execute the addition. As in the second operation, the third operation can be substituted by:

As to the partial product PPR.sub.1 being the result of the first operation, the data having been shifted rightwards by 3 bits [PPR.sub.1 /2.sup.3 ]is set in the register 52. As to the partial product PPR.sub.2 being the result of the second operation having employed this data of the register 52, the data having been shifted rightwards by 3 bits is set in the register 52. Therefore, the data of [PPR.sub.2 /2.sup.6 ]is set in the register 52.

Accordingly, also the third operation simply adds the data of the register 52 and the data of 1.times.MCD from the register 51, whereby the partial product PPR.sub.3 can be obtained. This operation is indicated as follows: ##EQU4## -21.times.MCD+64.times.MCD=43.times.MCD= PPR.sub.3 is obtained from the adder circuit 53. The data A.sub.3 and 3 bits sign augmentation of the operated result is set in the register 52, and the data B.sub.3 is set in the register 56 through the selector 55.

The multiplication of the example is completed by the above three operations. The data set in the register 52 and the register 56 form the product, as is confirmed by the following: ##STR6## The data of the products B.sub.3, B.sub.2 and B.sub.1 formed every 3 bits by the three operations form "101011000"=(344), which is transmitted through the bus 57 to the shift circuit 22 in FIG. 1. The shift circuit 22 contains a right shift count of "27" from the (.times.3) multiplier 20 shown in FIG. 1. Accordingly, the data of the register 52 and the register 56 are shifted rightwards by 27 bits. Then, they become: ##STR7## All the operations in the multiplication control illustrated in FIG. 1 are completed, and the result of the shifting, "0 . . . 0101011000"=(344) is delivered as the output.

The flow chart of the above multiplication control will be described with reference to FIG. 4. In initial step S.sub.1, a "0" is set into PPR register 52 and counter RCNT 13 is set to an initial value of "11." In step S2, the number of those digits of the multiplier MPR which need not be operated on is detected by the leading 0/1 decoder 16, and the output DLS is obtained. The multiplier MPR is set into the register 56. The number of recursive operations of the multiplying circuit 10 with [DLS/3] subtracted from counter RCNT 13 is determined and is set in the counter RCNT 13, and therewith, the right shift count of the product [DLS/3].times.3.fwdarw. RSC is obtained. At steps S.sub.3, S.sub.4, S.sub.5 and S.sub.6, the respective multiples of the multiplicand MCD are calculated and set in the register 51. At steps S.sub.7, the operations described with reference to FIG. 3 are executed with the operation number (loop count 12- [DLS/3]) controlled by the RCNT 13. The partial product PPR obtained every operation is shifted rightwards by 3 bits, and is transmitted to the register PPR 52 and the register RMPR 56. In step S.sub.8, the result obtained at S.sub.7 is shifted by the right shift count RSC and is then delivered at the output. An indicator is set according to the result obtained at S.sub.8 and the procedure terminates.

Although the MPR was assumed to have a positive value in the above embodiment, the system of the invention operates similarly in the case where it has a negative value. It is necessary to take care in the case of an overflow from the adder circuit 53 (only the case (-2.sup..+-.).times.(-2.sup.35)= 2.sup.70) that PPR register 52 bits 0-2 must be set to a special value representing the complement of bit 0 of the adder circuit 53. Although in the above described embodiment the number of significant digits of the MPR was detected by the leading 0/1 decoder, the system can also operate by detecting the significant digits of the MCD. This invention can be applied, not only to operations involving fixed point numbers, but also to multiplications of floating point numbers. Also in the case of floating point operation, most of the numbers are normalized, and hence, the lower order bits are often "0." Accordingly, how many bits are "0" as reckoned from the lowest bit is detected by the use of a trailing 0 decoder 60 as shown in FIG. 5, and the bits of the MPR or MCD are shifted in correspondence with the number of times of adding "0" likewise to the foregoing, whereby the average processing speed can be enhanced as in the previous embodiment. The number-of-digits detection output of the trailing 0 decoder 60 may be processed alike as the leading 0/1 decoder.