I needed a multiplier in a small footprint and Booth's Algorithm seemed the appropriate approach since the numbers were signed. I looked up multiple references on the web (isn't that where all knowledge is to be found?) and to make sure I understood the algorithm, I jimmied up a version is Excel. I thought I was having a problem with the way I was building it Excel (it really shouldn't be anyone's first choice for this sort of task...) as I could not get it to work for all inputs. I could get it to work for all multiplicands other than -2**n-1. Finally, I realized that ***NONE*** of the many examples I found on the web were correct! In order to work for all inputs, the implementation has to allow for a -2**n-1 to be negated to 2**n-1 which requires an extra bit in the arithmetic! Some examples do it all numerically, so you don't see this at all. Others even combine the multiplier with the product to save register bits, still, they don't add the extra bit at the msb. I guess they never tried their examples with -2**n-1 as a multiplicand... It took me quite a while to realize this was the problem and not my simulation. Is this extra bit obvious to everyone or am I just a bit slower than most? Rick
Subtleties of Booth's Algorithm Implementation
Started by ●June 21, 2009
Reply by ●June 21, 20092009-06-21
rickman <gnuarm@gmail.com> wrote: (snip) < I could get it to work for all multiplicands < other than -2**n-1. Finally, I realized that ***NONE*** of the many < examples I found on the web were correct! In order to work for all < inputs, the implementation has to allow for a -2**n-1 to be negated to < 2**n-1 which requires an extra bit in the arithmetic! I presume you mean -2**(n-1). < Some examples do it all numerically, so you don't see this at all. < Others even combine the multiplier with the product to save register < bits, still, they don't add the extra bit at the msb. I guess they < never tried their examples with -2**n-1 as a multiplicand... < It took me quite a while to realize this was the problem and not my < simulation. Is this extra bit obvious to everyone or am I just a bit < slower than most? I thought the case where you need the extra bit is when multiplying -2**(n-1) by itself. Anyway, yes that needs one additional product bit that no other case needs. Other than the extra bit, though, I hadn't thought you needed a special case for it. -- glen
Reply by ●June 22, 20092009-06-22
On Sun, 21 Jun 2009 15:27:09 -0700 (PDT), rickman <gnuarm@gmail.com> wrote:>I needed a multiplier in a small footprint and Booth's Algorithm >seemed the appropriate approach since the numbers were signed. I >looked up multiple references on the web (isn't that where all >knowledge is to be found?) and to make sure I understood the >algorithm, I jimmied up a version is Excel. I thought I was having a >problem with the way I was building it Excel (it really shouldn't be >anyone's first choice for this sort of task...) as I could not get it >to work for all inputs. I could get it to work for all multiplicands >other than -2**n-1. Finally, I realized that ***NONE*** of the many >examples I found on the web were correct! In order to work for all >inputs, the implementation has to allow for a -2**n-1 to be negated to >2**n-1 which requires an extra bit in the arithmetic! >Assuming n is the number of bits of the inputs I think you mean -2**(n-1) right? ie -8 = -2**3 is the most negative 4 bit two's complement number. When two n bit numbers are multiplied you get a 2n bit number. Continuing with our example, the number pair which generates a sign inversion and largest magnitute change is -8 x -8 or +64 ie 1000 x 1000 = 01000000. So the result of most negative n bit number squared fits into the 2n bit result. So far I don't see a need for any extra bits needed but I maybe missing something from your description. Muzaffer Kal DSPIA INC. ASIC/FPGA Design Services http://www.dspia.com
Reply by ●June 22, 20092009-06-22
On Jun 21, 8:28 pm, Muzaffer Kal <k...@dspia.com> wrote:> On Sun, 21 Jun 2009 15:27:09 -0700 (PDT), rickman <gnu...@gmail.com> > wrote: > > >I needed a multiplier in a small footprint and Booth's Algorithm > >seemed the appropriate approach since the numbers were signed. I > >looked up multiple references on the web (isn't that where all > >knowledge is to be found?) and to make sure I understood the > >algorithm, I jimmied up a version is Excel. I thought I was having a > >problem with the way I was building it Excel (it really shouldn't be > >anyone's first choice for this sort of task...) as I could not get it > >to work for all inputs. I could get it to work for all multiplicands > >other than -2**n-1. Finally, I realized that ***NONE*** of the many > >examples I found on the web were correct! In order to work for all > >inputs, the implementation has to allow for a -2**n-1 to be negated to > >2**n-1 which requires an extra bit in the arithmetic! > > Assuming n is the number of bits of the inputs I think you mean > -2**(n-1) right? ie -8 =3D -2**3 is the most negative 4 bit two's > complement number. When two n bit numbers are multiplied you get a 2n > bit number. Continuing with our example, the number pair which > generates a sign inversion and largest magnitute change is -8 x -8 or > +64 ie 1000 x 1000 =3D 01000000. So the result of most negative n bit > number squared fits into the 2n bit result. So far I don't see a need > for any extra bits needed but I maybe missing something from your > description. > > Muzaffer Kal > > DSPIA INC. > ASIC/FPGA Design Serviceshttp://www.dspia.comHi Rick, The following context may give you a help you may need. Find 3 =D7 -4, with m =3D 3 and r =3D -4, and x =3D 4 and y =3D 4: A =3D 0011 0000 0 S =3D 1101 0000 0 P =3D 0000 1100 0 Perform the loop four times : P =3D 0000 1100 0. The last two bits are 00. P =3D 0000 0110 0. Arithmetic right shift. P =3D 0000 0110 0. The last two bits are 00. P =3D 0000 0011 0. Arithmetic right shift. P =3D 0000 0011 0. The last two bits are 10. P =3D 1101 0011 0. P =3D P + S. P =3D 1110 1001 1. Arithmetic right shift. P =3D 1110 1001 1. The last two bits are 11. P =3D 1111 0100 1. Arithmetic right shift. The product is 1111 0100, which is -12. The above mentioned technique is inadequate when the multiplicand is the largest negative number that can be represented (i.e. if the multiplicand has 8 bits then this value is -128). One possible correction to this problem is to add one more bit to the left of A, S and P. Below, we demonstrate the improved technique by multiplying -8 by 2 using 4 bits for the multiplicand and the multiplier: A =3D 1 1000 0000 0 S =3D 0 1000 0000 0 P =3D 0 0000 0010 0 Perform the loop four times : P =3D 0 0000 0010 0. The last two bits are 00. P =3D 0 0000 0001 0. Right shift. P =3D 0 0000 0001 0. The last two bits are 10. P =3D 0 1000 0001 0. P =3D P + S. P =3D 0 0100 0000 1. Right shift. P =3D 0 0100 0000 1. The last two bits are 01. P =3D 1 1100 0000 1. P =3D P + A. P =3D 1 1110 0000 0. Right shift. P =3D 1 1110 0000 0. The last two bits are 00. P =3D 0 1111 0000 0. Right shift. The product is 11110000 (after discarding the first and the last bit) which is -16. It is copied from http://en.wikipedia.org/wiki/Booth_algorithm. There is no modified Booth algorithm in wikipedia and you may have to figure out how to adopt it to modified Booth algorithm. Weng
Reply by ●June 22, 20092009-06-22
On Sun, 21 Jun 2009 21:24:04 -0700 (PDT), Weng Tianxiang <wtxwtx@gmail.com> wrote:>On Jun 21, 8:28 pm, Muzaffer Kal <k...@dspia.com> wrote: >> On Sun, 21 Jun 2009 15:27:09 -0700 (PDT), rickman <gnu...@gmail.com> >> wrote: >> >> >I needed a multiplier in a small footprint and Booth's Algorithm >> >seemed the appropriate approach since the numbers were signed. I >> >looked up multiple references on the web (isn't that where all >> >knowledge is to be found?) and to make sure I understood the >> >algorithm, I jimmied up a version is Excel. I thought I was having a >> >problem with the way I was building it Excel (it really shouldn't be >> >anyone's first choice for this sort of task...) as I could not get it >> >to work for all inputs. I could get it to work for all multiplicands >> >other than -2**n-1. Finally, I realized that ***NONE*** of the many >> >examples I found on the web were correct! In order to work for all >> >inputs, the implementation has to allow for a -2**n-1 to be negated to >> >2**n-1 which requires an extra bit in the arithmetic! >> >> Assuming n is the number of bits of the inputs I think you mean >> -2**(n-1) right? ie -8 = -2**3 is the most negative 4 bit two's >> complement number. When two n bit numbers are multiplied you get a 2n >> bit number. Continuing with our example, the number pair which >> generates a sign inversion and largest magnitute change is -8 x -8 or >> +64 ie 1000 x 1000 = 01000000. So the result of most negative n bit >> number squared fits into the 2n bit result. So far I don't see a need >> for any extra bits needed but I maybe missing something from your >> description. >> >> Muzaffer Kal >> >> DSPIA INC. >> ASIC/FPGA Design Serviceshttp://www.dspia.com > >Hi Rick, >The following context may give you a help you may need....>It is copied from http://en.wikipedia.org/wiki/Booth_algorithm.The problem with the initial algorithm given in the above url is step 1.2. In two's complement representation the valid range is -2**(n-1) to 2**n-1 (ie [-8...7] for 4 bit numbers) so -m does not fit into x bits when m = -2**(n-1) (ie -8) as -m would be 2**n (+8). It's nice that wikipedia has a correction to it. The issue with Boothm multiplication as stated is the caveat given at the end of the url: "When the ones in a multiplier are grouped into long blocks", then "Booth's algorithm performs fewer additions and subtractions than the normal multiplication algorithm." In the worst case this algorithm has the same behavior as any other. I think it's better to use a booth encoder and halve the additions deterministically, especially when implementing in hardware. --- Muzaffer Kal DSPIA INC. ASIC/FPGA Design Services http://www.dspia.com
Reply by ●June 22, 20092009-06-22
On Jun 22, 1:22=A0am, Muzaffer Kal <k...@dspia.com> wrote:> On Sun, 21 Jun 2009 21:24:04 -0700 (PDT), Weng Tianxiang > > > > > > > > <wtx...@gmail.com> wrote: > >On Jun 21, 8:28 pm, Muzaffer Kal <k...@dspia.com> wrote: > >> On Sun, 21 Jun 2009 15:27:09 -0700 (PDT), rickman <gnu...@gmail.com> > >> wrote: > > >> >I needed a multiplier in a small footprint and Booth's Algorithm > >> >seemed the appropriate approach since the numbers were signed. =A0I > >> >looked up multiple references on the web (isn't that where all > >> >knowledge is to be found?) and to make sure I understood the > >> >algorithm, I jimmied up a version is Excel. =A0I thought I was having=a> >> >problem with the way I was building it Excel (it really shouldn't be > >> >anyone's first choice for this sort of task...) as I could not get it > >> >to work for all inputs. =A0I could get it to work for all multiplican=ds> >> >other than -2**n-1. =A0Finally, I realized that ***NONE*** of the man=y> >> >examples I found on the web were correct! =A0In order to work for all > >> >inputs, the implementation has to allow for a -2**n-1 to be negated t=o> >> >2**n-1 which requires an extra bit in the arithmetic! > > >> Assuming n is the number of bits of the inputs I think you mean > >> -2**(n-1) right? ie -8 =3D -2**3 is the most negative 4 bit two's > >> complement number. When two n bit numbers are multiplied you get a 2n > >> bit number. Continuing with our example, the number pair which > >> generates a sign inversion and largest magnitute change is -8 x -8 or > >> +64 ie 1000 x 1000 =3D 01000000. So the result of most negative n bit > >> number squared fits into the 2n bit result. So far I don't see a need > >> for any extra bits needed but I maybe missing something from your > >> description. > > >> Muzaffer Kal > > >> DSPIA INC. > >> ASIC/FPGA Design Serviceshttp://www.dspia.com > > >Hi Rick, > >The following context may give you a help you may need. > ... > >It is copied fromhttp://en.wikipedia.org/wiki/Booth_algorithm. > > The problem with the initial algorithm given in the above url is =A0step > 1.2. In two's complement representation the valid range is -2**(n-1) > to 2**n-1 (ie [-8...7] for 4 bit numbers) so -m does not fit into x > bits when m =3D -2**(n-1) (ie -8) as -m would be 2**n (+8). It's nice > that wikipedia has a correction to it. > The issue with Boothm multiplication as stated is the caveat given at > the end of the url: "When the ones in a multiplier are grouped into > long blocks", then "Booth's algorithm performs fewer additions and > subtractions than the normal multiplication algorithm." In the worst > case this algorithm has the same behavior as any other. I think it's > better to use a booth encoder and halve the additions > deterministically, especially when implementing in hardware. > --- > Muzaffer Kal > > DSPIA INC. > ASIC/FPGA Design Serviceshttp://www.dspia.com- Hide quoted text - > > - Show quoted text -Hi Muzaffer, Please compare modified Booth method with the method used by Xilinx in the following patent: The method used by Xilinx has the same advantage as modified Booth method: half the number of multiplicants, but with simpler logic connections. http://www.google.com/patents/about?id=3Dtq9_AAAAEBAJ&dq=3Dpatent:7205790&a= s_drrb_ap=3Dq&as_minm_ap=3D0&as_miny_ap=3D&as_maxm_ap=3D0&as_maxy_ap=3D&as_= drrb_is=3Dq&as_minm_is=3D0&as_miny_is=3D&as_maxm_is=3D0&as_maxy_is=3D My opinion about modified Booth method is: it is designed for ASIC, not for FPGA. Within FPGA, there are lot of solutions which is as good as modified Booth method. Weng
Reply by ●June 22, 20092009-06-22
rickman wrote:> I needed a multiplier in a small footprint and Booth's Algorithm > seemed the appropriate approach since the numbers were signed.I expect that c <= ieee.numeric_std."*"(signed(a),signed(b)); would work just as well for fewer brain cycles. -- Mike Treseler
Reply by ●June 22, 20092009-06-22
Muzaffer Kal wrote:> On Sun, 21 Jun 2009 21:24:04 -0700 (PDT), Weng Tianxiang > <wtxwtx@gmail.com> wrote: > >> On Jun 21, 8:28 pm, Muzaffer Kal <k...@dspia.com> wrote: >>> On Sun, 21 Jun 2009 15:27:09 -0700 (PDT), rickman <gnu...@gmail.com> >>> wrote: >>> >>>> I needed a multiplier in a small footprint and Booth's Algorithm >>>> seemed the appropriate approach since the numbers were signed. I >>>> looked up multiple references on the web (isn't that where all >>>> knowledge is to be found?) and to make sure I understood the >>>> algorithm, I jimmied up a version is Excel. I thought I was having a >>>> problem with the way I was building it Excel (it really shouldn't be >>>> anyone's first choice for this sort of task...) as I could not get it >>>> to work for all inputs. I could get it to work for all multiplicands >>>> other than -2**n-1. Finally, I realized that ***NONE*** of the many >>>> examples I found on the web were correct! In order to work for all >>>> inputs, the implementation has to allow for a -2**n-1 to be negated to >>>> 2**n-1 which requires an extra bit in the arithmetic! >>> Assuming n is the number of bits of the inputs I think you mean >>> -2**(n-1) right? ie -8 = -2**3 is the most negative 4 bit two's >>> complement number. When two n bit numbers are multiplied you get a 2n >>> bit number. Continuing with our example, the number pair which >>> generates a sign inversion and largest magnitute change is -8 x -8 or >>> +64 ie 1000 x 1000 = 01000000. So the result of most negative n bit >>> number squared fits into the 2n bit result. So far I don't see a need >>> for any extra bits needed but I maybe missing something from your >>> description. >>> >>> Muzaffer Kal >>> >>> DSPIA INC. >>> ASIC/FPGA Design Serviceshttp://www.dspia.com >> Hi Rick, >> The following context may give you a help you may need. > .... >> It is copied from http://en.wikipedia.org/wiki/Booth_algorithm. > > The problem with the initial algorithm given in the above url is step > 1.2. In two's complement representation the valid range is -2**(n-1) > to 2**n-1 (ie [-8...7] for 4 bit numbers) so -m does not fit into x > bits when m = -2**(n-1) (ie -8) as -m would be 2**n (+8). It's nice > that wikipedia has a correction to it.http://www.google.co.uk/search?pz=1&ned=uk&hl=en&q=booth+samavi&btnmeta%3Dsearch%3Dsearch=Search+the+Web This gives some further hints. I need to read this carefully before commenting. The wiki page does refer to a book which may give additional information. I need to convert a shift add unsigned multiplier into a booth unsigned/signed multiplier for a home project. I will get a solution but not that quickly because it is a home project and I'm still learning. Andy> --- > Muzaffer Kal > > DSPIA INC. > ASIC/FPGA Design Services > http://www.dspia.com
Reply by ●June 22, 20092009-06-22
On Mon, 22 Jun 2009 09:59:33 -0700, Mike Treseler <mtreseler@gmail.com> wrote:>rickman wrote: >> I needed a multiplier in a small footprint and Booth's Algorithm >> seemed the appropriate approach since the numbers were signed. > >I expect that > > c <= ieee.numeric_std."*"(signed(a),signed(b)); > >would work just as well for fewer brain cycles.But probably with more gates. This would generate a parallel multiplier and a shift-add/sub type multiplier can be made smaller by trading latency for area. - Muzaffer Kal DSPIA INC. ASIC/FPGA Design Services http://www.dspia.com
Reply by ●June 22, 20092009-06-22
On Jun 22, 11:10=A0am, Muzaffer Kal <k...@dspia.com> wrote:> On Mon, 22 Jun 2009 09:59:33 -0700, Mike Treseler > > <mtrese...@gmail.com> wrote: > >rickman wrote: > >> I needed a multiplier in a small footprint and Booth's Algorithm > >> seemed the appropriate approach since the numbers were signed. > > >I expect that > > > c <=3D ieee.numeric_std."*"(signed(a),signed(b)); > > >would work just as well for fewer brain cycles. > > But probably with more gates. This would generate a parallel > multiplier and a shift-add/sub type multiplier can be made smaller by > trading latency for area. > - > Muzaffer Kal > > DSPIA INC. > ASIC/FPGA Design Services > > http://www.dspia.comHi Mike, I have a question about multiplier. Given the fact that both Altera and Xilinx have multipliers built in FPGA chip, why is there a big interesting to constitute a multiplier from square one which seems to be very slow. I'v never use a multiplier in my design, so I would like to know on what conditions a FPGA user would like to built a multiplier. After reading the FPGA handbook I thought multiplication never is a problem with built-in multiplier. Weng
