floating point to fixed point conversion-in implementation of navigation system algorithm

On 2/14/2012 2:47 PM, glen herrmannsfeldt wrote:

   ...


> When the uncertainty does not scale with the quantity being
> measured, fixed point of sufficient precision, is often a
> better choice. According to Knuth, two types of calculations
> should always be done in fixed point: financial and typesetting.
> (He wrote that while working on his TeX typesetting system.)
>
> He had an example where they were working with a typesetter that
> they were told printed at 5333dpi, but the printed output was
> visibly wrong. When they later found that it was 5333.3333...
> then everthing came out right.

At RCA Labs, we had Gerber plotters serial numbers 1 and 2 working very 
well with floating point until they installed a new computer. (The 
original worked in BCD, the replacement in binary.) We were down for a 
long time, until we completely redid the program, trig and all, in fixed 
point. I haven't really trusted floating point since. :-)

   ...

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Tim Wescott <tim@seemywebsite.com> wrote:

(snip, I wrote)
>> The positioning accuracy of GPS doesn't depend on how far you are going,
>> but many measurement systems do. In many cases the uncertainty scales
>> with the quantity being measured.

(snip)
>> As for global positioning, I believe that the uncertainty in GPS is
>> pretty much independent of the distance being measured.

> The problem under review is a navigation system, which means GPS + 
> inertial measurements.

> The conceptually simplest way to represent positions in this circumstance 
> is in earth-centered, earth-fixed coordinates; when you do that, you end 
> up with the distance between you and the the center of the earth _all the 
> time_.  So your dynamic range immediately becomes something like +/-6.4 
> million meters in any of your three position variables (assuming you want 
> your algorithm to work anywhere on earth), vs. whatever accuracy you want 
> to achieve.  So if you're trying for one-meter accuracy and trying to set 
> quantization noise to 1/10th your accuracy, then you're up to needing 26 
> bits right there.

I am not at all against supplying enough bits. Fixed point could be
done with 64 or 96 or 128 bits. 

I will guess that with some processors and some algorithms
that 128 bit fixed point is faster than 64 bit floating point.

GPS has an uncertainty independent of the number of bits that
you use in the calculation. But say your round your 26 bits
up to 32, and then allow for the fact that you might need to
square that sometimes, so 64 bits. Note also that GPS is useless
for measurements of Gm or Tm, way outside the orbit radius.

From http://en.wikipedia.org/wiki/Global_Positioning_System it
seems that the satellite orbit is about 20Mm, and the system
is supposed to allow for 20m positioning resolution.

