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

Hi, 
   I have a floating point c code to implement a navigation system
algorithm.
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..

Thanks,
Divya

On 2/13/12 11:38 AM, divya_divee wrote:
> Hi,
>     I have a floating point c code to implement a navigation system
> algorithm.
> 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..

i never thought creating a lookup table for a well defined function was 
a hard process.  you can do it in C or MATLAB pretty easily.  but lookup 
tables tak a lot of memory and, of course, have the "granulization 
error" that can be mitigated with linear interpolation or polynomial 
interpolation (like Hermite) of higher order than 1.

but, if you end up dealing with discontinuities of the lookup table with 
smooth polynomials, you might want to evaluate these functions with 
finite order polynomials to begin with.

it depends on how big this navigation system is.  how many lines of 
code, how many different functions and files.  i have converted 
floating-point algs to fixed-point many times before (in the field of 
audio processing), and the biggest problem i have is the numerical 
sloppiness that floating-point sometimes allows one to get away with. 
in fixed-point, you need to know your range of numbers and you need to 
apply the appropriate scaling to put that range of numbers into the 
range of the fixed-point DSP.

all doable.  and it takes time to do it right, and if you do it well, it 
might turn out better and more predictable than the floating-point model 
it was built on.


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

On Mon, 13 Feb 2012 10:38:32 -0600, divya_divee wrote:

> Hi,
>    I have a floating point c code to implement a navigation system
> algorithm.
> 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..

Zeroth: Who the heck makes the "64+" DSP processor?  I should know...  
What's your specific chip?

First, some fixed-point DSP processors aren't too bad at floating point, 
so you may be able to just run the algorithm as-is.

Second, I have some passing familiarity with nav system computations; 
converting one to fixed point ain't gonna be trivial -- particularly if 
you're doing matrix inversions.

Third, many DSP processors have a sine look-up table tucked away in ROM 
somewhere; this at least gives you some of those trig functions.

Forth, there are some tricks to be played in getting other functions, but 
it depends on your chip.  Analog Devices 21xx parts were best at this -- 
they had a wide enough instruction word that you could do a MAC against a 
scalar x^n almost as easily as you could against a vector x[n], which 
made polynomial approximations easy-peasy.

Fifth, nav system algorithms are approximations to begin with, and most 
of them are optimized to get grant money or to get the project done while 
the company still has research money.  I rather suspect that in order to 
attain the overall goal of "make a nav system work with a fixed-point DSP" 
you need to start by designing (or finding) a nav algorithm that is 
tailored not only to fixed-point-ness in general, but possibly even to 
that specific processor.

-- 
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com

Tim Wescott <tim@seemywebsite.com> wrote:

(snip, someone wrote)
>> I have a floating point c code to implement a navigation system
>> algorithm.
>> In order to implement it in the 64x+ fixed point DSP processor, 
>> i need to have the code in fixed point. 

(snip)
> Fifth, nav system algorithms are approximations to begin with, 
> and most of them are optimized to get grant money or to get the 
> project done while the company still has research money.  
> I rather suspect that in order to attain the overall goal of 
> "make a nav system work with a fixed-point DSP" you need to 
> start by designing (or finding) a nav algorithm that is 
> tailored not only to fixed-point-ness in general, but possibly 
> even to that specific processor.

It does seem to me that fixed point, with a sufficient word size,
is likely a better choice. It is rare to need a navagation system
that works from nm to Gm. (That is, nanometers to gigameters.)

Even in floating point, one has to be careful when adding and
subtracting, not to lose most or all of the significant digits.
As you mentioned matrix inversion, (which I snipped), it is very
easy for intermediate steps to lose much of the precision.
The usual answer is to do it in double precision to get single
precision results. If you understand the math, though, keeping
the required precision is likely easier in fixed point.

-- glen

