Linear interpolation in vhdl

Hi,

I am looking for some insight on impelementing a linear interpolation
algorithm in vhdl.

thanks in advance

Dima

 

[Carson]

Hi Dima,

A 2 point interpolation is given by:

x = lambda * x_0 + (1 - lambda) * x_1 where lambda is between 0 to
1

Therefore the value of x is between x_0 and x_1

Directly implementing the above equation requires 2 multipliers and
2 adders (1 for x_0 and 1 for x_1). Rewriting the above equation,

x = lambda* (x_0 - x_1) + x_1.

so it now only uses 1 multiplier and 2 adders.

Please comment.

Thanks,

Carson

 

Well that is kind of what I was thinking, except I belive I also need
to implement a divider to calculate lambda.

lambda = (y - y_0) / (y_1 - y_0)

 

[Lawrence Wilkinson]

On Sun, 21 Aug 2005 14:11:02 -0700, df84077 wrote:

Well that is kind of what I was thinking, except I belive I also need
to implement a divider to calculate lambda.

lambda = (y - y_0) / (y_1 - y_0)

You could try searching for line-drawing algorithms (e.g. Bresenham) since
their basic function is to calculate interpolated coordinates. There are
probably algorithms which can calculate a given point without having to
calculate all the preceding values (maybe log2(N) values?).

LJW

 

Lawrence,

Thanks a lot for your help. I took a look at Bresenham's alrgorithm
and I am not sure if it will work (or how to modify it) for my
application.

Basically I have several A to D converters connected to an fpga
sampling at ~100 kHz. I am timestamping ADC data(32 bit counter running
from a 50 Mhz system clock) and need to be able to do linear
interpolation to obtain A/D values between sampling events. If
anybody has any suggestions on the best way to approach this I would
appreciate it.

 

[Andrew FPGA]

Hi Dima,
What are you really trying to do? Why are you wanting to linearly
interpolate? Do you really need to know the "A/D value" at arbitrary
times between A/D sampling events?

If you just want to know "A/D" values midway between sampling events
then interpolation will get you there. Insert zeros between samples and
then low pass filter. Actually you can insert any number of zeros
between A/D samples to get whatever sampling rate you want(well, an
integer mulitiple of the original sampling rate).

http://www.dspguru.com/info/faqs/multrate/interp.htm

Regards
Andrew

 

Thanks for your help guys. I didn't realize this right away, but the
A/D that I am using actually samples at a constant rate which is known.
So I can just precalculate the 1/(t_1- t_0), which turns the linear
interpolation into a couple of multiplications and an addition.

Thanks,

Dima

 

[Carson]

Hi Dima,

What you in DSP is called interpolation. If you have accessed to
IEEE filter, try to locate a paper call Farrow structure, it is an
efficient implementation for the interpolation (using first order,
second order, or higher)

As for the "lambda" term, I guess you have already figured out. But
you may also consider to use a huge counter (the larger the bits, the
higher the resolution) to count the relative position. (you can use the
remainder as the lambda)

Your project really interests me, I am quite familiar with these
interpolation tricks using digital filters interpolation. Let me know a
bit more detail and maybe I can help.

Carson