Fixed-point Math help - Page 2

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
Re: Fixed-point Math help

Quoted text here. Click to load it
group:
Quoted text here. Click to load it
algorithms in

try http://www.wwnet.net/~stevelim/fixed.html

basic idea is to look at the maximum/minium values of your floating
point inputs, and the maximum/minimum values of each computation, and
move the "decimal" point as needed for each computation to prevent
overflow AND  preserve the maximum resolution. If your using a large
enough date type (32 bits) you may be able to get away with keeping the
"decimal" point fixed throughout the calculations. If you are using a
16 bit processor, many calculations can be done with 16 bits, stuff
like integrations you will need 32 bits.


Re: Fixed-point Math help

Quoted text here. Click to load it

I rarely need floating point either. Someone else has already raised the
issue of the speed hit when you do a soft floating point calculation on
hardware without floating point support. However, if you really do need to
do it then take a look at some Forth floating point code. That is usually
quite good as a basis (mind you, I am already part way there as I use Forth
for most of my systems anyway. Still, the techniques should be
translatable).

In my current project I am using 48bit intermediaries on a 16 bit machine
in order to avoid delving into floating point calculations. It is still a
speed win and maintains the accuracy I need in the result.

--
********************************************************************
We've slightly trimmed the long signature. Click to see the full one.
Re: Fixed-point Math help
I'm not sure how good forth floating point code is, but for the
floating point routines I am using on a 16 DSP fixed point processor,
this is what I'm getting (clock cycles) for fixed vs floating point
math

Addition: 16 bit Fixed 1 cycle, Single Precision Float 122 Cycles
Subtraction: 1 cycle fixed , 124 cycles float
Multiplication 1 cycle fixed, 109 cycles float
Division 16 cycles fixed, 361 cycles float

this is custom floating point assembly code optimized for the processor
from the manufacturer. So I'm basically getting over 100x performance
boost when using fixed point, really hard to throw away that
improvement, though I still use floating point for non critical and
debug purposes.


Re: Fixed-point Math help
On 13 Dec 2004 12:36:47 -0800, "bungalow_steve"


Quoted text here. Click to load it

While I agree that doing floating point addition and subtraction in
software can be quite time consuming due to the denormalisation and
normalisation phases, I really do not understand, how the
multiplication can take that long. Basically you just multiply the
mantissa and add the exponents.

This should not take too long, unless the mantissa size is larger than
the integer register size. On a 16 bit integer processor, it would be
sensible to use a floating point format with 8 bit exponent and 16 bit
mantissa.

Paul


Re: Fixed-point Math help

Quoted text here. Click to load it

Those sort of numbers are almost certainly for IEEE-conformant floating
point emulation.  So you have full subroutine call overhead, packing and
unpacking the 32-bit (or 64-bit) IEEE format on a 16-bit DSP that wasn't
necessarily designed for such operations, and then taking care of the
special cases (denorms, NaNs and Infs).  That would be likely to be very
ugly on most 16-bit fixed point DSPs.

I don't think that the C standard stipulates IEEE arithmetic yet,
does it?  Many users probably expect it, though.

--
Andrew


Re: Fixed-point Math help

Quoted text here. Click to load it
than
bit

The floating point functions are IEEE-754 compliant (32 bit not 64
bit), with signed zero, signed infinity, NaN (Not a Number) and
denormal support and operated in the "round to nearest" mode. I
supposed if I rolled my own floating point format as you suggest the
multiply would be much faster.


Re: Fixed-point Math help
Quoted text here. Click to load it
... snip ...
Quoted text here. Click to load it

Doesn't Forth have some other form for handling many of these
problems, something like rational fractions is jiggling my memory.

