An interpolation question

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

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.