CN101739231A - Booth-Wallace tree multiplier - Google Patents

Abstract

The invention discloses a Booth-Wallace tree multiplier, which mainly solves the problems that the existing multiplier has a large time delay and complicated circuit and layout implementation. Including Booth encoding circuit, partial product intermediate state generating circuit and partial product result generating circuit. The Booth encoding circuit re-encodes the multiplier to generate a partial product multiple control signal and a sign control signal, which are respectively output to the partial product intermediate state generation circuit and the partial product result generation circuit; the partial product intermediate state generation circuit generates the partial product intermediate state of the corresponding multiple , and output to the partial product result generating circuit; the partial product result generating circuit generates the final positive and negative partial products according to the partial product control signal and the partial product intermediate state circuit generating result. The invention improves the partial product generating unit circuit, reduces the series and number of partial product compressors, effectively improves the operating speed of the multiplier, and reduces the complexity of circuit and layout implementation, and can be used in various types of microprocessors, digital signals in the processor.

Description

Booth-Wallace tree multiplier

technical field

The invention belongs to the technical field of electronic components and relates to a multiplier which can be used in various microprocessors and digital signal processors (DSP).

Background technique

As a basic arithmetic unit, the multiplier is used in various microprocessors, digital signal processors (DSP) and application-specific integrated circuits (ASIC). The current multiplier already has high performance, but due to the increasing importance of security and confidentiality applications in modern information processing, the performance of the multiplier is also continuously put forward higher and higher requirements.

Most of the early multipliers use shift-add algorithm and array multiplier algorithm. From the perspective of the implementation methods of these two algorithms, each bit of the multiplier will generate a partial product, and only 1 or 0 times the partial product form. Therefore, when the bit width of the multiplication operand is relatively wide, the amount of calculation is very large. In fact, when a certain bit of the multiplier is 0, no partial product with practical significance will be generated, let alone an accumulation operation. In the actual operation process, the generation of partial products and the number of partial accumulations are determined by the number of "1" in the multiplier. The Booth encoding algorithm is a partial product generation algorithm for complement operation, which recodes the multiplier to reduce the number of "1" in the multiplier, thereby reducing the number of partial products and the number of partial accumulations , effectively improving the efficiency of the multiplier operation. In the Booth coding algorithm, a widely used Booth coding algorithm is the improved Booth coding algorithm, that is, the second-order Booth coding algorithm.

The improved Booth coding algorithm can be applied to signed and unsigned multiplication numbers, and it can basically reduce the number of partial products to half that of the non-Booth coding algorithm. When the multiplication operand N is an odd number, the number of partial products is (N+1)/2, and when N is an even number, the number of partial products is (N/2)+1. It greatly reduces the area occupied by the partial product compression module and the delay generated, improves the performance of the multiplier unit and reduces the area.

A compression technique widely used in the partial product compression stage is the Wallace tree compression algorithm, which groups partial products by columns, each column corresponds to a set of adders, and each column is added at the same time, and the carry of the previous column is passed to the next column , generating a new partial product. Use the same method to simplify the new partial products until the last two rows of partial products are left, and then use a fast adder to add the products. This partial product compression method achieves the purpose of improving the speed of multiplication by performing parallel operations on the operands as much as possible. Therefore, the hybrid algorithm combining the Booth coding algorithm and the Wallace compression tree is often used in the high-speed multiplier structure.

When using this hybrid algorithm to implement a multiplier, the improved Booth algorithm divides the multiplier into groups of three bits. The three bits are respectively the low bit, the standard bit, and the high bit, wherein the low bit comes from the highest bit in the low group. Thus, partial products of multiples of {±2, ±1, 0} are generated, and then the Wallace tree is used to sum these partial products.

The realization of the negative part product is divided into two stages. In the first stage, the Booth coding algorithm is used to generate the negative of the positive partial product and output to the Wallace compression tree. In the second stage, 1 is added to the least significant bit of the partial product in this row, and this 1 is placed in the place where the partial product of the next row is aligned with the least significant bit of this partial product, as shown in Figure 10.

