Multistage Interpolation - Need help understanding each stage

From scouring this group, I see that someone else is attempting the same thing 
that I'm trying to accomplish - multistage interpolation of an audio signal. 
Just getting my feet wet with this topic, I'd like to ask you guys a few 
general qustions.

Taking a bandlimited audio signal sampled at 44.1kHz and interpolating by 160 
broken into multiple stages (4x, 5x, and 8x respectively), my question is do I 
have to apply a filter each stage? I assume I do since interpolation usually 
implies zero stuffing followed by a filter (often combined so as not to have 
to multiply filter coeffs by zero valued data) 

Here is my understanding, please correct me if I'm wrong:


In the first stage I interpolate by 4x, I would have 44.1 x 4 = 176.4kHz. So 
do I set my filter passband for 22.05Hz, and stopband at 88.2kHz (1/2 of 
176.4kHz)?

I'm confused with the 2nd & 3rd stage. With 5x I assume that I would keep the 
same passband but since the signal has been filtered in the previous stage, 
wouldn't I acutally be interpolating from 88.2kHz instead on 176.4kHz? Or do I 
just keep the same passband and filter the signal with a stopband at (176.4 x 
5)/2?

The multistage approach has thrown me off. If you guys don't mind please set 
me straight on this.

I realize that interpolation in this case anyway, is zero-stuffing (as 
opposed to cubic splines, etc) followed by a LPF. If I'm only to filter the 
last stage then what is the point of cascading the filter into multiple 
stages? Why not just zero-pad the entire bitstream and apply the filter at the 
end?

-Rick S.

"Rick S." <disregard@disregard.com> wrote in message
news:uczSb.12533$TO4.10884@newssvr23.news.prodigy.com...
> From scouring this group, I see that someone else is attempting the same
thing
> that I'm trying to accomplish - multistage interpolation of an audio
signal.
> Just getting my feet wet with this topic, I'd like to ask you guys a few
> general qustions.
>
> Taking a bandlimited audio signal sampled at 44.1kHz and interpolating by
160
> broken into multiple stages (4x, 5x, and 8x respectively), my question is
do I
> have to apply a filter each stage? I assume I do since interpolation
usually
> implies zero stuffing followed by a filter (often combined so as not to
have
> to multiply filter coeffs by zero valued data)

Yes, a filter after every stage.

>
> Here is my understanding, please correct me if I'm wrong:
>
>
> In the first stage I interpolate by 4x, I would have 44.1 x 4 = 176.4kHz.
So
> do I set my filter passband for 22.05Hz, and stopband at 88.2kHz (1/2 of
> 176.4kHz)?
>
> I'm confused with the 2nd & 3rd stage. With 5x I assume that I would keep
the
> same passband but since the signal has been filtered in the previous
stage,
> wouldn't I acutally be interpolating from 88.2kHz instead on 176.4kHz? Or
do I
> just keep the same passband and filter the signal with a stopband at
(176.4 x
> 5)/2?

I suggest you read the responses to the other thread on this topic which
clearly explain the exact frequencies you'd use and the filter cut-offs.
It is also helpful to approach the filter cut-offs by normalizing it to the
sample rate. It can help keep things more straight forward.

> The multistage approach has thrown me off. If you guys don't mind please
set
> me straight on this.
>
> I realize that interpolation in this case anyway, is zero-stuffing (as
> opposed to cubic splines, etc) followed by a LPF. If I'm only to filter
the
> last stage then what is the point of cascading the filter into multiple
> stages? Why not just zero-pad the entire bitstream and apply the filter at
the
> end?

The point of cascading the filter into multiple stages is that you get to
keep your filters smaller *and* run them at slower speeds. If you did it all
in one shot, your filter will be a fairly long filter (relative to the multi
stage approach) and you'd have to make it run at the high sample rate.
So this is more of a divide and conquer approach.

Cheers
Bhaskar

>
> -Rick S.
>

