JPS6250853B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION (1) Technical Field of the Invention The present invention provides a multiplication section having a decoder for decoding a multiplier, multiple gates, a CSA (carry save adder) tree, and a spill adder. In addition, in a multiplication device having a main adder into which the sum and carry outputted from each multiplication section are time-divisionally input, the bit width of the main adder and peripheral circuit section can be reduced. be.

(2) Problems with the prior art Figure 1 shows a conventional multiplication device.
1 is an input register where the multiplicand is set, 2 is an input register where the multiplier is set, 3 is a multiplexer, 4 is a decoder, 5 is a multiple gate,
6 and 7 are CSA, 8 is an intermediate register where the sum is set, 9 is an intermediate register where the carry is set, 10 is a spill adder, 11 is a flip-flop, and 12 is a carry propagation adder. The main adders 13 and 13 respectively indicate result registers.

In the example shown in FIG. 1, input registers 1 and 2 each have a 4-byte configuration. multiplexer 3
first selects the least significant byte (byte 3), and finally selects byte 0. The byte information selectively output from the multiplexer 3 is input to the decoder 4. The output of decoder 4 is multiple gate 5
is input. The multiple gate 5 selects four types of multipliers based on the decoded signal from the decoder 4.
K ₁ , K ₂ , K ₃ , and K ₄ are generated, and the multipliers multiplied by K ₁ , K ₂ , K ₃ , and K ₄ are input into the CSA 6. The sum and carry signals output from CSA6 are input to CSA7. At this time, the upper 4 bytes of intermediate register 8 and the upper 4 bytes of intermediate register 9 are also input to CSA 7. Sam and Carrie output from CSA7 are
The signals are input to intermediate registers 8 and 9, respectively. Least significant byte of intermediate register 8 and intermediate register 9
The least significant byte of is input to spill adder 10. The spill adder 10 also receives the contents of the flip-flop 11. The carry output from spill adder 10 is set in flip-flop 11. At a predetermined timing,
The contents of intermediate register 8, intermediate register 9 and flip-flop 11 are input to main adder 12, and the output of main adder 12 is set in result register 13.

In FIG. 1, the input register 1 has a 32-bit configuration, the bus from the input register 1 to the multiple gate 5 also has a 32-bit configuration, and the bus from the multiplexer 3 to the decoder 4 has an 8-bit configuration. Intermediate registers 8 and 9 have a 5-byte configuration, and from intermediate register 8 to main adder 1
The width of the bus from intermediate register 9 to main adder is 40 bits. The bus from intermediate register 8 to the input of CSA 7 has a 32-bit configuration, and the bus from intermediate register 9 to the input of CSA 7 also has a 32-bit configuration. Maine·
The output of the adder 12 consists of 5 bytes, but the least significant byte is discarded and only the upper 4 bytes are set in the result register 13. In addition, input registers 1 and 2, decoder 4, multiple gate 5,
CSAs 6 and 7, intermediate registers 8 and 9, spill adder 10 and flip-flop 11 constitute the multiplication section.

Figure 2 is a time signal showing the operation of the multiplier in Figure 1.
It's a chat. In FIG. 2, A indicates a multiplicand, B a multiplier, and C a result operand. When a multiplication is commanded, the multiplication of A×B(1) is started at the #1 clock. In addition, B(1) is byte (3) of multiplier B, B(2) is byte 2 of multiplier B, B(3)
indicates byte 1 of multiplier B, and B(4) indicates byte 0 of multiplier B, respectively.

At clock #2, multiplication of A×B(2) is started, and the sum component SU(1) and carry component CA(1) of A×B(1) output from CSA are transferred to intermediate registers 9 and 9. are set respectively.

