Fixed Point Calculations

Is the multiplier signed or unsigned ?

If the multiplier is unsigned and the result of the preceding subtraction is negative, this will cause havoc to the multiply result. If multiplier input is negative, set it to zero.

If the multiplier is signed and the result of the preceding addition/subtraction is larger than signed maximum (check carry and overflow flags), set the value to largest positive or negative value. That is, use saturated addition/subtraction. ,

Do you really have sensors of producing 17 significant bits ?

On Friday, January 1, 2021 at 6:33:44 AM UTC-5, snipped-for-privacy@downunder.com wrot e:

expect it won't be too difficult once I get my head wrapped around it, but I seem to be spinning my wheels getting started.

t feeding a three input, 55 bit adder. The other two inputs are a 54 bit in put that is subtracted and a loopback of the output for accumulation operat ions (using an enable).

I won't be feeding any negative numbers into the multiplier, so it doesn't matter, or does it??? If I multiply 8000h by 8000h with sign extension to the 32 bit register the only difference in the result is the msb which is a bit that would be ignored in the result. In this design the inputs are Q

1.17 so the result will be Q2.34. The interesting bits are Q1.17 working f rom the next to msb down. The msb and 17 lsbs are dropped to produce the Q 1.17 output. But looking at an example of multiplying -1 x -1 I can see th at would turn out differently it is considered signed or unsigned.

I remember coding a shift and add multiplier once and that had issues with a signed multiplier. So for negative multipliers I just complemented the m ultiplier to be a positive number and subtracted all the partial products o r complemented the result or something similar. I dug into the code for si mulating the DSP units and it appears they provide controls to indicate if each input is signed or unsigned. In the simulation they double with word width going into the multiplier, sign extending if signed, then pick the 36 lsbs for the result. This seems to work for signed values using the same hardware as for unsigned.

e read as 17 bit integers from 0 to 167772 (so a bit larger than 2^17). An offset is subtracted on all of them with different scale factors. Some are simple and used directly. Others must be processed a bit more by factoring in other inputs for scale correction. One is used directly but also integra ted over a period of time for another quantity. Some values need to be comp ared to limits.

You need to define the question better. What do you consider to be "signif icant"? We are using a sigma delta converter that will average the input o ver 167772 samples, so that as a max value. How many bits are "significant " I can't say yet. We haven't tested the circuit. But the process is doin g a lot of averaging and the "noise" that people talk about is mostly... in the noise when you filter over such a long period. I think issues with no nidealities in the digital output driving the analog element will be the li miting factor rather than noise. We actually don't need a lot of bits for these measurements, but with a 33 MHz clock rate and a 200 Hz sample rate y ou get 17.3 bits of resolution even if not the accuracy. I have no reason to toss any accuracy in the math. Some of the calculations will require di vision and at one point we were looking at a sensor that required a square root. Turns out a square root in the math messes up the resolution at the low end kinda like the inverse of u-law compression. It took me forever to convince the people who have spent months designing that flow sensor it wo uld not work well. Rather than them proving it would work, I had to prove it wouldn't. Sometimes people are idiots.

I might do the division in a lookup table by multiplying by the inverse. T he trouble with that is the poor accuracy when the value is large and the i nverse is small. But then that is simply the natural result of the divisio n, no? Not sure I will actually have that problem. I need to plan out the calculations better.

format. Any inputs that are not already close to a value that would be trea ted as ~1.0 can be multiplied to "normalize" the working value. At the end of calculations the appropriate scale factor can be used to retrieve the ac tual value each quantity.

ill require adjustment of the coefficients. Others are more straight forwar d with simple linear expressions.

there are any pitfalls. I haven't done much with fixed point arithmetic. In computing the quadratic correction it seems like a lot of data will be pot entially lost because the coefficient is small. I can square the variable f irst which will lose significant bits if it is small or multiply the variab le by the coefficient first which will also lose significant bits. I expect I may need to add a shifter to select just the right bits on each multiply rather than always picking off the msbs. I guess I should do the math to s ee what the new coefficient will be. I guess if the variable is normalized from 100 to 1.9 for example, the x^2 coefficient should be multiplied by 10 ,000 and the x coefficient should be multiplied by 100. Hmmm, or maybe the x^2 coefficient should be multiplied by 100 and the x coefficient not multi plied at all. I guess I should push some values around in a spread sheet to see what gives