Since the partial product generated by the improved Booth coding algorithm has positive and negative points, the Wallace tree structure will have a great difference when compressed. Figure 6 and Figure 8 respectively show the positive partial product array structure and the negative partial product array structure with partial product sign extension, and Figure 7 and Figure 9 respectively show the positive partial product compressor array structure and the negative partial product compressor array structure. The negative partial product array structure will cause the impact of an extra row due to the sign bit of the last row of partial product. An additional compressor is required when compressing the partial product of this row. This row of compressors not only increases the number of compression stages and makes the delay of the multiplier larger, but also the Wallace tree structure is more complicated when the layout is realized. .

With people's pursuit of high-performance multipliers, the improved Booth coding algorithm is not suitable for higher-performance multipliers because the number of partial products it produces is still relatively large. The fewer partial products produced, the fewer iterations of the multiplication, and thus the faster the multiplication operation. The partial product generated by the third-order Booth encoding algorithm is one-third of that of the non-Booth encoding algorithm, so it is more and more used in high-performance multipliers.

The third-order Booth encoding algorithm divides the multiplier into groups of four bits, three of which come from this group, and the lowest bit comes from the highest bit in the adjacent low-order group, as shown in Figure 13. The third-order Booth encoding algorithm produces partial products of multiples of {±4, ±3, ±2, ±1, 0}. The partial product of ±3 times is often referred to as a "difficult multiple" partial product. When realizing it, it is necessary to add a "difficult multiple" partial product realization circuit in the partial product encoding module, as shown in Figure 11. However, this third-order Booth coding algorithm, like the improved Booth coding algorithm, will generate negative partial products, which will also lead to large multiplier delays and complex circuit and layout implementations.

Contents of the invention

The purpose of the present invention is to overcome above-mentioned deficiencies in the prior art, propose a kind of Booth-Wallace tree type multiplier, realize the improvement of circuit by partial product, avoid needing extra partial product compressor because of negative partial product sign Influence, reduce the number of partial product compression series, increase the speed of the multiplier, and at the same time make the partial product compression array structure more regular, easy to realize the layout.

In order to achieve the above object, the Booth-Wallace tree multiplier of the present invention includes: a partial product generation module, a partial product compression module and an adder module of the last two row partial product additions, wherein the partial product generation module improves The partial product generating units include:

A Booth encoding circuit for re-encoding the multiplier to generate a partial product multiple control signal and a sign control signal. The partial product multiple control signal is output to the partial product intermediate state generating circuit, and the partial product sign control signal is output to the partial product result generating circuit.

The partial product intermediate state generation circuit generates partial product intermediate states of corresponding multiples according to the control signal generated by the Booth code, and outputs the partial product intermediate state to the partial product result generating circuit.

The partial product result generating circuit generates the final positive and negative partial products according to the control signal generated by the Booth code and the result of the partial product intermediate state circuit.

The partial product result generating circuit is composed of a negative partial product operation circuit and a two-choice selector, and the negative partial product operation circuit is used to perform operations on the partial product intermediate state result, and generates a negative partial product output to the two-choice selector middle; according to the partial product sign control signal generated by the Booth encoding circuit, the two-choice selector selects the result of the negative partial product operation circuit and the partial product intermediate state generation circuit result, and generates a partial product of the corresponding multiple and type, and Output to the partial product compression module.

The partial product compression circuit is an array structure composed of six stages of compression circuits, and the shape of the array structure is a regular right-angled trapezoidal structure.

The present invention changes the type of the last row of partial products by adding a negative partial product operation circuit in the partial product generation circuit, can effectively reduce the number of partial product compression arrays, and makes the structure regular and easy to realize in layout. At the same time, the operating speed of the multiplier is effectively improved, and the operating speed of the 16-bit multiplier is increased by 13% without increasing the circuit area.

Description of drawings

Fig. 1 is the overall structural diagram of multiplier of the present invention;

Fig. 2 is that last partial product among the present invention produces circuit diagram;

Fig. 3 is a partial product array diagram among the present invention;

Fig. 4 is a partial product compressor array diagram among the present invention;

Fig. 5 is the overall structural diagram of traditional multiplier;

Fig. 6 is positive partial product array diagram in traditional multiplier;

Fig. 7 is the positive partial product compressor array diagram in the traditional multiplier;

