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-]

# Multistage interpolation question

Started by ●January 27, 2008

Reply by ●January 27, 20082008-01-27

"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. 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.

Reply by ●January 27, 20082008-01-27

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 > > � � �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

Reply by ●January 27, 20082008-01-27

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 ratesShould be 'The two normalized bandwiths'> - The two corner frequency attenuationsRune

Reply by ●January 27, 20082008-01-27

"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

Reply by ●January 27, 20082008-01-27

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. �����������������������������������������������������������������������

Reply by ●January 27, 20082008-01-27

"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

Reply by ●January 27, 20082008-01-27

"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. > > FredI 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.

Reply by ●January 27, 20082008-01-27

On Jan 27, 7:13�am, Rick Lyons <R.Lyons@_BOGUS_ieee.org> 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? > > 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

Reply by ●January 27, 20082008-01-27

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-]