lighthsu wrote:
> Hi all,
> I'm working on a DSP project, which needs an arbitrary sampling rate
> converter.
> I searched several interpolation algorithms - windowed-sinc, Lagrange, and
> B-Spline. However, I can't determine which algorithm is suitable for
> low-ordered interpolation filter.
> According to my understanding, the performance of windowed-sinc
> interpolation(with table look-up) can be easily estimated by the
> specification of window(filter order, transition bandwidth, and stopband
> attenuation are trade-off). But I can't estimate the performace of
> Lagrange and B-Spline interpolater.
> Is there any document or paper about the performance of Lagrange and
> B-Spline interpolaters? I need the informations about filter order,
> transition bandwidth, and stopband attenuation of these interpolation
> algorithms.
>
> Thanks a lot for your help!! :)
>
> Sincerely yours,
> Light Hsu

um.. if i got it right, you're trying to make some that can resample a
signal to any specified length. i think I know how to do it (disclaimer
: i'm a newbie and often am wrong or off-topic :-)). I just do the FFT
of the signal i want to resample, I cut off samples in the highest
frequencies if i want to shorten it or i zero-pad the real and
imaginary bins if i want to make the signal longer and the I perform an
IFFT.

in article 1131754659.231097.24780@z14g2000cwz.googlegroups.com, Ron N. at
rhnlogic@yahoo.com wrote on 11/11/2005 19:17:

> robert bristow-johnson wrote:
...
>> 
>> the advantage of polynomial interpolation is that it can have infinite
>> precision in its fractional time index where a table lookup is, of course,
>> discrete.
> 
> The precision of a polynomial interpolation will be limited to
> the number of bits in your fixed or floating point data type.

but that's true for any of the interpolation methods.  that (coefficient
quantization, word width, etc.) is a different, sorta peripheral issue.

my point was addressed to the possible question of why we would want to use
polynomial interpolation at all, in the first place.  and the answer is, you
can calculate the coefficients on-the-fly, no matter where your
instantaneous fractional time ends up.  you can't do that for table lookup
(unless you interpolate, but how would you do that which brings us back to
the initial issue of why we would use piecewise polynomial interpolation in
the first place).   the word size for that time is another issue completely.
let's assume it is infinite precision.

...

> My question was how well this interpolation method works with
> a very small number of sample points (3,4, or 5, for instance)
> used for each interpolation.

well, that paper Duane and i did does it for 4 sample points and it has some
concrete results.  Olli's paper has more results.  it's not so great, unless
the upsample ratio is large.  but then how come the idea was only to apply
that to oversampled cases in the first place.
 

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

robert bristow-johnson wrote:
> in article hjvcf.26188$Q27.17475@trnddc02, Jon Harris at
> jon99_harris7@hotmail.com wrote on 11/09/2005 18:07:
>
> > "Ron N." <rhnlogic@yahoo.com> wrote in message
> > news:1131574772.921278.226370@g44g2000cwa.googlegroups.com...
> >> robert bristow-johnson wrote:
> >>> now, in my opinion, for an arbitrary sampling rate conversion ratio, i think
> >>> the simplest and best method is to use a lookup table based (Kaiser windowed
> >>> sinc or alternatively an optimally designed LPF) interpolation with a high
> >>> but finite upsampling ratio and then use linear interpolation in between.
> >>
> >> How wide a windowed sinc is required to match a given order of
> >> polynomial interpolator?  e.g. would some 4.5 sample-width windowed
> >> sinc FIR filter match a 3-rd order spline interpolation in quality,
> >> given that they use the same number of input sample points?
> >> Or would the windowed sinc need to be wider than the polynomial
> >> interpolator.
> >
> > For the same number of input sample points (or taps), an optimally designed
> > low-pass filter is going to be better than Lagrange interpolation, at least in
> > terms of pass-band flatness and stop-band rejection.  Plus, you can tune the
> > filter to give you exactly what you want, rather than relying on what the
> > frequency characteristics of a particular polynomial happen to be.  I don't
> > know about other types of splines, I've worked mostly with Lagrange.  And the
> > windowed sinc with a well-chosen window can be very close to the optimally
> > designed filter.
>
> for table lookup, an optimally designed filter (using Parks-McClellan or,
> perhaps, Least Square Error) will be better than a Kaiser windowed sinc()
> besides being better than the polynomial interpolation.
>
> the advantage of polynomial interpolation is that it can have infinite
> precision in its fractional time index where a table lookup is, of course,
> discrete.

