An interpolation question

Started by Rick Lyons 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. �����������������������������������������������������������������������
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.