Browse Prior Art Database

Architecture for efficient Implementation of Multipliers with Regular Trees

IP.com Disclosure Number: IPCOM000017445D
Original Publication Date: 2001-Jan-01
Included in the Prior Art Database: 2003-Jul-22
Document File: 2 page(s) / 21K

Publishing Venue

Siemens

Related People

Dr. Sven Simon: AUTHOR [+3]

Abstract

In the following, an efficient multiplier architecture for two’s complement numbers is proposed. Figure 1 shows the principle parts of the architecture. To reduce the number of partial products the modified Booth Algorithm is used [1]. The partial products are added with a binary tree based on 4/2-Compressors [2], which are built up with two fulladders (FA’s) as shown in Figure 2. A 4/2-Compressor is a combinational circuit that compresses four inputs to two outputs. Additionally, there is one input (Cint in ) and one output (Cint out ) both connected to the next neighbours. In a carry ripple adder this would lead to the typical carry ripple path. However, as seen in Figure 2 the interconnection output from the 4/2-Compressor does not depend on the interconnection input Cint in . Therfore, no carry ripple addition occurs. The adder tree structure with 4/2-Compressors results in a more regular structure than usual Wallace Trees [2,3] applying FA’s. It is possible to merge together four partial products rows in one row of 4/2-Compressors. The outputs of the 4/2-Compressors rows can be used as inputs for the next row. The proposed architecture makes use of the sign-generate sign-extension [4]. The advantage of this method is, that there is only one additional „1“ in each row of partial products, instead of filling the partial products rows with the sign of each partial product. Therefore, a „1“ has to be added to the MSB of the first partial product and an extra „1“ to the left of the MSB of each partial product (see Figure 3). For the „1“, which is added to the MSB of the first partial product, there is no input left in the 4/2-Compressors. All inputs are reserved by the partial product. Therfore, an extra carry save stage of FA’s is implemented. The second task of this carry save stage is the generation of two’s complement of the partial products. If the factor of the Booth Encoder is negative (-1 or -2) the two’s complement of the multiplicand has to be generated to get the correct result. The outputs have to be added in the final carry propagation adder, for which a carry select adder is used in this multiplier.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

-� � 25� � -

Bauelemente

Architecture for efficient Implementation of Multipliers with RegularTrees

Idee: Dr. Sven Simon, München; Thomas Wahl, München; Rainer Laube, Taufkirchen

In the following, an efficient multiplier architecture for two’s complement numbers is proposed.Figure 1 shows the principle parts of the architecture. To reduce the number of partial productsthe modified Booth Algorithm is used [1]. The partial products are added with a binary treebased on 4/2-Compressors [2], which are built up with two fulladders (FA’s) as shown in Figure2. A 4/2-Compressor is a combinational circuit that compresses four inputs to two outputs.Additionally, there is one input (Cint in ) and one output (Cint out ) both connected to the nextneighbours. In a carry ripple adder this would lead to the typical carry ripple path. However, asseen in Figure 2 the interconnection output from the 4/2-Compressor does not depend on theinterconnection input Cint in . Therfore, no carry ripple addition occurs. The adder tree structurewith 4/2-Compressors results in a more regular structure than usual Wallace Trees [2,3] applyingFA’s. It is possible to merge together four partial products rows in one row of 4/2-Compressors.The outputs of the 4/2-Compressors rows can be used as inputs for the next row.

The proposed architecture makes use of the sign-generate sign-extension [4]. The advantage ofthis method is, that there is only one additional „1“ in each row of partial products, instead offilling the partial products rows with the sign of each partial product. Therefore, a „1“ has to beadded to the MSB of the first partial product and an extra „1“ to the left of the MSB of eachpartial product (see Figure 3). For the „1“, which is added to the MSB of the first partial product,there is no input left in the 4/2-Compressors. All inputs are reserved by the partial product.Therfore, an extra carry save stage of FA’s is implemented. The second task of this carry savestage is the generation of two’s complement of the partial products. If the factor o...