"Bhaskar Thiagarajan" <bhaskart@deja.com> wrote in message
news:bvehcp$qr7hb$1@ID-82263.news.uni-berlin.de...
> "Rick S." <disregard@disregard.com> wrote in message
> news:uczSb.12533$TO4.10884@newssvr23.news.prodigy.com...
> > From scouring this group, I see that someone else is attempting the same
> thing
> > that I'm trying to accomplish - multistage interpolation of an audio
> signal.
> > Just getting my feet wet with this topic, I'd like to ask you guys a few
> > general qustions.
> >
> > Taking a bandlimited audio signal sampled at 44.1kHz and interpolating
by
> 160
> > broken into multiple stages (4x, 5x, and 8x respectively), my question
is
> do I
> > have to apply a filter each stage? I assume I do since interpolation
> usually
> > implies zero stuffing followed by a filter (often combined so as not to
> have
> > to multiply filter coeffs by zero valued data)
>
> Yes, a filter after every stage.
>
> >
> > Here is my understanding, please correct me if I'm wrong:
> >
> >
> > In the first stage I interpolate by 4x, I would have 44.1 x 4 =
176.4kHz.
> So
> > do I set my filter passband for 22.05Hz, and stopband at 88.2kHz (1/2 of
> > 176.4kHz)?
> >
> > I'm confused with the 2nd & 3rd stage. With 5x I assume that I would
keep
> the
> > same passband but since the signal has been filtered in the previous
> stage,
> > wouldn't I acutally be interpolating from 88.2kHz instead on 176.4kHz?
Or
> do I
> > just keep the same passband and filter the signal with a stopband at
> (176.4 x
> > 5)/2?
>
> I suggest you read the responses to the other thread on this topic which
> clearly explain the exact frequencies you'd use and the filter cut-offs.
> It is also helpful to approach the filter cut-offs by normalizing it to
the
> sample rate. It can help keep things more straight forward.
>
> > The multistage approach has thrown me off. If you guys don't mind please
> set
> > me straight on this.
> >
> > I realize that interpolation in this case anyway, is zero-stuffing (as
> > opposed to cubic splines, etc) followed by a LPF. If I'm only to filter
> the
> > last stage then what is the point of cascading the filter into multiple
> > stages? Why not just zero-pad the entire bitstream and apply the filter
at
> the
> > end?
>
> The point of cascading the filter into multiple stages is that you get to
> keep your filters smaller *and* run them at slower speeds. If you did it
all
> in one shot, your filter will be a fairly long filter (relative to the
multi
> stage approach) and you'd have to make it run at the high sample rate.
> So this is more of a divide and conquer approach.
>
> Cheers
> Bhaskar

There's got to be something to this multi-stage approach because it is
frequently suggested, but I have never been able to figure out how it is
useful in converting for example, from 44.1 to 48kHz.  If you just do a
single polyphase filter, you run the filter directly at the desired output
rate and don't have to do any zero-stuffing or worry about higher
intermediate frequencies, etc..

Maybe it makes sense if you are actually going to use the up-sampled result
for something rather than just immediately down-sampling it.  But when your
input and output sample rates are close, I can't see any advantage.  Am I
missing something?

For the original poster, are you really trying to upsample by 160, or is
your eventual goal to convert 44.1<->48kHz?  Sometimes you get more useful
answers if you ask a "bigger picture" question.

Jon Harris wrote:
> 
> There's got to be something to this multi-stage approach 
> because it is frequently suggested, 

I have never seen anything to suggest that it is even slightly
better than the direct approach.

> but I have never been able to figure out how it is
> useful in converting for example, from 44.1 to 48kHz.  If you 
> just do a single polyphase filter, you run the filter directly 
> at the desired output rate and don't have to do any zero-stuffing 
> or worry about higher intermediate frequencies, etc..

Agreed for cases where init to output sample rates are 
easily expressed as a rational number.

The polyphase approach becomes when you want to down sample
by from say 48000 to

	44100 * 1000/1001 = 44055.944055944055

which I believe shows up when converting from 48000 sampled
audio synchronised to 30 frames/sec video to 44100 sampled
audio synchronised to 29.95 frames/sec video.

