Tw  |  Fb  |  In  |  Rss
Max Maxfield

# The Basics of FPGA Mathematics

100%
0%
hamster
8/7/2012 5:29:08 PM
User Rank
Blogger
Fixed point math
One thing that I have never quite got to grips with is the signs required to multiply large signed fixed point mumbers using more than one MULT18x18 bocks.

If you have ever tried it you will know what I mean, if you haven't tried it you will have no idea what I'm talking about :-)

50%
50%
Max Maxfield
8/7/2012 5:31:46 PM
User Rank
Blogger
Re: Fixed point math
@Hamster: What are you talking about? (grin)

50%
50%
hamster
8/7/2012 6:16:56 PM
User Rank
Blogger
Re: Fixed point math
I know you are winding me up, but...

Have a look at "Forming Larger Multipliers" on pge 31 of the DSP48 user guide. (http://www.xilinx.com/support/documentation/user_guides/ug431.pdf)

The bit that confuses me is the sign extending of the partial products. Why is the lowest one zero extended? Why are the middle two extended with the signs of different multipliers?

I know it works because I use it, but I dont understand WHY it works.

50%
50%
rfindley
8/8/2012 2:57:36 AM
User Rank
Blogger
Re: Fixed point math
@Hamster, here is, I think, the simplest way to look at it.

When we humans do math, we think this way:
-54 = -50 + -4

Whereas computers think this way:
-54 = -60 + 6

To confirm this, let's look at a hexadecimal example:
0xFA = 0xF0 + 0x0A
or, in decimal:
-6 = -16 + 10

In other words, it is the sum of a signed MSB and an always-positive LSB offset.

So, when the DSP block multiplies, the partial products are:
AL*BL   <--  product of two positive offsets
AH*BL   <--  product of a signed MSB and a positive offset
BH*AL   <--  product of a signed MSB and a positive offset
AH*BH   <-- product of two signed MSBs.
` `

50%
50%
Max Maxfield
8/8/2012 9:43:59 AM
User Rank
Blogger
Re: Fixed point math
@rfindley: I think this is the clearest explanation I have ever seen for this topic -- thanks for sharing

50%
50%
David Ashton
8/8/2012 7:26:23 PM
User Rank
Guru
Re: Fixed point math
@Rfindley, thanks for that but I have a question:

"Whereas computers think this way:   -54 = -60 + 6"

Being as computers work in powers of 2, shouldn't that be -54 = -64 + 10?

Or am I missing something?  Maybe you were just illustrating your point?

Thanks

50%
50%
rfindley
8/8/2012 10:55:48 PM
User Rank
Blogger
Re: Fixed point math
@David, you are correct... it was for illustration only, from a decimal perspective.  Maybe it is clearer this way:

---------
We humans tend to think this way:
-54 = -50 + -4
Whereas computers think this way:
-54 = -60 + 6

Technically, a computer would more likely use "-64 + 10", but here I'm sticking with the decimal notation to illustrate the point, which is that the computer starts from a signed MSB base, and adds an always-positive offset.

(....)

---------

50%
50%
David Ashton
8/8/2012 11:06:06 PM
User Rank
Guru
Re: Fixed point math
@Rfindley - thanks for that...nice to know I'm not toooo stupid!! :-)

50%
50%
hamster
8/9/2012 4:39:54 AM
User Rank
Blogger
Re: Fixed point math
I second Max's comment - your post is so clear even I can understand it!

50%
50%
Karl
8/8/2012 4:36:48 PM
User Rank
Guru
Re: Fixed point math
@hamster:  Here is some c code to multiply 4 x -4, shows for negative numbers times positive requires the left bits to be 1's when the product width is extended.  So propagating the sign works also for both negative will result in a positive product when added.

int a = -4, b = 4, c = 0, d = 0, al, bl, au, bu, albl, aubl, albu, aubu;
c = a * b;
//   c ==  0xfffffff0
al = a & 0x0001ffff;
//   al == 0x0001fffc
au = (int)(a & 0xfffe0000) >> 16;
//   au == 0xfffffffe
bl = b & 0x0001ffff;
//   bl == 0x00000004
bu = (int)(b & 0xfffe0000) >> 16;
//   bu == 0x00000000
albl = al * bl;
// albl == 0x0007fff0
aubl = au * bl;
// aubl == 0xfffffff8
albu = al * bu;
// albu == 0x00000000
aubu = au & bu;
// aubu == 0x00000000
d = aubu + (aubl << 16) + (albu << 16) + albl;
//    d == 0xfffffff0  ..  c == 0xfffffff0

As was already pointed out (rfindley? I think) negative numbers are formed by adding a positive offset to the most negative number which is a 1 followed by however many 0's.  Not obvious when complementing and adding 1 to form 2's complement.

50%
50%
hamster
8/9/2012 4:40:15 AM
User Rank
Blogger
Re: Fixed point math
I pondered rfindley's post and your post while out for a run today. It now makes perfect sense!

In fact so much sense I feel confident that I could now multiply even bigger numbers without reaching for the web browser!

Many thanks to you!

50%
50%
JezmoSSL
8/11/2012 4:04:45 AM
User Rank
Blogger
Re: Fixed point math
Two interestiing and slightly related things this week, we thought briefly about using mathcad to generate code for some very simple filters like a couple of biquads, using their automagic vhdl builder, mainly because my boss didn't believe machine generated code could be so nasty and then we found out the cost and my boss very quickly went off the idea, you are basically paying the equivelent of a junior engineer's salery for a year to produce code which wouldnt be aceptable if it was produced by a junior engineer.

And the on-line demo which mathcad did for us didnt work which made me laugh.

50%
50%
8/11/2012 4:55:36 AM
User Rank
Blogger
Re: Fixed point math
I have used the matlab version in the past and Xilinx system generator it is useful for quick proof of concepts but not really for production code.

You mention a junior engineer do you take on many graduates ?

50%
50%
Douglas Mota Dias
8/8/2012 2:24:05 PM
User Rank
Beginner
Re: Fixed point math
@Max -- Thanks for this blog, Max! This is a major issue in high-performance reconfigurable computing field (i.e. algorithms acceleration by FPGA co-processing).

50%
50%
Max Maxfield
8/8/2012 2:29:22 PM
User Rank
Blogger
Re: Fixed point math
@Douglas: I keep on asking you... when are you going to "come to the light" and start writing blogs on high-performance reconfigurable computing for All Programmable Planet?

50%
50%
Paul A. Clayton
8/7/2012 6:37:44 PM
User Rank
Beginner
High result multiply
I was slightly disappointed by the lack of mention of the different types of multiplication (high result, low result, and doubled precision result).  For fixed point operations, using the high result is more usually appropriate than using the low result and can be cheaper than a doubled precision result.  (Normalized floating point numbers use the high result.  I would guess that FPGA DSP slices support generating the high result, though there might not be any reduction in resource use relative to doubled precision.)

50%
50%
Max Maxfield
8/7/2012 8:26:36 PM
User Rank
Blogger
Re: High result multiply
@Paul: Maxbe we can persuade Adam to do a series of blogs on these topics for All Programmable Planet...

50%
50%
hamster
8/8/2012 12:30:38 AM
User Rank
Blogger
Re: High result multiply
>  I would guess that FPGA DSP slices support generating the high result...

I think that the DSP48 slices are really poorly named (a mrketing choice??). They should really be called MULT18x18AndLotsOfAdding. However they are really flexible...

I think of them as multiplying in base 2^17 (plus sign makes 18).

Just like how when multiplying two 3 digit numbers you and I require perform nine single digit multipcations and lots of addition, to multiply two 35 bit numbers every cycle requires four DSP48 blocks....

So to perform a pipelined  64 bit mult every cycle requires 16 DSP48s...

50%
50%
8/8/2012 2:40:19 AM
User Rank
Blogger
Re: High result multiply
@Paul, sorry I did not mention them, it is always difficult to determine what to include and what not to in these articles. Typically most FPGA designs do not use floating point numbers due to the complexity hence my focus on the basics of fixed point multiplication.

Maybe I could do a follow on blog here, I will talk to Max about it

50%
50%
geekyasa
8/8/2012 3:29:37 AM
User Rank
Beginner
Re: High result multiply
Adam : Why not floating points ? It does not make things that difficult isnt it ? I used one which wasnt that complexed as such but I really like the suff so I right not have realized the complexicity.

50%
50%
Max Maxfield
8/8/2012 9:47:04 AM
User Rank
Blogger
Re: High result multiply
@geekyasa: I think there used to be a lot of overhead in doing floating-point in FPGAs, but more recently I've seen it used a lot -- let me chat to Adam about this -- maybe he will write some blogs on it for us...

50%
50%
8/8/2012 12:22:33 PM
User Rank
Blogger
Re: High result multiply
Generally FPGA are better suited for fixed point math, however this is something I will be blogging about in the future as there are more uses which require floating point.

50%
50%
Douglas Mota Dias
8/8/2012 2:28:28 PM
User Rank
Beginner
Re: High result multiply

50%
50%
Paul A. Clayton
8/8/2012 6:05:20 PM
User Rank
Beginner
Teaching is not easy
Adam Taylor wrote: "it is always difficult to determine what to include and what not to in these articles."

If teaching was easy, anyone could do it well.  Having done a very small amount of informal teaching, I have some appreciation of some of the difficulty.  For educational purposes, the shotgun approach--scattered coverage with limited coherence--tends to be less effective, so you are quite right in constraining what subtopics are covered.

I liked how the article went from concepts to application to implementation.  You just need to work on discerning what I want--note reading my mind will not work because even I do not know what I want--and writing perfect articles targeted to my wants. :-)