--

Rick C. 

+ Get 1,000 miles of free Supercharging 
+ Tesla referral code - https://ts.la/richard11209

The classical solution to signed multiply in 2's complement arithmetic is Booth's algorithm (Google for it).

--

-TV

With an 18 x 18 bit multiplier, you can multiply say 130000 by 130000 and get a correct result on both on a signed as well as unsigned multiplier.

If you try to multiply 140000 by 140000 you will get the correct result with an unsigned multiplier, however a signed multiplier would give an incorrect result. A signed multiplier would interpret 140000 as a small negative number and produce a small positive result.

Anyway, since you have 54 bit add/sub, why not do all arithmetic as 32 or 54 bit internal representation. That way you do not have to worry so much for overflows.

With 18 x 18 bit multiply, you can easily make 36x36=72 bit multiply with four multiplies, adds and shifts with unsigned multiply instruction. If the multiplier is signed, you could easily make a

34x34 bit multiply, still sufficient for 32 bit arithmetic.

Many RISC processors (e.g. Alpha) doesn't even have a division instruction just an inverse instruction. You may have to "normalize" the argument and then "demoralized" the result.

Square root is not bad. You may have to norm/denorm and use a 4th degree polynomial for 32 bits or 6 degree polynomial for 54 bits accuracy.

ith a signed multiplier. So for negative multipliers I just complemented th e multiplier to be a positive number and subtracted all the partial product s or complemented the result or something similar. I dug into the code for simulating the DSP units and it appears they provide controls to indicate i f each input is signed or unsigned. In the simulation they double with word width going into the multiplier, sign extending if signed, then pick the 3

6 lsbs for the result. This seems to work for signed values using the same hardware as for unsigned.

Yes, I am aware of Booth's, but that is not responsive to the issue. I'm n ot crafting a multiplier out of gates. I'm using one already built in the chip along with an accumulator, etc.

I think I've got a handle on it now. There are controls ASIGN and BSIGN wh ich I only saw as controlling a sign extension which I thought was at the p oint of the output of the multiplier feeding the accumulator. But this is at the input to the multiplier where it is doubling the width of the inputs so the resulting product has the correct answer in the 36 lsbs regardless of whether the inputs are signed or not. You just have to set the control inputs to match your data.

So I think I'm ok. I just need to verify this in simulation.

--

Rick C. 

-- Get 1,000 miles of free Supercharging 
-- Tesla referral code - https://ts.la/richard11209

"Multiply by reciprocal" is a very common way of doing division. It is particularly popular if you have several numbers to be divided by the same divisor, or if the divisor is a fixed known value. You need some care to get the scaling right, and to get the LSB's precisely correct, but it is entirely doable.

A lookup table for reciprocals is going to get impractical quite quickly for large ranges. Certainly it would take up a lot more space in an FPGA than putting in a Cortex M1 or RISC-V soft processor and doing the sane thing - implement your maths in software.

If you would like to participate, please let me know and I will connect you with the project lead. Then you can discuss the use of the MCU with him.

Not sure why you think the reciprocal would be so cumbersome. The reality is the values requires are all relatively close to 1.0, so I think it may b e fairly effective. This system is not doing general arbitrary math, it is doing a well defined set of calculations. So restrictions on range are en tirely realistic.

--

Rick C. 

-+ Get 1,000 miles of free Supercharging 
-+ Tesla referral code - https://ts.la/richard11209

No, thank you. But if you, or anyone else in the project, want to talk about MCU's (or soft processors, which was what I suggested) here then I'm happy to join in.

From what I have heard of this project (from your posts here and in other groups), it sounds like you may have spend an extraordinary amount of time trying to make things work with an FPGA alone where other devices would have made the job far easier. Obviously I am not privy to the details - I don't know if you have spent months working on things or merely a few hours spread out over months. And I don't know the budget balances between development costs and production costs. Nor do I know how much influence you have in the decision processes, nor how fixed the designs are at this stage. All I can say is how /I/ would handle things, or recommend other engineers to handle things, given a similar situation as well as I can surmise from your posts.