At clock #3, multiplication of A×B(3) is started. Also, the sum of A×B(2), the upper 4 bytes of the sum component SU(1), and the upper 4 bytes of the carry component CA(1) is separated into the sum component SU(2) and the carry component CA(2). They are set in intermediate registers 8 and 9, respectively. Furthermore, a carry R(1) obtained by adding the least significant byte of the sum component SU(1) and the least significant byte of the carry component CA(1) is set in the flip-flop 11.

At clock #4, multiplication of A×B(4) is started. Also, the sum of A×B(3), the upper 4 bytes of the sum component SU(2), and the upper 4 bytes of the carry component CA(2) is separated into the sum component SU(3) and the carry component CA(3). They are set in intermediate registers 8 and 9, respectively.
Further, carry R(2), which is generated when adding the least significant byte of the sum component SU(2), the least significant byte of the carry component CA(2), and the carry R(1), is set in the flip-flop 11.

In cycle #5, A×B(4) and sum component SU(3)
The sum of the upper 4 bytes of and the upper 4 bytes of the carry component CA(3) is separated into a sum component SU(4) and a carry component CA(4), which are set in intermediate registers 8 and 9, respectively. Also, the lowest byte of the sum component SU(3), the lowest byte of the carry component CA(3), and the carry R(2)
The carry R (3) that occurs when adding
It is set on flop 11. Furthermore, the main
The adder 12 is activated and the sum component SU(4), carry component CA(4), and carry R(3) are added.

At clock #6, the upper 4 bytes of the output of main adder 12 are set in result register 13.

By the way, a multiplier for vector operands consists of multiple multiplication parts and one multiplier as shown in Figure 1.
It has already been proposed to consist of two main adders. This type of multiplier has the disadvantage that it is necessary to transfer the 40-bit sum and carry components from each multiplication section to the main adder, making the bus and selection gate configurations very complex.

(3) Purpose of the Invention The present invention aims to eliminate the above-mentioned drawbacks and is to provide a decoder for decoding a multiplier and a multiple decoder for decoding a multiplier.
In a multiplier that has multiple multiplication sections consisting of gates, CSA trees, and spill adders, and one main adder into which the sum component, carry component, and numerical data for accuracy guarantee that are output from each multiplication section are input. The object of the present invention is to provide a multiplication method that can simplify the configuration of peripheral parts such as buses and selection gates leading from each multiplication part to a main adder, and can also reduce the bit width of the main adder.

(4) Structure of the Invention Therefore, the multiplication method of the present invention consists of a multiplicand register 1 in which an m×n bit multiplicand is set, a multiplier register 2 in which an m×n bit multiplier is set, and a multiplier register 2 in which an m×n bit multiplicand is set. A decoder 4 decodes the n-bit data extracted from the decoder 4, a multiple gate 5 that calculates a multiple of the multiplicand based on the decoding result of the decoder 4, and an intermediate register 8 for the multiple and sum of the multiplicand from the multiple gate 5. The carry save adder trees 6 and 7 to which the upper m×n bits and the upper m×n bits of the carry intermediate register 9 are input, and the sum components output from the carry save adder trees 6 and 7 are set. The carry components output from the sum intermediate register 8 of (m+1)×n bit width and the carry save adder trees 6 and 7 are set (m+1)×n bits wide.
1) ×n-bit wide carry intermediate register 9
and a spill adder 10 into which the lowest n bits of the sum intermediate register 8, the lowest n bits of the carry intermediate register 9, and the contents of the flip-flop 11 are input, and output from the spill adder 10. a plurality of multiplication parts having a flip-flop 11 in which the carry is set; and a final sum register in which the upper m×n bits of the intermediate sum register 8 selected in the plurality of multiplication parts are set. 14, a final carry register 15 to which the upper m×n bits of the selected carry intermediate register 9 in the plurality of multiplication parts are set, and a plurality of flip-flops 10 are selected, and the selected flip-flop - in a multiplication device comprising a multiplexer 16 which outputs the contents of the flop 10, and a carry propagation adder 12' into which the contents of the final sum register 14, the contents of the final carry register 15 and the output of the multiplexer 16 are input; , When input operands to be multiplied are sent, select one multiplication part and set multiplicand A and multiplier B in multiplicand register 1 and multiplier register 2 of the multiplication part, respectively, and The i-th n-bit data B(i) is extracted from , the n-bit data B(i) is decoded using the decoder 4, the multiple of the multiplicand A is obtained using the multiple gate 5, and the Using the carry adder trees 6 and 7, find the sum of A×B(i), the sum intermediate register 8, and the carry intermediate register 9, and the resulting sum component SU(i) and carry component CA(i ) in the sum intermediate register 8 and the carry intermediate register 9, respectively, and the sum component SU(i) of the thumb intermediate register 8 and the carry component CA(i) of the carry intermediate register 9.
and the contents of flip-flop 11.
Adder 10 is input, and the resulting carry is set in flip-flop 11.

