linear interpolation on 8bit microcontroller

Question

I need to do a linear interpolation over time between two values on an 8 bit PIC microcontroller (Specifically 16F627A but that shouldn't matter) using PIC assembly language. Although I'm looking for an algorithm here as much as actual code.

I need to take an 8 bit starting value, an 8 bit ending value and a position between the two (Currently represented as an 8 bit number 0-255 where 0 means the output should be the starting value and 255 means it should be the final value but that can change if there is a better way to represent this) and calculate the interpolated value.

Now PIC doesn't have a divide instruction so I could code up a general purpose divide routine and effectivly calculate (B-A)/(x/255)+A at each step but I feel there is probably a much better way to do this on a microcontroller than the way I'd do it on a PC in c++

Has anyone got any suggestions for implementing this efficiently on this hardware?

Answer 1

You could do it using 8.8 fixed-point arithmetic. Then a number from range 0..255 would be interpreted as 0.0 ... 0.996 and you would be able to multiply and normalize it.

Tell me if you need any more details or if it's enough for you to start.

Answer 2

You could characterize this instead as:

(B-A)*(256/(x+1))+A

using a value range of x=0..255, precompute the values of 256/(x+1) as a fixed-point number in a table, and then code a general purpose multiply, adjust for the position of the binary point. This might not be small spacewise; I'd expect you to need a 256 entry table of 16 bit values and the multiply code. (If you don't need speed, this would suggest your divison method is fine.). But it only takes one multiply and an add.

My guess is that you don't need every possible value of X. If there are only a few values of X, you can compute them offline, do a case-select on the specific value of X and then implement the multiply in terms of a fixed sequence of shifts and adds for the specific value of X. That's likely to be pretty efficient in code and very fast for a PIC.

Answer 3

The value you are looking for is (A*(255-x)+B*x)/255. It requires only 8x8 multiplication, and a final division by 255, which can be approximated by simply taking the high byte of the sum.

Choosing x in range 0..128, no approximation is needed: take the high byte of (A*(128-x)+B*x)<<1.

Answer 4

Interpolation

Given two values X & Y , its basically:

(X+Y)/2

or

X/2 + Y/2 (to prevent the odd-case that A+B might overflow the size of the register)

Hence try the following:

(Pseudo-code)

Initially A=MAX, B=MIN

Loop {

    Right-Shift A by 1-bit.

    Right-Shift B by 1-bit.

    C = ADD the two results.

    Check MSB of 8-bit interpolation value

    if MSB=0, then B=C

    if MSB=1, then A=C

    Left-Shift 8-bit interpolation value

}Repeat until 8-bit interpolation value becomes zero.

The actual code is just as easy. Only i do not remember the registers and instructions off-hand.

Answer 5

Assuming you interpolate a sequence of values where the previous endpoint is the new start point:

(B-A)/(x/255)+A

sounds like a bad idea. If you use base 255 as a fixedpoint representation, you get the same interpolant twice. You get B when x=255 and B as the new A when x=0.

Use 256 as the fixedpoint system. Divides become shifts, but you need 16-bit arithmetic and 8x8 multiplication with a 16-bit result. The previous issue can be fixed by simply ignoring any bits in the higher-bytes as x mod 256 becomes 0. This suggestion uses 16-bit multiplication, but can't overflow. and you don't interpolate over the same x twice.

interp = (a*(256 - x) + b*x) >> 8

256 - x becomes just a subtract-with-borrow, as you get 0 - x.

The PIC lacks these operations in its instruction set:

• Right and left shift. (both logical and arithmetic)
• Any form of multiplication.

You can get right-shifting by using rotate-right instead, followed by masking out the extra bits on the left with bitwise-and. A straight-forward way to do 8x8 multiplication with 16-bit result:

void mul16(
    unsigned char* hi, /* in: operand1, out: the most significant byte */
    unsigned char* lo  /* in: operand2, out: the least significant byte */
)
{
    unsigned char a,b;

    /* loop over the smallest value */
    a = (*hi <= *lo) ? *hi : *lo;
    b = (*hi <= *lo) ? *lo : *hi;
    *hi = *lo = 0;
    while(a){
        *lo+=b;
        if(*lo < b) /* unsigned overflow. Use the carry flag instead.*/
            *hi++;
        --a;
    }
}

Answer 6

The techniques described by Eric Bainville and Mads Elvheim will work fine; each one uses two multiplies per interpolation.

Scott Dattalo and Tony Kubek have put together a super-optimized PIC-specific interpolation technique called "twist" that is slightly faster than two multiplies per interpolation.

Is using this difficult-to-understand technique worth running a little faster?