On 2/13/12 3:15 PM, glen herrmannsfeldt wrote:
> Tim Wescott<tim@seemywebsite.com>  wrote:
>
> (snip, someone wrote)
>>> I have a floating point c code to implement a navigation system
>>> algorithm.
>>> In order to implement it in the 64x+ fixed point DSP processor,
>>> i need to have the code in fixed point.
>
> (snip)
>> Fifth, nav system algorithms are approximations to begin with,
>> and most of them are optimized to get grant money or to get the
>> project done while the company still has research money.
>> I rather suspect that in order to attain the overall goal of
>> "make a nav system work with a fixed-point DSP" you need to
>> start by designing (or finding) a nav algorithm that is
>> tailored not only to fixed-point-ness in general, but possibly
>> even to that specific processor.
>
> It does seem to me that fixed point, with a sufficient word size,
> is likely a better choice. It is rare to need a navagation system
> that works from nm to Gm. (That is, nanometers to gigameters.)
>

i didn't consider matrix inversion (or even just Gaussian elimination). 
  you can get really tiny or large numbers in intermediate states doing 
that.

> Even in floating point, one has to be careful when adding and
> subtracting, not to lose most or all of the significant digits.

in audio, that's often the cosine problem, where cos(2*pi*f/Fs) is a 
number so close to 1 (because most of the interesting stuff in happening 
in the middle or bottom few octaves) that all of the information is in 
the difference from 1 which falls off the edge, even for floating point.

> As you mentioned matrix inversion, (which I snipped), it is very
> easy for intermediate steps to lose much of the precision.

so, even for floating point, it's a good idea to remake your equations 
so that the "independent variable" is something in terms of 1-x, if x is 
expected to be close to 1.

> The usual answer is to do it in double precision to get single
> precision results. If you understand the math, though, keeping
> the required precision is likely easier in fixed point.

doing DSP in fixed point sorta imposes a discipline of *really* having 
to understand the alg and all of the intermediate quantities and states, 
so you know how big or small they can get.  doing it in floating point 
sometimes gives one the *illusion* that they need not worry about it.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

robert bristow-johnson <rbj@audioimagination.com> wrote:

(big snip, then I wrote)
>> The usual answer is to do it in double precision to get single
>> precision results. If you understand the math, though, keeping
>> the required precision is likely easier in fixed point.

> doing DSP in fixed point sorta imposes a discipline of *really* having 
> to understand the alg and all of the intermediate quantities and states, 
> so you know how big or small they can get.  doing it in floating point 
> sometimes gives one the *illusion* that they need not worry about it.

And often in other than DSP, too.

Floating point is great for quantities that vary over a large
range, but have a similar relative error, and that are 
mostly mulitplied.

For quantities where absolute error is more important, fixed
point tends to be a better choice, but also when addition
and subtraction are more common than multiply and divide.

-- glen

On Mon, 13 Feb 2012 20:15:28 +0000, glen herrmannsfeldt wrote:

> Tim Wescott <tim@seemywebsite.com> wrote:
> 
> (snip, someone wrote)
>>> I have a floating point c code to implement a navigation system
>>> algorithm.
>>> In order to implement it in the 64x+ fixed point DSP processor, i need
>>> to have the code in fixed point.
> 
> (snip)
>> Fifth, nav system algorithms are approximations to begin with, and most
>> of them are optimized to get grant money or to get the project done
>> while the company still has research money. I rather suspect that in
>> order to attain the overall goal of "make a nav system work with a
>> fixed-point DSP" you need to start by designing (or finding) a nav
>> algorithm that is tailored not only to fixed-point-ness in general, but
>> possibly even to that specific processor.
> 
> It does seem to me that fixed point, with a sufficient word size, is
> likely a better choice. It is rare to need a navagation system that
> works from nm to Gm. (That is, nanometers to gigameters.)
> 
> Even in floating point, one has to be careful when adding and
> subtracting, not to lose most or all of the significant digits. As you
> mentioned matrix inversion, (which I snipped), it is very easy for
> intermediate steps to lose much of the precision. The usual answer is to
> do it in double precision to get single precision results. If you
> understand the math, though, keeping the required precision is likely
> easier in fixed point.
> 
> -- glen

I looked into doing a nav solution all in fixed point.  I backed away 
from it.  It's not that it couldn't be done -- it's just that the 
solution itself was not at all trivial, and trying to add fixed-
pointedness on top of all that would have just been even more pain.

