Forums

Multistage interpolation question

Started by Rick Lyons 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 Jackson AD7GD <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&#2013266080;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, > > &#2013266080; &#2013266080; 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. &#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
On Jan 28, 9:45&#2013266080;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, > > >> &#2013266080; &#2013266080; 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. > &#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;- 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 your previous post). 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. >> &#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;- 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. &#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;

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. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com