Tools > Design tools > Fast interpolation algorithm

## 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 2n + 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