US 5,142,490 AGrant
Multiplication Circuit With Storing Means
Issue Date:1992-08-25
•3 Claims
•2 Drawing Sheets
Abstract
The multiplication circuit is formed in such a manner that the intermediate sums of partial products are divided into a lower places group and a higher places group and the operations for obtaining the products of the lower places group alone of the intermediate sums already found are carried out parallel to the processing for obtaining the higher places group of the intermediate sums to obtain the higher products thereafter, noting to the fact that the intermediate sums of partial products are found sequentially from lower places to higher places. By adopting such an arrangement, the operations for obtaining the higher places group of the intermediate sums can be processed in parallel with the operations for obtaining the products of the lower places group of the intermediate sums already found, and the higher products are found thereafter. Therefore, the time required for the former-stage processing and that required for the latter-stage processing can be made more uniform.
Metadata
Assignee
- Mitsubishi Denki Kabushiki Kaisha
Inventors
- Yoshiki Tsujihashi
- Kazuhiro Sakashita
Application Information
Application Number:US 617440&
Filing Date:1990-11-19
Priority Date:1988-10-18
Art Unit:231
Classifications
IPC:
G06F 752
Field of Search:
364754-760;784
Patent Drawings (2 sheets)
Description
Background of the Invention
1. Field of the Invention
The present invention relates to a multiplication circuit, and more in particular, to a multiplication circuit wherein the operational processing is pipelined.
2. Description of the Prior Art
FIG. 1 is a block diagram showing an arrangement of an 8 bits.times.8 bits secondary Booth's multiplier wherein applied is the arrangement of a multiplier as disclosed in Japanese Patent Application Laid-Open No. 58-31449 (1983).
In FIG. 1, the numeral 1 denotes a first adding circuit for calculating the intermediate sums of partial products, while a numeral 3 a first storing circuit for storing the output from the first adding circuit 1.
A numeral 2 denotes a second adding circuit. Here the product output is calculated from the outputs from the first adding circuit 1 stored in the first storing circuit 3, namely, the outputs of the intermediate sums, as inputs. The product output from the second adding circuit 2, that is, the multiplication result is stored in a second storing circuit 4.
Both the first adding circuit 1 and the second adding circuit 2 comprise plural number of adders. In the drawing, characters HA and FA denote a half adder and a full adder respectively.
The operations of such a conventional multiplication circuit are as follows.
In FIG. 1, four partial products P.sub.i8 P.sub.i7 . . . P.sub.i0 (where i equals to 0, 1, 2, 3) found in accordance with Booth's algorithm are added in the first adding circuit 1 to obtain S.sub.j, C.sub.j (j=0.about.14), the outputs of the intermediate sums of the partial products. Thus found outputs of the intermediate sums are temporarily stored in the first storing circuit 3. Then the signals for the intermediate sums S.sub.j are added, while the carry signals C.sub.j are sequentially transmitted to the adjacent higher place between the half adders and full adders constituting the second adding circuit 2, to obtain the product output Zk (k=0.about.15), which is stored in the second storing circuit 4. This product output Zk is the multiplication result.
Therefore, in such a construction, it is possible that the partial products outputs found in the first adding circuit 1 are temporarily stored in the first storing circuit 3 and the next operation is executed in the first adding circuit 1, while the operations for obtaining this product output are being carried out in the second adding circuit 2. That is, it is possible to increase the operational efficiency by the pipelined processing of the multiplication at two stages, first in the first adding circuit 1 and, second in the second adding circuit 2.
The generating operations of the partial products and the operations in the first adding circuit 1 are hereinafter called the former-stage operations, while the operations in the second adding circuit 2 the latter-stage operations.
Among the signal transmitting paths leading to the output signals S.sub.j, C.sub.j in the former-stage operations, the longest are those of S.sub.6 to S.sub.10 and C.sub.7 to C.sub.11. Three adders (HA, FA) are provided on each of these paths. The paths leading to other output signals are shorter than the paths just referred to. Consequently, generated are differences in delayed time caused by the existence of adders (HA, FA) provided on the signal paths.
On the other hand, the output signal Zk in the latter-stage operations is found, carrying sequentially from higher places to lower ones. Therefore, the greater k is, the more time it requires in determining the value. For this reason, as the number of the half adders and the full adders constituting the second adding circuit 2, that is, the number of places of the multiplication numbers increases, it takes more time in carrying out the latter-stage operations.
Thus in a multiplication circuit wherein Booth's algorithm is utilized, more time is required in carrying out the latter-stage operations than in carrying out the former-stage operations. Consequently, the cycle is forced to be dependent on the time required for carrying out the latter-stage operations when the operations are carried out in the two-staged pipeline wherein one stage is assigned to each of the former-stage operations and the latter-stage operations.
Thus arranged is a conventional multiplication circuit. Therefore, the degree of parallel of operations remains on a low level, and there is a room for further improvements in shortening the entire processing time. Furthermore, in the latter-stage operations, if the number multiplied is n bit.times.n bit, transmissions of the carry signals are caused 2n-1 times to require more time than in the former-stage operations. Consequently, the cycle for the pipelined processing is forced to be dependent on the time required for the latter-stage operations when the two-staged pipelined processing is carried out. As a result, there arises a problem that the entire efficiency in carrying out the processing is lowered.
Summary of the Invention
The present invention has been made in view of the problems as mentioned above, and intends to provide a multiplication circuit wherein the time needed for a cycle of the pipelined processing can be shortened by increasing the degree of parallel in operations and reducing the difference between the time required for the former-stage processing and that required for the latter-stage processing when a pipelined processing is carried out.
The multiplication circuit according to the present invention is formed in such a manner that the intermediate sums are divided into a lower places group and a higher places group and the operations for obtaining the products of the lower places group alone of the intermediate sums already found are carried out parallel to the processing for obtaining the higher places group of the intermediate sums to obtain the higher products thereafter, noting to the fact that the intermediate sums of partial products are found sequentially from lower places to higher places. By adopting such an arrangement, the operations for obtaining the higher places group of the intermediate sums can be processed in parallel with the operations for obtaining the products of the lower places group of the intermediate sums already found, and the higher products are found thereafter. Therefore, the time required for the former-stage processing and that required for the latter-stage processing can be made more uniform.
The above and further objects and features of the invention will more fully be apparent from the following detailed description with accompanying drawings.
Brief Description of the Drawings
FIG. 1 is a block diagram showing an arrangement of a conventional multiplication circuit; and
FIG. 2 is a block diagram showing an arrangement of a multiplication circuit according to the present invention.
Description of the Preferred Embodiments
The present invention will be described with reference to the drawing showing a preferred embodiment thereof.
FIG. 2 is a block diagram showing an arrangement of a multiplication circuit according to the present invention, which shows an example of an arrangement as an 8 bits.times.8 bits secondary Booth's multiplication circuit similarly to the conventional example.
In FIG. 2, the numeral 1 denotes a first adding circuit for calculating the intermediate sums of partial products. The lower six places of the outputs of the intermediate sums of partial products found in the first adding circuit 1 are directly given to a second adding circuit 2a for lower places group which will be described later, while other higher places are given to a first storing circuit 3.
The first storing circuit 3 stores the outputs from the first adding circuit 1, that is, the outputs of the higher places other than the lower six places of the outputs of the intermediate sums.
The signal 2a is the second adding circuit for lower places group for calculating the lower six places of the product output, which calculates the product output from the lower six places of the outputs of the intermediate sums found in the first adding circuit 1 as inputs. This product output from the second adding circuit 2a for lower places group and its final carry output ZC are stored in the first storing circuit 3.
The signal 2b is a second adding circuit for higher places group for calculating the higher places of the product output, which calculates the product output from the higher places other than the lower six places of the outputs of the intermediate sums found in the first adding circuit 1 and stored in the first storing circuit 3 as inputs. The output from the second adding circuit 2b for lower places group is stored in a second storing circuit 4 similarly to the output from the second adding circuit 2a for lower places group.
Both the first adding circuit 1 and the second adding circuit 2 comprise plural number of adders. In the drawing, characters HA and FA denote a half adder and a full adder respectively.
The operations of such a multiplication circuit of the present invention are as follows.
In FIG. 2, four partial products P.sub.i8 P.sub.i7 . . . P.sub.i0 (where i equals to 0, 1, 2, 3) found in accordance with Booth's algorithm are added in the first adding circuit 1 to obtain S.sub.j, C.sub.j (j=0.about.14), the outputs of the intermediate sums of the partial products.
Among thus found outputs of the intermediate sums, signals S.sub.0 to S.sub.5 for the intermediate sums of the lower six places and carry signals C.sub.3 to C.sub.5 are given to the second adding circuit 2a for lower places group, while other intermediate sums S.sub.6 to S.sub.14 of other higher places and C.sub.7 to C.sub.13 are given to the first storing circuit 3 and stored temporarily. At this time, the lower six places of the outputs of the intermediate sums can be found faster than other higher places, so, product outputs Z.sub.0 to Z.sub.5 of the lower six places and a carry output ZC have also been calculated to be stored in the first storing circuit 3 by the time the higher places are calculated and their results are stored in the first storing circuit 3.
In this connection, the generation of partial products in the first adding circuit 1 as mentioned above and the operations in the second adding circuit 2a for lower places group are called the former-stage operations in the circuit according to the present invention. The time required for the former-stage operations in the circuit according to the present invention is, of course, shorter than the sum of the time required for the operations in the first adding circuit 1 and that required for the operations in the second adding circuit 2a for lower places group.
In the next place, the outputs of the inter mediate sums S.sub.6 to S.sub.14 of higher places stored in the first storing circuit 3 and C.sub.7 to C.sub.13, and the final carry output ZC are given to the second adding circuit 2b for higher places group to obtain the higher ten places Z.sub.6 to Z.sub.15 of the product output. And the product output of the higher ten places and the product outputs Z.sub.0 to Z.sub.5 in the second adding circuit 2a for lower places group are stored in the second storing circuit 4.
In the circuit according to the present invention, the operations in the second adding circuit 2b for higher places group are called the latter-stage operations.
In the latter-stage operation according to the present invention, the operations of the higher ten places alone among sixteen places of 8 bits.times.8 bits product outputs are carried out. Therefore, the time required for the latter-stage operations can be reduced in comparison to a conventional multiplication circuit. In other words, the difference between the processing time required for the former-stage operations and that required for the latter-stage operations is reduced, so that the whole processing time is shortened and the cycle can be made shorter when the pipeline processing is carried out.
In the embodiment mentioned above, the Booth's algorithm is utilized, and additions for obtaining the intermediate sums of partial products are carried out by the carry-save method. Other alternative methods, however, can also be used. Also in the embodiment mentioned above, the present invention is applied to an 8 bits.times.8 bits multiplication circuit. But it should not be limited to such multiplication circuit. Likewise the position for dividing the outputs of the intermediate sums should not be limited.
As mentioned above in detail, in the multiplication circuit according to the present invention, among the operations of the final addition for obtaining the product outputs, the additions of lower places are carried out in parallel with those for obtaining higher places of the intermediate sums of the partial products, so that a multiplication circuit capable of processing at a higher-speed can be realized. It is also possible to shorten the cycle when the pipeline processing is carried out. As this invention may be embodied in several forms without departing from the spirit of essential characteristics thereof, the present embodiment is therefore illustrative and not restrictive, since the scope of the invention is defined by the appended claims rather than by the description preceding them, and all changes that fall within the meets and bounds of the claims, or equivalence of such meets and bounds thereof are therefore intended to be embraced by the claims.
Claims
What is claimed is:
1. A circuit for improving calculation distribution in a pipelined multiplication circuit, the multiplication circuit producing a plurality of intermediate sums from a plurality of partial products generated from a first number and a second number to be multiplied together, with a sum of the plurality of partial products producing a value representative of a product of the first and second number, the circuit comprising: a first adding circuit for stepwise addition of a plurality of partial products disposed in columns to calculate a plurality of intermediate sums; a second adding circuit, having a first part, coupled to said first adding circuit, for forming a bit-area of a final product from a low-order group of said plurality of intermediate sums and a carry out of said bit-area, and a second part for forming a final product of the first and the second number from said plurality of intermediate sums; and a storing circuit coupled to said first and said second adding circuits, for receiving said bit-area and said carry-out from said first part of said second adding circuit and a high-order group of said plurality of intermediate sums from said first adding circuit, said high-order group not including intermediate sums from said low-order group, and for providing said bit-area, said carry-out and said high-order group to said second part of said second adding circuit.
2. The circuit as set forth in claim 1, wherein a pipeline processing is carried out with said first adding circuit and said second adding circuit.
3. The circuit as set forth in claim 1, wherein said first and second adding circuits comprise a secondary Booth's multiplication circuit.
Patent Citations (5)
Non-Patent Literature (1)
- S. Waser et al., "Real Time Processing Gains Ground with Fast Digital Multiplier", Electronics, Sep. 29, 1977, pp. 93-99.