Discussion: Interpolation Can of Worms

To promote some interesting discussion I thought I would raise the
following question:

Possibly as part of a sequence of processing, to interpolate a sampled
sequence by 2 is it correct to keep the original samples and derive the
in-between samples, or replace the original samples in the process of
interpolating the signal.

Dirk Bell
DSP Consultant

dbell wrote:
> To promote some interesting discussion I thought I would raise the
> following question:
> 
> Possibly as part of a sequence of processing, to interpolate a sampled
> sequence by 2 is it correct to keep the original samples and derive the
> in-between samples, or replace the original samples in the process of
> interpolating the signal.

My gut tells me that the first option, being more tightly constrained, 
is in general more difficult than the second. I can see instances in 
which the first option is more desirable than the second, if only for 
esthetics. I therefore arrive at the Universal Answer: it depends.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jerry Avins wrote:
> dbell wrote:
> 
>> To promote some interesting discussion I thought I would raise the
>> following question:
>>
>> Possibly as part of a sequence of processing, to interpolate a sampled
>> sequence by 2 is it correct to keep the original samples and derive the
>> in-between samples, or replace the original samples in the process of
>> interpolating the signal.
> 
> 
> My gut tells me that the first option, being more tightly constrained, 
> is in general more difficult than the second. I can see instances in 
> which the first option is more desirable than the second, if only for 
> esthetics. I therefore arrive at the Universal Answer: it depends.
> 
> Jerry

More precisely:  It depends on your application.

I think that the only linear interpolation that you could use that would 
give you output points that match input points would be a 2-point, which 
doesn't have the best frequency domain characteristics.  Fancier linear 
filters will tend to let other points bleed into the 'current' one, 
violating your rule.

If you want to interpolate over more than two points _and_ get your 
exact match you'll either need to have a different rule for generating 
your in-between points, which is a shift-varying filter*, or you'd have 
to use something that's just plain nonlinear.  Either of these solutions 
may be better for the problem at hand, but might have bad effects, too.

So in the end (if it mattered) you'd have to investigate different 
methods, and choose the best one.

* I was going to say "or you'd have to use something like splines, which 
is nonlinear" -- but I think that for an even sample rate interpolating 
with splines would end up being shift-varying, but linear.  Hmm.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Posting from Google?  See http://cfaj.freeshell.org/google/

"Applied Control Theory for Embedded Systems" came out in April.
See details at http://www.wescottdesign.com/actfes/actfes.html

"dbell" <bellda2005@cox.net> wrote in news:1158072374.880336.237110
@e3g2000cwe.googlegroups.com:

> To promote some interesting discussion I thought I would raise the
> following question:
> 
> Possibly as part of a sequence of processing, to interpolate a sampled
> sequence by 2 is it correct to keep the original samples and derive the
> in-between samples, or replace the original samples in the process of
> interpolating the signal.
> 
> Dirk Bell
> DSP Consultant
> 

I like all the "depends" answers, but the only reason I could see for the 
latter would be if you absolutely need the result to be differentiable for 
a certain number of iterations.

It also depends on the interpolator you're using.  If you're using some 
sort of high-order piece of nastiness that might ring, you might be giving 
up any semblance of reality if you toss the original data.

-- 
Scott
Reverse name to reply

Tim Wescott wrote:

> Jerry Avins wrote:
>> dbell wrote:
>> 
>>> To promote some interesting discussion I thought I would raise the
>>> following question:
>>>
>>> Possibly as part of a sequence of processing, to interpolate a sampled
>>> sequence by 2 is it correct to keep the original samples and derive the
>>> in-between samples, or replace the original samples in the process of
>>> interpolating the signal.
>> 
>> 
>> My gut tells me that the first option, being more tightly constrained,
>> is in general more difficult than the second. I can see instances in
>> which the first option is more desirable than the second, if only for
>> esthetics. I therefore arrive at the Universal Answer: it depends.
>> 
>> Jerry
> 
> More precisely:  It depends on your application.
> 
> I think that the only linear interpolation that you could use that would
> give you output points that match input points would be a 2-point, which
> doesn't have the best frequency domain characteristics.  Fancier linear
> filters will tend to let other points bleed into the 'current' one,
> violating your rule.

