# Multistage interpolation question

Started by January 27, 2008
```On Jan 27, 5:19 pm, Rick Lyons <R.Lyons@_BOGUS_ieee.org> wrote:
> 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-]

Rick,
From what I remember, you should be able to use the exact same
equation - just think of it like going backwards through the
decimation steps. The filters you would design are to the exact same
specifications.

Cheers,
David
```
```On 2008-01-27, Rick Lyons <R.Lyons@_BOGUS_ieee.org> wrote:
>
> I upsampled by I1=10, lowpass filtered,
> upsampled by I2=32, and lowpass filtered again.
> ...using roughly 250 taps total in both filters.
>
> Then I swapped the I1 & I2 factors;
> using approximately 200 taps total in both filters.
> (A reduction in the total number of taps.)

I think you're evaluating the wrong criteria.  Not all taps are equal
in cost.  The total rate of operations is FS*I1*Taps1 + FS*I1*I2*Taps2.
Even if they both used 250 taps, chosing I2=10 is going to use a lot
fewer operations to calculate.

--
<ben@ben.com>
http://www.ben.com/
```
```>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,

For the equation see my other post on Two stage interpolation-Optimum
order.

Bharat Pathak

Arithos Designs
www.arithos.com

```
```Hello Rick,

I worked out the math and here is the solution. For two stage
interpolation I = I1 x I2, the optimum value of I1 can be given
by

I1 = (fp + fs + sqrt(I*Fs*(Fs - fs - fp)))/Fs

where various quantities are:

fp = passband freq in hz
fs = stopband freq in hz
Fs = sampling freq at the input side.
I = overall interpolation ratio.

For example if we take

fp = 1khz, fs = 3khz, Fs = 8khz and I = 128 and substitute in above
equation we get I1 = 8.5, (nearest integer value and also a value
which is ratio of 128 is 8). Hence 1st stage interpolation should be
by a factor of 8 and second stage interpolation should be by a factor
0f 128/8 = 16.

I1 = 8;
I2 = 16;

This will minimize the number of taps for both filters put together.
The above equation has been arrived using Bellangers formula to
compute
filter order. More accurate equation can be derived using Hermann
order
equation but that procedure will be very cumbersome and might not be
useful for hand calculations. Sometimes approximations help.

Regards
Bharat Pathak

Arithos Designs
~dsp simplified.

```
```On Jan 28, 9:29&#4294967295;pm, "bharat pathak" <bha...@arithos.com> wrote:
> >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,
>
> &#4294967295; &#4294967295; For the equation see my other post on Two stage interpolation-Optimum
> order.
>
> Bharat Pathak
>
> Arithos Designswww.arithos.com

Hello my DSP Brothers,

Why is focus at two stages? Why not more?

To optimise all reddy under-optimal approach make any sense?

Regards,

Kamar Ruptan
DSP Guru
```
```DSPGURU wrote:
> On Jan 28, 9:29 pm, "bharat pathak" <bha...@arithos.com> wrote:
>>> 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,
>>
>>     For the equation see my other post on Two stage interpolation-Optimum
>> order.
>>
>> Bharat Pathak
>>
>> Arithos Designswww.arithos.com
>
> Hello my DSP Brothers,
>
> Why is focus at two stages? Why not more?
>
> To optimise all reddy under-optimal approach make any sense?

A systematic approach to optimizing two stages is a first step to
finding a more general procedure.

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;
```
```On Jan 28, 9:45&#4294967295;pm, Jerry Avins <j...@ieee.org> wrote:
> DSPGURU wrote:
> > On Jan 28, 9:29 pm, "bharat pathak" <bha...@arithos.com> wrote:
> >>> 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,
>
> >> &#4294967295; &#4294967295; For the equation see my other post on Two stage interpolation-Optimum
> >> order.
>
> >> Bharat Pathak
>
> >> Arithos Designswww.arithos.com
>
> > Hello my DSP Brothers,
>
> > Why is focus at two stages? Why not more?
>
> > To optimise all reddy under-optimal approach make any sense?
>
> A systematic approach to optimizing two stages is a first step to
> finding a more general procedure.
>
> 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;- Hide quoted text -
>
> - Show quoted text -

Dr Avin,

Might be first step down path that go nowhere.  If real application
should just do it design starting closer to answer not as great a trip
away as can be.  Close form not required, maybe not possible as get
much bigger than too stages.

Ok, if only gymnastics of brain.

Regards,

Kamar Ruptan
DSP Guru
```
```>
>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?
>
>Kamar Ruptan
>DSP Guru helping the Supreme DSP Guru
>

Hi DSP Guru,

I liked your approach of up 2, up 2, down 3, up 2 ....

It reminded me of so many other things (also apart from the usual
DSP). One such thing I got reminded was the game of ping-pong. And
secondly i was thinking maybe this is how the instructions would
follow when 2 blind people date (just kidding).

Rather on a serious note, I want to know how do you come up with
some suggestions like this? Do you model it in matlab
or you just think about it? Also I want to know about the school
where you studied DSP so in case if I need to brush up my skills
it would be beneficial. Also can you tell us who your teacher was?
Also if you can tell which are your most favorite DSP books it will
help. one i suppose is rabeener and crushierre (i searched on amazon
but there is no book with these authors, I got the spelling from

Bharat
```
```DSPGURU wrote:
> On Jan 28, 9:45 pm, Jerry Avins <j...@ieee.org> wrote:
>> DSPGURU wrote:
>>> On Jan 28, 9:29 pm, "bharat pathak" <bha...@arithos.com> wrote:
>>>>> 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,
>>>>     For the equation see my other post on Two stage interpolation-Optimum
>>>> order.
>>>> Bharat Pathak
>>>> Arithos Designswww.arithos.com
>>> Hello my DSP Brothers,
>>> Why is focus at two stages? Why not more?
>>> To optimise all reddy under-optimal approach make any sense?
>> A systematic approach to optimizing two stages is a first step to
>> finding a more general procedure.
>>
>> 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;- Hide quoted text -
>>
>> - Show quoted text -
>
> Dr Avin,
>
> Might be first step down path that go nowhere.  If real application
> should just do it design starting closer to answer not as great a trip
> away as can be.  Close form not required, maybe not possible as get
> much bigger than too stages.
>
> Ok, if only gymnastics of brain.

Closed form will not be needed if an effective partitioning procedure
can be developed. For example, if it becomes evident that the optimum
two-way split is I1 = I2 = sqrt(I), then a good three-way split is
likely to be I1 = I2 = I3 = cube-root(I). If, on the other hand, the
best two-way split involves unequal I's (possibly because the filters
operate at different rates), then the formula that works there will
likely also lead to an efficient three-way split.

Once efficient splits can be generated easily, the way is open to
explore the relation between the number of splits and the size of the
interpolation.

Almost having a diploma makes you an apprentice, not a guru. You are
accustomed to learning neat formulas out of textbooks, but you haven't
yet realized that the messy problems aren't discussed in those texts.
You have the privilege of witnessing here a process by which those messy
problems come to be understood, then simplified in practice, and finally
reduced to formulas suitable for student "gurus".

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;
```
```
Jerry Avins wrote:

> A systematic approach to optimizing two stages is a first step to
> finding a more general procedure.

Unfortunately, no.

The FIR filters are optimized for the passband ripple/stopband
attenuation rather then cutoff/slope. When designing a FIR with many
stages it is important to know how the ripples of the different stages
are added altogether. If we assume the worst case the design may not be
very optimal.

For the multirate FIR, the transfer function is something like:

P(Z)P(Z^n1)P(Z^n2)...

This results in the nastiness and I don't know if Parks-Mcclellan can be
applied to this problem. If it is applicable, I would just search
through all ratios.