> Granted, you can make an approximation around any one spot on earth (the 
> dean's office in your university, or better yet your project advisor) and 
> significantly simplify the algorithm -- but you do so at the cost of 
> making it only work in the vicinity of that spot.

Seems to me that 32 bit distances, and 64 bits for intermediate
calculations might be enough. There is a lot of detail on how to
do the calculations on the above site, and ones linked from it.

Now, compare a 30cm silicon wafer to the uncertainty in the silicon
lattice constant of about 10am (attometer), or about 16 orders
of magnitude for about 50 bits.

For what can be done with an accurately known silicon lattice
constant, see: http://www.acpo.csiro.au/avogadro.htm

-- glen

On Tue, 14 Feb 2012 22:33:37 +0000, glen herrmannsfeldt wrote:

> Tim Wescott <tim@seemywebsite.com> wrote:
> 
> (snip, I wrote)
>>> The positioning accuracy of GPS doesn't depend on how far you are
>>> going, but many measurement systems do. In many cases the uncertainty
>>> scales with the quantity being measured.
> 
> (snip)
>>> As for global positioning, I believe that the uncertainty in GPS is
>>> pretty much independent of the distance being measured.
> 
>> The problem under review is a navigation system, which means GPS +
>> inertial measurements.
> 
>> The conceptually simplest way to represent positions in this
>> circumstance is in earth-centered, earth-fixed coordinates; when you do
>> that, you end up with the distance between you and the the center of
>> the earth _all the time_.  So your dynamic range immediately becomes
>> something like +/-6.4 million meters in any of your three position
>> variables (assuming you want your algorithm to work anywhere on earth),
>> vs. whatever accuracy you want to achieve.  So if you're trying for
>> one-meter accuracy and trying to set quantization noise to 1/10th your
>> accuracy, then you're up to needing 26 bits right there.
> 
> I am not at all against supplying enough bits. Fixed point could be done
> with 64 or 96 or 128 bits.
> 
> I will guess that with some processors and some algorithms that 128 bit
> fixed point is faster than 64 bit floating point.
> 
> GPS has an uncertainty independent of the number of bits that you use in
> the calculation. But say your round your 26 bits up to 32, and then
> allow for the fact that you might need to square that sometimes, so 64
> bits. Note also that GPS is useless for measurements of Gm or Tm, way
> outside the orbit radius.
> 
> From http://en.wikipedia.org/wiki/Global_Positioning_System it seems
> that the satellite orbit is about 20Mm, and the system is supposed to
> allow for 20m positioning resolution.
> 
>> Granted, you can make an approximation around any one spot on earth
>> (the dean's office in your university, or better yet your project
>> advisor) and significantly simplify the algorithm -- but you do so at
>> the cost of making it only work in the vicinity of that spot.
> 
> Seems to me that 32 bit distances, and 64 bits for intermediate
> calculations might be enough. There is a lot of detail on how to do the
> calculations on the above site, and ones linked from it.

Regular old GPS, by itself, isn't super precise, yes.  But bolt a GPS 
receiver to a big rock that doesn't move and let it accumulate for a 
while, and it's much more accurate.  Bolt a GPS receiver to an IMU that 
gives readings just as good as the rock does (i.e., an IMU that's 
infinitely good) and you'll be able to move around and get readings that 
are just as good as you got from the rock, and move around.

So you cannot judge from GPS precisions alone how precise a measurement 
can be when you have an integrated nav solution.

-- 
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com

Tim Wescott <tim@seemywebsite.please> wrote:

(snip, I wrote)
>> From http://en.wikipedia.org/wiki/Global_Positioning_System it seems
>> that the satellite orbit is about 20Mm, and the system is supposed to
>> allow for 20m positioning resolution.

(snip)
> Regular old GPS, by itself, isn't super precise, yes.  But bolt a GPS 
> receiver to a big rock that doesn't move and let it accumulate for a 
> while, and it's much more accurate.  Bolt a GPS receiver to an IMU that 
> gives readings just as good as the rock does (i.e., an IMU that's 
> infinitely good) and you'll be able to move around and get readings that 
> are just as good as you got from the rock, and move around.

> So you cannot judge from GPS precisions alone how precise a measurement 
> can be when you have an integrated nav solution.

Now it is back, and I don't remember if it is this thread or
a different one, about systematic error and random error.

Random error will eventually average out, but systematic error won't.

I don't know GPS well enough to say, but I am not completely sure
that there are no possible systematic errors, either short or
long term.

There is a whole wikipedia page:

http://en.wikipedia.org/wiki/Error_analysis_for_the_Global_Positioning_System

on GPS errors. Some not so obvious, such as ionosphere dispersion,
humidity, ordinary and gravitational time dilation. One that is on the
GPS page, and not the one above, is the variability of solar radiation
pressure on the satellites.

Before Selective Availability was turned off, differential GPS
was used to get more accurate positions. At some point, the
US government was running their own differential GPS correction
signals, at which point it became obvious that turning off SA
was a good idea.

It seems that you can still use differential GPS to correct for
ionospheric and humidity, the closer the second receiver, the
better correction. If you don't correct them, I believe that
they are sources of systematic error. (Humidity doesn't
average out to zero.)

I was recently reading about the discovery of cosmic rays.
It took some time, as there were some systematic errors that
had to be tracked down and understood. Among others, there
is a latitude dependence that they didn't know about.

-- glen

glen herrmannsfeldt wrote:
> Stefan Reuther <stefan.news@arcor.de> wrote:
>>I've not done navigation on a DSP yet, just audio, but from what I
>>gather there are algorithms that need the dynamic range of floating
>>point. Things like the computation of a geo-distance, which could be
>>halfway around the globe or just the next door. My company has done
>>navigation on a Blackfin, with emulated floating point.
> 
> It isn't the dynamic range that matters, it is the range of
> the uncertainty. For more dynamic range, you can add more bits
> to either one.
> 
> The positioning accuracy of GPS doesn't depend on how far
> you are going, but many measurement systems do. In many cases
> the uncertainty scales with the quantity being measured.

I was thinking actual navigation, not GPS. A navigation system is given
the order to go from A to B. How far are A and B apart? If it's 2000 km,
it'd should better look at the motorway grid; if it's just 2 km, it'll
suffice to open the map for the current city. And when giving driving
instructions, it'll have to decide whether the next turn is in 100 km or
in 25 m. And if it's 75 m, the computation better be pretty exact for
precise timing of the audio.

Doing that in fixed point would be pretty hairy. (But not impossible of
course.) But route calculation does not burn so many MIPS in
computations, but many more in decompression, decisionmaking, etc., so
using emulated floating point does not lose you as much as using
emulated floating point for processing audio.


  Stefan

Stefan Reuther <stefan.news@arcor.de> wrote:

(snip, I wrote)
>> It isn't the dynamic range that matters, it is the range of
>> the uncertainty. For more dynamic range, you can add more bits
>> to either one.
 
(snip on GPS)

> I was thinking actual navigation, not GPS. A navigation system is given
> the order to go from A to B. How far are A and B apart? If it's 2000 km,
> it'd should better look at the motorway grid; if it's just 2 km, it'll
> suffice to open the map for the current city. And when giving driving
> instructions, it'll have to decide whether the next turn is in 100 km or
> in 25 m. And if it's 75 m, the computation better be pretty exact for
> precise timing of the audio.

But the uncertainty is about the size of the car, if you are going
one block or across the country. As someone else noted, quantities
the size of the earth go into the calculation in either case.
(I suppose a little better if you are walking, but then you
don't usually walk across the country.)

> Doing that in fixed point would be pretty hairy. (But not 
> impossible of course.) But route calculation does not burn 
> so many MIPS in computations, but many more in decompression, 
> decisionmaking, etc., so using emulated floating point does 
> not lose you as much as using emulated floating point 
> for processing audio.

Now, if you want a system, that can navigate across a silicon
wafer to fm resolution, and across the solar system to Mm resolution,
then I recommend floating point. 

(Note that fm, 1e-15m, is named the Fermi, but is also a
femtometer. About the size of an atomic nucleus, and so 
commonly used in nuclear physics.)

-- glen

Stefan Reuther wrote:

> glen herrmannsfeldt wrote:
> 
>>Stefan Reuther <stefan.news@arcor.de> wrote:
>>
>>>I've not done navigation on a DSP yet, just audio, but from what I
>>>gather there are algorithms that need the dynamic range of floating
>>>point. Things like the computation of a geo-distance, which could be
>>>halfway around the globe or just the next door. My company has done
>>>navigation on a Blackfin, with emulated floating point.
>>
>>It isn't the dynamic range that matters, it is the range of
>>the uncertainty. For more dynamic range, you can add more bits
>>to either one.
>>
>>The positioning accuracy of GPS doesn't depend on how far
>>you are going, but many measurement systems do. In many cases
>>the uncertainty scales with the quantity being measured.
> 
> 
> I was thinking actual navigation, not GPS. A navigation system is given
> the order to go from A to B. How far are A and B apart? If it's 2000 km,
> it'd should better look at the motorway grid; if it's just 2 km, it'll
> suffice to open the map for the current city. And when giving driving
> instructions, it'll have to decide whether the next turn is in 100 km or
> in 25 m. And if it's 75 m, the computation better be pretty exact for
> precise timing of the audio.
> Doing that in fixed point would be pretty hairy. (But not impossible of
> course.)

I've done nav. calculations in the fixed point. It is not very difficult 
as any reasonable distance calculation on Earth fits into 32 bit fixed 
math.

> But route calculation does not burn so many MIPS in
> computations, but many more in decompression, decisionmaking, etc., so
> using emulated floating point does not lose you as much as using
> emulated floating point for processing audio.

On Blackfin, emulated 32 bit float is somewhat 6 times slower then 32 
bit fixed; which means float could be enough fast for audio.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

On Feb 15, 2:11&#4294967295;pm, Vladimir Vassilevsky <nos...@nowhere.com> wrote:
>
> On Blackfin, emulated 32 bit float is somewhat 6 times slower then 32
> bit fixed; which means float could be enough fast for audio.
>

depends on what the audio processing is, Vlad.

r b-j

On 2/13/2012 9:38 AM, divya_divee wrote:
> Hi,
>     I have a floating point c code to implement a navigation system
> algorithm.

What is the operating arena for the "navigation system algorithm"?
Are you working on land?  Sea?  Airborn?  Planet-wide?  Some *other*
planet?  Deep space?  etc.

Or, just providing a scheme whereby an automaton gets around the
factory floor/lot?

What are the ranges of parameters you will encounter and resolutions
required?

> In order to implement it in the 64x+ fixed point DSP processor, i need to
> have the code in fixed point. I learnt that there are few processor
> specific  IQmath libraries aiding this purpose. Is it practical to write
> the code using these libraries or should i manually write codes for each
> operation by scaling the inputs for each line of the code, in which case i
> have to create look up table for the trigonometric functions etc which is a
> harder process to begin with..

Ask yourself the above.  Then, put *numbers* on each of these and
look at what the computations you are required to perform (dictated
by the geometry of your system) require *of* those numbers.  Look
at where your computations will fall into the mud and where they
are likely to explode.  And, if there are alternative ways of
expressing/encoding those values to survive some of those
computations (even if you have to do this "conditionally".

Without constraints on your problem domain, its kinda hard to
suggest how much you can get away with in your range of *solutions*.

Hello Divya,
as the C64+ is a rather fast DSP I recommend to include the floating point
libraries first and check the performance.

If too slow, you should translate line by line into fixed point. Therefore,
examine the range before and after each mathematical operation. Check the
maximum possible values before each operation and scale if needed. Then
check if the minimum possible values have enough bits to represent the
signal. You may use double precision if needed.

If even too slow after that, code in assembly language!

BR
Alois Huber