Interpolation routine wanted (solved)

This project calls for a robust and easy to use interpolation function, preferably one that accepts a list of (Xn,Yn) points sorted for ascending value of X. The result should be (Y0) for X < X0, and Ylast for X > Xlast.

If anybody has some code lying around or knows of some code that's been published under a permissive Open Source license, I would love to hear about it. Otherwise you'll just have to wait until a sufficient number of neurons in my brain isn't already fully satisfied by working on work related problems ;-)

EDIT:

I brewed something up. @inter includes the table search and the interpolation function @K.C. Lee referred to, and a limiting function that works by comparing the pointers to value pairs. It can be used for arbitrary y=f(x) with saturation, which is what's needed for many control and linearizion tasks.

: @dif ( a -- n )     \ delta of value pairs
  dup 2+ 2+ @ swap @ - ;
: @inter ( x a -- y ) \ find value pairs, interpolate
  dup @ 1- >R 2+ dup begin 
    3 pick over @ < not while 
    nip dup 2+ 2+ next 
      drop dup
    else R> drop then \ eForth LEAVE idiom
  over = if           \ pointers equal: saturation 
    2+ @ nip 
  else 
    dup rot over @ - over 2+ @dif 
    rot @dif */ swap 2+ @ + then ;

@inter does a table lookup with interpolation. The input is the value and the address of a table with n value pairs (Xn, Yn) ordered by ascending values of X, and preceded by the number of n. @dif looks up two values returns the difference (X1-X0 or Y1-Y0 depending on the offset). A C program would be a bit longer, I guess. Compiled this code requires 177 bytes.

Here is an example:

500 1000 400 800 300 600 200 400 100 200 50 100 6 ok
create pairs , , , , , , , , , , , , , ok
: p pairs @inter . ; ok
450 p 225 ok
90 p 50 ok
1500 p 500 ok

pairs is an arbitraty list of 6 x/y value pairs: [6, [100, 50], [200, 100], [400, 200], [600, 300], [800, 400], [1000, 500] ]

Test values:

450 is between (400/200) and (600/300) -> result 225
90 is below X0, and following the requirements above Y0 is returned -> 50
1500 is above X(n-1) and Y(n-1) is returned -> 500

Discussions

K.C. Lee wrote 03/23/2017 at 13:26

http://www.blueleafsoftware.com/Products/Dagra/LinearInterpolationExcel.php

Basics on linear interpolation

Are you sure? yes | no

K.C. Lee wrote 03/23/2017 at 13:22

Here is my code for linear search on X array. Used for figuring the button pressed using ADC in another project. It search for a range of value centered on X +/- tolerance.

// return raw key(s) pressed
// These are based on calculations and minor tweaking
code const uint16_t ButtonValues[] =
{ 0x3FF0,0x2000,0x154F,0x0FFB,0x0D86,0x0B29,0x0981,0x846 };

uint8_t ADC_Button(void)
{
uint8_t i;
uint16_t value, key=ADC_Raw_Data[ADC_BUTTON];

for(i=0;i {
value=ButtonValues[i];

if(key >=(value-ButtonTolerance)&&(key<=(value+ButtonTolerance)))
return(i);
}

return(0);
}

Are you sure? yes | no

K.C. Lee wrote 03/23/2017 at 13:13

i have untested code for linearizing RTD. The table is evenly spaced, so the entry is determined by calculating which Y entry to use. My code was squeezed for space than readability

#define NSEG 8 // number of sections in table
#define RMIN (1792) // input resistance at 0 degC

// fixed point integer <<4
const uword C_rtd[] = {0x0000,0x0240,0x0487,0x06d4,0x0928,0x0b83,0x0de5,0x104e,0x12c0};

calculating for evently spaced table - No X entries. C_rtd[] is my Y table.

i=(ADC-RMIN)/(uword)RSEG; // determine which coefficients to use
If you have a generic X,Y entries, you first have to search for the index i such that that X[i-1] < x <= X[i]. For small tables, a linear search can be used and should consider a binary search once you are in the double digits.

Range testing:

if (i<0) // if input is under-range..
i=0; // ..then use lowest coefficients

else if (i>NSEG-1) // if input is over-range..
i=NSEG-1; // ..then use highest coefficients

Linear interpolation:

return ((uword)(C_rtd[i]+((unsigned long)(ADC-(RMIN+RSEG*i))*(C_rtd[i+1]-C_rtd[i]))/RSEG)) ;

Are you sure? yes | no

Thomas wrote 03/23/2017 at 20:54

Hi K.C., thanks for the code! I think the main challenge will be to silence my inner perfectionist (e.g. must be fast, must be reentrant, must be easy to use etc etc) ;-) I've just got to hack/do it, I guess ;-)

