# An interpolation question

Started by February 6, 2006
```Hi Guys,

I was re-thinking an interpolation topic and
wondered if any of you have looked into something.

Ya' know how we usually implement interpolation
(by an integer factor) by inserting zero-valued
samples in between some original time sequence,
and then we pass the "zero-stuffed" sequence
through a lowpass filter whose output is the
desired "interpolated" sequence?

That is, if the original time sequence is

*
*
*

Time -->

After the zero stuffing (for interpolation by, say, 3)
the extended sequence would be:

*
*
*
** ** **

Time -->

If instead of inserting the zero-valued samples we
decided to upsample the original sequence by
using "repeat samples" (a zero-order hold process)
so that the extended sequence would be:

***
***
***

Time -->

If my modeling is correct, the "image" spectral
components of the "repeated samples" extended sequence
are attenuated by a sin(x)/x envelope.  This means the
the "image" spectral components that we want to attenuate
by lowpass filtering are reduced in magnitude *before*
the extended sequence is applied to a lowpass filter.

(As far as I can tell the upsampling by "repeated samples"
scheme induces no phase distortion in the extended
sequence.)

So, after lowpass filtering,
the "repeated samples" extended sequence is a more
accurate interpolated sequence than if we had used the
traditional inserting zero-valued samples scheme
prior to lowpass filtering.

The only disadvantage that I can see in the upsampling by
"repeated samples" method is that the lowpass filter
must compensate for the droop in the sin(x)/x freq
response envelope near zero Hz.  That's not really a big
problem, but I'm guessing that the droop in the sin(x)/x
freq envelope of the upsampled sequence means that
half-band filters (with their alternating zero-valued
coefficients) can't be used as lowpass filters when we're
decimating by 2 raised to some integer factor (4, 8, 16,...).

Have any of you guys "looked into this"?

Thanks,
[-Rick-]

```
```
Rick Lyons wrote:

> Hi Guys,
>
>   I was re-thinking an interpolation topic and
> wondered if any of you have looked into something.
>
> Ya' know how we usually implement interpolation
> (by an integer factor) by inserting zero-valued
> samples in between some original time sequence,

[...]

> If instead of inserting the zero-valued samples we
> decided to upsample the original sequence by
> using "repeat samples" (a zero-order hold process)

[...]

> The only disadvantage that I can see in the upsampling by
> "repeated samples" method is that the lowpass filter
> must compensate for the droop in the sin(x)/x freq
> response envelope near zero Hz.

> Have any of you guys "looked into this"?
>

This is a very known topic from the ABC books on the DSP. If you apply
the N-th order interpolation polynomial, the result of upsapmling is
equivalent to be lowpassed with the filter of the order N.

The main disadvantage is that you can't use a polyphase filter in this
case. The smoothing filter has to run on *all* samples, not just nonzero
samples. The tradeoff in the computation is not justified by the
additional smoothing due to the interpolation, so usually there is no
point to do it this way.

Vladimir Vassilevsky

DSP and Mixed-Up Signal Design Consultant

http://www.abvolt.com

```
```Rick Lyons wrote:
> Hi Guys,
>
>   I was re-thinking an interpolation topic and
> wondered if any of you have looked into something.
>
> Ya' know how we usually implement interpolation
> (by an integer factor) by inserting zero-valued
> samples in between some original time sequence,
> and then we pass the "zero-stuffed" sequence
> through a lowpass filter whose output is the
> desired "interpolated" sequence?
>
> That is, if the original time sequence is
>
>     *
>      *
>       *
>
>      Time -->
>
> After the zero stuffing (for interpolation by, say, 3)
> the extended sequence would be:
>
>     *
>        *
>           *
>      ** ** **
>
>        Time -->
>
> If instead of inserting the zero-valued samples we
> decided to upsample the original sequence by
> using "repeat samples" (a zero-order hold process)
> so that the extended sequence would be:
>
>     ***
>        ***
>           ***
>
>        Time -->
>
>
> If my modeling is correct, the "image" spectral
> components of the "repeated samples" extended sequence
> are attenuated by a sin(x)/x envelope.  This means the
> the "image" spectral components that we want to attenuate
> by lowpass filtering are reduced in magnitude *before*
> the extended sequence is applied to a lowpass filter.
>
> (As far as I can tell the upsampling by "repeated samples"
> scheme induces no phase distortion in the extended
> sequence.)
>
> So, after lowpass filtering,
> the "repeated samples" extended sequence is a more
> accurate interpolated sequence than if we had used the
> traditional inserting zero-valued samples scheme
> prior to lowpass filtering.
>
> The only disadvantage that I can see in the upsampling by
> "repeated samples" method is that the lowpass filter
> must compensate for the droop in the sin(x)/x freq
> response envelope near zero Hz.  That's not really a big
> problem, but I'm guessing that the droop in the sin(x)/x
> freq envelope of the upsampled sequence means that
> half-band filters (with their alternating zero-valued
> coefficients) can't be used as lowpass filters when we're
> decimating by 2 raised to some integer factor (4, 8, 16,...).
>
> Have any of you guys "looked into this"?

The phase is shifted relative to zero stuffing, from
40000   44444
here ^ to here ^.  The effect is precisely that of a zero-order hold for
the simple reason that it is one. Why do you feel that the effect at
zero Hz is more pronounced than at the old f_s?

Jerry
--
Engineering is the art of making what you want from things you can get.
&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;
```
```In fact what you describe is mathematically equivalent to zero-stuffing
the signal and then filtering it with an FIR filter with all
coefficients equal to one (and the length of the filter equal to the
interpolation factor). This is called a hold interpolator.

You can even think of it as a polyphase interpolator where each
polyphase branch has a single coefficient and it is equal to one.

The sin(x)/x envelope is a lousy lowpass filter, but it is a lowpass
filter and does the job to a certain extent. You could compensate for
the sin(x)/x with another filter, but better yet is to precompensate.
Typically you would a hold interpolator like this at final stage of a
multistage interpolator, when the sin(x)/x error will be small and where
you are operating at a high-rate and you want to keep computational cost
down by not using any multipliers for the interpolation. So you can use
a lowpass filter with a passband shape to compensate for the hold
interpolator in a previous interpolation stage.

If this sounds a whole lot like CIC it's because it's the same thing. In
fact a single-stage CIC is nothing but a hold interpolator.

This makes implementing a CIC interpolator a little cheaper by replacing
the innermost comb-upsampler-integrator set with a simple hold interpolator.

In fact, a cheap way to implement a multiplierless linear interpolator?
use a 2-stage CIC interpolator and replace the innermost
comb-upsampler-integrator set with a simple hold interpolator. It will
cost just 2 adders and 2 delays.

- Ricardo.

Rick Lyons wrote:
> Hi Guys,
>
>   I was re-thinking an interpolation topic and
> wondered if any of you have looked into something.
>
> Ya' know how we usually implement interpolation
> (by an integer factor) by inserting zero-valued
> samples in between some original time sequence,
> and then we pass the "zero-stuffed" sequence
> through a lowpass filter whose output is the
> desired "interpolated" sequence?
>
> That is, if the original time sequence is
>
>     *
>      *
>       *
>
>      Time -->
>
> After the zero stuffing (for interpolation by, say, 3)
> the extended sequence would be:
>
>     *
>        *
>           *
>      ** ** **
>
>        Time -->
>
> If instead of inserting the zero-valued samples we
> decided to upsample the original sequence by
> using "repeat samples" (a zero-order hold process)
> so that the extended sequence would be:
>
>     ***
>        ***
>           ***
>
>        Time -->
>
>
> If my modeling is correct, the "image" spectral
> components of the "repeated samples" extended sequence
> are attenuated by a sin(x)/x envelope.  This means the
> the "image" spectral components that we want to attenuate
> by lowpass filtering are reduced in magnitude *before*
> the extended sequence is applied to a lowpass filter.
>
> (As far as I can tell the upsampling by "repeated samples"
> scheme induces no phase distortion in the extended
> sequence.)
>
> So, after lowpass filtering,
> the "repeated samples" extended sequence is a more
> accurate interpolated sequence than if we had used the
> traditional inserting zero-valued samples scheme
> prior to lowpass filtering.
>
> The only disadvantage that I can see in the upsampling by
> "repeated samples" method is that the lowpass filter
> must compensate for the droop in the sin(x)/x freq
> response envelope near zero Hz.  That's not really a big
> problem, but I'm guessing that the droop in the sin(x)/x
> freq envelope of the upsampled sequence means that
> half-band filters (with their alternating zero-valued
> coefficients) can't be used as lowpass filters when we're
> decimating by 2 raised to some integer factor (4, 8, 16,...).
>
> Have any of you guys "looked into this"?
>
> Thanks,
> [-Rick-]
>
>
```
```R.Lyons@_BOGUS_ieee.org (Rick Lyons) writes:
> [...]
> If my modeling is correct, the "image" spectral components of
> the "repeated samples" extended sequence are attenuated by a
> sin(x)/x envelope.  This means the the "image" spectral components
> that we want to attenuate by lowpass filtering are reduced in
> magnitude *before* the extended sequence is applied to a lowpass
> filter.
>
> (As far as I can tell the upsampling by "repeated samples" scheme
> induces no phase distortion in the extended sequence.)
>
> So, after lowpass filtering, the "repeated samples" extended
> sequence is a more accurate interpolated sequence than if we had
> used the traditional inserting zero-valued samples scheme prior to
> lowpass filtering.

Hi Rick,

I think you're correct. But, if I've interpreted things right, the
downside of the approach is that you lose the opportunity efficiently
compute the filter since you can no longer use polyphase filtering
(those intermediate samples are not zero anymore so you must multiply
them).

And I would think that any advantage gained in the extra sin(x)/x
attenuation is a net loss when compared with the loss of the ability
to implement a longer filter.

Does this sound right?
--
%  Randy Yates                  % "...the answer lies within your soul
%% Fuquay-Varina, NC            %       'cause no one knows which side
%%% 919-577-9882                %                   the coin will fall."
%%%% <yates@ieee.org>           %  'Big Wheels', *Out of the Blue*, ELO
http://home.earthlink.net/~yatescr
```
```Rick Lyons wrote:

> Hi Guys,
>
>   I was re-thinking an interpolation topic and
> wondered if any of you have looked into something.
>
> Ya' know how we usually implement interpolation
> (by an integer factor) by inserting zero-valued
> samples in between some original time sequence,
> and then we pass the "zero-stuffed" sequence
> through a lowpass filter whose output is the
> desired "interpolated" sequence?
>
> That is, if the original time sequence is
>
>     *
>      *
>       *
>
>      Time -->
>
> After the zero stuffing (for interpolation by, say, 3)
> the extended sequence would be:
>
>     *
>        *
>           *
>      ** ** **
>
>        Time -->
>
> If instead of inserting the zero-valued samples we
> decided to upsample the original sequence by
> using "repeat samples" (a zero-order hold process)
> so that the extended sequence would be:
>
>     ***
>        ***
>           ***
>
>        Time -->
>
>
> If my modeling is correct, the "image" spectral
> components of the "repeated samples" extended sequence
> are attenuated by a sin(x)/x envelope.  This means the
> the "image" spectral components that we want to attenuate
> by lowpass filtering are reduced in magnitude *before*
> the extended sequence is applied to a lowpass filter.
>
> (As far as I can tell the upsampling by "repeated samples"
> scheme induces no phase distortion in the extended
> sequence.)
>
> So, after lowpass filtering,
> the "repeated samples" extended sequence is a more
> accurate interpolated sequence than if we had used the
> traditional inserting zero-valued samples scheme
> prior to lowpass filtering.
>
> The only disadvantage that I can see in the upsampling by
> "repeated samples" method is that the lowpass filter
> must compensate for the droop in the sin(x)/x freq
> response envelope near zero Hz.  That's not really a big
> problem, but I'm guessing that the droop in the sin(x)/x
> freq envelope of the upsampled sequence means that
> half-band filters (with their alternating zero-valued
> coefficients) can't be used as lowpass filters when we're
> decimating by 2 raised to some integer factor (4, 8, 16,...).
>
> Have any of you guys "looked into this"?
>
> Thanks,
> [-Rick-]
>
>
Without repeated samples:

You 'zero stuff', then run the thing through a filter who's transfer
function is some polynomial in z^-1:

H(z) = a_0 + a_1 z^-1 + a_2 z^-2 ...

You get to choose any polynomial that you want, or to put it another way
my filter can have zeros anywhere I want.

With repeated samples:

Repeated samples is the same as zero stuffing then running through a
filter who's transfer function is

H_r(z) = 1 + z^-1 + ... + z^-(N-1).

This filter will have zeros at e^(j2pi/N), e^(j2pi 2/N) ...
e^(j2pi (N-1)/N).

Then you run it through the 'real' filter, which can have poles anywhere
you want.

In the end, you can have any filter that you want, as long as it has
zeros at e^(j2pi/N), e^(j2pi 2/N) ... e^(j2pi (N-1)/N).

Hmm.  I'll take zeros anywhere I want, instead of anywhere I want as
long as it includes some predefined set.

Unless!

I get some computational advantage out of the whole thing.

--

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com
```
```On Mon, 06 Feb 2006 17:35:57 -0500, Jerry Avins <jya@ieee.org> wrote:

(snipped)
>>
>> Have any of you guys "looked into this"?
>
>The phase is shifted relative to zero stuffing, from
>      40000   44444
>here ^ to here ^.  The effect is precisely that of a zero-order hold for
>the simple reason that it is one. Why do you feel that the effect at
>zero Hz is more pronounced than at the old f_s?
>
>Jerry

Hi Jerry,

Oh shoot.  I didn't understand your
question: "Why do you feel that the effect at
zero Hz is more pronounced than at the old f_s?"
I'm not sure what you mean by "the effect at
zero Hz".

[-Rick-]

```
```On Mon, 06 Feb 2006 17:45:25 -0500, Ricardo Losada
<Ric.Losada@mathworks.com> wrote:

Hi Ricardo,

>In fact what you describe is mathematically equivalent to zero-stuffing
>the signal and then filtering it with an FIR filter with all
>coefficients equal to one (and the length of the filter equal to the
>interpolation factor). This is called a hold interpolator.

Humm, I haven't heard that phrase "hold interpolator" before.
I'll have to search the Internet for it to
see what "pops up".
>
>You can even think of it as a polyphase interpolator where each
>polyphase branch has a single coefficient and it is equal to one.

OK, yes.

>The sin(x)/x envelope is a lousy lowpass filter, but it is a lowpass
>filter and does the job to a certain extent. You could compensate for
>the sin(x)/x with another filter, but better yet is to precompensate.
>Typically you would a hold interpolator like this at final stage of a
>multistage interpolator, when the sin(x)/x error will be small and where
>you are operating at a high-rate and you want to keep computational cost
>down by not using any multipliers for the interpolation.

Ah, now that's an interesting thought.

>So you can use
>a lowpass filter with a passband shape to compensate for the hold
>interpolator in a previous interpolation stage.
>
>If this sounds a whole lot like CIC it's because it's the same thing. In
>fact a single-stage CIC is nothing but a hold interpolator.
>
>This makes implementing a CIC interpolator a little cheaper by replacing
>the innermost comb-upsampler-integrator set with a simple hold interpolator.
>
>In fact, a cheap way to implement a multiplierless linear interpolator?
>use a 2-stage CIC interpolator and replace the innermost
>comb-upsampler-integrator set with a simple hold interpolator. It will
>cost just 2 adders and 2 delays.
>
>- Ricardo.

Gosh, I hadn't viewed these "stuffed zeros" versus "repeated
samples" methods of upsampling in terms of how they compare
CIC filters.  Neat Ricardo.  I see that I have more modeling
to do.

Thanks,
[-Rick-]

```
```Hi Rick,

This was the topic of a thread that started June 17, 1998 that both
Jerry and I participated in.  It was titled "Upsampling Help?"  That
may be a good place to start.

BR,
Dan

```
```dan wrote:
> Hi Rick,
>
> This was the topic of a thread that started June 17, 1998 that both
> Jerry and I participated in.  It was titled "Upsampling Help?"  That
> may be a good place to start.
>
> BR,
> Dan
>

I put forth this same idea here in 1999:

http://groups.google.com/group/comp.dsp/browse_thread/thread/b105bd29bbd771a1/52d1f72465f510e1?lnk=st&q=zero+order+hold++%22jthomas%22+group%3Acomp.dsp&rnum=1&hl=en#52d1f72465f510e1

It was discussed then that by factoring out the repeated samples and
summing adjacent coefficients, the computations can be reduced to the
same level as with zero-insertion.

--
Jim Thomas            Principal Applications Engineer  Bittware, Inc
jthomas@bittware.com  http://www.bittware.com    (603) 226-0404 x536
Having a smoking section in a restaurant is like
having a peeing section in a swimming pool.
```