interpolation accuracy, oversampling and fractional interpolation

Viognier wrote:
>
> When resampling a sequence to an output sample rate equal to a rational
> number times the input sample rate, (FSout = (P/Q) * FSin), polyphase
> filtering is the method of choice.  But when the output sample rate is
> an irrational multiple of the input rate (FSout = r * FSin), one cannot
> use the polyphase filtering. That's when spline methods may be helpful.

i kinda agree with Eric that polyphase interpolation (essentially
designing an optimal LPF and keeping the impulse response in a table)
is preferable to spline or polynomial interpolation for any bandlimited
reconstruction but where i might agree with Viognier is because of the
cost.  you can't have a polyphase table that has all infinite possible
fractional delays.  but you *can* evaluate a polynomial for any
fractional delay expressible in the machine arithmetic.  but if you can
afford some memory for the polyphase table, you can use a polynomial
interpolation between entries of that table.

r b-j

Martin Eisenberg wrote:
> robert bristow-johnson wrote:
> > Mark wrote:
>
> > you can compare the merits by recognizing that, even for
> > spline/polynomial interpolation, all methods can be represented
> > as convolving the string of ideal impulses (weighted by the
> > sample values) with the corresponding interpolation function
> > which is an impulse response of a LPF.  then you can judge which
> > LPF is better for the application.
>
> >> It seems to me that in the case of the audio method.. if the
> >> low pass filter were "perfect" in rejection of the image
> >> frequencies, the insert sample/filter method provides "perfect"
> >> results.  By comparison, the linear, cubic, spline methods are
> >> always imperfect.
> >
> > so is any FIR or causal IIR.
>
> What's more, don't the IRs of interpolating splines converge to the
> sinc function at infinite order?

not B-splines (as i understand the definition) but any polynomial that
interpolates directly through the given (uniformly spaced) samples.
since the IR corresponding to Lagrange or Hermite polynomials has to be
1 at t=0 and 0 for every other sample time, i would think that this
function would become a sinc() function in the limit.

r b-j

Eric Jacobsen wrote:

> I'd still disagree, having used polyphase filters for many years for
> locking symbol clocks in digital recievers, with no measurable loss.
>

I can see using polyphase to compensate for receiver sample clock phase
offset. Can it be used to compensate for receiver sample clock
frequency offset too ( as in the case when a fixed crystal asynchronous
ADC is being used)?

-V

On Oct 11, 2:46 pm, "robert bristow-johnson"
<r...@audioimagination.com> wrote:
> Viognier wrote:
>
> > When resampling a sequence to an output sample rate equal to a rational
> > number times the input sample rate, (FSout = (P/Q) * FSin), polyphase
> > filtering is the method of choice.  But when the output sample rate is
> > an irrational multiple of the input rate (FSout = r * FSin), one cannot
> > use the polyphase filtering.

Note that this is confusing the method of sample interpolation
with the functional approximation of a filter kernel.  You
can also directly compute or approximate the coefficients for
any fractional delay expressible in the machine arithmetic, at
some computational cost for a given accuracy.  Whether linear
interpolation from a table lookup is the best method for the
functional approximation is a completely separate subject.
For a "one shot" interpolation within a small set of points,
and using a simple interpolation kernel (von Hann windowed sinc,
for instance), it can be faster to compute a few individual
interpolation coefficients directly using a floating point
math library rather than pre-computing some big table, only
to never use any table entries without interpolation.


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

On Oct 9, 7:57 am, "Mark" <makol...@yahoo.com> wrote:
> I have always been confused about the relationship between this kind of
> interpolation (linear, cubic, spline etc) and the kind used in DSP
> audio work for up sampling.  In audio up-sampling we  just insert zero
> value samples and then pass the result through a low pass filter to
> remove the image frequencies.

The DSP kind of interpolation usually assumes the the data is
from a bandlimited signal (or "close enough").  Other polynomial
types of interpolation usually have an error bounded by the
existance, continuity, or peak magnitude of some number of
derivatives of the function.

How are these two different types of constraints related?


-- 
rhn A.T nicholson d.0.t C-o-M