Perhaps I misunderstood what you meant by 2-point, but any filter with
impulse response of the form

   h[n] = {..., g[-2], 0, g[-1], 0, g[0], 1, g[1], 0, g[2], 0, g[3], ...}

will match the input points with the output points.


-- 
Jani Huhtanen
Tampere University of Technology, Pori

Jani Huhtanen wrote:

> Tim Wescott wrote:
> 
> 
>>Jerry Avins wrote:
>>
>>>dbell wrote:
>>>
>>>
>>>>To promote some interesting discussion I thought I would raise the
>>>>following question:
>>>>
>>>>Possibly as part of a sequence of processing, to interpolate a sampled
>>>>sequence by 2 is it correct to keep the original samples and derive the
>>>>in-between samples, or replace the original samples in the process of
>>>>interpolating the signal.
>>>
>>>
>>>My gut tells me that the first option, being more tightly constrained,
>>>is in general more difficult than the second. I can see instances in
>>>which the first option is more desirable than the second, if only for
>>>esthetics. I therefore arrive at the Universal Answer: it depends.
>>>
>>>Jerry
>>
>>More precisely:  It depends on your application.
>>
>>I think that the only linear interpolation that you could use that would
>>give you output points that match input points would be a 2-point, which
>>doesn't have the best frequency domain characteristics.  Fancier linear
>>filters will tend to let other points bleed into the 'current' one,
>>violating your rule.
> 
> 
> Perhaps I misunderstood what you meant by 2-point, but any filter with
> impulse response of the form
> 
>    h[n] = {..., g[-2], 0, g[-1], 0, g[0], 1, g[1], 0, g[2], 0, g[3], ...}
> 
> will match the input points with the output points.
> 
> 
Well I'll be damned.  That's obvious.

The nice thing about always doing my newsgroup stuff in the morning is 
that I can claim that I'm not awake yet.  Certainly that must be the 
case here.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Posting from Google?  See http://cfaj.freeshell.org/google/

"Applied Control Theory for Embedded Systems" came out in April.
See details at http://www.wescottdesign.com/actfes/actfes.html

That would be a halfband filter.

Dirk

Jani Huhtanen wrote:
> Tim Wescott wrote:
>
> > Jerry Avins wrote:
> >> dbell wrote:
> >>
> >>> To promote some interesting discussion I thought I would raise the
> >>> following question:
> >>>
> >>> Possibly as part of a sequence of processing, to interpolate a sampled
> >>> sequence by 2 is it correct to keep the original samples and derive the
> >>> in-between samples, or replace the original samples in the process of
> >>> interpolating the signal.
> >>
> >>
> >> My gut tells me that the first option, being more tightly constrained,
> >> is in general more difficult than the second. I can see instances in
> >> which the first option is more desirable than the second, if only for
> >> esthetics. I therefore arrive at the Universal Answer: it depends.
> >>
> >> Jerry
> >
> > More precisely:  It depends on your application.
> >
> > I think that the only linear interpolation that you could use that would
> > give you output points that match input points would be a 2-point, which
> > doesn't have the best frequency domain characteristics.  Fancier linear
> > filters will tend to let other points bleed into the 'current' one,
> > violating your rule.
>
> Perhaps I misunderstood what you meant by 2-point, but any filter with
> impulse response of the form
>
>    h[n] = {..., g[-2], 0, g[-1], 0, g[0], 1, g[1], 0, g[2], 0, g[3], ...}
>
> will match the input points with the output points.
> 
> 
> -- 
> Jani Huhtanen
> Tampere University of Technology, Pori

dbell wrote:
> To promote some interesting discussion I thought I would raise the
> following question:
> 
> Possibly as part of a sequence of processing, to interpolate a sampled
> sequence by 2 is it correct to keep the original samples and derive the
> in-between samples, or replace the original samples in the process of
> interpolating the signal.
> 
> Dirk Bell
> DSP Consultant
> 

Hi Dirk,

I think the only time the latter would be preferable is if the signal
needs to be filtered with a corner frequency other than the original
folding frequency.  Or if development time is more precious than cpu
cycles :)


As for the former ... Yes! Increasing the rate by two with anti-aliasing
can be accomplished by interleaving the original samples with the
sequence delayed by one-half sample.

