Architecture for efficient Implementation of Multipliers with Regular Trees
Original Publication Date: 2001-Jan-01
Included in the Prior Art Database: 2003-Jul-22
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 . The partial products are added with a binary tree based on 4/2-Compressors , 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 . 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.