Home >>  Electronics  >>  ffast multiplier using booth's encoding

A Fast andWell-Structured Multiplier Jung-Yup Kang Department of Electrical Engineering University of Southern California Jean-Luc Gaudiot EECS Department University of California at Irvine Abstract The performance of multiplication is crucial for multimedia applications such as 3D graphics and signal processing systems which depend on extensive numbers of multiplications. Previously reported multiplication algorithms mainly focus on rapidly reducing the partial products rows down to final sums and carries used for the final accumulation. These techniques mostly rely on circuit optimization and minimization of the critical paths. In this paper, an algorithm to achieve fast multiplication in two’s complement representation is presented. Indeed, our approach focuses on reducing the number of partial product rows. In turn, this directly influences the speed of the multiplication, even before applying partial products reduction techniques. Fewer partial products rows are produced, thereby lowering the overall operation time. This results in a true diamond-shape for the partial product tree which is more efficient in terms of implementation. 1 Introduction The performance of 3D graphics and signal processing systems strongly depends on the performance of multiplications because these applications need to support highly multiplication intensive operations. Therefore, there has been much work on advanced multiplication algorithms and designs [1, 22, 3, 23, 18, 14, 13, 6, 7, 16, 20, 24, 4, 12]. There are three major steps to any multiplication. In the first step, the partial products are generated. In the second step, the partial products are reduced to one row of final sums and one row of carries. In the third step, the final sums and carries are added to generate the result. Most of the above mentioned approaches employ the Modified Booth Encoding (MBE) approach [6, 7, 13, 24, 4] for the first step because of its ability to cut the number of partial products rows in half. They then select some variation of any one of partial products reduction schemes such as the Wallace trees [22, 6] or the compressor trees [16, 13, 18, 14] in the second step to rapidly reduce the number of partial product rows to the final two (sums and carries). In the third step, they use some kind of advanced adder approach such as carry-lookahead or carry-select adders [5, 17, 11] to add the final two rows, resulting in the final product. The main focus of recent multiplier papers [7, 16, 20, 24, 4, 12] has been on rapidly reducing the partial product rows by using some kind of circuit optimization and identifying the critical paths and signal races. In other words, the goals have been to optimize the second step of the multiplication described above. However, in this paper, we will concentrate on the first step which consists in forming the partial product array and we will strive to design a multiplication algorithm which will produce fewer partial product rows. By having fewer partial product rows, the reduction tree can be smaller in size and faster in speed. It should also be noted that 8 or 16-bit words are the most commonly used word sizes in the kernels of most multimedia applications [19] and that the implementation of our overall algorithm is particularly well suited to such word sizes. In the next section, the conventional multiplication method is described in detail with an emphasis on its weaknesses. In section 3, a step-by-step procedure to prevent the adverse effects of some conventional multiplication algorithms is presented. In section 4, the effectiveness and usage of our method is presented by showing a detailed evaluation. 2 Multiplication Algorithms There is no doubt that MBE is efficient when it comes to reducing the partial products. However, it is important to note that there are two unavoidable consequences when using MBE: sign extension prevention and negative encoding. The combination of these two unavoidable consequences results in the formation of one additional partial product row and of course, this additional partial product row requires more hardware but more importantly time (to add this one more row of partial products). 2.1 Modified Booth Encoding and the Overhead of Negative Encodings This grouping of the multiplier bits of MBE is shown in Figure 1 and it is based on a window size of 3 bits and a stride of 2. The multiplier (Y) is segmented into groups of three bits (y2i+1, y2i, y2i−1) and each such group of bits is associated with its own partial product row by using Table 1 [15]. In this grouping, y−1 = 0. By applying this encoding, the number of partial product rows to be accumulated is reduced from n to n 2. For Proceedings of the EUROMICRO Systems on Digital System Design (DSD’04) 0-7695-2203-3/04 $ 20.00 IEEE

  

Please send me the details about the project.

  

plz post the complete porject to "nitin.noornook@gmail.com"

  

For Good engineering projects

Visit

Elektor India (www.elektor.in)