Custom Search
Site Home Archive Home FAQ Home How to search the Archive How to Navigate the Archive
Compare FPGA features and resources
Threads starting:
Authors:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
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.comArticle: 141376
Hello, I would like to know if would be possible to use SERDES like RocketIO, Serial RapidIO etc to detect an asynchronous random = 1ns pulse. What I understand is that the clock recovery process is not be possible in this situation so I would like to use TX Serializer to feed the clock of the Deserializer and just get the RxData at the output. Any idea if this is possible? What FPGA do I need in this case? Thanks, Dan.Article: 141377
On Jun 22, 1:48=A0pm, "Ndf" <ndf123456...@yahoo.fr> wrote: > Hello, > > I would like to know if would be possible to use SERDES like RocketIO, > Serial RapidIO etc to detect an asynchronous random =3D 1ns pulse. > What I understand is that the clock recovery process is not be possible i= n > this situation so I would like to use TX Serializer to feed the clock of = the > Deserializer and just get the RxData at the output. > > Any idea if this is possible? What FPGA do I need in this case? > > Thanks, > Dan. you can use MGT serder in non synced mode so it works basically as 3GBit single bit logic analyzer AnttiArticle: 141378
i am just trying to run "hello world" form microblaze......i wrote
the software program in SDK, where i have just used xil_printf("hello
world").......
if i load the program to FPGA board form XPS it outputs fine but when
i load the program from SDK, it didn't display anything(output was
displayed on Hyper Terminal).....
another thing ...if i changed the thing inside xil_printf function and
run from XPS , i didn't get the new word that i have written inside
the printf function printed, it always prints "hello world"....(build
all is also done) ....
Is there any configuration setting that i have to made ??
or what should i do to fix this problem??
any help will be greatly appreciated!!
Article: 141379On 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. WengArticle: 141380
On Fri, 19 Jun 2009 22:51:40 -0700 Ed McGettigan <ed.mcgettigan@xilinx.com> wrote: > Rob Gaddi wrote: > > On Fri, 19 Jun 2009 16:59:13 -0700 (PDT) > > lenz19@gmx.de wrote: > > > >> Rob, John thanks for reply. > >> > >> > >>>> 2. R => not R, S => not S > >> > >> That's the point. > >> Your suggestion would infer an inverter realized in a LUT. > >> I don't want to infer extra inverter logic in the CLB. I want the > >> inverter for free. > >> > > > > That's why there's a synthesis tool that's able to perform > > optimization. Last I checked, if you go back in to the FPGA Editor > > and look in on what you've got, you'll find that XST will very > > happily have collapsed those inverters into the free ones built into > > the slice. > > > > You seem to be of the opinion that it's necessary for you to > > outsmart the synthesis tools. As I said earlier, it's really > > rarely the case. If you code: > > > > process(clk, r, s) > > begin > > if (r = '1') then > > q <= '0'; > > elsif (s = '1') then > > q <= '1'; > > elseif rising_edge(clk) then > > q <= d; > > end if; > > end process; > > > > You'll find that the synthesis tool still gives you exactly what you > > wanted, without you having to slog through unnecessary direct > > instatiation. The people telling you that it doesn't work haven't > > updated their opinions since the mid 1990s. > > > > The code above is not equivalent to FDRSE, but this code is: > > process (clk) > begin > if rising_edge(clk) then > if (r = '1') then > q <= '0'; > elsif (s = '1') then > q <= '1'; > elsif (ce = '1') then > q <= d; > end if; > end process; > > Ed McGettigan > -- > Xilinx Inc. > Good catch, you're exactly right. I coded FDCPE instead. Teach me to post past five on a Friday, jacket in hand. -- Rob Gaddi, Highland Technology Email address is currently out of orderArticle: 141381
I have a device that require a free running clock with 0.5V DC offset and 500mv swing. (0.25V VIL and 0.75V VIH). I am using Spartan3 1000 FPGA and all the outputs are connected to 3.3V bank. Your ideas are most welcome. Thanks. CPArticle: 141382
On Mon, 22 Jun 2009 09:21:22 -0700 (PDT), Test01 <cpandya@yahoo.com> wrote: >I have a device that require a free running clock with 0.5V DC offset >and 500mv swing. (0.25V VIL and 0.75V VIH). I am using Spartan3 >1000 FPGA and all the outputs are connected to 3.3V bank. Is this differential or single-ended? And what frequency? --- Muzaffer Kal DSPIA INC. ASIC/FPGA Design Services http://www.dspia.comArticle: 141383
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
Article: 141384Muzaffer 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.comArticle: 141385
On Jun 22, 11:52=A0am, Muzaffer Kal <k...@dspia.com> wrote: This is a single ended signal running at 32KHz. It is a free running clock running at 32KHz. > On Mon, 22 Jun 2009 09:21:22 -0700 (PDT), Test01 <cpan...@yahoo.com> > wrote: > > >I have a device that require a free running clock with 0.5V DC offset > >and 500mv swing. =A0(0.25V VIL and 0.75V VIH). =A0 I am using Spartan3 > >1000 FPGA and all the outputs are connected to 3.3V bank. > > Is this differential or single-ended? And what frequency? > --- > Muzaffer Kal > > DSPIA INC. > ASIC/FPGA Design Serviceshttp://www.dspia.comArticle: 141386
On Mon, 22 Jun 2009 10:46:51 -0700 (PDT), Test01 wrote: >This is a single ended signal running at 32KHz. It is a free running >clock running at 32KHz. In which case I suggest you think about a few resistors and some simple circuit calculations :-) -- Jonathan Bromley, Consultant DOULOS - Developing Design Know-how VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK jonathan.bromley@MYCOMPANY.com http://www.MYCOMPANY.com The contents of this message may contain personal views which are not the views of Doulos Ltd., unless specifically stated.Article: 141387
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.comArticle: 141388
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.com Hi 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. WengArticle: 141389
On Mon, 22 Jun 2009 11:42:29 -0700 (PDT), Weng Tianxiang wrote: >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. Some reasons (I'm sure there are more): 1) you might run out of embedded multipliers; 2) you might need a very fast multiplier - faster than the builtins - for narrow data words; 3) you might be using a device that lacks multipliers (there still are some of those); 4) you are aiming for portability to non-FPGA technologies. -- Jonathan Bromley, Consultant DOULOS - Developing Design Know-how VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK jonathan.bromley@MYCOMPANY.com http://www.MYCOMPANY.com The contents of this message may contain personal views which are not the views of Doulos Ltd., unless specifically stated.Article: 141390
On Mon, 22 Jun 2009 10:46:51 -0700 (PDT), Test01 <cpandya@yahoo.com> wrote: >On Jun 22, 11:52 am, Muzaffer Kal <k...@dspia.com> wrote: >This is a single ended signal running at 32KHz. It is a free running >clock running at 32KHz. > >> On Mon, 22 Jun 2009 09:21:22 -0700 (PDT), Test01 <cpan...@yahoo.com> >> wrote: >> >> >I have a device that require a free running clock with 0.5V DC offset >> >and 500mv swing. (0.25V VIL and 0.75V VIH). I am using Spartan3 >> >1000 FPGA and all the outputs are connected to 3.3V bank. You should be able to make it work with a %1 500+100 ohm voltage divider at the output of your 3.3V IO which puts your VOHmin around 0.5V. If your clock input capacitance is too high and you get slew rate issues, you can add a transistor driver. - Muzaffer Kal DSPIA INC. ASIC/FPGA Design Services http://www.dspia.comArticle: 141391
Muzaffer Kal wrote:
> But probably with more gates.
That depends on the target and how clever the tool is.
This could be an fpga with an unused DSP block.
-- Mike Treseler
Article: 141392Hi MUzaffer, You mentioned about using 500/100 Oho voltage divider. I am trying to understand the amplitude. For 3.3V output signal at 32KHz, when the output is at 3.3V, the voltage divider will generate 0.55V When the fpga Output pin is at 0V, the voltage divider will generate 0V. Thus it will swing from 0 to 0.55V. Is that correct? I have Vih requirement of 0.75 and Vil requirement of 0.25. I am not sure this is considered meeting that requirement. Thanks. CP On Jun 22, 2:03=A0pm, Muzaffer Kal <k...@dspia.com> wrote: > On Mon, 22 Jun 2009 10:46:51 -0700 (PDT), Test01 <cpan...@yahoo.com> > wrote: > > >On Jun 22, 11:52=A0am, Muzaffer Kal <k...@dspia.com> wrote: > >This is a single ended signal running at 32KHz. =A0It is a free running > >clock running at 32KHz. > > >> On Mon, 22 Jun 2009 09:21:22 -0700 (PDT), Test01 <cpan...@yahoo.com> > >> wrote: > > >> >I have a device that require a free running clock with 0.5V DC offset > >> >and 500mv swing. =A0(0.25V VIL and 0.75V VIH). =A0 I am using Spartan= 3 > >> >1000 FPGA and all the outputs are connected to 3.3V bank. > > You should be able to make it work with a %1 500+100 ohm voltage > divider at the output of your 3.3V IO which puts your VOHmin around > 0.5V. If your clock input capacitance is too high and you get slew > rate issues, you can add a transistor driver. > - > Muzaffer Kal > > DSPIA INC. > ASIC/FPGA Design Services > > http://www.dspia.comArticle: 141393
On Jun 22, 2:17=A0pm, Test01 <cpan...@yahoo.com> wrote: > Hi MUzaffer, > > You mentioned about using 500/100 Oho voltage divider. =A0I am trying to > understand the amplitude. > > For 3.3V output signal at 32KHz, when the output is at 3.3V, the > voltage divider will generate 0.55V > > When the fpga Output pin is at 0V, the voltage divider will generate > 0V. > > Thus it will swing from 0 to 0.55V. =A0Is that correct? =A0I have Vih > requirement of 0.75 and Vil requirement of 0.25. =A0I am not sure this > is considered meeting that requirement. > > Thanks. > > CP > > On Jun 22, 2:03=A0pm, Muzaffer Kal <k...@dspia.com> wrote: > > > > > On Mon, 22 Jun 2009 10:46:51 -0700 (PDT), Test01 <cpan...@yahoo.com> > > wrote: > > > >On Jun 22, 11:52=A0am, Muzaffer Kal <k...@dspia.com> wrote: > > >This is a single ended signal running at 32KHz. =A0It is a free runnin= g > > >clock running at 32KHz. > > > >> On Mon, 22 Jun 2009 09:21:22 -0700 (PDT), Test01 <cpan...@yahoo.com> > > >> wrote: > > > >> >I have a device that require a free running clock with 0.5V DC offs= et > > >> >and 500mv swing. =A0(0.25V VIL and 0.75V VIH). =A0 I am using Spart= an3 > > >> >1000 FPGA and all the outputs are connected to 3.3V bank. Also with simple voltage divider my DC offset will be around 0.25V and not 0.5V. Thus it may not work having a voltage divider. is that correct? > > You should be able to make it work with a %1 500+100 ohm voltage > > divider at the output of your 3.3V IO which puts your VOHmin around > > 0.5V. If your clock input capacitance is too high and you get slew > > rate issues, you can add a transistor driver. > > - > > Muzaffer Kal > > > DSPIA INC. > > ASIC/FPGA Design Services > > >http://www.dspia.com- Hide quoted text - > > - Show quoted text -Article: 141394
Test01 <cpandya@yahoo.com> wrote: > Also with simple voltage divider my DC offset will be around 0.25V and > not 0.5V. Thus it may not work having a voltage divider. is that > correct? You need a not-so-simple voltage divider, with a resistor to ground, Vcc, and the output. -- glenArticle: 141395
On Jun 22, 12:59=A0pm, 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 > > =A0c <=3D ieee.numeric_std."*"(signed(a),signed(b)); > > would work just as well for fewer brain cycles. > > =A0 =A0 =A0 =A0-- Mike Treseler Did you miss the part about "small footprint"? I used that in an earlier design and it uses about 300 LUTs for the multiplier. I have lots of clock cycles, so I can generate the partial products sequentially using much less logic. RickArticle: 141396
On Jun 22, 1:29 pm, Andy Botterill <a...@plymouth2.demon.co.uk> wrote: > Muzaffer Kal 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. 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 fromhttp://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&btnme... > 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 I've been looking at this pretty hard and I have come to the conclusion that a shift and add uses fewer resources in an FPGA. Why do you feel you need to use Booth's algorithm? If you are saying that you need a signed multiplier, you can use the shift and add just fine. Booth's requires the multiplier stage to include an adder to negate the multiplicand in addition to the adder to form the partial product. This is repeated for each partial product. The shift and add algorithm can work for signed number by using the sign of the multiplier to negate both the multiplier and multiplicand. The adder which outputs the partial product can be made to either add or subtract, implementing the negate for the multiplicand. If the shift and add multiplier is implementing all stages, the negate circuit for the multiplier is only implemented once instead of for each partial product stage. If the design is using the same circuit sequentially, the negate of the multiplier can be done bit serially. Either way the shift and add uses less resources than Booth's algorithm. RickArticle: 141397
rickman wrote:
> I used that in an
> earlier design and it uses about 300 LUTs for the multiplier. I have
> lots of clock cycles, so I can generate the partial products
> sequentially using much less logic.
Less than 200 LUTs?
-- Mike Treseler
Article: 141398On Jun 22, 6:33=A0pm, Mike Treseler <mtrese...@gmail.com> wrote: > rickman wrote: > > I used that in an > > earlier design and it uses about 300 LUTs for the multiplier. =A0I have > > lots of clock cycles, so I can generate the partial products > > sequentially using much less logic. > > Less than 200 LUTs? > > =A0 =A0 =A0 -- Mike Treseler Are you joking? I expect it to be on the order of 40 LUTs for a 16 x 16 multiplier. Maybe I am not making myself clear. I am calculating one partial product at a time and adding them to the product sequentially using the same hardware, but multiple clock cycles. Sort of like a bit serial adder, but this is a partial product serial multiplier or maybe you could call it a multiplier bit serial multiplier. A truely bit serial multiplier could be done in a dozen to twenty LUTs I expect, but a 16x16 multiply would take 256 clock cycles. I actually considered this on an earlier design, but it turned out I didn't need to push on the LUTs used and the X*Y multiplier took some 300 LUTs. So going down to 40 or 50 LUTs is a big improvement. I should have this done later this week and I'll post the results. RickArticle: 141399
rickman wrote: > On Jun 22, 1:29 pm, Andy Botterill <a...@plymouth2.demon.co.uk> wrote: >> Muzaffer Kal 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. 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 fromhttp://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&btnme... >> 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 > > I've been looking at this pretty hard and I have come to the > conclusion that a shift and add uses fewer resources in an FPGA. Why > do you feel you need to use Booth's algorithm? > > If you are saying that you need a signed multiplier, you can use the > shift and add just fine. Booth's requires the multiplier stage to The shift and add multiplier was my first proper verilog for my home project. This was designed as an unsigned multiplier and uses 8 adders so that it can complete in 4 cycles. Later on I realised that I needed a signed/unsigned multiplier done in 4 cycles. The only way that I think that I can get signed multiplication is to double the data size from 32 to 64. That was suggested by a friend in design. This increases the number of adders needed to complete in 4 cycles. It also changes the cycle taken for the unsigned multiplication. Using booths gives me less area, correct cycles and signed/unsigned operation. I've only got to do it.... > include an adder to negate the multiplicand in addition to the adder > to form the partial product. This is repeated for each partial > product. The shift and add algorithm can work for signed number by > using the sign of the multiplier to negate both the multiplier and > multiplicand. The adder which outputs the partial product can be made > to either add or subtract, implementing the negate for the > multiplicand. If the shift and add multiplier is implementing all > stages, the negate circuit for the multiplier is only implemented once > instead of for each partial product stage. If the design is using the > same circuit sequentially, the negate of the multiplier can be done > bit serially. Either way the shift and add uses less resources than > Booth's algorithm. The purpose of this home project is to prove to myself that I can do design. The idea is to meet the functional requirements and cycle requirements. Where I think that I can reduce the area I have. Using one signed/unsigned multiplier will also simplify the fsm in another design block. I think the simplification (reducing FSM states) should reduce the design ara. Thanks for the help. Andy > > Rick
Site Home Archive Home FAQ Home How to search the Archive How to Navigate the Archive
Compare FPGA features and resources
Threads starting:
Authors:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z