I've used this with great results.

As others in this thread have mentioned, half-band filters are superb
for this application.

Convolving the original signal with the odd coefficients from a
half-band filter will create this half-sample delayed signal.

Works good with fast convolution too, at least on a GPP.

FWIW, This makes a good first stage in a multirate interpolator.  The
subsequent stages can use much shorter FIRs since they are nicely
band-limited and the anti-aliasing filters can have wide transition
bands. There is no call for fast convolution on anything but the first
stage.


-- Mark Borgerding

dbell skrev:
> To promote some interesting discussion I thought I would raise the
> following question:
>
> Possibly as part of a sequence of processing, to interpolate a sampled
> sequence by 2 is it correct to keep the original samples and derive the
> in-between samples, or replace the original samples in the process of
> interpolating the signal.

I generally tend to prefer the "intuitively acceptable" method
wherever possible. I always use the simple, intuitive approaches
first to get a "baseline" of how a method works, and then
test out whatever modifications. The idea is to get a feel for
when a particular method works, and when it doesn't.
Hopefully, one is able to make informed choises about which
method to use with what problem.

Besides, it is an easier "sell" to keep the original samples
and fill in the missing ones. From a pedagogical point of
view (maybe during a project progress meeting with
a paying customer present) it is easy to see -- and for the
customer to accept -- the old samples with some new ones
in between, as opposed to all "new" samples.

Of course, at a later stage you may find it convenient to
combine an interpolation step and, say, a subsequent
filtering step into one block, but in that case you can always
say that "the interpolation + filter sequence has been combined
into one operation", which may be easier for the customer to
keep track of.

Rune

dbell wrote:
> 
> To promote some interesting discussion I thought I would raise the
> following question:
> 
> Possibly as part of a sequence of processing, to interpolate a sampled
> sequence by 2 is it correct to keep the original samples and derive the
> in-between samples, or replace the original samples in the process of
> interpolating the signal.


I would like to contradict what everyone else in this thread
has said ;-). I prefer the second method or rather I consider the
first method wrong and here's why.

So, for the upsample by 2 case lets use:

    fs -- source sample rate
	fd -- desitnation sample rate (fs * 2)

Consider a source signal with frequency components all the
way up to a frequency of

     fx = 0.5 * fs - epsilon

where epsilon is orders of magnitude smaller than fs.

Now upsample the source signal by inserting a zero valued sample
between each of the original samples and filter the resulting
signal (at sample rate of fd) using a half band FIR anti aliasing
filter of the form:

    h[n] = {..., g[-2], 0, g[-1], 0, g[0], 1, g[1], 0, g[2], 0, g[3], ...}

Notice however than the frequency response of this filter has
a passband magnitude response of 2, a -3dB point occuring at
0.5 of the source sample rate. This looks something like
(ASCII art):

    +---------------------     -3dB point
    |                     \  /
    |                      \
    |                      |\
    |                      | \
    |                      |  \
    |                      |   \
    |                      |    \
    |                      |     \
    |                      |      \
    |                      |       \
    +----------------------+----------------------+-
                     fs/2                        fd/2


So whats the problem here? Well remember that source frequency at a
frequency of fx? Well, that frequency gets aliased to 

    fx1 = 0.5 * fs + epsilon

and the attenuation of the anti aliasing filter at fx1 is only about
3dB. Now normally, fs/2 is 22.05kHz or more so that the original 
fx and the alias frequency fx1 are both out of hearing range. However,
they do exist and at least one of them shouldn't be there. These 
alias frequencies should be obvious when upsample from say 8kHz to
16kHz.

As far as I am concerned the filter should look like this:

    +---------------  
    |               \ 
    |                \
    |                 \
    |                  \
    |                   \
    |                    \     target stopband attenuation
    |                     \  /  
    |                      |
    |                      |\
    |                      | \
    +----------------------+----------------------+-
                     fs/2                        fd/2


The anti-aliasing filters in Secret Rabbit Code

    http://www.mega-nerd.com/SRC/

are designed like this.

Erik



Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo
+-----------------------------------------------------------+
"It has been discovered that C++ provides a remarkable facility
for concealing the trival details of a program -- such as where 
its bugs are." -- David Keppel