By the way, what do you think about the results on the scope? At least, it should be sufficient for use cases like this: http://www.ti.com/lit/an/snva681a/snva681a.pdf or some of these: http://www.st.com/content/ccc/resource/technical/document/application_note/1f/d7/fc/6d/2e/27/48/98/CD00181783.pdf/files/CD00181783.pdf/jcr:content/translations/en.CD00181783.pdf

Are you sure? yes | no

K.C. Lee wrote 03/23/2017 at 22:29

Not sure which scope picture you are talking about and how that is related to the 2 URLs for automotive electrical system protection. As for automotive protection, I have done something in that area.

If you are talking about the noise on the dynamic load test...

Might want to try to add a small value capacitor in parallel with the upper branch of the voltage divider. That might increase the AC gain a bit. Might or might not make the results worse.

Are you sure? yes | no

K.C. Lee wrote 03/23/2017 at 22:35

It is kind of a pain to do any math related stuff reentrant unless your math library is reentrant. i.e. doesn't have internal storage for floating point/fixed point work area for intermediate results.

Are you sure? yes | no

Thomas wrote 03/24/2017 at 06:21

Hi K.C., I was referring pictures in a log some days ago:

https://hackaday.io/project/19647-low-cost-programmable-power-supply/log/54775-switched-load-test-with-a-modified-dc-dc-converter

The automotive test pulses is an interesting and recurrent topic:

- load-dump is clear, that's about protection, robustness, and embedded system recovery time

- Cold cranking is about connected systems robustness, and diagnostics

Load-Dump is clearly out of scope for hobby projects (a generously dimensioned protection circuit takes care of that). The cold cranking is important for anything that's supposed to work in a car with combustion engine. One might argue that these are obsolete, but at least for hacking the will play a major role for decades to come ;-)

Are you sure? yes | no

Thomas wrote 03/24/2017 at 06:31

About re-entrance: as long as no variables (i.e. fixed memory addresses) are used, all code in TG9541/STM8EF is re-entrant. It's also possible to use the same routine in interrupts with multiple priority levels as long as time constraints are met.

Are you sure? yes | no

K.C. Lee wrote 03/24/2017 at 10:32

Load dump protection isn't out of reach for hobbyists. Microchip-Micrel MIC29150/29300/29500/29750 LDO has it built-in along with reverse protection. Assume the hobbyist knows beyond copy/paste 7805 from youtube for everything and done the research like the old days before the web. :P

Absolute Maximum Rating: -20V to 60V
60V less than 100ms, 1% duty cycle. Max continuous voltage 26V.

There are other chip(s) for a frontend last time I looked.

In most cases, this along with a good surge protection frontend would work. Getting the surge protection right and testing it in real life is the tough part for hobbyists.

Are you sure? yes | no

Thomas wrote 03/24/2017 at 18:48

You're right about the implementation of a good Load-Dump protection. What I had in mind was real life testing (we're on the same page).

Are you sure? yes | no

Instructions updated

Linearized output

Discussions

Become a Hackaday.io Member