linear interpolation, is it necessary to search for the neighboring points?

Hi all,

Let's discuss scalar function y=f(x). I generate a 1-D Look-up table
as follows:

I sample non-regularly (i.e. not equally spaced partition) the x axis
into N points.  Then, store the y_i=f(x_i) ,  i=1,...,N into a 1D-LUT.
To estimate y_j=f(x_j) for a x_j not in the grids, I use the the
linear interpolation.

Now my question is that, in the hardware implementation, is it
necessary to do a search to  determine the neigboring points of x_j so
that I can implement the linear interpolation?

I know in the case of regular partition, if I sample the x axis to the
2^k equally spaced points, I can be based on the kth MSB bit of x_j to
determine its lower neigboring point. This way will be much faster
than comparison operators in a search algorithm.

However, in the case of non-regular sampling, is there any way to
determine the neigboring points without a searching?

I read a book that discusses the trilinear interpolation. It says that
for trilinear interpolation, it is not necessary to do a search (with
comparison, that is slow in hardware implementation) to do so.

I guess, for linear interpolation, it would be the same. But I am
still looking for how to do it.

So please help.

Thanks

On Oct 20, 10:54&#4294967295;pm, MBALOVER <mbalov...@gmail.com> wrote:
>
> Let's discuss scalar function y=f(x). I generate a 1-D Look-up table
> as follows:
>
> I sample non-regularly (i.e. not equally spaced partition) the x axis
> into N points. &#4294967295;Then, store the y_i=f(x_i) , &#4294967295;i=1,...,N into a 1D-LUT.
> To estimate y_j=f(x_j) for a x_j not in the grids, I use the the
> linear interpolation.
>
> Now my question is that, in the hardware implementation, is it
> necessary to do a search to &#4294967295;determine the neigboring points of x_j so
> that I can implement the linear interpolation?

why must this be non-uniformly spaced?  if it must be, can you use
another function to convert your argument to another argument that is
used for uniformly-spaced table lookup and interpolation?

> I know in the case of regular partition, if I sample the x axis to the
> 2^k equally spaced points,

it doesn't have to be a power of 2, does it?

> I can be based on the kth MSB bit of x_j to
> determine its lower neigboring point. This way will be much faster
> than comparison operators in a search algorithm.
>
> However, in the case of non-regular sampling, is there any way to
> determine the neigboring points without a searching?

a pre-determined mapping function (using a table of uniformly spaced
points).

> I read a book that discusses the trilinear interpolation. It says that
> for trilinear interpolation, it is not necessary to do a search (with
> comparison, that is slow in hardware implementation) to do so.

i dunno what trilinear interpolation is.

> I guess, for linear interpolation, it would be the same. But I am
> still looking for how to do it.
>
> So please help.

i don't have any idea why searching and comparison have anything to do
with linear interpolation, unless maybe you are trying to invert a
function represented as a set of points that are linearly
interpolated.

oh, i suppose if the points in the table are not equally spaced, there
is a sorta search to convert the continuous argument to point to the
first point of the pair being interpolated.  but if the points are
uniformly spaced, there is no need of searching to index into the
table to get to the two adjacent points being interpolated.  it's an
operation of scaling, separating the integer and fractional parts, and
using the integer part as an index for going into the table.

> Thanks

FWIW.  i mostly just echoed your question back to you.

r b-j