Help regarding Fixed point implementation.

[simar]

Hi there,

First of all thanks for providing me so much support in this forum. I have come here with another question.

I have a project using MC9s12xd256 MCU. I have found that a instruction of this type;

corr_dc = kp_Dc*error;

 takes around 0.7ms and if kp_dc is float and if i change kp_dc as int, the time of execution is 0.007ms, so there is a big difference. As my application is very time critical. Do you advice me to use fixed point implementation instead of floating point. Here is the all floating code in the main loop of my project.

float kp=0.2;float ki=0.0023;float kd=0.033;correction = kp*error + ki*iterm + kd*dterm;


float com_ratio[7]={23.44,23.44 ...};
for(int i=0;i<7;i++)
{
   com_val = (int)(com_ratio*sen_val);
}

I think I can save  a lot of time by implementing fixed point. Also regarding fixed point representation, is there is a library avaliable for mc9s12x or I will have to write it on my own...

[kef]

To substitute multiply by float like 22.45, you can multiply by 2245, then divide by 100. But you need to care about possible integer overflows and switch to long integers when necessary.

Multiply by 2245 will overflow for signed multipliers below -14 and above +14. Unsigned x*2245 will  overflow starting from unsigned short x > 29. Switching to long int will give you muchj more freedom but often at a cost of slower operations.

You may try to find biggest common divisors and extend short int usage range. For example 2245 and 100 can be both divided by 5. So multiply by 22.45 can be replaced by *449 and then /20. Overflow margins will rise to signed +-72 and unsigned 145.

Excerpts from your code are absolutely useless without all declarations of all used objects. Is error variable integer? Is sen_val float? Sometimes it is faster to operate with all float parameters than doing intermediate conversions from / to integers.

[simar]

I know I have posted enough but I can't wait anymore to share result of your advice

See another snippet of my code and the time of execution that I calculated using real time simulator..

# define KP_DC 2#define KD_DC 3.23int correction_dc,error_dc,perror_dc;   //all are signed integers.. correction_dc =(int) ( (KP_DC*error_dc )+ KD_DC*(error_dc-perror_dc));//TIme i found is 1.267-0.473=0.794ms// with non of values as 0.

Second case

# define KP_DC 2#define KD_DC 323int correction_dc,error_dc,perror_dc;   //all are signed integers.. correction_dc =(int) ( (KP_DC*error_dc )+ KD_DC*(error_dc-perror_dc)/100);//TIme i found is 0.482-0.468ms = 
// with none of values as 0..

I don't think that the result (corrrection_dc) will vary ...  with either of the technique

[bigmac]

Hello Gursimran,

For the servo_set calculation of Snippet 1, since ypur constants are much less than 1, rather than multiplying by a very small value, you could divide by the reciprocal of your constants.  For the values given, the reciprocals are very close to integer values.  The servo_set value might possibly have an error of 1 because the result of each quotient has the fractional part truncated, and three quotients are added.  Additional "rounding" could be applied to each quotient calculation, but would require a more complex calculation.

You could also apply the quasi fixed point method described below, but again requiring more execution cycles.

// SNIPPET 1int error, iterm, dterm, correction;int r_kp = 5;   // 1/0.2int r_ki = 435; // 1/0.0023int r_kd = 30;  // 1/0.033correction = (int)(error/r_kp + iterm/r_ki + dterm/r_kd);if (correction > 300)   correction = 300;else if (correction < -300)   correction = -300;servo_set = 1500 - correction;  // Feed these values to servos

It would seem that, for fixed point calculations, there may be sufficient accuracy, using an 8-bit fractional part.  This may be effectively achieved "on the fly" by making sure that each intermediate result is increased by 256 times, and the final integer result achieved by finally dividing by 256.  Multiplying and dividing by 256 should result in  fast operations for the compiler.

There also does seem to be some ambiguity with the com_ratio variable, whether it is a simple variable or a constant array.  For the array version, 23.44 * 256 ~= 6001.

// SNIPPET 2/* black_val and white_val are sensor values when IR sensors are on   black and white surfaces .. from ATD data register*/unsigned char black_val, white_val;int com_ratio;unsigned char i;//unsigned int com_ratio[7] = {6001, 6001, 6001 ... }; // ?? Name conflictcom_ratio = (int)(black_val - white_val); // /256;  Leave as 8-bit integer
for (i = 0; i < 7; i++) {   com_val = (unsigned char)(com_ratio * sen_val / 256);      ...      }//------------------------------------------------​-------------------#define KP_DC  512L  // 2.00 * 256#define KD_DC  827L  // 3.23 * 256 int correction_dc, error_dc, perror_dc;   // all are signed integers..  correction_dc = (int)((KP_DC*error_dc + KD_DC*(error_dc - perror_dc))/256);

For the last example, specifying KP_DC and KD_DC as long values will promote the intermediate calculations to long values, to prevent potential overflow.

Regards,

Mac

[simar]

unsigned char com_ratio;
float com_ratio[7]={23.44,23.44 ...};
for(int i=0;i<7;i++)
{
   com_val = (unsigned char)(com_ratio*sen_val);
}

There is a correction here

unsigned char com_val[7];

float com_ratio[7]={23.44,23.44 ...};
for(int i=0;i<7;i++)
{
   com_val = (unsigned char)(com_ratio*sen_val);
}

