From: pmcguirk@mrcmicroe.com (Pat McGuirk) Newsgroups: comp.arch.fpga Subject: Shift and Add Multiplier With Signed Numbers Date: 8 Jul 2001 11:00:59 -0700 Organization: http://groups.google.com/ Lines: 25 Message-ID: NNTP-Posting-Host: 63.20.87.151 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 994615260 4597 127.0.0.1 (8 Jul 2001 18:01:00 GMT) X-Complaints-To: groups-support@google.com NNTP-Posting-Date: 8 Jul 2001 18:01:00 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.ifi.unizh.ch!news.imp.ch!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.stanford.edu!postnews1.google.com!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:7743 Hi, I'm trying to implement a scaling multiplier for 2s complement numbers. I can't come up conceptually with how to do the shift and adds and handle the signs. If I want to multiply two numbers such as -2 * -3, what should the partial products be ? Ex: 1110 -2 1101 -3 --------- 11111110 -- Sign extend first partial product 00000000 -- Second partial product zero 11111000 -- Third partial product ???????? -- For this partial product I need -2^3 * (-2^3 + 2^2 + 2^1) = 2^6 - 2^5 -2^4. So, I guess I don't know the trick for representing this last partial product, or I'm missing something obvious. Or, do I have the wrong approach for doing the scaling multiplier with 2s complement numbers? Can anyone help out or provide a good reference for me? Thanks in advance, Pat ###### From: Alan Nishioka Newsgroups: comp.arch.fpga Subject: Re: Shift and Add Multiplier With Signed Numbers Date: Sun, 08 Jul 2001 12:19:46 -0700 Organization: http://extra.newsguy.com Lines: 27 Message-ID: <3B48B252.6B6B8B29@accom.com> References: NNTP-Posting-Host: charon.accom.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 4.75 [en] (Windows NT 5.0; U) X-Accept-Language: en To: Pat McGuirk Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.ifi.unizh.ch!news.imp.ch!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!pln-e!spln!dex!extra.newsguy.com!newsp.newsguy.com!enews1 Xref: chonsp.franklin.ch comp.arch.fpga:8015 You're very close. Just use the negative of the sign extended shifted partial product. This is because the top bit represents a negative number -2^3. Alan Nishioka alann@accom.com Pat McGuirk wrote: > Hi, > > I'm trying to implement a scaling multiplier for 2s complement > numbers. I can't come up conceptually with how to do the shift and > adds and handle the signs. If I want to multiply two numbers such as > -2 * -3, what should the partial products be ? > > Ex: > 1110 -2 > 1101 -3 > --------- > 11111110 -- Sign extend first partial product > 00000000 -- Second partial product zero > 11111000 -- Third partial product > 00010000 -- For this partial product I need -2^3 * (-2^3 + 2^2 + 2^1) > ======= > 00000110 2^6 - 2^5 -2^4. ###### From: Philip Freidin Newsgroups: comp.arch.fpga Subject: Re: Shift and Add Multiplier With Signed Numbers Organization: Fliptronics Reply-To: philip@fliptronics.com Message-ID: References: X-Newsreader: Forte Agent 1.8/32.548 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 38 Date: Sun, 08 Jul 2001 12:59:21 -0700 NNTP-Posting-Host: 216.103.85.188 X-Complaints-To: abuse@pacbell.net X-Trace: news.pacbell.net 994622416 216.103.85.188 (Sun, 08 Jul 2001 13:00:16 PDT) NNTP-Posting-Date: Sun, 08 Jul 2001 13:00:16 PDT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.ifi.unizh.ch!news.imp.ch!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!feed2.onemain.com!feed1.onemain.com!cyclone-sf.pbi.net!206.13.28.33!news.pacbell.net.POSTED!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:7895 One solution is: Save the XOR of the MSB of both numbers. For each number, if the MSB is set, negate the number (make it positive) Do the multiply, N-1 steps, since MSBs are always '0' If the saved XOR result is set, negate the result. Philip Freidin On 8 Jul 2001 11:00:59 -0700, pmcguirk@mrcmicroe.com (Pat McGuirk) wrote: >Hi, > >I'm trying to implement a scaling multiplier for 2s complement >numbers. I can't come up conceptually with how to do the shift and >adds and handle the signs. If I want to multiply two numbers such as >-2 * -3, what should the partial products be ? > >Ex: > 1110 -2 > 1101 -3 >--------- >11111110 -- Sign extend first partial product >00000000 -- Second partial product zero >11111000 -- Third partial product >???????? -- For this partial product I need -2^3 * (-2^3 + 2^2 + 2^1) >= > 2^6 - 2^5 -2^4. > >So, I guess I don't know the trick for representing this last partial >product, or I'm missing something obvious. Or, do I have the wrong >approach for doing the scaling multiplier with 2s complement numbers? >Can anyone help out or provide a good reference for me? > >Thanks in advance, >Pat Philip Freidin Fliptronics ###### Message-ID: <3B48F93A.82B47D43@andraka.com> From: Ray Andraka Organization: Andraka Consulting Group, Inc X-Mailer: Mozilla 4.77 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: Shift and Add Multiplier With Signed Numbers References: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 50 Date: Mon, 09 Jul 2001 00:21:48 GMT NNTP-Posting-Host: 24.13.238.93 X-Complaints-To: abuse@home.net X-Trace: news1.wwck1.ri.home.com 994638108 24.13.238.93 (Sun, 08 Jul 2001 17:21:48 PDT) NNTP-Posting-Date: Sun, 08 Jul 2001 17:21:48 PDT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news-ge.switch.ch!codeine.org!deine.net!out.nntp.be!propagator-dallas!news-in-dallas.newsfeeds.com!in.nntp.be!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newshub2.home.com!news.home.com!news1.wwck1.ri.home.com.POSTED!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:7919 I was going to send you to my website, but on checking it I realize I never got around to putting the part on handling negative numbers on there. The secret is to realize that two's complement numbers are represented by weighting the msb as -2^(n-1), not 2^(n-1). Recognizing this, it becomes obvious that you need to subtract the partial (1xN) product corresponding to the MSB of the serial input instead of adding it. This is easiest to accomplish if you use an adder/subtractor instead of a straight adder for the scaling accumulator. That takes care of a signed serial input. For a signed parallel input, you simply need to sign extend the parallel input to the full width of the scaling accumulator (normally the scaling accumulator has one bit above the parallel input for an LSB first implementation). Also don't forget to sign extend the shifted accumulator feedback. Pat McGuirk wrote: > Hi, > > I'm trying to implement a scaling multiplier for 2s complement > numbers. I can't come up conceptually with how to do the shift and > adds and handle the signs. If I want to multiply two numbers such as > -2 * -3, what should the partial products be ? > > Ex: > 1110 -2 > 1101 -3 > --------- > 11111110 -- Sign extend first partial product > 00000000 -- Second partial product zero > 11111000 -- Third partial product > ???????? -- For this partial product I need -2^3 * (-2^3 + 2^2 + 2^1) > = > 2^6 - 2^5 -2^4. > > So, I guess I don't know the trick for representing this last partial > product, or I'm missing something obvious. Or, do I have the wrong > approach for doing the scaling multiplier with 2s complement numbers? > Can anyone help out or provide a good reference for me? > > Thanks in advance, > Pat -- -Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email ray@andraka.com http://www.andraka.com ###### Message-ID: <3B49DBD6.3550FA09@mail.com> From: John_H X-Mailer: Mozilla 4.75 [en]C-CCK-MCD (Win95; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: Shift and Add Multiplier With Signed Numbers References: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 35 Date: Mon, 09 Jul 2001 16:29:12 GMT NNTP-Posting-Host: 192.65.17.17 X-Complaints-To: postmaster@tek.com X-Trace: news-west.eli.net 994696152 192.65.17.17 (Mon, 09 Jul 2001 10:29:12 MDT) NNTP-Posting-Date: Mon, 09 Jul 2001 10:29:12 MDT Organization: Tektronix NewsReader Service Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.ifi.unizh.ch!news.imp.ch!fr.clara.net!heighliner.fr.clara.net!telocity-west!TELOCITY!news-west.eli.net!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:8007 It's pretty obvious that a positive second multiplicand works fine whether the first multiplicand is positive or negative. It's the second negative that's a problem. For any x and positive y x * -y = x * (16-y) for a 4 bit input x * -y = x * 16 - x * y Since what you want is - x * y you could just subtract out x*16. So a shift and add with a final subtract would get you to your goal 1110 1101 ----------- ...1111110 ...0000000 ...1111000 ...1110000 ----------- ...1100110 -..11100000 -16*(-2) ----------- ...0000110 It's not pretty but it's one way to get there. You could probably do an internet search and find a better way to implement the 4 quadrant multiplier. Enjoy. - John ###### From: Santiago de Pablo Newsgroups: comp.arch.fpga Subject: Re: Shift and Add Multiplier With Signed Numbers Date: Tue, 10 Jul 2001 18:24:57 +0200 Organization: Universidad de Valladolid - Spain Lines: 72 Message-ID: <3B4B2C59.90433517@eis.uva.es> References: NNTP-Posting-Host: cdem23.dte.eis.uva.es Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Trace: simancas.uva.es 994781534 10971 157.88.140.23 (10 Jul 2001 16:12:14 GMT) X-Complaints-To: usenet@news.uva.es NNTP-Posting-Date: 10 Jul 2001 16:12:14 GMT X-Mailer: Mozilla 4.5 [es] (Win98; I) X-Accept-Language: es Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news-ge.switch.ch!news.rediris.es!news.uva.es!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:7894 Hi folks, Philip Freidin escribió: > > One solution is: > Save the XOR of the MSB of both numbers. > For each number, if the MSB is set, negate the number (make it positive) > Do the multiply, N-1 steps, since MSBs are always '0' > If the saved XOR result is set, negate the result. > > Philip Freidin > > On 8 Jul 2001 11:00:59 -0700, pmcguirk@mrcmicroe.com (Pat McGuirk) wrote: > >Hi, > > > >I'm trying to implement a scaling multiplier for 2s complement > >numbers. I can't come up conceptually with how to do the shift and > >adds and handle the signs. If I want to multiply two numbers such as > >-2 * -3, what should the partial products be ? > > > >Ex: > > 1110 -2 > > 1101 -3 > >--------- > >11111110 -- Sign extend first partial product > >00000000 -- Second partial product zero > >11111000 -- Third partial product > >???????? -- For this partial product I need -2^3 * (-2^3 + 2^2 + 2^1) > > = 2^6 - 2^5 -2^4. 1110 (-2) 1101 (-3) --------- 11111110 (-2)*1 * 1 0000000 (-2)*2 * 0 111110 (-2)*4 * 1 11110 (-2)*8 * 1 -> (-2)*(8+16+32+64+128+...) = 1110 (-2)*16 * 1 = (-2)*(1+2+4+8+16+...)*8 = 110 (-2)*32 * 1 = (-2)*(-1)*8 ! = (+2)*8 10 (-2)*64 * 1 0 (-2)*128 * 1 ---------- 00000110 (+6) 1110 (-2) 1101 (-3) --------- 11111110 (-2)*1 * 1 0000000 (-2)*2 * 0 111110 (-2)*4 * 1 00010 (+2)*8 * 1 ! ---------- 00000110 (+6) You may look at http://www.dte.eis.uva.es/OpenProjects/OpenDSP/index.htm#CODIGOVERILOG. Enjoy, Santiago. > > > >So, I guess I don't know the trick for representing this last partial > >product, or I'm missing something obvious. Or, do I have the wrong > >approach for doing the scaling multiplier with 2s complement numbers? > >Can anyone help out or provide a good reference for me? > > > >Thanks in advance, > >Pat > > Philip Freidin > Fliptronics ###### Reply-To: "Rob Finch" From: "Rob Finch" Newsgroups: comp.arch.fpga References: Subject: Re: Shift and Add Multiplier With Signed Numbers Lines: 4 X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.50.4133.2400 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 Message-ID: Date: Thu, 12 Jul 2001 02:28:17 -0400 NNTP-Posting-Host: 64.229.15.84 X-Complaints-To: abuse@sympatico.ca X-Trace: news20.bellglobal.com 994996685 64.229.15.84 (Thu, 12 Jul 2001 23:58:05 EDT) NNTP-Posting-Date: Thu, 12 Jul 2001 23:58:05 EDT Organization: Bell Sympatico Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.ifi.unizh.ch!news.imp.ch!news.stealth.net!207.35.177.132.MISMATCH!nf1.bellglobal.com!nf2.bellglobal.com!news20.bellglobal.com.POSTED!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:8087 Try using Booth recoding. ###### Message-ID: <3B4E8927.BF2AB802@andraka.com> From: Ray Andraka Organization: Andraka Consulting Group, Inc X-Mailer: Mozilla 4.77 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: Shift and Add Multiplier With Signed Numbers References: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 30 Date: Fri, 13 Jul 2001 05:37:04 GMT NNTP-Posting-Host: 24.13.238.93 X-Complaints-To: abuse@home.net X-Trace: news1.wwck1.ri.home.com 995002624 24.13.238.93 (Thu, 12 Jul 2001 22:37:04 PDT) NNTP-Posting-Date: Thu, 12 Jul 2001 22:37:04 PDT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.ifi.unizh.ch!news.imp.ch!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newshub2.home.com!news.home.com!news1.wwck1.ri.home.com.POSTED!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:8077 Booth recoding won't help much in this case. A scaling accumulator multiplier is a single accumulator with the feedback shifted. It is a serial by parallel multiplier, that uses a conventional adder. Booth recoding seeks to reduce the number of partial products by recoding strings of '1' bits into an equivalent 1, -1 and zeros. The result is that you can reduce the number of partial products to be combined in an adder tree, which in turn reduces the size of the tree. Since the scaling accumulator multiplier is shifting once and adding for N cycles, you essentially are doing all the partial products regardless of whether or not they are zero. You could conceivably use Booth recoding in this case to reduce the number of cycles, but in a practical sense, the added complexity to the circuit would outweigh the benefit (one could use two scaling accumulator multipliers, or go to a 2 bits/clock version to get on average a better speedup for less area and complexity). All he has to do is subtract the partial product corresponding to the MSB of the serial input and sign extend the parallel input to handle signed muliplicands. Rob Finch wrote: > Try using Booth recoding. -- -Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email ray@andraka.com http://www.andraka.com ###### Message-ID: <3B4A2E3A.7E9B1587@mail.com> From: John_H X-Mailer: Mozilla 4.75 [en]C-CCK-MCD (Win95; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: Shift and Add Multiplier With Signed Numbers - just a bit more References: <3B49DBD6.3550FA09@mail.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 13 Date: Mon, 09 Jul 2001 22:20:40 GMT NNTP-Posting-Host: 192.65.17.17 X-Complaints-To: postmaster@tek.com X-Trace: news-west.eli.net 994717240 192.65.17.17 (Mon, 09 Jul 2001 16:20:40 MDT) NNTP-Posting-Date: Mon, 09 Jul 2001 16:20:40 MDT Organization: Tektronix NewsReader Service Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.ifi.unizh.ch!news.imp.ch!uni-erlangen.de!news-nue1.dfn.de!news-lei1.dfn.de!newsfeed00.sul.t-online.de!t-online.de!fr.usenet-edu.net!usenet-edu.net!wanadoo.fr!proxad.net!fr.clara.net!heighliner.fr.clara.net!telocity-west!TELOCITY!news-west.eli.net!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:8009 Silly me - just subtract the last stage instead of adding when the second multiplicand is negative since +8-16=-8 1110 1110 -2 1101 1101 1101 ----------- ----------- ----- +...1111110 +...1111110 + -2 +...0000000 +...0000000 + 0 +...1111000 +...1111000 + -8 -...1110000 +...0010000 - -16 ----------- ----------- ----- ...0000110 ...0000110 6 ###### From: "Steve Casselman" Newsgroups: comp.arch.fpga References: <3B4E8927.BF2AB802@andraka.com> Subject: Re: Shift and Add Multiplier With Signed Numbers Lines: 46 X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.50.4133.2400 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 Message-ID: Date: Sat, 14 Jul 2001 10:51:44 -0700 NNTP-Posting-Host: 64.174.106.246 X-Complaints-To: abuse@pacbell.net X-Trace: news.pacbell.net 995133262 64.174.106.246 (Sat, 14 Jul 2001 10:54:22 PDT) NNTP-Posting-Date: Sat, 14 Jul 2001 10:54:22 PDT Organization: SBC Internet Services Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!pinatubo.switch.ch!news-ge.switch.ch!isdnet!sunqbc.risq.qc.ca!headwall.stanford.edu!news-out.nibble.net!hub1.nntpserver.com!easynews!cyclone.swbell.net!cyclone-sf.pbi.net!206.13.28.143!news.pacbell.net.POSTED!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:8114 I have to disagree. A booth multiplier is more efficient than a regular shift and add. In the 4000 I was able to fit a booth multiplier in the same area as a normal shift and add (which does not use all the inputs in a 4 bit LUT and the recoding just takes two three-LUTs and an inverter). As you know one of our demos is the mandelbrot hardware. You can "unroll" the booth multiplier and pipeline it to save 1/2 the area. Steve "Ray Andraka" wrote in message news:3B4E8927.BF2AB802@andraka.com... > Booth recoding won't help much in this case. A scaling accumulator > multiplier is a single accumulator with the feedback shifted. It is a > serial by parallel multiplier, that uses a conventional adder. Booth > recoding seeks to reduce the number of partial products by recoding > strings of '1' bits into an equivalent 1, -1 and zeros. The result is > that you can reduce the number of partial products to be combined in an > adder tree, which in turn reduces the size of the tree. Since the > scaling accumulator multiplier is shifting once and adding for N cycles, > you essentially are doing all the partial products regardless of whether > or not they are zero. You could conceivably use Booth recoding in this > case to reduce the number of cycles, but in a practical sense, the added > complexity to the circuit would outweigh the benefit (one could use two > scaling accumulator multipliers, or go to a 2 bits/clock version to get > on average a better speedup for less area and complexity). All he has > to do is subtract the partial product corresponding to the MSB of the > serial input and sign extend the parallel input to handle signed > muliplicands. > > Rob Finch wrote: > > > Try using Booth recoding. > > -- > -Ray Andraka, P.E. > President, the Andraka Consulting Group, Inc. > 401/884-7930 Fax 401/884-7950 > email ray@andraka.com > http://www.andraka.com > > > ###### Message-ID: <3B51EF50.EEB86579@mail.com> From: John_H X-Mailer: Mozilla 4.75 [en]C-CCK-MCD (Win95; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: Shift and Add Multiplier With Signed Numbers References: <3B4E8927.BF2AB802@andraka.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 28 Date: Sun, 15 Jul 2001 19:30:26 GMT NNTP-Posting-Host: 192.65.17.17 X-Complaints-To: postmaster@tek.com X-Trace: news-west.eli.net 995225426 192.65.17.17 (Sun, 15 Jul 2001 13:30:26 MDT) NNTP-Posting-Date: Sun, 15 Jul 2001 13:30:26 MDT Organization: Tektronix NewsReader Service Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news-ge.switch.ch!news-fra1.dfn.de!newsfeed.hanau.net!fr.clara.net!heighliner.fr.clara.net!telocity-west!TELOCITY!news-west.eli.net!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:8142 In my quick internet scan, I see the Booth Multiplier as an algorithm which might reduce the number of accumulator cycles but requires a variable shift to skip over unneeded cycles. If I understand the Modified Booth Multiplier as taking bit pairs, each stage of the multiplier requires more resources since there are too many inputs to fit onto one LUT: accumulator feedback, first multipler (unshifted), first multiplier (shifted), 2 bits of select for 0/+1/-1/-2(/+2?). You might attain better speeds with the external mux to get the right value - 0/+1/-1/-2(/+2?) - in with the accumulator in the older Xilinx 4000 series devices or the Altera arithmatic functions, but for the Xilinx Virtex devices, the complete shift/add/subtract accumulation can take place in a single level of LUTs. A booth approach might be more efficient from a cycle perspective, but for resources too? Steve Casselman wrote: > I have to disagree. A booth multiplier is more efficient than a regular > shift and add. In the 4000 I was able to fit a booth multiplier in the same > area as a normal shift and add (which does not use all the inputs in a 4 bit > LUT and the recoding just takes two three-LUTs and an inverter). As you know > one of our demos is the mandelbrot hardware. You can "unroll" the booth > multiplier and pipeline it to save 1/2 the area. ###### Message-ID: <3B522253.182195AD@andraka.com> From: Ray Andraka Organization: Andraka Consulting Group, Inc X-Mailer: Mozilla 4.77 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: Shift and Add Multiplier With Signed Numbers References: <3B4E8927.BF2AB802@andraka.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 78 Date: Sun, 15 Jul 2001 23:07:17 GMT NNTP-Posting-Host: 24.13.238.93 X-Complaints-To: abuse@home.net X-Trace: news1.wwck1.ri.home.com 995238437 24.13.238.93 (Sun, 15 Jul 2001 16:07:17 PDT) NNTP-Posting-Date: Sun, 15 Jul 2001 16:07:17 PDT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!pinatubo.switch.ch!news-ge.switch.ch!enews.sgi.com!newshub2.rdc1.sfba.home.com!news.home.com!news1.wwck1.ri.home.com.POSTED!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:8148 Steve, I think we are talking apples and oranges here. The orignal post on this thread was asking specifically about scaling accumulator multipliers, which do the shift-add on a cycle by cycle basis. The multiplier exists as an accumulator with one input gated (to initialize on first cycle) and the other XOR'ed with the MSB control. The area occupied is the same as an adder of the same width, if you get the tools to make it right. The accumulator feedback is a fixed (wired shift). In order to do a booth mulitplier with this structure, you need to modify the serial input to replace strings of 1's with a shortened 1 and -1 input. That requires dropping bit times and dynamically changing the shift in the accumulator feedback. There is a serial booth multiplier which is a different architecture. That one uses a series of serial adders, as described in my FIR filter paper from 1992 PLDCOn. This one can be run faster than the scaling accumulator because it doesn't use the carry chain, but it also requires about twice the number of LUTs, since the carry chain gives you half the logic for free. On reading your posts, I am pretty sure you are describing a parallel by parallel multiplier, in which case the Booth recoding does reduce the size of the adder tree needed to sum the partial products. Steve Casselman wrote: > I have to disagree. A booth multiplier is more efficient than a regular > shift and add. In the 4000 I was able to fit a booth multiplier in the same > area as a normal shift and add (which does not use all the inputs in a 4 bit > LUT and the recoding just takes two three-LUTs and an inverter). As you know > one of our demos is the mandelbrot hardware. You can "unroll" the booth > multiplier and pipeline it to save 1/2 the area. > > Steve > > "Ray Andraka" wrote in message > news:3B4E8927.BF2AB802@andraka.com... > > Booth recoding won't help much in this case. A scaling accumulator > > multiplier is a single accumulator with the feedback shifted. It is a > > serial by parallel multiplier, that uses a conventional adder. Booth > > recoding seeks to reduce the number of partial products by recoding > > strings of '1' bits into an equivalent 1, -1 and zeros. The result is > > that you can reduce the number of partial products to be combined in an > > adder tree, which in turn reduces the size of the tree. Since the > > scaling accumulator multiplier is shifting once and adding for N cycles, > > you essentially are doing all the partial products regardless of whether > > or not they are zero. You could conceivably use Booth recoding in this > > case to reduce the number of cycles, but in a practical sense, the added > > complexity to the circuit would outweigh the benefit (one could use two > > scaling accumulator multipliers, or go to a 2 bits/clock version to get > > on average a better speedup for less area and complexity). All he has > > to do is subtract the partial product corresponding to the MSB of the > > serial input and sign extend the parallel input to handle signed > > muliplicands. > > > > Rob Finch wrote: > > > > > Try using Booth recoding. > > > > -- > > -Ray Andraka, P.E. > > President, the Andraka Consulting Group, Inc. > > 401/884-7930 Fax 401/884-7950 > > email ray@andraka.com > > http://www.andraka.com > > > > > > -- -Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email ray@andraka.com http://www.andraka.com