Different technologies have their strengths and weaknesses. There are times when an FPGA is clearly better, times when an MCU is clearly better, times when either will do just as well, and times where one can be made to work even if it is not ideal for the task. It is important for you to know where you stand here.

I did not describe reciprocal method as "cumbersome". You simply need to be careful with the details to get things accurate - it's very easy to be a bit off in the lowest bits of the result, and it's very easy to have bad behaviour in corner cases. And a lookup table might be fine if there are only a small number of possible divisors, but if it is needed for a whole 17-bit range, that's 128K entries of 34 bits each.

A restricted range, as you describe, certainly helps here. It means you don't need the whole 128K, and you can have less than 34 bits on each entry while covering the accuracy you need. Only you can figure out how big the table must be, and whether it is affordable or not.

If the alternative is to calculate the reciprocal using an iterative process - it can be done with each cycle doubling the number of bits, giving perhaps 5 cycles.

For 17 bit numbers, this is probably not worth the bother. After all, a straight-forward long-division in base 2 will give you the answer in 17 cycles.

I solved the problem of fixed point math being a PITA by changing to floati ng point which is easier in some ways even if a bit of a bother in others. Multiplies and divides only need to be handled between numbers in the ran ge of 1.0 to 1.999... Turns out the divide ends up being very easy. A ta ble lookup gets around 10 bits of accuracy and one iteration of the Newton- Raphson algorithm gives the full 18 bits the basic hardware is capable of a nd more than is needed for the calculations. Adds/subtractions are a bit m ore work requiring denormalization before the sum and renormalization after . In order to prevent having to deal with negative numbers the two addend s are ordered so a subtraction does not result in a negative mantissa.

Once the details are worked out floating point is not hard at all and lends itself to an easy solution to the divide problem as well as the tracking o f scale factor in fixed point math. Someone had suggested that a 32.32 for mat fixed point would do the job without floating point, but it would requi re a lot more hardware resources and still not work for every calculation t hat might be required. One of the calcs involved squaring a value then app lying a coefficient with a 10^-6 range. I suppose that could be done by ta king the square root of the coefficient, but it's just easier to not have t o worry with how many significant bits are left at the end. With floating point the main worry is the small result from subtracting large numbers and I will be able to identify those ahead of time.

--

Rick C. 

++ Get 1,000 miles of free Supercharging 
++ Tesla referral code - https://ts.la/richard11209

Floating point makes multiplies and divides easier (ignoring NaNs and other complications), but addition and subtraction harder.

I still can't help feeling you are over-complicating things by your approach, and that this should all be doable by a few lines of code (whether in an HDL or in a software HLL), or by ready-made components. You are not the first person to do a division in an FPGA.