--
Chuck F ( snipped-for-privacy@yahoo.com) ( snipped-for-privacy@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
We've slightly trimmed the long signature. Click to see the full one.
Re: Fixed-point Math help

Quoted text here. Click to load it

That is the thing about Forth. If you need it you either find it in the
Forth Scientific Library or, more likely, you end up rolling your own. My
48bit intermediary is quite necessary to maintain the accuracy up until the
point I do the cube root. It is all back to 16 bits then.

--
********************************************************************
We've slightly trimmed the long signature. Click to see the full one.
Re: Fixed-point Math help

Quoted text here. Click to load it

No one has directly addressed this, I think.  Probably because there is a lot of
truth in the idea of "integer ADC --> processing --> integer DAC" means you
shouldn't insert FP into the "processing" block if you can avoid it.  Most
applications just don't have the wide dynamic range that floating point supports
and there are "gotchas" with using floating point that require care to use well.
And why add it, if everything coming in is integer and everything going out is
integer?  Just stay in integer... if you can.

But if you are really interested in learning how, Analog Devices has a book on
implementing floating point with their ADSP-21xx processors that I believe may
be able to be downloaded.  You can also examine the floating point formats
commonly used, along with a tedious description about special cases, in Intel's
documentation on their processors, available from Intel's web site.  Some of the
older DEC manuals included details on implementing floating point, too.  (In the
earlier days, teaching programmers about floating point details was important as
it was a required skill for everyday programmers.  That's far less true, today.)

I don't have a convenient web site in mind, but Tim Wescott's suggestion of
using google is probably a good one.  Use "floating point" and "normalization"
and "denormalization" and "exponent" and "mantissa" and "hidden bit" and perhaps
the four common operations to help track something down.  This is more your 'do
diligence,' until you've done this yourself and can explain why it's not getting
you there.

The basic idea is that you have an exponent (signed, twos-complement) and an
unsigned mantissa (with a possible hidden bit for non-zero values) and a
separate sign bit.  These can be packed in any format you like or is convenient
to you.  Each of these is an integer.  There is no explicit radix (decimal)
point, but it is usually assumed for the mantissa at any convenient place and
the exponent then adjusts this, left or right, for - or + values of the
exponent.  The mantissa is usually stored 'normalized' which means that it is
shifted until the leading bit is always a '1' (which is always possible unless
the value is actually zero, but that is easily detected.)  Some formats simply
throw away the leading bit, because it is always '1', and put it back when
needed in order to add one apparent bit of precision.

The rest is just software.  Try a paper exercise and see where it takes you.
That's a good start, if you plan to try and implement something yourself.
Another choice would be to examine library code -- again, search google.

Jon

Re: Fixed-point Math help
Quoted text here. Click to load it


If you're doing floating point on a fixed point DSP, for dynamic range
reasons, and you have no particular reason to comply with IEEE floating
point formats, why would you bother with an unsigned mantissa or implied
leading bit?  Is it because you knew that you absolutely needed that extra
bit of precision?  One can go a long way with a simple two-word format:
mantissa and exponent, with nothing special about the mantissa, so that
the chip's normal signed multiplies and adds work fine.  (I never used it,
but I believe that the Motorola C compiler for the 56000 series used this
format.  At least, one of the debuggers knew how to display memory blocks
in that format...)

Many (most?) DSP processors have "normalize" or "count leading
zeros/leading ones" instructions too, which makes the
normalization/alignment process a bit of a slam-dunk.

Quoted text here. Click to load it

There are some fairly good introductions on the web (some in pdf, from
memory), but I'm afraid that I don't have them handy.  The suggestions to
google are good ones.

Here are a couple of other random suggestions:

If your need for floating point (for dynamic range reasons) is on the
real-time critical path, so it has to be time/power efficient, you can
often get away with what's known as "block floating point".  That is, a
collection of calculations, (the passes of an FFT, for example) might
usefully share a single exponent.  That doesn't give you quite as even a
dynamic range/precision trade-off as conventional floating point, but it
makes the bulk of the work look more like fixed point, while still having
some of the dynamic range advantage.

One application area that I am familiar with that requires vast dynamic
range is anything that does pattern matching with hidden-markov models (or
similar).  Most of the fixed-point DSP implementations of these algorithms
meet the precision/range trade-off by performing the arithmetic in the log
domain.  This requires log() and exp() functions to get in and out, but
the win can be large if a large amount of processing has to take place in
between. [The use of log arithmetic also helps to explain a virtue of
Viterbi searches, as opposed to forward/backward or the like: additions
are replaced by maximums.]

Hope some of these rambles help.  Or at least offer some more search terms
to help narrow down google's focus.

Cheers,

--
Andrew


Re: Fixed-point Math help
On Wed, 15 Dec 2004 19:44:03 +1100, Andrew Reilly

Quoted text here. Click to load it

Actually, I don't use hidden bit notation, at all.  Everything explicit.  The
mantissas are signed (or unsigned) as needed, and I don't use a separate sign
bit in some other field.  I was talking generally at that point and hinting at
common format standards.

Quoted text here. Click to load it

Yup.  On the ADSP-21xx processors I referenced there is a fully combinatorial
32-bit barrel shifter with the ability to find the leading '1' in a single cycle
and report the required shift.

Jon

Re: Fixed-point Math help
Quoted text here. Click to load it
... snip ...
Quoted text here. Click to load it

You can find a complete example in the Dr. Dobbs Journal archives.
I published a complete system for the 8080 there about 25 years
ago.  It's purpose was to supply dynamic range, and used a 16 bit
significand with an 8 bit exponent.  The result was much faster
than anything else available at the time, because it could all be
done in registers, and in addition was re-entrant.  The system
included i/o procedures, transcendentals, etc. and had
over/underflow detection.  The system underwent minor revisions and
continuous use in the ten years or so since publication, and
processed the majority of tests in a 1000 bed hospital for much
longer.  I.E. it was reliable and accurate.

--
Chuck F ( snipped-for-privacy@yahoo.com) ( snipped-for-privacy@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
We've slightly trimmed the long signature. Click to see the full one.
Re: Fixed-point Math help

Quoted text here. Click to load it

It would be wonderful if that were on the web somewhere or in a .DOC from a site
you have.  Do you have separate rights to it?  Or can you modify it and regain
the right to make it publicly available?

Jon

Re: Fixed-point Math help
Quoted text here. Click to load it

I never gave up any rights - when originally published DDJ did not
pay anything.  When they published their later book of "DDJ for the
year ..." I gave them further permission to reprint.  I lost my
sources some years ago in a disk crash, although I had promulgated
them to some others before then.  Now all I have is a hard copy
listing of the version used in my Pascal system, and possibly
faulty copies typed by a French gentleman in comp.os.cpm.

Whether DDJ has it available in anything other than scans I do not
know.  There is no great demand for 8080 assembly code today,
especially since the Rabbit doesn't even implement the full 8080
instruction set.  I believe one of the critical things it misses is
the XTHL instruction.  So does the 8086, thus making it impossible
to preserve all registers at all times.

Talk in this thread of emulating FP processors seems ridiculous.
The FP processors themselves were attempts to speed up the FP
routines.  Other methods included hardware instructions to ease
justification, multiplication, division, etc.  Some systems even
broke up division by having a dividestep instruction.  For example,
as eventually (not in the DDJ issue) implemented in my system,
16x16 -> 32 multiplication was done by two 8 x 16 -> 24 bit
operations, and a summation.  This was about 50% faster.

If there is any real demand I can put it up for download on my
page, in the form I received it from Arobase.  i.e. totally
unverified.  I do not have facilities for scanning my hard copy.

--
Chuck F ( snipped-for-privacy@yahoo.com) ( snipped-for-privacy@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
We've slightly trimmed the long signature. Click to see the full one.
Re: Fixed-point Math help
 
Quoted text here. Click to load it

I found a lot of older (and some current) medical applications use
floating point BCD for results calculation.  Data was processed
serially a nibble/digit at a time, as in a 4-bit calculator CPU.  

The math-pac was always a home brew and buggy - but then in consulting
all you get to see are other folk's bugs.  Nobody hires a consultant to
come in an fix a success (although if I did government work I am sure
that would change).

I have never had a client give a rational reason for using BCD.
Lots of paranoia, but nothing rational.

--
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
We've slightly trimmed the long signature. Click to see the full one.
Re: Fixed-point Math help
Quoted text here. Click to load it

If I were to guess, I'd say it comes down to
visualization or perhaps mental laziness.
Everyone can make the jump from ten fingers
to a BCD digit.  And not having to write the
conversion routines saves half the work.





Re: Fixed-point Math help
And why add it, if everything coming in is integer and everything
going out is
Quoted text here. Click to load it

The problem is what if you developed/tested all your floating point
control laws code on a pc based simulator (e.g., Matlab/Simulink) and
now want to put that code between an A/D and D/A in an embedded
product. Easier just to drop it into a processor that supports the
identical floating point format as the simulator then to rewrite it in
fixed point math.


Re: Fixed-point Math help
On 15 Dec 2004 08:23:09 -0800, the renowned "bungalow_steve"

Quoted text here. Click to load it

Cheap, fast(easy), good: pick any two.


Best regards,
Spehro Pefhany
--
"it's the network..."                          "The Journey is the reward"
snipped-for-privacy@interlog.com             Info for manufacturers: http://www.trexon.com
We've slightly trimmed the long signature. Click to see the full one.
Re: Fixed-point Math help
Quoted text here. Click to load it
and
in
reward"
Quoted text here. Click to load it
http://www.trexon.com
Quoted text here. Click to load it
http://www.speff.com

I think of it more as a nonrecurring vs recurring expense tradeoff,
rewrite the code in fixed point, save on recurring costs, don't
rewrite, save on non recurring costs. Old business problem.


Re: Fixed-point Math help
Quoted text here. Click to load it

Equivalent to saying to the client "How would you like your
project: late, over budget or buggy?"

--
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
We've slightly trimmed the long signature. Click to see the full one.

Site Timeline