KR100425673B1 - Method for operating multiplication based on ppr scheme - Google Patents

Abstract

PURPOSE: A multiplication operating method is provided to enhance a regularity within a multiplication operator for minimizing a routing factor and eliminate an extra row generated within a PPRT(Partial Product Reduction Tree) for increasing an operation speed and reducing a layout area. CONSTITUTION: The method comprises several steps. A PP(Partial Product) array of two rows is reconstructed into a new PP array of one row by using a 6 bit adder(S1). An extra carry row is eliminated from the new PP array by using a 3 bit adder with a carry input end(S2). By passing the output, resulted from the step S2, through pass modules, 1 bit full adders, a 4:2 compressor, and a 1 bit half adder, two PP arrays for being input into an output end adder are generated(S3).

Description

Multiplication Method Using PPI

The present invention relates to a technique for performing multiplication using an optimal PPR (Partial Product Reduction) technique in the multiplier, in particular, to improve the regularity in the multiplier to minimize the routing factor (Ruting Factor), The present invention relates to a multiplication method using the PPI technique that eliminates extra rows generated in a Partial Product Reduction Tree (PPRT) to increase speed and reduce layout area.

In general, the multiplier is composed of a bus encoder 1, a PPRT 2, and an output adder 3, as in FIG. Here, PPI2 is a part which finally outputs two PP arrays while reducing the partial multiplication result PP generated by the bus encoder 1, which takes up a very large part in the area and speed of the multiplier. In the related art, an embodiment thereof will be described with reference to FIGS. 2 to 7 as follows.

First, FIG. 2 shows an implementation of a 4x4 array multiplier in which the AND gate AD and the adder ADD are designed in a matrix form, which is free to configure and expand, but has a low processing speed and a large area. There is a fault made.

Figure 3 shows that proposed by Wallace, which adder 31 is configured in the form of a tree, which has the advantage that the speed is fast, but the comparative routing factor (Routing Factor) is large, the wiring ( Wiring) has a disadvantage in that the area becomes large, and regularity is lowered, which causes difficulty in expansion.

4 shows an example implemented using a 4: 2 tree compressor, where 41 is a vertical slice and 42 is an adder for carry delivery. Its multiplication principle is almost similar to the third figure. That is, attempts were made to improve the speed by transferring the carry in the horizontal and vertical directions, but similar to those of FIG.

5 shows the compression ratio of various compressors. Fig. 6A shows the principle of the operation of PPI2 implemented using the 4-bit adders 61-64, and Fig. 6B shows the critical path of the 24 × 24-bit multiplier PIPALTI. ) Verification explanatory diagram.

7 is an explanatory diagram showing a PP reduction method of a 24x24 bit multiplier using the algorithm of FIG.

As shown in FIG. 4, the PPI2 using the carry transfer adder 42 has a compression ratio C _r = 2 and C _r = 1.0, which is much higher than those of the other compressors shown in FIG. 5, and the carry propagation delay time T _C ) improves speed when implemented with an adder that is faster than the total propagation delay time T _S.

However, as shown in FIG. 7, the carry is discharged from each of the 4-bit adders in the compression process to generate an extra low. That is, even if the adder is configured to avoid the overlap of the carry, one extra row is generated per four rows. In order to process the extra row, the regularity of the entire PPI 2 is lowered, and the complexity due to routing is increased to increase the area loss. In addition, the extra low increases the compression stage, which slows down the processing speed.

However, in the conventional multiplication to which the PPI has been applied, there is a defect that the regularity is lowered, the routing factor is increased, and the speed is decreased and the layout area is increased by the extra rows generated in the PPI.

Accordingly, an object of the present invention is to provide a multiplication method using a PPI method in which a conventional 4-bit adder is replaced with a 6-bit adder and a 3-bit adder to remove an extra row consisting of a carry generated using a 4-bit adder. Is in.

Multiplication method using the present invention PPI method for achieving the above object is a first step (S1) to reconstruct two lines of PP array to a new line of PP array using a 6-bit adder (91); A second step (S2) of reconstructing the processing result in the first step (S1) by using a 3-bit adder (92) with a carry input (C _in ); The results of the second step (S2) are directly passed through (93A), (93F), (93H), 1bit full adder (93B), (93D), 4: 2 compressor (93C), 1bit half adder (93E). It consists of a third step (S3) of reconstructing into two PP arrays provided to the input of the output stage adder (3) by using the first and eighth to the appended action and effect of the present invention The detailed description with reference to FIG. 10 is as follows.