The precision of a polynomial interpolation will be limited to
the number of bits in your fixed or floating point data type.
The same precision (maybe minus a bit or two) is often available
from most trig or bessel math libraries, so windowed sinc
interpolation will have essentially the same precision available.

Of course, if performance requires it, you could implement
a lower precision math library using table lookup plus table
interpolation (by storing finite difference tables, for instance).

My question was how well this interpolation method works with
a very small number of sample points (3,4, or 5, for instance)
used for each interpolation.


IMHO. YMMV.
-- 
rhn A.T nicholson d.O.t C-o-M

in article hjvcf.26188$Q27.17475@trnddc02, Jon Harris at
jon99_harris7@hotmail.com wrote on 11/09/2005 18:07:

> "Ron N." <rhnlogic@yahoo.com> wrote in message
> news:1131574772.921278.226370@g44g2000cwa.googlegroups.com...
>> robert bristow-johnson wrote:
>>> now, in my opinion, for an arbitrary sampling rate conversion ratio, i think
>>> the simplest and best method is to use a lookup table based (Kaiser windowed
>>> sinc or alternatively an optimally designed LPF) interpolation with a high
>>> but finite upsampling ratio and then use linear interpolation in between.
>> 
>> How wide a windowed sinc is required to match a given order of
>> polynomial interpolator?  e.g. would some 4.5 sample-width windowed
>> sinc FIR filter match a 3-rd order spline interpolation in quality,
>> given that they use the same number of input sample points?
>> Or would the windowed sinc need to be wider than the polynomial
>> interpolator.
> 
> For the same number of input sample points (or taps), an optimally designed
> low-pass filter is going to be better than Lagrange interpolation, at least in
> terms of pass-band flatness and stop-band rejection.  Plus, you can tune the
> filter to give you exactly what you want, rather than relying on what the
> frequency characteristics of a particular polynomial happen to be.  I don't
> know about other types of splines, I've worked mostly with Lagrange.  And the
> windowed sinc with a well-chosen window can be very close to the optimally
> designed filter. 

for table lookup, an optimally designed filter (using Parks-McClellan or,
perhaps, Least Square Error) will be better than a Kaiser windowed sinc()
besides being better than the polynomial interpolation.

the advantage of polynomial interpolation is that it can have infinite
precision in its fractional time index where a table lookup is, of course,
discrete.  remember that linear interpolation is a 1st order B-spline,
Hermite, or Lagrange polynomial and you can combine the table lookup (with
an optimal design) and some polynomial interpolation for in between those
discrete-time interpolated values.  this is quite straight-forward and it
works pretty well.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

"Ron N." <rhnlogic@yahoo.com> wrote in message 
news:1131574772.921278.226370@g44g2000cwa.googlegroups.com...
> robert bristow-johnson wrote:
>> now, in my opinion, for an arbitrary sampling rate conversion ratio, i think
>> the simplest and best method is to use a lookup table based (Kaiser windowed
>> sinc or alternatively an optimally designed LPF) interpolation with a high
>> but finite upsampling ratio and then use linear interpolation in between.
>
> How wide a windowed sinc is required to match a given order of
> polynomial interpolator?  e.g. would some 4.5 sample-width windowed
> sinc FIR filter match a 3-rd order spline interpolation in quality,
> given that they use the same number of input sample points?
> Or would the windowed sinc need to be wider than the polynomial
> interpolator.

For the same number of input sample points (or taps), an optimally designed 
low-pass filter is going to be better than Lagrange interpolation, at least in 
terms of pass-band flatness and stop-band rejection.  Plus, you can tune the 
filter to give you exactly what you want, rather than relying on what the 
frequency characteristics of a particular polynomial happen to be.  I don't know 
about other types of splines, I've worked mostly with Lagrange.  And the 
windowed sinc with a well-chosen window can be very close to the optimally 
designed filter. 

robert bristow-johnson wrote:
> now, in my opinion, for an arbitrary sampling rate conversion ratio, i think
> the simplest and best method is to use a lookup table based (Kaiser windowed
> sinc or alternatively an optimally designed LPF) interpolation with a high
> but finite upsampling ratio and then use linear interpolation in between.