A series of processes are performed in order for each of the first n-bit data to the m-th n-bit data of the multiplier register 2, and after the above processing is completed for the m-th n-bit data. , intermediate register 8 for thumb
and the upper m×n bits of the intermediate register 9 for carry are respectively used as the final sum.
Register 14 and final carry register 15
After the above processing is completed for the mth n-bit data, the final sum register 1 is set to
4, the contents of the final carry register 15, and the contents of the flip-flop 11 are added by a carry propagation adder 12'.

(5) Examples of the invention Hereinafter, the present invention will be explained with reference to the drawings.

FIG. 3 is a block diagram of one embodiment of the present invention, and FIG.
The figure is a time chart showing the operation.

In Figure 3, 1-1 and 1-2 are input registers, 2-1 and 2-2 are also input registers, 3-1 and 3
-2 is a multiplexer, 4 is a decoder, 5-1 and 5-2 are multiple gates, 6-1 and 6-2 are
CSA, 7-1 and 7-2 are also CSA, 8-1 and 8-2
is the intermediate register where the sum is set, 9-1 and 9
-2 is the intermediate register where the carry is set, 1
0-1 and 10-2 are spill adders, 11-1 and 11-2 are flip-flops, 12' is the main adder, 13 is the result register, 14 is the final sum register, 15 is the final carry register,
16 indicates a multiplexer, respectively. Input registers 1-1 and 2-1, multiplexer 3-
1, decoder 4-1, multiple gate 5-
1. CSA6-1 and 7-1, intermediate register 8-1
and 9-1, a spill adder 10-1, and a flip-flop 11-1 constitute the first multiplication section, and similarly input registers 1-2 and 2-2, multiplexer 3-2, and decoder 4- 2. Multiple gates 5-2, CSA 6-2 and 7-2, intermediate registers 8-2 and 9-2, spill adder 10-
2 and flip-flop 11-2 constitute a second multiplication section. These first multiplication section and second multiplication section have the same configuration as the multiplication section shown in FIG. The final sum register 14 is set with the upper four bytes of the final sum component of intermediate register 8-1 or 8-2. The final carry register 15 is set with the upper four bytes of the final carry component of intermediate register 9-1 or 9-2. The final sum register 14 has a 4-byte configuration, and the final carry register 15 also has a 4-byte configuration. The multiplexer 16 selects and outputs the accuracy guarantee carry of the flip-flop 11-1 or 11-2. The main adder 12' includes a final sum register 14.
, the contents of final carry register 15 and the output of multiplexer 16 are input. Main adder 12' is 32 bits wide. The output of main adder 12' is set in result register 13.

FIG. 4 is a time chart showing the operation of the embodiment shown in FIG. As shown in FIG. 4, first, multiplicand A1 and multiplier B1 are input into the first multiplication section, and two cycles later, multiplicand A2 and multiplier B2 are input into the second multiplication section. First, the multiplication of A1×B1 will be explained.

At the #1 clock, multiplication of A1×B1 is started.