But I get the impression that you are restrained by certain requirements, and whether or not they are logical (I've seen projects that ban "software" for "reliability reasons" but are quite happy with FPGA code).

Anyway, it's nice to hear you've got it under control.

But not appreciably so. The basic architecture is a MAC where the multipli er serves dual duty as a multiplier and as a shifter. So normalization and denormalization are trivial. First a test is done to see which is to be d enormalized and the denormalization is done in the same cycle with the add/ subtract. So three clock cycles compared to two for the multiply. No mis takes in tracking the scaling factors!

You seem to be contradicting yourself. Is it just a a few lines of code or is it a big hassle?

Dividing by coding A But I get the impression that you are restrained by certain

Not your problem really. So why dwell on it?

Indeed! I appreciate the support.

--

Rick C. 

--- Get 1,000 miles of free Supercharging 
--- Tesla referral code - https://ts.la/richard11209

What sort of hardware was produced for integer operations? When you say in teger, do you mean literally integer data type as in VHDL, or do you mean i nteger interpretation of a array of binary signals like signed/unsigned or the equivalent in Verilog? If I don't use floating point, I would need to use fixed point. I've not worked with the fixed point library in VHDL and didn't want to climb the learning curve. So I'm expecting to plan it all m anually.

Float to fixed is pretty straightforward. It's just a shifter to align the mantissa according to the value in the exponent and forming the 2's comple ment according to the sign bit. That is one clock cycle using the DSP mul tiplier. Think of it as a denormalize operation in prep for an add in floa ting point. The int to float is similar with the setting of the exponent. That's essentially a normalize operation and uses the same hardware.

Since I require similar operations on multiple data it makes sense to have an ALU that can be controlled to process data sequentially rather than dedi cating logic to various data flows. Was your application similar or did yo u have high data rates that needed dedicated hardware for a given data path ?

--

Rick C. 

--+ Get 1,000 miles of free Supercharging 
--+ Tesla referral code - https://ts.la/richard11209

Yes, the required shift count an be obtained from the exponent.

The shift count is the difference in exponents.

How do you determine the required shift count ?

One way is to use some dedicated hardware that determines in which bit position is the most significant "1" bit and then shift left by that amount.

The other method is to shift the integer one position to the left at a time into carry. If the carry bit is 1, you have found the (hidden bit) normalized value and the process completes. However, if the carry bit was "0" start over in a loop by shifting one more bit position. The loop must terminate if the value was all zeroes.

Shifting one bit a time in a loop is time consuming for large integers such as 64 bit integers (up to 63 cycles). This can be speeded up by examining e.g. a byte (8 bits) at a time starting from the left. As long as the byte is 0x00, continue looping. When the first non-zero byte is detect, find out which is the first bit set by shifting into carry. This reduces the cycle count to 7+7=14 cycles.

On an 8 bit processor, large (multiple of 8 bit) shifts can be implemented with byte moves and only the last 1-7 position needs to be implemented with actual shifts. If both the integer as well as the float mantissa uses 2's complement then you need to change the logic slightly for negative values, i.e. continue looping as long as the carry bit is "1" or when the byte is

0xFF. If the float uses sign + magnitude representation, better do the conversion to unsigned prior to the shifts,

On Tuesday, January 19, 2021 at 3:44:32 AM UTC-5, snipped-for-privacy@downunder.com wr ote:

he mantissa according to the value in the exponent and forming the 2's comp lement according to the sign bit. That is one clock cycle using the DSP mul tiplier.

int.

entially a normalize operation and uses the same hardware.

In this case it's not hard. The shifting is being done by a multiplier, so the logic is a bit less complex than a priority encoder, but similar. The msb of the integer is used to set the multiplier value. For normalizing t he integer there is a reverse correspondence in bit position. Once an outp ut bit is selected, the other lsbs are ignored. An older Altera part had a chain of AND gates they used for carry that was perfect for this sort of o peration with the proper polarity. This logic is required for every addition renormalization, not just integer to float conversion.

Neither use 2's complement. The integer values are all positive numbers an d I don't recall seeing a floating point format that uses 2's complement. If you use sign magnitude and use a biased exponent between the sign bit an d the mantissa, a standard arithmetic subtract on the full word can be used to compare floats. That's too useful to toss out the window by using 2's complement.

--

Rick C. 

-+- Get 1,000 miles of free Supercharging 
-+- Tesla referral code - https://ts.la/richard11209

The input and output data types were std_logic_vector so unsigned division of bits interpreted as integers. Unfortunately I don't have access to the code any more. This was part of converting some sensor manufacturer's awful reference C code into VHDL to convert raw sensor values to real ones. The C code used 32-bit signed and unsigned integers and while it was long, it was straightforward to do in VHDL.

I didn't experience much in the way of learning curve with the sfixed types even though I hadn't used them before. A few minutes browsing through Ashenden. But then that was only for a PID controller which is after all a pretty simple thing and I didn't have to be overly concerned about accuracy.

Now that would mean a learning curve for me although I remember I did a floating point multiplier as student over 20 years ago. Pity I don't think I have the VHDL code from back then any more.

It was similar, there were three sensors which all shared the single divider and other calculations. I was pretty relaxed about the use of HW multipliers since I had plenty. Just not so many I could've had 3x the number used.

Data rate was slow, I only read the sensors at something like 2 Hz. No rush to get from the raw data to final data either but that took maybe

20-30 50ns cycles per sensor.