Now, if you had a well-defined nav solution algorithm in hand, and you 
wanted to convert it to fixed point -- that might be doable.  But even 
so, you'd be tasking yourself with doing some fairly heavy-duty linear 
algebraic operations all in fixed point.

Until you've at least worked out the degree of difficulty to implement an 
extended Kalman filter in fixed point (which means you absolutely must 
calculate the covariance matrix on line), I don't think that you're in a 
position to speak wisely about whether it's practical.

-- 
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com

Tim Wescott wrote:
> On Mon, 13 Feb 2012 10:38:32 -0600, divya_divee wrote:
>>   I have a floating point c code to implement a navigation system
>>algorithm.
>>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..
> 
> Zeroth: Who the heck makes the "64+" DSP processor?

Maybe the OP means a "C64+" DSP which comes with some Texas Instruments
SoC's, and I've seen that vague type name in their documents as well. I
prefer saying "I code for a C64". Sounds more retro :-)

> First, some fixed-point DSP processors aren't too bad at floating point, 
> so you may be able to just run the algorithm as-is.
> 
> Second, I have some passing familiarity with nav system computations; 
> converting one to fixed point ain't gonna be trivial -- particularly if 
> you're doing matrix inversions.

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.

> Third, many DSP processors have a sine look-up table tucked away in ROM 
> somewhere; this at least gives you some of those trig functions.

I wonder why people think predefined trig support is so important for
DSP. "Hey, software guy, I have this new DSP for you, which has a CORDIC
coprocessor, which can compute arbitrary sine/cosine in just 10 cycles.
I heard your MP3 decoder has a cosine transform, that must be wonderful
for you!" - "No thanks, all I need is that 64-element array of constants
and circular addressing."


  Stefan

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

(snip)
> 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.

The lattice constant (size of the unit cell of the crystal)
for silicon, according to physics.nist.gov, is 543.1020504pm,
with an uncertainty of 0.0000089pm. About 10 significant
digits, or in binary, about 33 significant bits.

Now, measure the distance from your house to the house next door,
center to center. You would have a hard time even getting two
significant digits. I guarantee you can't measure it with an
uncertainty approaching 0.0000089pm.

There are many cases where small quantities can be measured 
much more accurately, in both absolute and relative terms.

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.

There is currently another thread discussing incoherent and
coherent averaging. If the positions are off by 1 in 16000,
randomly distributed, then it likely won't be visible.
When the errors are not random, as in the case of roundoff,
they can be surprisingly visible. In fixed point, you have
full control over any rounding, but not, usually, in 
floating point. TeX uses fixed point for all calculations 
related to text positioning, floating point for some printed
messages that don't affect the printed output. Positioning
is done with 32 bit signed floating point with 16 bits after
the binary point, with the unit being (1/72.27) inch.

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

-- glen

On Tue, 14 Feb 2012 19:47:02 +0000, glen herrmannsfeldt wrote:

> Stefan Reuther <stefan.news@arcor.de> wrote:
> 
> (snip)
>> 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.
> 
> The lattice constant (size of the unit cell of the crystal) for silicon,
> according to physics.nist.gov, is 543.1020504pm, with an uncertainty of
> 0.0000089pm. About 10 significant digits, or in binary, about 33
> significant bits.
> 
> Now, measure the distance from your house to the house next door, center
> to center. You would have a hard time even getting two significant
> digits. I guarantee you can't measure it with an uncertainty approaching
> 0.0000089pm.
> 
> There are many cases where small quantities can be measured much more
> accurately, in both absolute and relative terms.
> 
> 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.
> 
> There is currently another thread discussing incoherent and coherent
> averaging. If the positions are off by 1 in 16000, randomly distributed,
> then it likely won't be visible. When the errors are not random, as in
> the case of roundoff, they can be surprisingly visible. In fixed point,
> you have full control over any rounding, but not, usually, in floating
> point. TeX uses fixed point for all calculations related to text
> positioning, floating point for some printed messages that don't affect
> the printed output. Positioning is done with 32 bit signed floating
> point with 16 bits after the binary point, with the unit being (1/72.27)
> inch.
> 
> 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.

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.

-- 
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com