By the way, I wonder if APP should set up a hypertext knowledge base (possibly using a wiki).  Sometimes a narrative style of presenting information is appropriate (blogs, articles, books) and sometimes an information web is more useful.

50%
50%
KenwickVS
8/8/2012 7:59:00 PM
User Rank
Blogger
Re: Teaching is not easy
@Paul: "and sometimes an information web is more useful" I agree. The APP Blog moves "fast and furious" and is fun. However, sometimes an idea or technology discussion emerges that needs more time to be developed by those interested in the subject. Unfortunately, the subject closes because it is superceded by the "latest and greatest" blog. We're moving too fast, IMHO (I just learned what that means!)

50%
50%
William Murray
8/8/2012 7:04:45 AM
User Rank
Blogger
More info on the DC-DC converter paper would be great to feritt out
More info on the DC-DC converter paper would be great to feritt out -- May have a need for this in the future --

50%
50%
thrakkor
8/8/2012 11:34:48 AM
User Rank
Blogger
great article
great article Adam.  also extremely glad to see it appears you are using the IEEE numeric_std library rather than std_logic_unsigned/signed and std_logic_arith libraries.

there are also some new fixed and floating point packages included in the forthcoming VHDL-2008 updates (last I heard at least).

the fixed point packages have an interesting way of using negative vector indexing to represent the fractional part of the signed or unsigned vector...  i.e., (7 downto -8) => 8.8