The partial multiplication result value PP, which is encoded by the bus encoder 1 and input to the PPI2 side, that is, the PP array is as shown in FIG. 8, which includes a sign bit and an additional element by a booth encoding technique. Additive Element) is included. The process of rearranging the PP arrays (Partial Products Arrays) and calculating the final result of PPI2 will be described with reference to FIG.

First, in the first step S1, a 6-row adder 91 is used to reconstruct two rows of PP arrays into a single row of new PP arrays (12PPA'S → 6PPA'S).

Here, two adders indicated by the solid line in order to process the additional element is used with the carry input (C _in) was used for 6bit adder in the adder of the other is the carry input (C _in) is not an adder (shown by dashed lines) It was. At this time, in configuring the 6-bit addition array, the number of digits is allocated so that the output carry does not overlap.

In the second step S2, the processing result of the first step S1 is reconstructed using the 3-bit adder 92 having the carry input C _in . (6PPA'S → 3PPA'S)

That is, the extra carry row generated in FIGS. 6 and 7 of the prior art is processed by the carry input C _in of the 3-bit adder 92 to be removed.

In the third step S3, the result of the second step S2 is directly passed through 93A, 93F, 93H, 1 bit full adder 93B, 93D, and 4: 2 compressor 93C. 1 bit half adder 93E is used to reconstruct two PP arrays provided as inputs of the output adder 3.

The 4: 2 compressor 93C can be easily implemented using two 1-bit full adders 101 and 102 as shown in FIG.

As described in detail above, the present invention applies the multiplication method of the PIRP method in which the existing 4-bit adder is replaced with a 6-bit adder and a 3-bit adder. The number of compression stages can be reduced from five to three stages. In addition, by eliminating the extra row, hardware such as wiring constituting the extra row is removed, thereby reducing layout area and reducing delay time, thereby contributing to high speed.

1 is a block diagram of a general multiplier.

FIG. 2 is a circuit diagram of PPI in FIG.

3 is a diagram illustrating an implementation of PPI Alti proposed by Wallace.

4 is a diagram showing another embodiment of pipialti using a 4: 2 compressor.

5 is a table showing the compression ratio of the various compressors.

Figure 6 (a) is an illustration of the implementation of the general PPI Alti using a 4-bit adder.

(B) is an example of critical path verification of a 24 × 24-bit multiplier PPI.

7 is a diagram illustrating an embodiment of a 24 × 24 bit multiplier PPI.

8 is an explanatory diagram of a PPI array for explaining the multiplication input of the present invention.

Fig. 9 is an explanatory diagram of the data operation processing of PPITI according to the present invention.

FIG. 10 illustrates one embodiment implementation of a 4: 2 compressor in FIG.

*** Explanation of symbols for main parts of drawing ***

1: Booth Encoder 2: PPI Alti

3: output adder 91: 6bit adder

92: 3-bit adder 93A, 93F, 93H: Direct pass-through

93B, 93D: 1bit Full Adder 93C: 4: 2 Compressor

93E: 1-bit half adder

Claims (3)

In the method of calculating the final result by rearranging the PP array, which is a partial multiplication result output from the multiplier's booth encoder, the first reconstruction of the two lines of PP array using a 6-bit adder 91 to a new line of PP array Steps; A second step of reconstructing the result of the processing in the first step by using a 3-bit adder 92 having a carry input C _in to remove the extra carry row; The results of the second stage are directly passed through the pass-through 93A, 93F, 93H, 1-bit full adder 93B, 93D, 4: 2 compressor 93C, and 1-bit half adder 93E. And a third step of reconstructing the two PP arrays provided as inputs of the output adder. 2. The method of claim 1, wherein the first step uses two 6-bit adders with carry inputs (C _in ) to process additional elements. The multiplication method of claim 1, wherein the second step is to remove the extra carry row by a carry input (C _in ) of a 3-bit adder.