Question about down-sample using right shift, and then interpolation?

Hi all,

In a technical report, they use the following technique which I do not
fully understand:

The objective is to implement function y=f(x) using LUT. x is a 4 bit
positive integer (range from 0 to 2^4-1). (The actual number in the
report is much larger but let's take 4 bits for the sake of
simplicity).

x=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.

Due to the hardware difficulty, they use only a LUT with 2^3 entries
(i.e. each entry has a 3-bit address).  The basic idea of their
implementation is to subsample f(x), and then take the linear
interpolation. And from the report, I see they use right-shift
operator for subsampling. For example for an integer x, to determine
its lower bound entry in the 3-bit-add LUT  they use  x>>1.

What I am confused is that what samples will be picked up to populate
the 3-bit-add LUT? They are likely f(0), f(2), f(4), f(6), f(8), f
(10), f(12), f(14). But if so,  how to interpolate to get the value of
f(15)?

I am really confused. Assume you need to do this task, f(x) where x is
from 0 to 15. And you have only 3 bit add LUT? what should you do?


Thanks a lot.

A.E lover <aelover11@gmail.com> wrote:

>I am really confused. Assume you need to do this task, f(x) where x is
>from 0 to 15. And you have only 3 bit add LUT? what should you do?

y = x == 15 ? f(15) : x & 1 ? (g(y>>1) + g((y>>1)+1))/2 : g(y>>1);

Where g() is the decimated lookup table with 8 entries.

Not so traumatic, I don't think.

s.

Thanks Steve, but sorry, I do not understand your "pseudo-codes".
Would any one can inteprate Steve's codes in plain text for me?

Thank you.


Regards,


On Jan 31, 5:01�pm, spop...@speedymail.org (Steve Pope) wrote:
> A.E lover <aelove...@gmail.com> wrote:
> >I am really confused. Assume you need to do this task, f(x) where x is
> >from 0 to 15. And you have only 3 bit add LUT? what should you do?
>
> y = x == 15 ? f(15) : x & 1 ? (g(y>>1) + g((y>>1)+1))/2 : g(y>>1);
>
> Where g() is the decimated lookup table with 8 entries.
>
> Not so traumatic, I don't think.
>
> s.

OK I see Steve. I did not recognize that you use inline function in C
to describe your work. Now I understand your idea. But maybe you meant
g(x>>1)... in your codes.
However even that, you still need some type of memory to store f(15),
don't you? That is not acceptable in the technical report I am
refering to. Moreover, what if now OUT is 2 bit (i.e. they have only
2- bit- address LUT ). The original range is
x=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.

I guess after down sampling, the sampled x (denoted as x_s) will be:

x_s=0  4  8   12.

And the 2-bit LUT will store f(x_s).

If so how to obtain the rest: f(13), f(14) and f(15)? Do I need to
store f(15) too so that I can take the interpolation. If so the LUT
now will need 3 bit for addressing f(15) and waste some address
numbers pointing to nothing.

I am very confused. Or you guys have another way to down sample f(x).

Please help me, hardware people.

Thanks.






On Jan 31, 2:01�pm, spop...@speedymail.org (Steve Pope) wrote:
> A.E lover <aelove...@gmail.com> wrote:
> >I am really confused. Assume you need to do this task, f(x) where x is
> >from 0 to 15. And you have only 3 bit add LUT? what should you do?
>
> y = x == 15 ? f(15) : x & 1 ? (g(y>>1) + g((y>>1)+1))/2 : g(y>>1);
>
> Where g() is the decimated lookup table with 8 entries.
>
> Not so traumatic, I don't think.
>
> s.

A.E lover <aelover11@gmail.com> wrote:

>OK I see Steve. I did not recognize that you use inline function in C
>to describe your work. Now I understand your idea. But maybe you meant
>g(x>>1)... in your codes.

Yes, sorry, that was a typo, the y's on the right hand side should 
be x's.

>However even that, you still need some type of memory to store f(15),
>don't you?  

f(15) is a scalar constant.  There is almost no hardware cost to 
a scalar constant.

Steve