Fig. 8 is negative partial product array diagram in the traditional multiplier;

Fig. 9 is negative partial product compressor array figure in traditional multiplier;

Fig. 10 is the realization figure of negative partial product in traditional multiplier;

Fig. 11 is the partial product generation circuit diagram in the traditional multiplier;

Fig. 12 is an array diagram of a partial product compressor in a traditional multiplier;

Figure 13 is a diagram of a third-order Booth encoding.

specific implementation

Referring to Fig. 5, the basic structure of currently known third-order Booth-Wallace tree multiplier is mainly composed of a partial product generation module, a partial product compression module and a final adder module, wherein:

The partial product generation module generates partial product intermediate states and partial product symbols of corresponding multiples by recoding the multipliers, and outputs the generated partial product intermediate states and partial product symbols to the partial product compression module.

The partial product compression array module, according to the partial product compressor array structure, compresses all partial product intermediate states and partial product symbols at the same time, until the last two rows of partial products are generated, and output them to the final adder module.

The final adder module adds up the partial products of the last two rows generated by the partial product compressed array to obtain the product result.

The partial product generating module is composed of 6 partial product generating units 021, and its structure is shown in Figure 11, which includes: a Booth encoding circuit, a general multiple partial product realization circuit and a "difficult multiple" partial product realization circuit. The Booth encoding circuit is used to re-encode the multiplier to generate the multiple control signal and sign control signal of the partial product; the general multiple partial product realization circuit mainly realizes the partial product intermediate of {±4, ±2, ±1} multiples state; the "difficult multiple" partial product realization circuit mainly realizes the partial product intermediate state result of ±3 multiples.

The partial product multiplier control signal generated by Booth encoding is output to the general multiple partial product realization circuit and the "difficult multiple" partial product realization circuit, and the partial product symbol is output to the partial product compression array. The general multiple realization circuit and the "difficult multiple" realization circuit output the partial product intermediate state results to the partial product compression module.

In order to simplify the circuit structure in the traditional multiplier, the realization of the negative partial product is divided into two stages as shown in Figure 10: the first stage is in the partial product generation circuit, which generates the intermediate state of the partial product of the corresponding multiple, and outputs it to the partial in a packed array. The second stage is in the partial product compression stage, by adding 1 to the end of the partial product intermediate state to generate a negative partial product. Since the partial product generation circuit will generate positive and negative partial products, and the array structures of the positive and negative partial products are different, the structure of the compressor array will also be different. When all partial products are positive, the symbols of the partial products are all 0, so the last row of the partial product array will not appear an extra row of partial products composed of sign bits. The structure of the partial product array is shown in Figure 6, and the corresponding partial product The compressor array structure is shown in Figure 7. When all the partial products are negative, the signs of the partial products are all 1, and the last row of the partial product array structure will have a partial product composed of sign bits, as shown in Figure 8, and the partial product compressor array is shown in Figure 9 Show.

Since the Booth-Wallace tree multiplier needs to process positive and negative partial products at the same time, the traditional Booth-Wallace tree multiplier structure must take into account both positive and negative partial product compressor array structures. However, the negative partial product compressor array structure needs an additional partial product compressor due to the need to compress the sign bit, which will lead to the problem of irregular partial product compressor array structure and large number of compression stages. Therefore, the traditional Booth-Wallace tree The structure of the partial product compressor array in the type multiplier is shown in Fig. 12. This structure also has the disadvantages of irregular structure of the partial product compressor array and large number of compression stages.

In order to reduce the problem of large delay and complex array structure of partial product compressors in the traditional Booth-Wallace tree multiplier, the present invention reduces the traditional The delay of the Booth-Wallace tree multiplier solves the problem that the array structure of the partial product compressor is complex and the layout is difficult to realize.

Referring to Fig. 1, the Booth-Wallace tree multiplier structure in the present invention includes: a partial product generation module, a partial product compression module and a final adder module. in:

The partial product generation module generates the partial product intermediate state, partial product sign and partial product result of corresponding multiples by recoding the multiplier. It consists of five partial product generating units 021 and one improved partial product generating unit 022. The circuit structure of the partial product generating unit 021 is the same as that of the partial product generating unit 021 in the traditional multiplier. The circuit structure of the improved partial product generation unit 022 is shown in FIG. 2 . It includes: Booth encoding circuit, partial product intermediate state generating circuit and partial product result generating circuit. The Booth coding circuit is used to recode the multiplier to generate the multiple control signal and the sign control signal of the partial product; the partial product intermediate state generation circuit generates the corresponding multiple partial product intermediate state according to the control signal generated by the Booth code; the partial product A result generating circuit for generating a partial product result. The partial product result generating circuit is composed of a negative partial product operation circuit and a two-choice selector. Its working principle is: the negative partial product operation circuit operates on the partial product intermediate state, and generates a negative partial product output to the two-choice selector. Among them, the two-to-one selector selects the result of the negative partial product operation circuit and the result of the partial product intermediate state generation circuit according to the partial product sign control signal generated by the Booth encoding circuit, and generates a partial product of a corresponding multiple and type. The working principle of the partial product generation unit 022 is: the partial product multiple control signal generated by the Booth encoding circuit is output to the partial product intermediate state generation circuit, and the partial product sign control signal is output to the partial product result generation circuit. The partial product intermediate state result generated by the partial product intermediate state generating circuit is output to the partial product result generating circuit. The partial product result generating circuit outputs the generated positive and negative partial products to the partial product compression module.

The partial product compression module compresses all the partial products according to the partial product compressor array structure until the last two rows of partial products are generated, and outputs the last two rows of partial products to the final adder module. In the multiplier of the present invention, due to changing the partial product type produced by the last partial product generating unit in the partial product generating module, the partial product of the last row will not bring the sign bit into the partial product array, so it is different from the traditional Booth- Compared with the partial product array of the Wallace tree multiplier, its partial product array can reduce a row of partial products, thereby reducing the number of partial product compression stages, and regularizing the partial product array structure, as shown in Figure 3. When the partial product array shown in FIG. 3 is used for compression, the compressor array structure will be changed from the traditional partial product compressor array structure shown in FIG. 12 to that shown in FIG. 4 of the present invention. Compared with the traditional partial product compressor array shown in Figure 12, the partial product compressor array shown in Figure 4 reduces the number of stages of the compression array and the number of compressors in the partial product compressor array, thereby simplifying the circuit implementation The number of stages and the complexity of circuit connections.

The final adder module adds up the partial products of the last two rows generated by the partial product compressed array to obtain the product result.

Compared with the prior art, the present invention has the advantages of reducing the complexity of the circuit structure and layout realization of the multiplier, and at the same time, can increase the operating speed of the multiplier without increasing the area.

Claims (4)

1. a booth-Wallace tree multiplier comprises: partial product produces circuit, partial product compressor circuit and the adder circuit that last two row partial products add up mutually, it is characterized in that partial product produces circuit and comprises:

This coding circuit of cloth is used for the multiplier recompile to produce the multiple control signal and the Signed Domination signal of partial product.Partial product multiple control signal outputs to the partial product intermediate state and produces circuit, and partial product Signed Domination signal outputs to the partial product result and produces in the circuit.

The partial product intermediate state produces circuit, and the control signal that is produced according to this coding of cloth produces the partial product intermediate state of corresponding multiple, and the partial product intermediate state is outputed to the partial product result produces in the circuit.

Partial product result produces circuit, and the control signal and the bearing results of partial product intermediate state circuit that are produced according to this coding of cloth produce final positive and negative partial product.

2. multiplier according to claim 1, it is characterized in that, partial product result produces circuit and is made of long-pending computing circuit of negative part and alternative selector switch, and the long-pending computing circuit of this negative part is used for partial product intermediate state result is carried out computing, and the generation negative part is long-pending to output in the alternative selector switch; The partial product Signed Domination signal that this alternative selector switch is produced according to this coding circuit of cloth, long-pending computing circuit result of negative part and partial product intermediate state generation circuit result are selected, produce the partial product of corresponding multiple and type, and output in the partial product compression module.

3. multiplier according to claim 1 is characterized in that, the array structure that the partial product compressor circuit is made up of six grades of compressor circuits.

4. multiplier according to claim 3 is characterized in that, described array structure is shaped as the ladder structure of right angle of rule.

Images