How wide a windowed sinc is required to match a given order of
polynomial interpolator?  e.g. would some 4.5 sample-width windowed
sinc FIR filter match a 3-rd order spline interpolation in quality,
given that they use the same number of input sample points?
Or would the windowed sinc need to be wider than the polynomial
interpolator.

-- 
rhn

"Ron N." <rhnlogic@yahoo.com> wrote in message 
news:1131485494.187399.48850@g44g2000cwa.googlegroups.com...
> robert bristow-johnson wrote:
>> now, in my opinion, for an arbitrary sampling rate conversion ratio, i think
>> the simplest and best method is to use a lookup table based (Kaiser windowed
>> sinc or alternatively an optimally designed LPF) interpolation with a high
>> but finite upsampling ratio and then use linear interpolation in between.
>
> You're mixing an interpolation formula and an implementation
> optimization.  The simplest method would be to simply use a
> (Kaiser) windowed sinc interpolation formula directly.
>
> The decision on whether  to precalculate and store some number
> of coefficients or to interpolate from a smaller number coefficients
> of interpolation should be based on whether or not the needed
> performance and on the amount of  available memory in your
> particular implementation.

The Kaiser window is pretty nasty and an optimally designed FIR is even worse. 
There are of course ways to simplify the calculations, but often the look-up 
table approach is very attractive.  Even if you can't afford the memory for a 
big one, often a small one followed by linear (or better) interpolation is 
computationally simpler than full on-the-fly coef calculation.

But I'm sure there are situations where on-the-fly makes sense too.  If I 
absolutely _had_ to do on-the-fly, I would probably pick a different window than 
Kaiser and just throw more taps at it to get similar performance. 

in article ksudna9bW7IY6ezeRVn-oQ@giganews.com, lighthsu at
lighthsu2004@yahoo.com.tw wrote on 11/08/2005 23:01:

> Hi Robert and all,
> Thanks for your information!
> I've studied your paper, and have one question about B-spline polynomial.
> For the 6-point 5th-order B-spline polynomial, are the coefficients
> adjustable for different transition bandwidth and stopband attenuation?

no.  but the different polynomials for interpolation (of a given order) all
have different passband, transition band, and stopband characteristics.  in
the oversampled case (which is what the case is if you were to use
polynomial interpolation along with a table lookup sinc-like interpolation)
there is a reason that B-spline will kill the images better than any other
polynomial interpolation of the same order.  but B-spline will also have the
most passband LPF roll-off (which can be compensated to a degree in the
design of the sinc-like LPF).

just FYI:  i would consider only odd order polynomial interpolation where
the number of samples used in the interpolation is one greater than the
order.  this means the number of samples is even and there are an equal
number of samples behind the interpolated region as is in front of it.  in
our and Olli's paper, we like to define that region as  0 <= alpha < 1 .
so, if N-1 is the order, the samples you use are

    { x[-N/2+1], x[-N/2+2], ... x[-1], x[0], x[1], ... x[N/2] }

those are your "control points".  and you are always interpolating between
x[0] and x[1].

also FYI, linear interpolation is 1st order Lagrange, 1st order Hermite, and
1st order B-spline.  they're all the same at order=1.  these polynomials
start diverging in definition at order=2 (or order=3 if you stick to odd
order).