#2 clock starts the multiplication of A1×B1(2), and also the A1×B1(1) output from CSA7-1.
The sum component SU1(1) and carry component CA1(1) of are set in intermediate registers 8-1 and 9-1, respectively.

At clock #3, multiplication of A1×B1(3) is started. Also, the sum of A1×B1(2), the upper 4 bytes of the sum component SU1(1), and the upper 4 bytes of the carry component CA1(1) is separated into the sum component SU1(2) and the carry component CA1(2). They are set in intermediate registers 8-1 and 9-1, respectively. Furthermore, the carry R1(1) obtained by adding the least significant byte of the sum component SU1(1) and the least significant byte of the carry component CA1(1) is set in the flip-flop 11-1.

At clock #4, multiplication of A1×B1(4) is started. Also, the sum of A1×B1(3), the upper 4 bytes of the sum component SU1(2), and the upper 4 bytes of the carry component CA1(2) is separated into the sum component SU1(3) and the carry component CA1(3). They are set in intermediate registers 8-1 and 9-1, respectively. Furthermore, carry R1(2), which is generated when adding the least significant byte of sum component SU1(2), the least significant byte of carry component CA1(2), and carry R1(1), is set in flip-flop 11-1. .

In #5 cycle, A1×B1(4) and sum component SU1
The upper 4 bytes of (3) and the upper 4 of carry component CA1(3)
The sum of the bites is the sum component SU1 (4) and the carry component CA1
(4) Separated into intermediate registers 8-1 and 9, respectively.
-1. Also, the carry value generated when adding the least significant byte of the sum component SU1(3), the least significant byte of the carry component CA1(3), and the carry R1(2)
R1(3) is set in flip-flop 11-1.

In cycle #6, the upper 4 bytes of the sum component SU1(4) are set in the final sum register 14, and the upper 4 bytes of the carry component CA1(4) are set in the final carry register 15. Note that in FIG. 4, X indicates the register 14 and Y indicates the register 15. Also, the carry value generated when adding the least significant byte of the sum component SU1(4), the least significant byte of the carry component CA1(4), and the carry R1(3)
R1(4) is set in flip-flop 11-1, and multiplexer 16 selectively outputs the contents of flip-flop 11-1. moreover,
The main adder 12' is activated and the sum component SU1
(4), the carry component CA1(4) and the accuracy guarantee carry R1(4) are added.

At clock #7, the output of main adder 12' is set in result register 13.

The multiplication of A2×B2 is also performed in the same manner as the multiplication of A1×B1. However, the A2×B2 multiplication starts two cycles after the A1×B1 multiplication. Although the control means for performing the above-mentioned control is not shown in FIG. 3, the above-mentioned control can be performed by a microprogram or a wiring logic control circuit.

As can be seen by comparing the multiplication device of FIG. 1 with the embodiment of FIG. The bit width is getting smaller. This is Spill Adder 10-1,10
This is because by using -2 for four cycles, the spill adders 10-1 and 10-2 perform the 1-byte truncation that is performed by the main adder 12 in FIG. If the multiplier has multiple multiplier sections, as in FIG. 3, it will be necessary to select the final sum and carry components from each multiplier section and enter them into the main adder 12'.
Compared to a general-purpose type multiplication device as shown in FIG. 1, one cycle of the previous stage of the main adder is required.
The present invention utilizes this selection cycle to reflect the results of each spill adder 10-1 and 10-2 in the result operand, thereby reducing the bit width of the main adder and peripheral circuit portion. be. Furthermore, if the result operand is 8 bytes, the main adder can be 7 bytes, and the remaining 1 byte can be supplemented with 1 byte of the spill adder result.

(6) Effects of the invention As is clear from the above explanation, according to the present invention, a decoder that decodes a multiplier, a multiple
In the main adder, which has a plurality of multiplication sections including gates, CGA tris, and spill adders, and into which the sum and carry output from each multiplication section are time-divisionally input, the main adder and the peripheral circuit section It becomes possible to reduce the bit width of

