Browse Prior Art Database

Method for the compress tree of a 32-bit integer multiplier

IP.com Disclosure Number: IPCOM000018662D
Publication Date: 2003-Jul-30

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for the compress tree of a 32-bit integer multiplier. Benefits include improved performance and improved ease of implementation.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 30% of the total text.

Method for the compress tree of a 32-bit integer multiplier

Disclosed is a method for the compress tree of a 32-bit integer multiplier. Benefits include improved performance and improved ease of implementation.

Background

              The conventional 32-bit multiplier is a pipe-lined multiplier, which requires 4 multiplication steps to finish the 32-bit multiplication (see Figure 1). The input operands (ALU-1, ALU-2, …ALU-N, where N is an integer) are passed into multiplier through N-to-1 multiplexers. The Radix-4 Booth encoding algorithm is used to generate the partial product generation control signals. Depending on the control signals from the Booth encoder block, partial products are generated by the partial product generator (PPG). The partial products are passed into the compress tree that adds up all the input data. This function is where the bulk of the multiplication operation is being done. The conventional implementations of the 6-to-1 compress tree require 4 stages of carry-save-adder (CSA) operation to perform the calculation. For example, a conventional implementation has four processing stages and four stages of CSA delay). It uses five CSA arrays, requiring a total of 191 CSA bitcells (see Figure 2).

General description

              The disclosed method is the compress tree of a 32-bit integer multiplier. The method uses one less stage delay and one less carry-save-adder (CSA) array than the conventional compress tree of Booth multipliers, saving area and reducing processing time.

              The disclosed method uses three processing stages of delay with the same or a lesser number of gates as the conventional solution.

Advantages

              The disclosed method provides advantages, including:

•             Improved performance due to the reduced number of processing stages

•             Improved ease of implementation due to using conventional place-and-route tools

•             Improved cost effectiveness in terms of area savings and potentially lower power consumption due to utilizing fewer gates (in some cases)

Detailed description

              The compress tree uses six input operands, adds them up, and produces two results (see Figure 3). The six operands are partial products. Each partial product, except the first one, has 35 bits (bit-0 to bit-34, which includes 33 bits of the actual partial product, 1 bit of the extended sign, and 1 most significant bit (MSB) with the value ‘1’). The first partial product, PP0, has 36 bits (33 bits of the actual partial product, 2 bits of extended sign, and 1 MSB of the inverted sign). PP0 shares the data bus with the recirculated sum and carry, which has 33 bits. The compress tree must be able to add up all 6 operands and generate a resultant 40-bit sum and carry.

              In addition to the partial products and the recirculated sum and carry, there are also extra bits (neg0, neg1, neg2, neg3 and neg4). These extra bits have the value of ‘1’ whenever the corresponding partial product is n...