sample rate conversion: Windowed-Sinc v.s. Lagrange v.s. B-Spline?

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

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."

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.


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

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."

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 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."

"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. 

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: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. 

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."