[Brief explanation of the drawing]

FIG. 1 is a block diagram of a conventional multiplication device, FIG. 2 is a time chart showing its operation, FIG. 3 is a block diagram of an embodiment of the present invention, and FIG. 4 is a time chart showing its operation. 1-1 and 1-2...input register, 2-1 and 2-
2...Input register, 3-1 and 3-2...Multiplexer, 4...Decoder, 5-1 and 5-2...Multiple gate, 6-1 and 6-2...CSA, 7-1 and 7-2...CSA , 8-1 and 8-2...intermediate registers where sum is set, 9-1 and 9-2...intermediate registers where carry is set, 10-1 and 10-
2... Spill adder, 11-1 and 11-2... Flip-flop, 12'... Main adder, 13
...Result register, 14...Final sum register, 1
5...Final carry register, 16...Multiplexer.

Claims (1)

[Claims] 1 Multiplicand register 1 in which an m×n bit multiplicand is set, multiplier register 2 in which an m×n bit multiplier is set, and n-bit data extracted from multiplier register 2. a decoder 4 that decodes the decoder 4; a multiple gate 5 that calculates a multiple of the multiplicand based on the decoding result of the decoder 4;
Carry save adder trees 6 and 7 are input with the multiple of the multiplicand from the multiple gate 5, the upper m×n bits of the sum intermediate register 8, and the upper m×n bits of the carry intermediate register 9, and the digit. An intermediate register 8 for sum with a width of (m+1)×n bits, in which the sum component output from the carry save adder trees 6 and 7 is set, and a carry save adder tree 6 and 7
The carry component output from is set (m
+1)×n-bit width intermediate carry register 9
and a spill adder 10 into which the lowest n bits of the sum intermediate register 8, the lowest n bits of the carry intermediate register 9, and the contents of the flip-flop 11 are input, and output from the spill adder 10. a plurality of multiplication parts having a flip-flop 11 in which the carry is set; and a final sum register in which the upper m×n bits of the intermediate sum register 8 selected in the plurality of multiplication parts are set. 14, a final carry register 15 to which the upper m×n bits of the selected carry intermediate register 9 in the plurality of multiplication parts are set, and a plurality of flip-flops 10 are selected, and the selected flip-flop - in a multiplication device comprising a multiplexer 16 which outputs the contents of the flop 10, and a carry propagation adder 12' into which the contents of the final sum register 14, the contents of the final carry register 15 and the output of the multiplexer 16 are input; , When input operands to be multiplied are sent, select one multiplication part and set multiplicand A and multiplier B in multiplicand register 1 and multiplier register 2 of the multiplication part, respectively, and The i-th n-bit data B(i) is extracted from , the n-bit data B(i) is decoded using the decoder 4, the multiple of the multiplicand A is obtained using the multiple gate 5, and the Using the carry adder trees 6 and 7, find the sum of A×B(i), the sum intermediate register 8, and the carry intermediate register 9, and the resulting sum component SU(i) and carry component CA( i) in the thumb intermediate register 8 and the carry intermediate register 9, respectively, and the sum component SU(i) of the thumb intermediate register 8 and the carry component CA(i) of the carry intermediate register 9.
and the contents of flip-flop 11.
Adder 10 is input, and the resulting carry is set in flip-flop 11. A series of processes are performed in order for each of the first n-bit data to the m-th n-bit data of the multiplier register 2, and after the above processing is completed for the m-th n-bit data. , intermediate register 8 for thumb
and the upper m×n bits of the intermediate register 9 for carry are respectively used as the final sum.
Register 14 and final carry register 15
After the above processing is completed for the mth n-bit data, the final sum register 1 is set to
4, the contents of the final carry register 15, and the contents of the flip-flop 11 are added by a carry propagation adder 12'.