//com_ratio are not constants and are calculated right in the code and initialized early in the code but here I have explicitely initialized to avoid pasting all the code..

[simar]

Your suggestions helped a lot though...

[TomE]

It is always better to use someone else's tested implementation rather than writing one yourself.

There are fixed point libraries around. Have a look at the ones used in FreeType at:

http://www.freetype.org

http://savannah.nongnu.org/projects/freetype

The files you may want to look at are:

http://git.savannah.gnu.org/cgit/freetype/freetype2.git/tree/include/freetype/freetype.h?h=VER-2-0-4...

http://git.savannah.gnu.org/cgit/freetype/freetype2.git/tree/src/base/ftcalc.c?h=VER-2-0-4-PATCH

In the code I'm working on we have the compiler (gcc) set to use SINGLE-PRECISION floating point emulation (on an MCF5329) for all the code that doesn't have to run too fast but does have to get the right answer. That's faster than the default double-precision code. I think we're using the newlib single-precision float libraries for this:

http://www.sourceware.org/newlib/

For the code that does have to run fast and we can spend the time to inspect and test, we're using custom variants of the FreeType fixed-point functions. This stuff doesn't look as pretty as letting the compiler handle things though:

nXInner_f = fixedMul(INT_TO_FIXED(a_nY), INT_TO_FIXED(a_psZoid->nXMax - a_psZoid->nXBottom));nXInner_f = fixedDiv(nXInner_f, INT_TO_FIXED(a_psZoid->nYMax));nXInner_f = INT_TO_FIXED(a_psZoid->nXMax) - nXInner_f;

[simar]

Thanks TomE for th links... This is exactly what I was looking after but eventually keff and bigmac showed me a better alternative to the problem. I hope this will help somebody else with similar issues.

I feel like we should archive such useful posts in a NewBie post as this http://www.avrfreaks.net/index.php?name=PNphpBB2&file=viewtopic&t=70673 so that a new person to these MCU will not find a hard time as I did..

I hope many people here including me will get some time to try to post some useful stuff for absolute beginners.. As there isn't any help avaliable on the net too for this MCUs, I hope this will be a very good starting point for these MCu's programmers ..

Regards

[simar]

Sorry I forget to add the following link, you may refer

http://www.eetimes.com/discussion/other/4024639/Fixed-point-math-in-C

[simar]

Thanks again keff

All the variables are short integers or unsigned chars except that I explicitely mentioned as float.

error -> signed intger

sen_val is unsigned char

com_val -> unsigned char

Actually I have limitation on that datatypes of these, as, I will have to feed these values to registers at some point that will not accept float values ofcourse, so at some point I will have to convert the variables to unsigned int or unsigned char..

[simar]

Revised code with range and all datatypes defined

//SNIPPET 1

//range of kp,ki,kd is (0,1)
int error,iterm,dterm,correction;

float kp=0.2;float ki=0.0023;float kd=0.033;correction = (int)(kp*error + ki*iterm + kd*dterm);
if(correction>300)
       correction=300
if(correction<-300)
        correction=-300

servo_set = 1500-correction //i have to feed these values to servos..


//SNIPPET 2
//range of com_ratio is (0,3.00)

unsigned char com_ratio;
float com_ratio[7]={23.44,23.44 ...};
for(int i=0;i<7;i++)
{
   com_val = (unsigned char)(com_ratio*sen_val);
}

"To substitute multiply by float like 22.45, you can multiply by 2245, then divide by 100."

Seems to be a very good idea but I have two questions regarding it..

1. If I divide it by 100, I think it will take a lot of time, isn't using fixed point a better alternative..

2. Yes, by this I will definately save a lot of clock cycles but I have a problem implementing it in case of my second code snippit, where I first calculate com_ratio which is float using

//black_val and white_val are sensor values when I place my IR sensors on black and white surfaces..  so they are unsigned char read for ATD data registerunsigned char black_val,white_valcom_ratio = (black_val-white_val)/256;

 Then I store these in EEPROM and retrieve later. I can skip this EEPROM but I will definately have to store these in variables by the above formula ..

[kef]

Since S12(X) are equipped with hardware division instructions, integver divide by 100 isn't very slow. Being smart enough you could make divide replaced with shift left or right or transferring higher order byte/word to lower order word. For example *0.45 could be replaced with multiply by 0.45*256=115.2 ~115  and divide by 256. Compiler most likely will optimize /256 by trasnferring HI byte to LO byte and clearing HI byte. In case you need better accuracy and can't discard fractional part of 115.2 (115 is 0.17% off), you could find more accurate multiplier. 115.2 * 2 = 230.4 ~230. Error of 230 vs 230.4 is the same. 230.4 * 2 = 460.8 ~ 461. Now error is 0.04%. So multiply by 0.45 could be replaced with * 461 / 1024. Divide by 1024 can be replaced with >>2 and transferrring HI byte to LO byte. Etc etc

Fixed point library may be easier to use than optimizing each */, but like with floating point, it is done at a cost of longer execution times. Packing - unpacking bit fields takes time because shifting bits left or right and masking/unmasking unused or new bits are involved. Universal FIXP_x_r_mul  routine is unavoidably slower than in-place * /.