> I don't know how to decide the coefficients of B-spline polynomial.
> By my limited knowledge about B-spline, it's generated by the knot vector
> T = { t0, t1, t2, ..., tm } and the control points P = { P0, P1, ..., Pn }
> ( Refer to http://mathworld.wolfram.com/B-Spline.html )

in the sense that Duane and i and Olli use B-spline, the control points are
synonymous with the input data points.  i believe, since there is a unique
(N-1)th order polynomial that will precisely hit all N points given it (that
is the Lagrange polynomial) and if the control points of the B-spline are
defined in such a way that the internal knots all hit your input points, the
resulting net polynomial (from input points to polynomial coefficients) of
the B-spline will be identical to the Lagrange.  someone here on comp.dsp is
welcome to dispute this, because this is not something i proved explicitly.

> Please help me about how to generate the coefficients of B-spline
> interpolator for arbitrary sampling rate conversion (used for both
> upsampling and downsampling).

for third order, it's shown in the paper.  i would not recommend B-spline of
anything higher order for sample interpolation.  in fact, unless memory is a
real problem (and you cannot spare 8K word), i would recommend linear
interpolation between sinc-like entries in a look-up table.  if you *must*
not use any table look-up (presumably because you don't have the memory to
spare), i would recommend Hermite polynomial interpolation.

try Googling and Google Groups.  such as this thread:

http://groups.google.com/group/comp.dsp/browse_frm/thread/aa2be6819f584d85


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

Hi Robert and all,
Thanks for your information!
I've studied your paper, and have one question about B-spline polynomial.
For the 6-point 5th-order B-spline polynomial, are the coefficients
adjustable for different transition bandwidth and stopband attenuation?
I don't know how to decide the coefficients of B-spline polynomial.
By my limited knowledge about B-spline, it's generated by the knot vector
T = { t0, t1, t2, ..., tm } and the control points P = { P0, P1, ..., Pn
}
( Refer to http://mathworld.wolfram.com/B-Spline.html )

Please help me about how to generate the coefficients of B-spline
interpolator for arbitrary sampling rate conversion (used for both
upsampling and downsampling).

Thanks again!

Sincerely yours,
Light Hsu


>in article 68OdnRPFy8CHPu3enZ2dnUVZ_tCdnZ2d@giganews.com, lighthsu at
>lighthsu2004@yahoo.com.tw wrote on 11/08/2005 08:07:
>
>> I'm working on a DSP project, which needs an arbitrary sampling rate
>> converter.
>> I searched several interpolation algorithms - windowed-sinc, Lagrange,
and
>> B-Spline. However, I can't determine which algorithm is suitable for
>> low-ordered interpolation filter.
>> According to my understanding, the performance of windowed-sinc
>> interpolation(with table look-up) can be easily estimated by the
>> specification of window(filter order, transition bandwidth, and
stopband
>> attenuation are trade-off). But I can't estimate the performace of
>> Lagrange and B-Spline interpolater.
>> Is there any document or paper about the performance of Lagrange and
>> B-Spline interpolaters? I need the informations about filter order,
>> transition bandwidth, and stopband attenuation of these interpolation
>> algorithms.
>
>Duane Wise and i did a paper back in '97 about it.  i'll email you a pdf
>copy.  Olli Niemita has an improvement on it that is available at:
>
>   http://www.biochem.oulu.fi/~oniemita/dsp/deip.pdf
>
>you might want to also look at Hermite and other "osculating" polynomial
>interpolation.  essentially, for an Nth order B-spline, in the limit,
you'll
>get 6.02*(N+1) dB S/N ratio for each octave of oversampling (that is the
>upsampled Nyquist/Bandwidth).
>
>now, in my opinion, for an arbitrary sampling rate conversion ratio, i
think
>the simplest and best method is to use a lookup table based (Kaiser
windowed
>sinc or alternatively an optimally designed LPF) interpolation with a
high
>but finite upsampling ratio and then use linear interpolation in
between.
>
>i try to be a little more rigorous about that in
>
>   http://groups.google.com/group/comp.dsp/msg/f9e0ad7b430bc653?fwc=1
>
>
>-- 
>
>r b-j                  rbj@audioimagination.com
>
>"Imagination is more important than knowledge."
>
>
>

in article 1131485494.187399.48850@g44g2000cwa.googlegroups.com, Ron N. at
rhnlogic@yahoo.com wrote on 11/08/2005 16:31:

> robert bristow-johnson wrote:
>> now, in my opinion, for an arbitrary sampling rate conversion ratio, i think
>> the simplest and best method is to use a lookup table based (Kaiser windowed
>> sinc or alternatively an optimally designed LPF) interpolation with a high
>> but finite upsampling ratio and then use linear interpolation in between.
> 
> You're mixing an interpolation formula and an implementation optimization.

when i say the "simplest" way of doing something, i am not differentiating.
i'm thinking about the bottom line.

>  The simplest method would be to simply use a
> (Kaiser) windowed sinc interpolation formula directly.

it's "simple" computing a Kaiser window on the fly?  or doing the division
required in a sinc() on the fly?

> The decision on whether  to precalculate and store some number
> of coefficients or to interpolate from a smaller number coefficients
> of interpolation should be based on whether or not the needed
> performance and on the amount of  available memory in your
> particular implementation.

it does depend on how cheap memory is.  in most apps, that i know of, memory
is cheap enough that 8K word is not so bad (and you still have the
computational hit of computing *two* interpolated values and linearly
interpolating between the two for an arbitrary step size).  maybe memory
won't be so cheap for FPGAs or similar and you can fritter away a lot of
real-time instruction cycles calculating some nasty stuff.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."