Been a while since I last looked at audio/video synchronisation
so I may be a little off the mark here. The point I am making 
is that the polyphase approach falls down in some situations
where the Julius O. Smith approach:

   http://ccrma-www.stanford.edu/~jos/resample/

comes through with flying colours. There is an implementation
of the above algorth on the above page and I have another at

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

The later is also capable of time varying sample rate 
conversion.


Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo  nospam@mega-nerd.com (Yes it's valid)
+-----------------------------------------------------------+
"Python addresses true pseudocode's two major failings: that it
isn't standardized, and it isn't executable."
- Grant R. Griffin  in comp.dsp

"Erik de Castro Lopo" <nospam@mega-nerd.com> wrote in message
news:401AD577.DD65D672@mega-nerd.com...
> Jon Harris wrote:
> >
> > There's got to be something to this multi-stage approach
> > because it is frequently suggested,
>
> I have never seen anything to suggest that it is even slightly
> better than the direct approach.

Just in the recent thread here (Re: Resampling questions - from 44.1kHz to
48kHz), it was suggested.  And it seems to come up frequency from posters
here whenever this topic is discussed.

> > but I have never been able to figure out how it is
> > useful in converting for example, from 44.1 to 48kHz.  If you
> > just do a single polyphase filter, you run the filter directly
> > at the desired output rate and don't have to do any zero-stuffing
> > or worry about higher intermediate frequencies, etc..
>
> Agreed for cases where init to output sample rates are
> easily expressed as a rational number.
>
> The polyphase approach becomes when you want to down sample
                               ^^^
missing word here--cumbersome?  difficult?

I know that the filter coef table requires more entries the larger the
integer relationship is.  One alternative is to come up with a reasonable
length table and further interpolate the coefs between the table values to
get increased accuracy (as discussed in the recent "Re: Fast interpolation
?" thread).

> by from say 48000 to
>
> 44100 * 1000/1001 = 44055.944055944055
>
> which I believe shows up when converting from 48000 sampled
> audio synchronised to 30 frames/sec video to 44100 sampled
> audio synchronised to 29.95 frames/sec video.

(it's 29.970026, but your basic point is well taken)

> Been a while since I last looked at audio/video synchronisation
> so I may be a little off the mark here. The point I am making
> is that the polyphase approach falls down in some situations
> where the Julius O. Smith approach:
>
>    http://ccrma-www.stanford.edu/~jos/resample/

I'm not sure what is the difference is between JOS's approach and what I'm
talking about.  Polyphase is just an implementation of bandlimited
interpolation.
What would the "JOS approach" be to the problem of 1000/1001 you mention?

> comes through with flying colours. There is an implementation
> of the above algorth on the above page and I have another at
>
>     http://www.mega-nerd.com/SRC/
>
> The later is also capable of time varying sample rate
> conversion.

Maybe I'm picking nits here, but I see your code supports irrational sample
rate ratios.  How is that specified to the software?  It can't be _truly_
irrational unless you support something like sqrt 2 or pi.  A ratio like
44.14312431847343143/46.948371493914931481 is very cumbersome, but still
rational!

Jon Harris wrote:
> 
> > The polyphase approach becomes when you want to down sample
>                                ^^^
> missing word here--cumbersome?  difficult?

I can't remember exactly what I had in mind, but I think impossible is
pretty suitable.

> >    http://ccrma-www.stanford.edu/~jos/resample/
> 
> I'm not sure what is the difference is between JOS's approach and what I'm
> talking about.  Polyphase is just an implementation of bandlimited
> interpolation.

The JOS approach is to keep a large table containing a windowed sinc 
function. Linear interplation of this table is then used to generate 
the exact required sinc function for a given subsample delay. In effect,
this is a polyhphase implmentation with an infinite number of fractional
delay FIR filters.

> > of the above algorth on the above page and I have another at
> >
> >     http://www.mega-nerd.com/SRC/
> >
> > The later is also capable of time varying sample rate
> > conversion.
> 
> Maybe I'm picking nits here, but I see your code supports irrational sample
> rate ratios.  How is that specified to the software?  It can't be _truly_
> irrational unless you support something like sqrt 2 or pi.  A ratio like
> 44.14312431847343143/46.948371493914931481 is very cumbersome, but still
> rational!

Congratulations, nit sucessfully picked :-). However, if you are willing
to dither the ratio (already a double floating point) you can achive a
arbitrarily  close approximation to an irational ratio.

Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo  nospam@mega-nerd.com (Yes it's valid)
+-----------------------------------------------------------+
Linux, the UNIX defragmentation tool.

>
>For the original poster, are you really trying to upsample by 160, or is
>your eventual goal to convert 44.1<->48kHz?  Sometimes you get more useful
>answers if you ask a "bigger picture" question.
>
>


Yes, I am going to try 44.1<->48kHz. I'm just trying to figure out how to do 
the interpolation part using a series of cascaded filters. The decimation part 
I believe will be pretty straightforward if it takes advantage of using the 
same LPF as the last stage of the interpolator.

-Rick S.

"Jon Harris" <goldentully@hotmail.com> wrote in message
news:bvej4j$rhjko$1@ID-210375.news.uni-berlin.de...
> "Bhaskar Thiagarajan" <bhaskart@deja.com> wrote in message
> news:bvehcp$qr7hb$1@ID-82263.news.uni-berlin.de...
> > "Rick S." <disregard@disregard.com> wrote in message
> > news:uczSb.12533$TO4.10884@newssvr23.news.prodigy.com...
> > > From scouring this group, I see that someone else is attempting the
same
> > thing
> > > that I'm trying to accomplish - multistage interpolation of an audio
> > signal.
> > > Just getting my feet wet with this topic, I'd like to ask you guys a
few
> > > general qustions.
> > >
> > > Taking a bandlimited audio signal sampled at 44.1kHz and interpolating
> by
> > 160
> > > broken into multiple stages (4x, 5x, and 8x respectively), my question
> is
> > do I
> > > have to apply a filter each stage? I assume I do since interpolation
> > usually
> > > implies zero stuffing followed by a filter (often combined so as not
to
> > have
> > > to multiply filter coeffs by zero valued data)
> >
> > Yes, a filter after every stage.
> >
> > >
> > > Here is my understanding, please correct me if I'm wrong:
> > >
> > >
> > > In the first stage I interpolate by 4x, I would have 44.1 x 4 =
> 176.4kHz.
> > So
> > > do I set my filter passband for 22.05Hz, and stopband at 88.2kHz (1/2
of
> > > 176.4kHz)?
> > >
> > > I'm confused with the 2nd & 3rd stage. With 5x I assume that I would
> keep
> > the
> > > same passband but since the signal has been filtered in the previous
> > stage,
> > > wouldn't I acutally be interpolating from 88.2kHz instead on 176.4kHz?
> Or
> > do I
> > > just keep the same passband and filter the signal with a stopband at
> > (176.4 x
> > > 5)/2?
> >
> > I suggest you read the responses to the other thread on this topic which
> > clearly explain the exact frequencies you'd use and the filter cut-offs.
> > It is also helpful to approach the filter cut-offs by normalizing it to
> the
> > sample rate. It can help keep things more straight forward.
> >
> > > The multistage approach has thrown me off. If you guys don't mind
please
> > set
> > > me straight on this.
> > >
> > > I realize that interpolation in this case anyway, is zero-stuffing (as
> > > opposed to cubic splines, etc) followed by a LPF. If I'm only to
filter
> > the
> > > last stage then what is the point of cascading the filter into
multiple
> > > stages? Why not just zero-pad the entire bitstream and apply the
filter
> at
> > the
> > > end?
> >
> > The point of cascading the filter into multiple stages is that you get
to
> > keep your filters smaller *and* run them at slower speeds. If you did it
> all
> > in one shot, your filter will be a fairly long filter (relative to the
> multi
> > stage approach) and you'd have to make it run at the high sample rate.
> > So this is more of a divide and conquer approach.
> >
> > Cheers
> > Bhaskar
>
> There's got to be something to this multi-stage approach because it is
> frequently suggested, but I have never been able to figure out how it is
> useful in converting for example, from 44.1 to 48kHz.  If you just do a
> single polyphase filter, you run the filter directly at the desired output
> rate and don't have to do any zero-stuffing or worry about higher
> intermediate frequencies, etc..

Ahh..but most novice DSP folks asking about resampling aren't quite ready to
jump into polyphase resampling techniques - hence the multi-stage approach
is often suggested.

> Maybe it makes sense if you are actually going to use the up-sampled
result
> for something rather than just immediately down-sampling it.  But when
your
> input and output sample rates are close, I can't see any advantage.  Am I
> missing something?
>
> For the original poster, are you really trying to upsample by 160, or is
> your eventual goal to convert 44.1<->48kHz?  Sometimes you get more useful
> answers if you ask a "bigger picture" question.

I agree with your statements. The multi-stage approach has maximum advantage
when the up-sampling is viewed as a separate entity.


Cheers
Bhaskar

"Erik de Castro Lopo" <nospam@mega-nerd.com> wrote in message
news:401AE58E.2CEAC566@mega-nerd.com...
> Jon Harris wrote:
> >
> > >    http://ccrma-www.stanford.edu/~jos/resample/
> >
> > I'm not sure what is the difference is between JOS's approach and what
I'm
> > talking about.  Polyphase is just an implementation of bandlimited
> > interpolation.
>
> The JOS approach is to keep a large table containing a windowed sinc
> function. Linear interplation of this table is then used to generate
> the exact required sinc function for a given subsample delay. In effect,
> this is a polyhphase implmentation with an infinite number of fractional
> delay FIR filters.

OK, that's the approach I've used myself.  I still considered in polyphase,
but I see how it can be viewed as an extension of the basic polyphase
approach.
(You snipped the part where I said: "One alternative is to come up with a
reasonable length table and further interpolate the coefs between the table
values to get increased accuracy.")

> Congratulations, nit sucessfully picked :-). However, if you are willing
> to dither the ratio (already a double floating point) you can achive a
> arbitrarily  close approximation to an irational ratio.

Agreed.

"Bhaskar Thiagarajan" <bhaskart@deja.com> wrote in message
news:bveqa8$rj0fn$1@ID-82263.news.uni-berlin.de...
> "Jon Harris" <goldentully@hotmail.com> wrote in message
> news:bvej4j$rhjko$1@ID-210375.news.uni-berlin.de...
> >
> > There's got to be something to this multi-stage approach because it is
> > frequently suggested, but I have never been able to figure out how it is
> > useful in converting for example, from 44.1 to 48kHz.  If you just do a
> > single polyphase filter, you run the filter directly at the desired
output
> > rate and don't have to do any zero-stuffing or worry about higher
> > intermediate frequencies, etc..
>
> Ahh..but most novice DSP folks asking about resampling aren't quite ready
to
> jump into polyphase resampling techniques - hence the multi-stage approach
> is often suggested.

OK.  For me, polyphase actually makes much more sense that all this crazy
"zero stuffing, interpolating to some ridiculous sample rate, filtering,
decimating" stuff!  :-)

Maybe that's because I first did sample rate conversion using simple linear
interpolation because I didn't know any better.  It then made sense to start
looking at more and more samples around my interpolated point and use some
sort of look-up table to generate the weights for each point.  Pretty soon
you're doing the polyphase thing, even if you don't know it!  Hence
polyphase FIR band-limited interpolation was a natural extension of simple
linear interpolation.  But maybe I'm weird!

> > Maybe it makes sense if you are actually going to use the up-sampled
> result
> > for something rather than just immediately down-sampling it.  But when
> your
> > input and output sample rates are close, I can't see any advantage.  Am
I
> > missing something?
> >
> > For the original poster, are you really trying to upsample by 160, or is
> > your eventual goal to convert 44.1<->48kHz?  Sometimes you get more
useful
> > answers if you ask a "bigger picture" question.
>
> I agree with your statements. The multi-stage approach has maximum
advantage
> when the up-sampling is viewed as a separate entity.

Cool.