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

Re: Fixed-point Math help

group:

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

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.

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

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

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

Andrew

Re: Fixed-point Math help

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

... snip ...

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.

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

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

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

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.

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

Andrew

Re: Fixed-point Math help

On Wed, 15 Dec 2004 19:44:03 +1100, Andrew Reilly

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.

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

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.

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

... snip ...

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.

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

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.

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

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.

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

And why add it, if everything coming in is integer and everything

going out is

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.

going out is

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"

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

Best regards,

Spehro Pefhany

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

"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

and

in

reward"

http://www.trexon.com

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.

#### Site Timeline

- » Reverse current into a lithium battery
- — Next thread in » Embedded Programming

- » EEPROM reading FF's ...
- — Previous thread in » Embedded Programming

- » RabbitWeb and BL2600
- — Newest thread in » Embedded Programming

- » Re: Computer Assisted Fornication
- — The site's Newest Thread. Posted in » Electronics Design

- » Bluetooth headphone repair
- — The site's Last Updated Thread. Posted in » Electronics Repair