50%
50%
Max Maxfield
8/8/2012 11:38:41 AM
User Rank
Blogger
Re: great article
@thrakkor: "(7 downto -8) => 8.8"

Interesting -- there's always a different way to do something, and always something new to learn -- I LOVE being an engineer!!!

50%
50%
8/8/2012 12:21:06 PM
User Rank
Blogger
Re: great article
thanks, numeric_std is the only way to do FPGA math ;)

I was planning another blog here on the fixed and float packages, as you say they are very interesting. I did some expoeriments many years ago with them (maybe 2007/2008 ish) and the results where interesting I plan to re run the experiments using modern devices and tool chains and blog about it.

50%
50%
thrakkor
8/8/2012 12:29:16 PM
User Rank
Blogger
Re: great article
I stumbled across both the new fixed/float packages and numeric-std while rolling my own Rectangular to Polar CORDIC, not being happy with the opencores one at the time.

once I started using numeric_std and read the philosophy behind using it versus the other method, I embraced it and haven't regretted it since.

one day i plan to fold the fixed point package stuff into my CORDIC and see what happens.

50%
50%
More Blogs from Max Maxfield
The appellation "primary colors" refers to a small collection of colors that can be combined to form a range of additional colors, but which "small collection of colors" should we use as our primaries?
To celebrate Geek Pride Day, Sylvie Barak has created a mega-cool infographic that depicts how geeks have been building the Internet since 1832.
I am shocked and horrified. It appears that those little scamps at Planet Analog are writing blogs pertaining to field-programmable issues.
This week's live online chat takes place on Thursday, May 23, 2013, at 1:00 p.m. ET.
Would you class these as adages, aphorisms, axioms, dictums, epigrams, maxims, precepts, saws, truisms, or... well, what?
flash poll