Patent Publication Number: US-2005138102-A1

Title: Arithmetic unit

Description:
BACKGROUND OF THE INVENTION  
      1. Field of the Invention  
      The present invention relates to an arithmetic unit using a Wallace tree array, and particularly to a multiplication device.  
      2. Description of the Background Art  
      Multiplication is one of the arithmetic operations that are most often performed in semiconductor integrated circuits, such as microcomputers, so that constructing high-speed computing systems necessarily requires implementing high-speed multiplication devices. The Booth&#39;s algorithm, which modifies the multiplier to reduce the total number of partial products, is a well-known method of realizing high-speed multiplication. Also well-known are multiplication devices using the Wallace tree, which adds partial products in a tree-like manner to sequentially reduce the total number of partial products. Multiplication devices adopting these two methods are disclosed for example in Japanese Patent Application Laid-Open Nos. 3-177922 (1991), 9-231056 (1997), and 2001-195235 (hereinafter these references are referred to as first to third patent documents, respectively).  
      However, in the multiplication device disclosed in the first patent document, the maximum-degree partial product adder (hereinafter referred to as “an mth partial product adder) in the Wallace tree largely protrudes in space beyond lower-degree partial product adders and shifter/inverters. The protrusion of the mth partial product adder forms dead (or unutilized) area in the Wallace tree array, thus lowering area efficiency.  
      In the multiplication device disclosed in the second patent document, partial product adders of respective degrees are each divided into a high order part and a low order part at a border between particular positions of the multiplicand, where the high and low order parts are placed in different rows in the Wallace tree array to prevent formation of dead area. Therefore the area can be used efficiently. However, because the low order part of the mth partial product adder is placed in the top row of the Wallace tree array while the high order part of the mth partial product adder is placed in the bottom row of the Wallace tree array, the carry path from the low order part of the mth partial product adder to its high order part (the carry path forms part of the critical path) requires a long interconnection, which lowers the multiplying speed.  
      Also, in the multiplication device disclosed in the third patent document, an undivided mth partial product adder is placed in a middle row in the Wallace tree array. Accordingly, unlike in the multiplication device disclosed by the second patent document, the mth partial product adder does not need a long carry path interconnection, allowing high multiplying speed. However, because of the same reason mentioned about the multiplication device of the first patent document, the mth partial product adder protrudes to cause dead area, lowering area efficiency.  
      Thus, conventional multiplication devices have a problem that enhancing area efficiency lowers multiplying speed, while increasing multiplying speed lowers area efficiency.  
     SUMMARY OF THE INVENTION  
      An object of the present invention is to provide an arithmetic unit capable of enhancing area efficiency while suppressing reduction of operating speed.  
      An arithmetic unit according to the present invention includes a partial product generating portion, an array-form Wallace tree portion, and a final adder. The partial product generating portion receives a multiplicand and a multiplier and generates 0th partial products. The Wallace tree portion has jth partial product adders that add ith (0≦i≦m-1) partial products to generate jth (j=i+1) partial products, so as to perform an addition in a tree-like manner while sequentially reducing the number of partial products to finally output an mth partial product from an mth partial product adder. The final adder receives the mth partial product and obtains a result of multiplication of the multiplicand by the multiplier. The jth partial product adders are each divided into a plurality of parts at a border between particular positions of the multiplicand and the plurality of parts are placed in different rows in the array. The mth partial product adder includes a first part provided in a row at an end of the array and a second part provided in a middle row in the array.  
      It is possible to enhance area efficiency while suppressing reduction of operating speed.  
      These and other objects, features, aspects and advantages of the present invention will become more apparent from the following detailed description of the present invention when taken in conjunction with the accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       FIG. 1  is a diagram schematically showing the layout of a multiplication device according to a first preferred embodiment of the invention;  
       FIG. 2  is a circuit diagram showing part of the configuration of a first partial product adder;  
       FIGS. 3 and 4  together form a diagram schematically showing a first layout of a multiplication device according to a second preferred embodiment of the invention;  
       FIGS. 5 and 6  together form a diagram schematically showing a second layout of the multiplication device of the second preferred embodiment of the invention;  
       FIG. 7  is a diagram schematically showing the layout of a multiplication device according to a third preferred embodiment of the invention;  
       FIG. 8  is a diagram schematically showing the layout of a multiplication device according to a fourth preferred embodiment of the invention;  
       FIG. 9  is a diagram schematically showing the layout of a multiplication device according to a fifth preferred embodiment of the invention; and  
       FIG. 10  is a diagram schematically showing the layout of a multiplication device according to a sixth preferred embodiment of the invention. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS  
      The arithmetic unit of the present invention is now described. While multiplication devices are explained below by way of example, the present invention is not limited to multiplication devices but is applicable to any arithmetic units using Wallace tree arrays, such as sum-of-products operation devices and division devices.  
     First Preferred Embodiment  
       FIG. 1  is a diagram schematically showing the layout of a multiplication device of 32-bit multiplicand×25-bit multiplier, according to a first preferred embodiment of the invention (throughout this specification, “layout” means a layout that is configured as an integrated circuit on a semiconductor chip). The multiplication device includes a Wallace tree array, an X driver  1  provided at the top side of the Wallace tree array, a booth encoder  2  provided in the left part of the top side of the Wallace tree array, and a final adder  3  provided in the right part of the bottom side of the Wallace tree array.  
      A 25-bit multiplier is inputted to the booth encoder  2 . The booth encoder  2  then reduces the multiplier according to a Booth&#39;s algorithm and outputs the reduced multiplier (hereinafter referred to as “a modified multiplier”). The multiplication device of the first preferred embodiment adopts a second-order Booth algorithm, so that the booth encoder  2  reduces the 25-bit multiplier to output a modified multiplier of 13 bits (booth 1  to booth 13 ).  
      The Wallace tree array includes booth selectors B 101  to B 113  (shown as B 101   a  to B 113   a  and B 101   b  to B 113   b  in  FIG. 1 ), first partial product adders F 101  to F 104  (F 101   a  to F 104   a  and F 101   b  to F 104   b  in  FIG. 1 ), second partial product adders S 101  and S 102  (S 101   a , S 101   b , S 102   a , and S 102   b  in  FIG. 1 ), and a third partial product adder T 101  (T 101   a  and T 101   b  in  FIG. 1 ).  
      The X driver  1 , functioning as a driving buffer for driving the multiplicand, provides the multiplicand to the booth selectors B 101  to B 113 .  
      The booth selectors B 101  to B 113  receive the modified multiplier from the booth encoder  2  and also receives the multiplicand from the X driver  1 , and they generate and output 0th partial products. More specifically, the booth selectors B 101  to B 113  function as shifter/inverters; according to the second-order Booth algorithm, they generate 0th partial products by keeping the multiplicand unchanged when the modified multiplier is 1, 1-bit shifting the multiplicand when the modified multiplier is 2, and inverting the multiplicand when the modified multiplier is negative.  
      The booth selector B 101  is divided into a high order part B 101   a  including high-order 21 bits and a low order part B 101   b  including low-order 12 bits, at the border between the 12th and 13th bits counted from its least significant bit, i.e. at the border between the 12th and 13th bits from the least significant bit of the multiplicand. The booth selector B 101  receives the least significant bit “booth1” of the modified multiplier. The booth selector B 102  is divided into a high order part B 102   a  including high-order  23  bits and a low order part B 102   b  including low-order 10 bits, at the border between the 10th and 11th bits counted from its least significant bit. The booth selector B 102  receives the bit booth 2  of the modified multiplier. The booth selector B 103  is divided into a high order part B 103   a  including high-order 25 bits and a low order part B 103   b  including low-order 8 bits, at the border between the 8th and 9th bits counted from its least significant bit. The booth selector B 103  receives the bit booth 3  of the modified multiplier. The booth selector B 104  is divided into a high order part B 104   a  including high-order 27 bits and a low order part B 104   b  including low-order 6 bits, at the border between the 6th and 7th bits counted from its least significant bit. The booth selector B 104  receives the bit booth 4  of the modified multiplier. The booth selector B 105  is divided into a high order part B 105   a  including high-order 29 bits and a low order part B 105   b  including low-order 4 bits, at the border between the 4th and 5th bits counted from its least significant bit. The booth selector B 105  receives the bit booth 5  of the modified multiplier. The booth selector B 106  is divided into a high order part B 106   a  including high-order 31 bits and a low order part B 106   b  including low-order 2 bits, at the border between the 2nd and 3rd bits counted from its least significant bit. The booth selector B 106  receives the bit booth 6  of the modified multiplier.  
      The booth selector B 107  receives the bit booth 7  of the modified multiplier. The booth selector B 108  is divided into a high order part B 108   a  including high-order 2 bits and a low order part B 108   b  including low-order 31 bits, at the border between the 31st and 32nd bits counted from its least significant bit. The booth selector B 108  receives the bit booth 8  of the modified multiplier. The booth selector B 109  is divided into a high order part B 109   a  including high-order 4 bits and a low order part B 109   b  including low-order 29 bits, at the border between the 29th and 30th bits counted from its least significant bit. The booth selector B 109  receives the bit booth 9  of the modified multiplier. The booth selector B 110  is divided into a high order part B 110   a  including high-order 6 bits and a low order part B 110   b  including low-order 27 bits, at the border between the 27th and 28th bits counted from its least significant bit. The booth selector B 110  receives the bit booth 10  of the modified multiplier. The booth selector B 111  is divided into a high order part B 111   a  including high-order 8 bits and a low order part B 111   b  including low-order 25 bits, at the border between the 25th and 26th bits counted from its least significant bit. The booth selector B 111  receives the bit booth 11  of the modified multiplier. The booth selector B 112  is divided into a high order part B 112   a  including high-order 10 bits and a low order part B 112   b  including low-order 23 bits, at the border between the 23rd and 24th bits counted from its least significant bit. The booth selector B 112  receives the bit booth 12  of the modified multiplier. The booth selector B 113  is divided into a high order part B 113   a  including high-order 12 bits and a low order part B 113   b  including low-order 21 bits, at the border between the 21st and 22nd bits counted from its least significant bit. The booth selector B 113  receives the bit booth 13  of the modified multiplier.  
      The first partial product adder F 101  adds 0th partial products from the booth selectors B 101  and B 102  to generate and output a first partial product. The first partial product adder F 101  is divided into a high order part F 101   a  including high-order 23 bits and a low order part F 101   b  including low-order 12 bits at the border between the 12th and 13th bits from its least significant bit. The high order part F 101   a  and the low order part F 101   b  are placed in different rows in the Wallace tree array. The first partial product adder F 102  adds 0th partial products from the booth selectors B 103  to B 106  to generate and output a first partial product. The first partial product adder F 102  is divided into a high order part F 102   a  including high-order 31 bits and a low order part F 102   b  including low-order  4  bits at the border between the 4th and 5th bits from its least significant bit. The high order part F 102   a  and the low order part F 102   b  are placed in different rows in the Wallace tree array. The first partial product adder F 103  adds 0th partial products from the booth selectors B 107  to B 110  to generate and output a first partial product. The first partial product adder F 103  is divided into a high order part F 103   a  including high-order 6 bits and a low order part F 103   b  including low-order 29 bits at the border between the 29th and 30th bits from its least significant bit. The high order part F 103   a  and the low order part F 103   b  are placed in different rows in the Wallace tree array. The first partial product adder F 104  adds 0th partial products from the booth selectors B 111  to B 113  to generate and output a first partial product. The first partial product adder F 104  is divided into a high order part F 104   a  including high-order 12 bits and a low order part F 104   b  including low-order 21 bits at the border between the 21st and 22nd bits from its least significant bit. The high order part F 104   a  and the low order part F 104   b  are placed in different rows in the Wallace tree array.  
      The second partial product adder S 101  adds first partial products from the first partial product adders F 101  and F 102  to generate and output a second partial product. The second partial product adder S 101  is divided into a high order part S 101  a including high-order 31 bits and a low order part S 101   b  including low-order 8 bits at the border between the 8th and 9th bits from its least significant bit. The high order part S 101  a and the low order part S 101   b  are placed in different rows in the Wallace tree array. Particularly, the low order part  5101   b  is placed in the top row in the Wallace tree array. The second partial product adder S 102  adds first partial products from the first partial product adders F 103  and F 104  to generate and output a second partial product. The second partial product adder S 102  is divided into a high order part S 102   a  including high-order 12 bits and a low order part S 102   b  including low-order 25 bits at the border between the 25th and 26th bits from its least significant bit. The high order part S 102   a  and the low order part S 102   b  are placed in different rows in the Wallace tree array.  
      The third partial product adder T 101  adds second partial products from the second partial product adders S 101  and S 102  to generate and output a third partial product. The third partial product adder T 101  is divided into a high order part T 101   a  including high-order 12 bits and a low order part T 101   b  including low-order 33 bits at the border between the 33rd and 34th bits from its least significant bit. The high order part T 101   a  and the low order part T 101   b  are placed in different rows in the Wallace tree array. Particularly, the low order part T 101   b  is placed in a middle row in the Wallace tree array. More specifically, the low order part T 101   b  is placed right under the high order part S 101   a  and right above the low order part S 102   b . The high order part T 101   a  is placed in the bottom row of the Wallace tree array. More specifically, the high order part T 101   a  is placed right under the high order part S 102   a.    
      Thus, in the area where the high order parts B 101   a  to B 106   a , F 101   a , F 102   a , S 101   a , and the low order part T 101   b  are disposed, the addition is performed from the top to the bottom as shown by the arrow D 1 . In the area where the low order parts B 101   b  to B 106   b , F 101   b , F 102   b , and S 101   b  are disposed, the addition is performed from the bottom to the top as shown by the arrow D 2 . In the area where the high order parts B 108   a  to B 113   a , F 103   a , F 104   a , S 102   a , and T 101   a  are disposed, the addition is performed from the top to the bottom as shown by the arrow D 3 . In the area where the booth selector B 107  and the low order parts B 108   b  to B 113   b , F 103   b , F 104   b , S 102   b , and T 101   b  are disposed, the addition is performed from the bottom to the top as shown by the arrow D 4 .  
      The final adder  3  receives the results of addition from the low order part S 101   b  and the third partial product adder T 101 . Then the final adder  3  provides the result of the multiplication of the multiplicand by the multiplier. In order to achieve high-speed operation, the final adder  3  employs a high-speed addition method, such as the carry lookahead or carry skip.  
       FIG. 2  is a circuit diagram illustrating the configuration of the first partial product adder F 102 , where only a part corresponding to 3 bits is shown. 4-input (with a carry-in) 2-output (with a carry-out) adder elements P k+1 , P k , and P k−1  are sequentially connected in series. Each of the adder elements P k+1 , P k , and P k−1  corresponds to 1 bit of the first partial product adder F 102  shown in  FIG. 1 . The adder elements P k+1 , P k , and P k−1  each have a carry-in terminal CI, input terminals I 1  to I 4  each receiving 1 bit of the partial products  121  to  124 , a sum terminal S outputting a low order bit of the result of addition of the 5 bits provided to the carry-in terminal CI and the input terminals I 1  to I 4 , and a carry terminal C and a carry-out terminal CO outputting a high order bit of the same order. The carry-out terminals CO of the adder elements P k+1 , P k , and P k−1  are connected respectively to the carry-in terminals CI of the succeeding adder elements. The second partial product adders S 101  and S 102  and the third partial product adder T 101  shown in  FIG. 1  are configured the same as the first partial product adder F 102  of  FIG. 2  except that they have different numbers of input terminals, I 1 -I 4 .  
      As described so far, in the multiplication device of the first preferred embodiment, the maximum-degree partial product adder in the Wallace tree, i.e. the third partial product adder T 101 , is divided into the high order part T 101   a  and the low order part T 101   b , and the high order part T 101   a  and the low order part T 101   b  are arranged in different rows in the Wallace tree array. Neither of the number of bits (12 bits) of the high order part T 101   a  and the number of bits (33 bits) of the low order part T 101   b  is more than the number of bits (33 bits) of the booth selectors B 101  to B 113 , so that the high order part T 101   a  and the low order part T 101   b  do not spatially protrude beyond the booth selectors B 101  to B 113 . This avoids formation of dead area in the Wallace tree array that would otherwise be caused by protrusion of the third partial product adder T 101 .  
      Referring to  FIG. 1 , while a space is left on the left of the low order parts S 101   b  and F 101   b , this space is not a dead area because the booth encoder  2  is provided there, and so area efficiency is not lowered. Similarly, the final adder  3  is provided in the space on the right of the high order parts F 104   a , S 102   a , and T 101   a , so that this space is not a dead area and does not lower the area efficiency.  
      In the multiplication device of the first preferred embodiment, the critical path of the Wallace tree array is the route from the low order part B 113   b  to the final adder  3  sequentially passing through the low order parts F 104   b , S 102   b , T 101   b , and the high order part T 101   a . The longest interconnection in this route is the carry path interconnection that connects the carry-out terminal CO of the adder element corresponding to the most significant bit of the low order part T 101   b  and the carry-in terminal CI of the adder element corresponding to the least significant bit of the high order part T 101   a . Now, in the multiplication device of the first preferred embodiment, the low order part T 101   b  is positioned in a middle row in the Wallace tree array. Accordingly, as compared with a multiplication device in which the low order part T 101   b  is positioned in the top row of the Wallace tree array (e.g. the multiplication device disclosed in the second patent document mentioned earlier), the interconnection length of this carry path is shorter, which suppresses multiplying speed reduction.  
      In the multiplication device of the first preferred embodiment, since the multiplication result by the low order part S 101   b  is inputted to the final adder  3 , the length of the interconnection connecting the low order part S 101   b  and the final adder  3  (referred to as “interconnection W” hereinafter) is longer than the interconnection length of the above-mentioned carry path. However, the multiplication result by the low order part S 101   b  is inputted to the final adder  3  without passing through the third partial product adder T 101 . Therefore, the result from the low order part S 101   b  is propagated to the final adder  3  through one fewer partial product adder stages than those from the high order parts S 101   a , S 102   a  and the low order part S 102   b . Accordingly the length of the interconnection W does not cause reduction of multiplying speed.  
     Second Preferred Embodiment  
      While the first preferred embodiment has shown the layout of a 32-bit-multiplicand×25-bit-multiplier multiplication device, the numbers of bits of the multiplicand and multiplier are not limited to these numbers but can be any numbers of bits. A second preferred embodiment describes an expanded version of the multiplication device of the first preferred embodiment for multiplication of 54-bit multiplicand×54-bit multiplier.  
       FIGS. 3 and 4  together schematically show a first layout of the multiplication device of the second preferred embodiment of the invention.  FIGS. 3 and 4  continue together at line Q 1 -Q 1 . Note that  FIGS. 3 and 4  do not show the X driver  1 , the booth encoder  2 , and the final adder  3  shown in  FIG. 1 .  
      Booth selectors B 201  to B 227  are divided into high order parts B 201   a  to B 227   a , respectively, and low order parts B 201   b  to B 227   b , respectively. First partial product adders F 201  to F 207  are divided respectively into high order parts F 201   a  to F 207   a  and low order parts F 201   b  to F 207   b . Second partial product adders S 201  to S 204  are divided respectively into high order parts S 201   a  to S 204   a  and low order parts S 201   b  to S 204   b . Third partial product adders T 201  and T 202  are divided respectively into high order parts T 201   a  and T 202   a  and low order parts T 201   b  and T 202   b . A fourth partial product adder E 201  is divided into a high order part E 201   a  and a low order part E 201   b . Particularly, the low order part E 201   b  is placed in a middle row in the Wallace tree array. More specifically, the low order part E 201   b  is placed right above the low order part T 202   b . The high order part E 201   a  is placed in the bottom row of the Wallace tree array. More specifically, the high order part E 201   a  is positioned right under the high order part T 202   a.    
      In the area where the high order parts B 201   a  to B 206   a , F 201   a , F 202   a , S 201   a  and the low order part T 201   b  are provided, the addition is performed from the top to the bottom as shown by the arrow D 5 . In the area where the low order parts B 201   b  to B 206   b , F 201   b , F 202   b , and S 201   b  are provided, the addition is performed from the bottom to the top as shown by the arrow D 6 . In the area where the high order parts B 207   a  to B 214   a , F 203   a , F 204   a , S 202   a , and T 201   a  are provided, the addition is performed from the top to the bottom as shown by the arrow D 7 . In the area where the low order parts B 207   b  to B 214   b , F 203   b , F 204   b , S 202   b , and T 201   b  are provided, the addition is performed from the bottom to the top as shown by the arrow D 8 . In the area where the high order parts B 215   a  to B 227   a , F 205   a  to F 207   a , S 203   a , S 204   a , T 202   a , and E 201   a  are provided, the addition is performed from the top to the bottom as shown by the arrow D 9 . In the area where the low order parts B 215   b  to B 227   b , F 205   b  to F 207   b , S 203   b , S 204   b , T 202   b , and E 201   b  are provided, the addition is performed from the bottom to the top as shown by the arrow D 10 .  
       FIGS. 5 and 6  together schematically show a second layout of the multiplication device of the second preferred embodiment of the invention.  FIGS. 5 and 6  continue together at line Q 2 -Q 2 . Note that  FIGS. 5 and 6  do not show the X driver  1 , booth encoder  2 , and final adder  3  shown in  FIG. 1 .  
      Booth selectors B 301  to B 314  are divided respectively into high order parts B 301   a  to B 314   a  and respectively into low order parts B 301   b  to B 314   b . Booth selectors B 315  to B 327  are divided respectively into high order parts B 315   a  to B 327   a , middle order parts B 315   b  to B 327   b , and low order parts B 315   c  to B 327   c . First partial product adders F 301  to F 304  are divided respectively into high order parts F 301   a  to F 304   a  and low order parts F 301   b  to F 304   b . First partial product adders F 305  to F 307  are divided respectively into high order parts F 305   a  to F 307   a , middle order parts F 305   b  to F 307   b , and low order parts F 305   c  to F 307   c . Second partial product adders S 301  and S 302  are divided respectively into high order parts S 301   a  and S 302   a  and low order parts S 301   b  and S 302   b . Second partial product adders S 303  and S 304  are divided respectively into high order parts S 303   a  and S 304   a , middle order parts S 303   b  and S 304   b , and low order parts S 303   c  and S 304   c . A third partial product adder T 301  is divided into a high order part T 301   a  and a low order part T 301   b . A third partial product adder T 302  is divided into a high order part T 302   a , a middle order part T 302   b , and a low order part T 302   c . A fourth partial product adder E 301  is divided into a high order part E 301   a , middle order parts E 301   b  and E 301   c , and a low order part E 301   d . Particularly, the low order part E 301   d  is placed in a middle row in the Wallace tree array. More specifically, the low order part E 301   d  is placed right above the low order part S 303   c . The high order part E 301   a  is placed in the bottom row of the Wallace tree array. More specifically, the high order part E 301   a  is positioned right under the high order part T 302   a.    
      In the area where the high order parts B 301   a  to B 306   a , F 301   a , F 302   a , S 301   a  and the low order part T 301   b  are provided, the addition is performed from the top to the bottom as shown by the arrow D 11 . In the area where the low order parts B 301   b  to B 306   b , F 301   b , F 302   b , and S 301   b  are provided, the addition is performed from the bottom to the top as shown by the arrow D 12 . In the area where the high order parts B 307   a  to B 314   a , F 303   a , F 304   a , S 302   a , and T 301   a  are provided, the addition is performed from the top to the bottom as shown by the arrow D 13 . In the area where the low order parts B 307   b  to B 314   b , F 303   b , F 304   b , S 302   b , and T 301   b  are provided, the addition is performed from the bottom to the top as shown by the arrow D 14 . In the area where the high order parts B 315   a  to B 322   a , F 305   a , F 306   a , S 303   a , and the middle order part E 301   b  are provided, the addition is performed from the top to the bottom as shown by the arrow D 15 . In the area where the middle order parts B 315   b  to B 322   b , F 305   b , F 306   b , S 303   b , and E 301   c  are provided, the addition is performed from the top to the bottom as shown by the arrow D 16 . In the area where the low order parts B 315   c  to B 322   c , F 305   c , F 306   c , S 303   c , and E 301   d  are provided, the addition is performed from the bottom to the top as shown by the arrow D 17 . In the area where the high order parts B 323   a  to B 327   a , F 307   a , S 304   a , T 302   a , and E 301   a  are provided, the addition is performed from the top to the bottom as shown by the arrow D 18 . In the area where the middle parts B 323   b  to B 327   b , F 307   b , S 304   b , T 302   b , and E 301   b  are provided, the addition is performed from the bottom to the top as shown by the arrow D 19 . In the area where the low order parts B 323   c  to B 327   c , F 307   c , S 304   c , T 302   c , and the middle order part E 301   c  are provided, the addition is performed from the bottom to the top as shown by the arrow D 20 .  
      In the multiplication device shown in  FIGS. 3 and 4 , the maximum-degree partial product adder in the Wallace tree, i.e. the fourth partial product adder E 201 , is divided into the high order part E 201   a  and the low order part E 201   b , and the high order part E 201   a  and the low order part E 201   b  are arranged in different rows in the Wallace tree array. The number of bits (43 bits) of the high order part E 201  a and the number of bits (37 bits) of the low order part E 201   b  are both less than the number of bits (55 bits) of the booth selectors B 201  to B 227 , so that the high order part E 201   a  and the low order part E 201   b  do not spatially protrude beyond the booth selectors B 201  to B 227 . Similarly, in the multiplication device shown in  FIGS. 5 and 6 , the maximum-degree partial product adder in the Wallace tree, i.e. the fourth partial product adder E 301 , is divided into the high order part E 301   a , the middle order parts E 301   b  and E 301   c , and the low order part E 301   d , where the high order part E 301   a , the middle order parts E 301   b  and E 301   c , and the low order part E 301   d  are arranged in different rows in the Wallace tree array. The number of bits (11 bits) of the high order part E 301   a , the number of bits (53 bits) of the middle order parts E 301   b  and E 301   c , and the number of bits (16 bits) of the low order part E 301   d  are all less than the number of bits (55 bits) of the booth selectors B 301  to B 327 , so that the high order part E 301   a , the middle order parts E 301   b  and E 301   c , and the low order part E 301   d  do not spatially protrude beyond the booth selectors B 301  to B 327 . Thus, the multiplication device of the second preferred embodiment avoids formation of dead area in the Wallace tree array that would otherwise be caused by protrusion of the fourth partial product adders E 201  and E 301 .  
      In the multiplication device shown in  FIGS. 3 and 4 , the critical path of the Wallace tree array is the route passing from the low order part B 226   b  to the final adder  3  sequentially through the low order parts F 207   b , S 204   b , T 202   b , E 201   b  and the high order part E 201   a . The longest interconnection in this route is the carry path interconnection that connects the carry-out terminal CO of the adder element corresponding to the most significant bit of the low order part E 201   b  and the carry-in terminal CI of the adder element corresponding to the least significant bit of the high order part E 201   a . Now, in the multiplication device of the second preferred embodiment, the low order part E 201   b  is positioned in a middle row in the Wallace tree array. Accordingly, as compared with a multiplication device in which the low order part E 201   b  is positioned in the top row of the Wallace tree array, the interconnection length of this carry path is shorter, which suppresses multiplying speed reduction. The same is true with the multiplication device shown in  FIGS. 5 and 6 .  
     Third Preferred Embodiment  
       FIG. 7  is a diagram schematically showing the layout of a multiplication device according to a third preferred embodiment of the invention.  FIG. 7  does not show the X driver  1  and the final adder  3  shown in  FIG. 1 . While the multiplication device of the first preferred embodiment has the booth encoder  2  placed in the left part of the top side of the Wallace tree array, the multiplication device of the third preferred embodiment includes a booth encoder  2 A, in place of the booth encoder  2 , that is placed in a middle row in the Wallace tree array. More specifically, the booth encoder  2 A is placed between the low order part T 101   b  and the low order part S 102   b . Like the booth encoder  2 , the booth encoder  2 A reduces a 25-bit multiplier to a 13-bit modified multiplier (booth 1  to booth 13 ) according to the Booth&#39;s algorithm and outputs them respectively to the booth selectors B 101  to B 113 .  
      The booth encoder  2 A has a first driver (not shown) for the booth selectors B 101  to B 106  and a second driver (not shown) for the booth selectors B 107  to B 113 . The first driver and the second driver are paralleled to each other.  
      Except that the booth encoder  2  is replaced by the booth encoder  2 A, the configuration and operation of the multiplication device of the third preferred embodiment are the same as those of the multiplication device of the first preferred embodiment, and so they are not described in detail here again. However, note that the invention of the third preferred embodiment is applicable also to the multiplication device of the second preferred embodiment.  
      The multiplication device of the third preferred embodiment is capable of simultaneously performing the output operation of the modified multipliers booth 1  to booth 6  from the first driver to the booth selectors B 101  to B 106  and the output operation of the modified multipliers booth 7  to booth 13  from the second driver to the booth selectors B 107  to B 113 . Furthermore, the interconnection length between the booth encoder  2 A and the booth selectors (the booth selectors B 101  and B 113 ) that are farthest from the booth encoder  2 A is reduced to about ½ of the interconnection length between the booth encoder  2  shown in  FIG. 1  and the booth selector (the booth selector B 113 ) farthest from the booth encoder  2 . Accordingly, the multiplication device of the third preferred embodiment offers higher signal propagation speed from the booth encoder  2 A to the booth selectors B 101  to B 113 , as compared with the multiplication device of the first preferred embodiment.  
     Fourth Preferred Embodiment  
       FIG. 8  is a diagram schematically showing the layout of a multiplication device according to a fourth preferred embodiment of the invention.  FIG. 8  does not show the booth encoder  2  and the final adder  3  shown in  FIG. 1 . While the multiplication device of the first preferred embodiment has the X driver  1  provided at the top side of the Wallace tree array, the multiplication device of the fourth preferred embodiment includes an X driver  1 A, in place of the X driver  1 , that is placed in a middle row in the Wallace tree array. More specifically, the X driver  1 A is placed between the low order part T 101   b  and the low order part S 102   b . Like the X driver  1 , the X driver  1 A functions as a driving buffer for driving the multiplicand, which gives the multiplicand to the booth selectors B 101  to B 113 .  
      The X driver  1  A has a first driver (not shown) for the booth selectors B 101  to B 106  and a second driver (not shown) for the booth selectors B 107  to B 113 . The first driver and the second driver are paralleled to each other.  
      Except that the X driver  1  is replaced by the X driver  1 A, the configuration and operation of the multiplication device of the fourth preferred embodiment are the same as those of the multiplication device of the first preferred embodiment, and so they are not described in detail here again. However, note that the invention of the fourth preferred embodiment is applicable also to the multiplication devices of the second and third preferred embodiments.  
      Thus, the multiplication device of the fourth preferred embodiment is capable of simultaneously performing the output operation of the multiplicand from the first driver to the booth selectors B 101  to B 106  and the output operation of the multiplicand from the second driver to the booth selectors B 107  to B 113 . Furthermore, the interconnection length between the X driver  1 A and the booth selectors (the booth selectors B 101  and B 113 ) that are farthest from the X driver  1 A is reduced to about ½ of the interconnection length between the X driver  1  shown in  FIG. 1  and the booth selector (the booth selector B 113 ) that is farthest from the X driver  1 . Accordingly, the multiplication device of the fourth preferred embodiment offers higher signal propagation speed from the X driver  1 A to the booth selectors B 101  to B 113 , as compared with the multiplication device of the first preferred embodiment.  
     Fifth Preferred Embodiment  
       FIG. 9  is a diagram schematically showing the layout of a multiplication device according to a fifth preferred embodiment of the invention.  FIG. 9  does not show the X driver  1  and the booth encoder  2  shown in  FIG. 1 . While the multiplication device of the first preferred embodiment has the final adder  3  provided in the right part of the bottom side of the Wallace tree array, the multiplication device of the fifth preferred embodiment has a final adder  3 A, in place of the final adder  3 , that is provided in a middle row in the Wallace tree array. More specifically, the final adder  3 A is placed right under the low order part T 101   b . Like the final adder  3 , the final adder  3 A receives results of addition from the low order part S 101   b  and the third partial product adder T 101  and obtains the result of multiplication of the multiplicand by the multiplier.  
      Except that the final adder  3  is replaced by the final adder  3 A, the configuration and operation of the multiplication device of the fifth preferred embodiment are the same as those of the multiplication device of the first preferred embodiment, and so they are not described in detail here again. However, note that the invention of the fifth preferred embodiment is applicable also to the multiplication devices of the second to fourth preferred embodiments.  
      According to the multiplication device of the fifth preferred embodiment, the interconnection length between the final adder  3 A and the low order part T 101   b  is reduced than the interconnection length between the final adder  3  shown in  FIG. 1  and the low order part T 101   b . Accordingly, the multiplication device of the fifth preferred embodiment offers higher signal propagation speed from the low order part T 101   b  to the final adder  3 A, as compared with the multiplication device of the first preferred embodiment.  
     Sixth Preferred Embodiment  
       FIG. 10  is a diagram schematically showing the layout of a multiplication device according to a sixth preferred embodiment of the invention. While the multiplication device of the first preferred embodiment has the final adder  3  placed in the right part of the bottom side of the Wallace tree array, the multiplication device of the sixth preferred embodiment has a high-order final adder  3   a  and a low-order final adder  3   b  in place of the final adder  3 , where the high-order final adder  3   a  and the low-order final adder  3   b  are divided at the border between the 12th and 13th bits from the least significant bit of the multiplicand. The final adder  3   a  is placed at the bottom side of the Wallace tree array and the final adder  3   b  is placed near the low order part S 101   b , in the right part at the top side of the Wallace tree array. The final adders  3   a  and  3   b  are thus arranged so that the Wallace tree array is interposed between them. The final adder  3   a  receives a third partial product from the third partial product adder T 101  and the final adder  3   b  receives a second partial product from the low order part S 101   b . Then, like the final adder  3  shown in  FIG. 1 , the final adders  3   a  and  3   b  obtain the result of the multiplication of the multiplicand by the multiplier.  
      The multiplication device of the sixth preferred embodiment further includes a latch  10   a  interposed between the high order part T 101   a  and the final adder  3   a , a latch  10   b  interposed between the low order part T 101   b  and the final adder  3   a , and a latch  10   c  interposed between the final adder  3   b  and the final adder  3   a . Third partial products outputted from the high order part T 101   a  and the low order part T 101   b  are inputted to the final adder  3   a  respectively through the latches  10   a  and  10   b . A carry signal outputted from the final adder  3   b  is inputted to the final adder  3   a  through the latch  10   c . That is to say, the insertion of the latches  10   a  to  10   c  provides the multiplication device with a pipeline configuration.  
      Except for these modifications, the configuration and operation of the multiplication device of the sixth preferred embodiment are the same as those of the multiplication device of the first preferred embodiment, and so they are not described in detail here again. However, note that the invention of the sixth preferred embodiment is applicable also to the multiplication devices of the second to fourth preferred embodiments.  
      Thus, according to the multiplication device of the sixth preferred embodiment, the final adder  3   b  is placed proximate to the low order part S 101   b , which shortens the interconnection length between the low order part S 101   b  and the final adder  3   b , thus speeding up addition in the final adder  3   b.    
      When two final adders  3   a  and  3   b  are arranged so that the Wallace tree array is interposed between them, the carry path from the low-order final adder  3   b  to the high-order final adder  3   a  extends over the Wallace tree array, and so the long interconnection length lowers speed. However, the multiplication device of the sixth preferred embodiment is provided with a pipeline configuration by the provision of the latches  10   a  to  10   c , where the carry signal outputted from the final adder  3   b  is once held in the latch  10   c  and then inputted to the final adder  3   a . This avoids the speed reduction problem.  
      Modifications.  
      In the multiplication devices of the first, second, and fourth to sixth preferred embodiments, the booth encoder  2  may be placed at any of the four sides of the Wallace tree array, depending on design requirements. Also, the both encoder  2  may be omitted, in which case the multiplier is inputted to the shifter/inverters without being modified.  
      In the multiplication devices of the first to third, fifth, and sixth preferred embodiments, the X driver  1  may be placed at any of the four sides of the Wallace tree array depending on design requirements.  
      In the multiplication devices of the first to fourth preferred embodiments, the final adder  3  may be placed at any of the four sides of the Wallace tree array depending on design requirements.  
      While the invention has been described in detail, the foregoing description is in all aspects illustrative and not restrictive. It is understood that numerous other modifications and variations can be devised without departing from the scope of the invention.