Ron N. wrote:
>
> Note that this is confusing the method of sample interpolation
> with the functional approximation of a filter kernel.  You
> can also directly compute or approximate the coefficients for
> any fractional delay expressible in the machine arithmetic, at
> some computational cost for a given accuracy.  Whether linear
> interpolation from a table lookup is the best method for the
> functional approximation is a completely separate subject.
> For a "one shot" interpolation within a small set of points,
> and using a simple interpolation kernel (von Hann windowed sinc,
> for instance), it can be faster to compute a few individual
> interpolation coefficients directly using a floating point
> math library rather than pre-computing some big table, only
> to never use any table entries without interpolation.

strictly speaking, i agree with you, Ron. because you said "for a given
accuracy".  but i would say that directly computing the coefficients
for an optimally designed (say, using Parks-McClellan) LPF for
bandlimited interpolation in a DSP real-time is not realistic.
practically speaking, if you want your filter kernel to be what comes
out of P-McC (often called "remez" by the MATLABers) or a similar
optimizing program, then the method has to be some kind of table lookup
and, if you need arbitrary fractional delays that do not correspond
exactly to any table entry, you gotta interpolate using some function
that has infinite resolution.

r b-j

For high performance interpolator, take a look at the thesis of "Jussi 
Vesma". Also he has published numerous paper in IEEE about Polynomial-Based 
interpolation.

If someone tell you that you cannot get good performance with a polymonial 
interpolator, send them this link:
www.cs.tut.fi/kurssit/83080/Pol_Interpol2004.pdf   (see fig 25)


LM

