| Home | Products | Tools | Downloads | Contacts |

Fast interpolation algorithm

The fast interpolation algorithm is based on linear interpolation equation:

It uses of aligned lookup table (LUT), which allows easy find interpolation interval and replace division by arithmetic binary shift operation.

Where:
N - Resolution of input value in bits
n - Width of LUT in bits
i - Index of actual element in lookup table
The necessary size of lookup table can be calculated as 2ⁿ + 1

This implementation especially suited for microcontrollers applications. It minimizes the calculation time, code size and allows to have constant performance independent from interpolation table size.
The example C code for 12bit input values and 17 LUT entries is shown below.

static inline signed short fast_interpolate(unsigned short x) {
        register unsigned short i = (x >> 8);
        return lut[i] + (signed short)((signed long)(lut[i + 1] - lut[i]) * (x - (i << 8)) >> 8);
}

Interpolation of temperature values from NTC

As measurement circuit a resistive voltage divider with NTC sensor referenced to ground is used.

Here is a calculated lookup table for NTCLE100E3103 sensor with n = 4. The table transforms raw unsigned 12 bit ADC values into temperature, represented in fixed points format (fix7_8).

static const signed short lut[17] = {
        32767, // Upper limit (temperature value is not correct), short circuit  ADC value:0
        25737, // T:100.54'C,  Rt:0.667k    ADC value:256
        19477, // T:76.08'C,   Rt:1.429k    ADC value:512
        15902, // T:62.12'C,   Rt:2.308k    ADC value:768
        13330, // T:52.07'C,   Rt:3.333k    ADC value:1024
        11265, // T:44.01'C,   Rt:4.545k    ADC value:1280
         9491, // T:37.08'C,   Rt:6.0k      ADC value:1536
         7894, // T:30.84'C,   Rt:7.778k    ADC value:1792
         6400, // T:25.0'C,    Rt:10.0k     ADC value:2048
         4954, // T:19.35'C,   Rt:12.857k   ADC value:2304
         3511, // T:13.72'C,   Rt:16.667k   ADC value:2560
         2019, // T:7.89'C,    Rt:22.0k     ADC value:2816
          412, // T:1.61'C,    Rt:30.0k     ADC value:3072
        -1413, // T:-5.52'C,   Rt:43.333k   ADC value:3328
        -3679, // T:-14.37'C,  Rt:70.0k     ADC value:3584
        -7031, // T:-27.47'C,  Rt:150.0k    ADC value:3840
       -32768, // Lower limit (temperature value is not correct), open circuit  ADC value:4096
};

Graphical plot of interpolation results:

LUT calculation script

The LUT calculation Python script for fast interpolation algorithm can be found here: ntc.py

The script transforms known temperature values into n-bits aligned lookup table and generates C structure, which can be directly integrated into C code.

The script has following parameters:
R - Upper resistor value
N - ADC resolution in bits
n - Width of lookup table in bits
ADCref - ADC reference voltage
NTCref - resistive divisor reference voltage
Rntc - Temperature and resistance values from datasheet must be placed in tuple or list:
((temperature 1, resistance 1), (temperature 2, resistance 2), ...)