Multiplication by a Fixed Point Constant - Embedded.com

Multiplication by a Fixed Point Constant

Multiplication and division is something we take for granted whenworking with desktop computers, but avoid like the plague on embeddeddevices. However it is here to stay and often times we must simply dealwith it.

If the CPU you use does not have native multiply and divide support,any use will likely bring in a library, and all of the overheadimplied. If you step back a bit further and insist on using floatingpoint numbers, the overhead can quickly consume all of the memoryleaving precious little space for the real, “working,'' code.

Luckily, for the most part true floating point math is rarelynecessary, especially in small embedded devices. For these, fixed pointmath is sufficient [1] . Immediately a massive support libraryhas been reduced to only a large one, but even fixed point has itsproblems ” namely overflow. Let us say I need to multiply an number by3.14. Naively, this would be achieved with something like:

x = x * 314 / 100

If x happens to be an 8-bit number, the multiply will overflow and alarger temporary (more data space ) will be required. Luckilythere are numerous ways around this (yes, one could use 157/50, butthe overall problem still remains ).

Often times, a program only needs one or two multiplies. Thecanonical example would be scaling the results from an ADC for display.Say you have an ADC with 10 bit precision which you would like todisplay as a percentage. Before display, you use x = x * 100 / 1023.That could very well be the only time a multiply is required ” so whyincur the overhead of a library for a single use?

The embedded platform I use is based on MicroChip's PIC 16F877. Forthose not familiar, this chip has neither multiply nor divideinstructions, the shift instructions only shift a value one bit, andboth code and data memories are severely limited.

Let us begin with a simple example, integer multiply by 100. Forthose blessed with native support for multiply, and who think thesetechniques do not apply to you, they might. Back in another life, eventhough the processor in use had native multiply, it was often faster toshift + add. Much faster.

To determine the necessary shifts, start by looking at the number inbinary (highest bit on the left):

100: 0 1 1 0 0 1 0 0

Considering each bit the co-efficient of a polynomial results in thefollowing equation:

x = 64x + 32x + 4x

or, using shifts instead:

t0 = x << 6
t1 = x << 5
x = x << 2
x += t0
x += t1

This clearly works but it requires two temporary variables and atotal of 13 shifts. Today I do not have the luxury of multi-bit shiftsand I also cannot afford even the two extra variables!

It is clear that some of the shifts are redundant. Start byfactoring the original equation:

x = 64x + 32x + 4x   = 4 ( 16x + 8x + x )   = 4 ( 8 ( x + 2x ) + x )

which yields the following:

t0 = x
x = x << 1 ; 2x
x += t0 ; x + 2x
x = x << 3 ; 8 ( x + 2x )
x += t0 ; 8 ( x + 2x ) + x
x = x << 2 ; 4 ( 8 ( x + 2x ) +x )

Note only a single temporary is used, and the number of shifts isreduced from 13 to 6.

Now that I have shown the simple multiply by an integer, I willgeneralize this to use fixed point values. For this I am going to usethe constant 1.234. It appears arbitrary and somewhat useless but isactually a perfect example as it shows each point I want to make.

As mentioned above, begin by converting this value to a 64-bit fixedpoint binary. When doing this programmatically, I find it easiest tosimply use an array of 64 bytes for reasons which should becomeobvious.

The first 32 bytes in the array represent the whole part and are setby converting value into an integer, running through the bits of theinteger and setting the appropriate elements to 1. The second 32 bytesare set by first subtracting off the whole part of the value, thencontinuously multiplying by 2. Every time the value exceeds one, setthe corresponding array element to 1, and subtract 1 from the value.

In fixed point binary, 1.234 looks like this:

0001.0011 1011 1110 0111 0110 11001000 1011

The first 28 bits are zero, and therefore not shown. Remember thevalues on the right of the binary point are negative powers of 2, so,this represents 2^0 + 2^-3 + 2^-4 +2^-5 + 2^-7 …

At first blush, this appears to be a lot of work: a total of 299shifts and 20 additions! Luckily there are some tricks that can be usedto reduce this. For example, contiguous runs of 1s can be reduced. Saywe want to multiply a number by 15, or 1111 in binary. Thestraightforward way would be:

x = x * 8 + x * 4 + x * 2 + x

giving 6 shifts and 3 adds. Alternately, one could do this:

x = x * 16 ” x

giving 4 shifts and a subtract at the expense of a possibleoverflow. This is represented as follows:

+0001 0000
-0000 0001

Experience shows that runs of three or more 1s will usually reducethe resulting code. Rewriting the above, taking into account runs of1s, yields:

+0001.0100 0100 0000 1000 0110 11001000 1011
-0000.0000 1000 0010 0001 0000 00000000 0000

The number of shifts required has been reduced to 250 (with 11additions and three subtractions). Can more be done? Of course. Oncethe bit stream has been split into additive and subtractive partsabove, occasionally an identity will present itself. Again, by example,let use say we end up with the following:

+0100
-0010

which becomes the following equation:

x = 4x – 2x

which is the same as:

x = 2x

Any time an additive bit is immediately followed by a subtractiveone (or vise versa), one of the bits can be removed saving a shift andeither an add or subtract. The above example then becomes:

+0010
-0000

Applying this `identity' detection to the original expression gives:

+0001.0100 0000 0000 1000 0110 11001000 1011
-0000.0000 0100 0010 0001 0000 00000000 0000

saving 5 more shifts, for a total of 245, a roughly 20% reductionfrom the original, but still rather hefty. Now consider requiredprecision. The equation above results in a fixed point constantmultiply with no loss of precision.

In the ADC example above, if the display is only going to show aninteger between 0 and 100 it is silly to calculate the result to tendecimal places. To limit the precision, simply evaluate the expressionfrom left to right, stopping when the result of the expression iswithin the tolerances and zeroing all of the co-efficients past thatpoint. Allowing an error of just 0.01% the expression becomes:

+0001.0100 0000 000
-0000.0000 0100 001

This represents a multiply by 1.233887 instead of 1.234, for anactual error of 0.009%. This has reduced the number shifts to 19,yielding:

x + x / 4 ” x / 64 ” x / 2048

This leads us to the the final step, refactoring:

x + ( ( -x / 32 ” x ) / 16 + x ) / 4

giving a final total of 11 shifts and 4 adds and subtracts, just 4%of the original 299.

This is all well and good, if not tedious ” I certainly would notwant to go through this work for each constant I need. Luckily,computers are really good at doing tedious chores and not complaining.

Kyle York is a programmer for Cisco Systems specializingin layer 2 security. He also wrote and maintains the JALv2 compiler forthe PIC microncontrollers.

Referebces:
[1]
Gordon, Robert. “A Calculated Look at Fixed-PointArithmetic,'' Embedded.com June 17 2003

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.