"renaudin" <alsaeed86@gmail.com> wrote in message 
news:g-6dnVM345-viLfYnZ2dnUVZ_vidnZ2d@giganews.com...
> Hi all,
>
> Interpolation of a sampled signal x(n) to generate an up-sampled signal
> y(n) can be represented mathematically as:
>
> y(n) = x(n/L) /* here L is the intrpolation factor.
>
> Regardless of the type of interpolation, if we increase the value of 'L'
> weather it will increase the accuracy of interpolation process?
>
> Whats about the fractional Interpolation/Decimation factors how to deal
> with them?
>
> Thanks in advance for the discussion and comments.
>
> Renaudin
> 

robert bristow-johnson wrote:
> Viognier wrote:
> >
> > When resampling a sequence to an output sample rate equal to a rational
> > number times the input sample rate, (FSout = (P/Q) * FSin), polyphase
> > filtering is the method of choice.  But when the output sample rate is
> > an irrational multiple of the input rate (FSout = r * FSin), one cannot
> > use the polyphase filtering. That's when spline methods may be helpful.
>
> i kinda agree with Eric that polyphase interpolation (essentially
> designing an optimal LPF and keeping the impulse response in a table)
> is preferable to spline or polynomial interpolation for any bandlimited
> reconstruction but where i might agree with Viognier is because of the
> cost.  you can't have a polyphase table that has all infinite possible
> fractional delays.  but you *can* evaluate a polynomial for any
> fractional delay expressible in the machine arithmetic.  but if you can
> afford some memory for the polyphase table, you can use a polynomial
> interpolation between entries of that table.
>
> r b-j


I'm just starting to look at this interpolation problem, but i'm
confused by the terminology that you're using in the thread.  When you
refer to a low pass polyphase interpolation filter, what are you
actually talking about?  The ideal brickwall bandlimiting filter aka
the sinc function in the time domain truncated to the length of your
FIR (windowed if you prefer)?  I know that you can use any type of low
pass filter to perform the interpolation, but what parameters influence
the design?

In addition, I have one comment regards using polynomial or splines for
the interpolation, it seems to me that the FIR polyphase method
requires that a new set of filter coefficients must be generated for
each change in, say, the fractional delay, hence the lookup table that
Eric talked about.  However, when using polynomial interpolation via a
Farrow type FIR structure, then only one parameter is used to change
the interpolation and approximate the fractional delay.  This is what
LM posted a link to further down in this thread and what i had  been
looking at implementing.  The latter method seems to me to be more
flexible and efficient because there isn't any swapping in and out of
filter coefficients.

Perhaps i'm missing something important here?


col

On Oct 12, 6:08 am, c...@hotmail.com wrote:
> robert bristow-johnson wrote:
> > Viognier wrote:
>
> > > When resampling a sequence to an output sample rate equal to a rational
> > > number times the input sample rate, (FSout = (P/Q) * FSin), polyphase
> > > filtering is the method of choice.  But when the output sample rate is
> > > an irrational multiple of the input rate (FSout = r * FSin), one cannot
> > > use the polyphase filtering. That's when spline methods may be helpful.
>
> > i kinda agree with Eric that polyphase interpolation (essentially)
> > designing an optimal LPF and keeping the impulse response in a table)
> > is preferable to spline or polynomial interpolation for any bandlimited
> > reconstruction but where i might agree with Viognier is because of the
> > cost.  you can't have a polyphase table that has all infinite possible
> > fractional delays.  but you *can* evaluate a polynomial for any
> > fractional delay expressible in the machine arithmetic.  but if you can
> > afford some memory for the polyphase table, you can use a polynomial
> > interpolation between entries of that table.
>
> > r b-jI'm just starting to look at this interpolation problem, but i'm
> confused by the terminology that you're using in the thread.  When you
> refer to a low pass polyphase interpolation filter, what are you
> actually talking about?  The ideal brickwall bandlimiting filter aka
> the sinc function in the time domain truncated to the length of your
> FIR (windowed if you prefer)?  I know that you can use any type of low
> pass filter to perform the interpolation, but what parameters influence
> the design?
>
> In addition, I have one comment regards using polynomial or splines for
> the interpolation, it seems to me that the FIR polyphase method
> requires that a new set of filter coefficients must be generated for
> each change in, say, the fractional delay, hence the lookup table that
> Eric talked about.  However, when using polynomial interpolation via a
> Farrow type FIR structure, then only one parameter is used to change
> the interpolation and approximate the fractional delay.  This is what
> LM posted a link to further down in this thread and what i had  been
> looking at implementing.  The latter method seems to me to be more
> flexible and efficient because there isn't any swapping in and out of
> filter coefficients.

Aren't the Farrow stucture and the table lookup, after the
algorithms are unwound, essentially just 2 different
way of generating each set of filter coefficients?  It comes
down to a trade-off between efficiency and quality of two
different methods of function estimation of a filter kernel
for a given delay.  Table look-up, polynomial approximation,
a combination of the two, or some other method of functional
approximation (e.g. calculate all the trig fuctions using
cordic inside the system math libraries, etc.)


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

On 11 Oct 2006 14:46:25 -0700, "robert bristow-johnson"
<rbj@audioimagination.com> wrote:

>
>Viognier wrote:
>>
>> When resampling a sequence to an output sample rate equal to a rational
>> number times the input sample rate, (FSout = (P/Q) * FSin), polyphase
>> filtering is the method of choice.  But when the output sample rate is
>> an irrational multiple of the input rate (FSout = r * FSin), one cannot
>> use the polyphase filtering. That's when spline methods may be helpful.
>
>i kinda agree with Eric that polyphase interpolation (essentially
>designing an optimal LPF and keeping the impulse response in a table)
>is preferable to spline or polynomial interpolation for any bandlimited
>reconstruction but where i might agree with Viognier is because of the
>cost.  you can't have a polyphase table that has all infinite possible
>fractional delays.  but you *can* evaluate a polynomial for any
>fractional delay expressible in the machine arithmetic.  but if you can
>afford some memory for the polyphase table, you can use a polynomial
>interpolation between entries of that table.
>
>r b-j

As I mentioned elsewhere, in a practical system with fixed precision
there is a number of phases beyond which the coefficients won't change
when trying to increase the resolution.   I looked at this years ago
when designing a polyphase for a comm receiver and trying to answer
the question of how many phases did we really need to not lose any
performance.

In other words, for an example system that uses 8-bit precision for
the coefficients there will be some minimum phase change beyond which
the change in phase will result in coefficient changes that are below
the LSB in the current coefficients.

Surprisingly, I found that for our case that meant that with a very
practical number of phases we had essentially infinite phase
precision, or at least within the precision we were using one would
never tell the difference.

Eric Jacobsen
Minister of Algorithms, Intel Corp.
My opinions may not be Intel's opinions.
http://www.ericjacobsen.org