# Multistage interpolation question

Started by January 27, 2008
```Hi Guys,
some days ago "hsquared" posted a question about
interpolating an audio signal from an original sample
rate of 11025 Hz to 24000 Hz.  As far as I can tell,
that means an overall interpolation factor of 320/147.
I played around a little bit, using MATLAB, with this
notion of interpolation by 320.  As you can imagine
the lowpass filter, following the upsampling
(zero stuffing) by 320, required a *HUGE* (<1000)
number of taps to achieve 45 dB of "image" frequency
attenuation.

Following the sensible approach of interpolating in
multiple stages, I upsampled by I1=10, lowpass filtered,
upsampled by I2=32, and lowpass filtered again.  The
result of that multistage interpolation achieved 50 dB
of "image" frequency attenuation using roughly 250 taps
total in both filters.

Then I swapped the I1 & I2 factors; interpolation by
I1=32, followed by interpolation by I2=10.  This gave
me similar "image" attenuation using approximately
200 taps total in both filters. (A reduction in
the total number of taps.)

So here's my question: If we want to interpolate
by a factor of "I", and we interpolate in two stages
(interp by I1 followed by interp by I2) such that

I = I1*I2,

do any of you know an equation that gives us the
optimum value for I1 (from which we can obtain I2)
that minimizes the total number of taps in the two
interpolation filters?

Thanks,
[-Rick-]

```
```"Rick Lyons" <R.Lyons@_BOGUS_ieee.org> wrote in message
news:a8top3pmfek52t7t8q2u8ctvndbrl62lmr@4ax.com...
>
> Hi Guys,
>  some days ago "hsquared" posted a question about
> interpolating an audio signal from an original sample
> rate of 11025 Hz to 24000 Hz.  As far as I can tell,
> that means an overall interpolation factor of 320/147.
>
> Following the sensible approach of interpolating in
> multiple stages, I upsampled by I1=10, lowpass filtered,
> upsampled by I2=32, and lowpass filtered again.  The
> result of that multistage interpolation achieved 50 dB
> of "image" frequency attenuation using roughly 250 taps
> total in both filters.
>
> Then I swapped the I1 & I2 factors; interpolation by
> I1=32, followed by interpolation by I2=10.  This gave
> me similar "image" attenuation using approximately
> 200 taps total in both filters. (A reduction in
> the total number of taps.)
>
> So here's my question: If we want to interpolate
> by a factor of "I", and we interpolate in two stages
> (interp by I1 followed by interp by I2) such that
>
>     I = I1*I2,
>
> do any of you know an equation that gives us the
> optimum value for I1 (from which we can obtain I2)
> that minimizes the total number of taps in the two
> interpolation filters?
>

time-honored form, I will offer the following observation: ;-)

Suppose that when you upsampled by 32 you had used the
technique of computing a DFT on the data, inserting enough
zeroes in the middle of the spectrum to make it 32 times larger
and then iDFT'ing the result.  It seems to me that the
resulting upsampled signal should have no images at all
(because of the zeroes inserted in the spectrum) and,
consequently, should contribute nothing to your total required
filter taps.  Likewise for upsampling by 10 (except it might
take longer since you now have 32 times as much data and you
can't use the FFT--if my observation holds, you might partition
into (64)(5) and do the *5 first ).

Capitalizing on this in real-time or with huge data sets might
be problematic since I think this will only be true if you can
DFT/iDFT the entire signal all at one time.

```
```On 27 Jan, 13:13, Rick Lyons <R.Lyons@_BOGUS_ieee.org> wrote:

> So here's my question: If we want to interpolate
> by a factor of "I", and we interpolate in two stages
> (interp by I1 followed by interp by I2) such that
>
> &#4294967295; &#4294967295; &#4294967295;I = I1*I2,
>
> do any of you know an equation that gives us the
> optimum value for I1 (from which we can obtain I2)
> that minimizes the total number of taps in the two
> interpolation filters?

Hmmm... one starts out with an original system sampled
with an original sample rate Fo, and wants to interporlate
to a sample rate Fi = I*Fo.

The image rejection filters need to obtain an attenuation
A at the corner frequency Fc, which means that the
transition bands are is expressed as normalized bandwidths
as

Bo = (Fc - Fp)/Fo
Bi = (Fc - Fp)/Fi
Bi = Bo/I

It suffices that the combined attenuation of the two
filters meets the spec, meaning that

A >= Ao + Ai.

So we have (at least) six coupled degrees of freedom here:

- The two sampling rates
- The two normalized sampling rates
- The two corner frequency attenuations

I would be very surprised if these things could be
easily analyzed. I may be wrong, though. Maybe this
problem is better analyzed in terms of Butterorth
filters than FIRs. With Butterworths these sorts
of details can be solved analytically. Getting an
analytical solution up first, and understanding it,
might be a good starting point for understanding
the general case with general filters.

Apart from that, I think this might be a good
subject for an MSc thesis.

Rune
```
```On 27 Jan, 14:14, Rune Allnor <all...@tele.ntnu.no> wrote:

Typo correction:

> So we have (at least) six coupled degrees of freedom here:
>
> - The two sampling rates
> - The two normalized sampling rates

Should be 'The two normalized bandwiths'

> - The two corner frequency attenuations

Rune
```
```"John E. Hadstate" <jh113355@hotmail.com> wrote in message
news:13pp1d222hrng20@news.supernews.com...
>
> "Rick Lyons" <R.Lyons@_BOGUS_ieee.org> wrote in message
> news:a8top3pmfek52t7t8q2u8ctvndbrl62lmr@4ax.com...
>>
>> Hi Guys,
>>  some days ago "hsquared" posted a question about
>> interpolating an audio signal from an original sample
>> rate of 11025 Hz to 24000 Hz.  As far as I can tell,
>> that means an overall interpolation factor of 320/147.
>>
>> Following the sensible approach of interpolating in
>> multiple stages, I upsampled by I1=10, lowpass filtered,
>> upsampled by I2=32, and lowpass filtered again.  The
>> result of that multistage interpolation achieved 50 dB
>> of "image" frequency attenuation using roughly 250 taps
>> total in both filters.
>>
>> Then I swapped the I1 & I2 factors; interpolation by
>> I1=32, followed by interpolation by I2=10.  This gave
>> me similar "image" attenuation using approximately
>> 200 taps total in both filters. (A reduction in
>> the total number of taps.)
>>
>> So here's my question: If we want to interpolate
>> by a factor of "I", and we interpolate in two stages
>> (interp by I1 followed by interp by I2) such that
>>
>>     I = I1*I2,
>>
>> do any of you know an equation that gives us the
>> optimum value for I1 (from which we can obtain I2)
>> that minimizes the total number of taps in the two
>> interpolation filters?
>>
>
> Since I don't know the answer to your question, following time-honored
> form, I will offer the following observation: ;-)
>
> Suppose that when you upsampled by 32 you had used the technique of
> computing a DFT on the data, inserting enough zeroes in the middle of the
> spectrum to make it 32 times larger and then iDFT'ing the result.  It
> seems to me that the resulting upsampled signal should have no images at
> all (because of the zeroes inserted in the spectrum) and, consequently,
> should contribute nothing to your total required filter taps.

Well .... doing it exactly this way can create "images" in time.  You can do
it reasonably (and more blindly) if you first do an interpolation by 2, then
lowpass filter by multiplying in frequency by something such as a halfband
filter, then insert zeros where the energy is already pretty much zero to
increase the temporal interpolation factor.

Fred

```
```Rick Lyons wrote:
> Hi Guys,
>   some days ago "hsquared" posted a question about
> interpolating an audio signal from an original sample
> rate of 11025 Hz to 24000 Hz.  As far as I can tell,
> that means an overall interpolation factor of 320/147.
> I played around a little bit, using MATLAB, with this
> notion of interpolation by 320.  As you can imagine
> the lowpass filter, following the upsampling
> (zero stuffing) by 320, required a *HUGE* (<1000)
> number of taps to achieve 45 dB of "image" frequency
> attenuation.
>
> Following the sensible approach of interpolating in
> multiple stages, I upsampled by I1=10, lowpass filtered,
> upsampled by I2=32, and lowpass filtered again.  The
> result of that multistage interpolation achieved 50 dB
> of "image" frequency attenuation using roughly 250 taps
> total in both filters.
>
> Then I swapped the I1 & I2 factors; interpolation by
> I1=32, followed by interpolation by I2=10.  This gave
> me similar "image" attenuation using approximately
> 200 taps total in both filters. (A reduction in
> the total number of taps.)
>
> So here's my question: If we want to interpolate
> by a factor of "I", and we interpolate in two stages
> (interp by I1 followed by interp by I2) such that
>
>      I = I1*I2,
>
> do any of you know an equation that gives us the
> optimum value for I1 (from which we can obtain I2)
> that minimizes the total number of taps in the two
> interpolation filters?

Proceeding with the confidence of ignorance, my gut tells me that the
least filtering effort will be needed when I1 and I2 are as nearly equal
as practical. (Like all maxima, the optimum will be broad.) Based on
only a few examples, putting the larger first seems to be better.

If those guesses are right, I1 = 20 and I2 = 16 should be hard to beat.

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;
```
```"Rick Lyons" <R.Lyons@_BOGUS_ieee.org> wrote in message
news:a8top3pmfek52t7t8q2u8ctvndbrl62lmr@4ax.com...

> So here's my question: If we want to interpolate
> by a factor of "I", and we interpolate in two stages
> (interp by I1 followed by interp by I2) such that
>
>     I = I1*I2,
>
> do any of you know an equation that gives us the
> optimum value for I1 (from which we can obtain I2)
> that minimizes the total number of taps in the two
> interpolation filters?

Rick,

1) I don't know.

2) I will try / have a thought

The reason that the filter is so long doing it in one pass is that the
transition band is so narrow.
Using multiple passes (NOT just multiple filter stages folks - that wouldn't
make any difference) of upsampling and filtering suggests this:

For each upsampling and filtering operation there is a transition band
width.  The higher the ratio, the narrower the transition band width and the
longer the filter.
So, there's an objective of making the transition bands as wide as possible.

The transition band width depends on the upsampling ratio (varies
inversely).
We'll call the overall upsampling ratio "I" as is common in interpolation.
Since we're talking about two stages, let's call their individucal ratios I1
and I2 so that I=I1*I2.

The filter length is proportional to I or I1 and I2.  So, the task is to
minimize I1 + I2 isn't it?

I1*I2 is a constant I
Minimize I1 + I2
Minimize I1 + I1/I = [(I +1)I1]/I
d/dI1 [(I +1)I1]/I = sqrt(I)

Which is sorta what I expected would happen.  The minimum sum of the filter
lengths is when they are equal in length - when the interpolation ratios are
equal.

I hope I got it right....

So for 320 it would be 17.88.  And, 320=5*2^6.
Since 5 is prime, you're stuck with it.
The closest integer to 5 in 16 would be 4.
So, you are forced to use the factors 5 and 4 in the ratio pair leaving 2^4
which nicely splits into 2^2 for each ratio.
This gives 5*4=20 and 4*4=16 as the two ratios that appear to be optimum for
this purpose.

But, to agree with John, I think this might well be a place to use frequency
domain upsampling and filtering combined (with judicious use of
zero-stuffing as I mentioned in another post in this thread).  I've done it
and it works well.  But that's not what you asked....

Just for fun - to go back to the objective you started with - what if one
would do this?:

- Assume we will process 1 second of data.
- 11025 samples FFTd for 11025 frequency samples.
- Conceptually zero-stuff to get a factor of 4; to 44,100 samples in
frequency.
- Conceptually zero-remove to get 24,000 samples in frequency.
This means we would actually zero-stuff 12,975 zeros and would be done less
the IFFT.
The result is one second of data at 24,000Hz.

It appears in this case that there are ample opportunities to take smaller
time chunks as 11025 =       3^2 * 5^2 * 7^2
24000 = 2^6 * 3   * 5^3
12975 =       3   * 5^2 * 173

So, time chunks down to 1/75 seconds would appear to be OK.

The conceptual process would be:
Take 147 samples
Stuff 173 samples
End up with 320 samples.
320*75= 24000 Hz.

Perhaps a more reasonable process would be:
Take 147 samples.
Repeat the spectrum twice yielding 294 samples.
Halfband filter in frequency.
Stuff 26 zero samples yielding 320 samples.

Then you do whatever you do to blend the chunks.

Fred

```
```"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in
message news:9JCdna80LIJAJgHanZ2dnUVZ_oOnnZ2d@centurytel.net...
>
> - Assume we will process 1 second of data.
> - 11025 samples FFTd for 11025 frequency samples.
> - Conceptually zero-stuff to get a factor of 4; to 44,100
> samples in frequency.
> - Conceptually zero-remove to get 24,000 samples in
> frequency.
> This means we would actually zero-stuff 12,975 zeros and
> would be done less the IFFT.
> The result is one second of data at 24,000Hz.
>
> It appears in this case that there are ample opportunities to
> take smaller time chunks as 11025 =       3^2 * 5^2 * 7^2
> 24000 = 2^6 * 3   * 5^3
> 12975 =       3   * 5^2 * 173
>
> So, time chunks down to 1/75 seconds would appear to be OK.
>
> The conceptual process would be:
> Take 147 samples
> Stuff 173 samples
> End up with 320 samples.
> 320*75= 24000 Hz.
>
> Perhaps a more reasonable process would be:
> Take 147 samples.
> Repeat the spectrum twice yielding 294 samples.
> Halfband filter in frequency.
> Stuff 26 zero samples yielding 320 samples.
>
> Then you do whatever you do to blend the chunks.
>
> Fred

I intend to try something similar to this sometime this week in
connection with another problem.  Up until now, I've ignored
this type of processing for real-time problems because I wasn't
sure how to "blend the chunks" without introducing additional
artifacts.

```
```On Jan 27, 7:13&#4294967295;am, Rick Lyons <R.Lyons@_BOGUS_ieee.org> wrote:
> Hi Guys,
> &#4294967295; some days ago "hsquared" posted a question about
> interpolating an audio signal from an original sample
> rate of 11025 Hz to 24000 Hz. &#4294967295;As far as I can tell,
> that means an overall interpolation factor of 320/147.
> I played around a little bit, using MATLAB, with this
> notion of interpolation by 320. &#4294967295;As you can imagine
> the lowpass filter, following the upsampling
> (zero stuffing) by 320, required a *HUGE* (<1000)
> number of taps to achieve 45 dB of "image" frequency
> attenuation. &#4294967295;
>
> Following the sensible approach of interpolating in
> multiple stages, I upsampled by I1=10, lowpass filtered,
> upsampled by I2=32, and lowpass filtered again. &#4294967295;The
> result of that multistage interpolation achieved 50 dB
> of "image" frequency attenuation using roughly 250 taps
> total in both filters.
>
> Then I swapped the I1 & I2 factors; interpolation by
> I1=32, followed by interpolation by I2=10. &#4294967295;This gave
> me similar "image" attenuation using approximately &#4294967295;
> 200 taps total in both filters. (A reduction in
> the total number of taps.)
>
> So here's my question: If we want to interpolate
> by a factor of "I", and we interpolate in two stages
> (interp by I1 followed by interp by I2) such that
>
> &#4294967295; &#4294967295; &#4294967295;I = I1*I2,
>
> do any of you know an equation that gives us the
> optimum value for I1 (from which we can obtain I2)
> that minimizes the total number of taps in the two
> interpolation filters?
>
> Thanks,
> [-Rick-]

Hi Rick, Supreme DSP Guru, Large Man Of IEEE,

From the books (Rabeener and Crushierre IIIRC) it seem best is to go
up a little and down a little, time after time, to change sampling.

320=5*pow(2,6)
147=3*7*7

It seem many use of halfband filter is best way to do since no reeson
CIC boxcar filter has apply to here.

Can combines ups and downs in special order to signal BW is preserve.

Maybe something like up 2, up 2, down 3, up 2, up 2, up 2, down 7, up
2, up, 5 down 7?

Exact order and little filter designs to figure out with analyze. Hvae
real control on images as made.

Regards,

Kamar Ruptan
DSP Guru helping the Supreme DSP Guru

```
```Hi Guys,
Wow.  Thanks for all the replies.  You've
given me a lot to think about.

One of the things that prompted my question
is the fact that if we need to decimate by
a large factor D, we can decimate in two stages
(decimate by D1, followed by decimation by D2)
to reduce the overall filtering workload.

If D = D1*D2, there's an equation
to find the optimum value of the first decimation
factor D1, from which we can then find D2.
("Optimum" means: what value of D1 yields the minimum
number of taps in the two decimation filters.)

The equation for finding the optimum value D1
can be found in:

Crochiere, R. and Rabiner, L. "Optimum FIR Digital
Implementations for Decimation, Interpolation, and
Narrow?band Filtering," IEEE Trans. on Acoust.
Speech, and Signal Proc., Vol. ASSP-23, No. 5,
October 1975.

SOOooo, ... in my original post I was just wondering
if any of you have ever seen a similar equation for finding
the "optimum" I1 for use when doing two-stage interpolation
by I = I1*I2.

Thanks for all the info, and suggestions, guys.

[-Rick-]

```