Multi-stage filter delay!

Started by September 21, 2003
Hi!

I am trying to compute the delay of a multi-stage half band FIR filter
bank (upsampling by factor 2 in each stage).

(N is number of taps).

With one stage (half band filter) I get: (N1-1) /2 + 1.
With two stages: (N1-1)/2 * 2 + 1 + (N2-1)/2 - 4

On stages higher then 2 filter length is equal to N2.

But I am having trouble deriving the general formula...
Any ideas?

Thanks!
Atmapuri

"Atmapuri" <Janez.Makovsek@usa.net> wrote in message
news:N8ibb.3460\$2B6.667150@news.siol.net...
> Hi! > > I am trying to compute the delay of a multi-stage half band FIR filter > bank (upsampling by factor 2 in each stage). > > (N is number of taps). > > With one stage (half band filter) I get: (N1-1) /2 + 1. > With two stages: (N1-1)/2 * 2 + 1 + (N2-1)/2 - 4 > > On stages higher then 2 filter length is equal to N2. > > But I am having trouble deriving the general formula... > Any ideas?
You mean *symmetric* FIR filters - only they have constant delay. If they are cascaded then the delay is D1 + D2 + D3 ..... +Dn A halfband filter is of odd length with an even number of delays. So N1-1 is the number of delays. (N1-1)/2 is half the number of delays. If the first tap on the filter has zero delay, then the delay of the filter is just (N1-1)/2 isn't it? Example: Filter length 5. Delay of first tap =0 Delay of middle tap=2 Delay of filter=2 (5-1)/2 = 2. When you upsample are you adding zeros before or after the input samples? How are you defining time after you do this? Are you considering that the added zeros are at half-sample intervals? Or, are you considering that the added zeros are at the original sample rate? The former seems more appropriate but you are free to scale time any way you want if all you're doing is processing arrays of numbers. If you consider the added zeros in upsampling to be at half the input sample interval and if you insert zeros only after the samples and if the insertion doesn't take any time, then there is zero delay introduced by upsampling. This may or may not be the case for your implmentation. Let's assume that you use the same half-band filter at each stage. In effect, the sample rate of the filter increases at each stage then because the upsampler changes the sample rate. So, you will have (where N is the length of the half-band filter and D1, D2, etc. are the filter delays): D1=(N-1)/2 followed by the delay of the upsampler which I will assume is zero D2=(N-1)/4 because N has not changed but the time scale has changed by a factor of 2 due to the upsampling. etc. Oh yes, I am assuming that the multipliers and adders take no time. If this isn't the case, then you have to add the time for them to work - to the filter delay. Fred
"Atmapuri" <Janez.Makovsek@usa.net> wrote in message
news:N8ibb.3460\$2B6.667150@news.siol.net...
> Hi! > > I am trying to compute the delay of a multi-stage half band FIR filter > bank (upsampling by factor 2 in each stage). > > (N is number of taps). > > With one stage (half band filter) I get: (N1-1) /2 + 1. > With two stages: (N1-1)/2 * 2 + 1 + (N2-1)/2 - 4 > > On stages higher then 2 filter length is equal to N2. > > But I am having trouble deriving the general formula... > Any ideas? > > Thanks! > Atmapuri
You mean *symmetric* FIR filters - only they have constant delay. If they are cascaded then the delay is D1 + D2 + D3 ..... +Dn A halfband filter is of odd length with an even number of delays. So N1-1 is the number of delays. (N1-1)/2 is half the number of delays. If the first tap on the filter has zero delay, then the delay of the filter is just (N1-1)/2 isn't it? Example: Filter length 5. Delay of first tap =0 Delay of middle tap=2 Delay of filter=2 (5-1)/2 = 2. When you upsample are you adding zeros before or after the input samples? How are you defining time after you do this? Are you considering that the added zeros are at half-sample intervals? Or, are you considering that the added zeros are at the original sample rate? The former seems more appropriate but you are free to scale time any way you want if all you're doing is processing arrays of numbers. If you consider the added zeros in upsampling to be at half the input sample interval and if you insert zeros only after the samples and if the insertion doesn't take any time, then there is zero delay introduced by upsampling. This may or may not be the case for your implmentation. Let's assume that you use the same half-band filter at each stage. In effect, the sample rate of the filter increases at each stage then because the upsampler changes the sample rate. So, you will have (where N is the length of the half-band filter and D1, D2, etc. are the filter delays): D1=(N-1)/2 followed by the delay of the upsampler which I will assume is zero D2=(N-1)/4 because N has not changed but the time scale has changed by a factor of 2 due to the upsampling. etc. Oh yes, I am assuming that the multipliers and adders take no time. If this isn't the case, then you have to add the time for them to work - to the filter delay. Fred
"Fred Marshall" <fmarshallx@remove_the_x.acm.org> writes:

> > You mean *symmetric* FIR filters - only they have constant delay. >
:-) Or anti-symmetric ones... Ciao, Peter K. -- Peter J. Kootsookos "Na, na na na na na na, na na na na" - 'Hey Jude', Lennon/McCartney
Hi!

> If they are cascaded then the delay is D1 + D2 + D3 ..... +Dn
Yes, but the sampling frequency is changing. This is true for a constant frequency.
> A halfband filter is of odd length with an even number of delays. > So N1-1 is the number of delays. (N1-1)/2 is half the number of delays. > If the first tap on the filter has zero delay, then the delay of the
filter
> is just (N1-1)/2 isn't it? > Example: > > Filter length 5. > Delay of first tap =0 > Delay of middle tap=2 > Delay of filter=2 > (5-1)/2 = 2. > > When you upsample are you adding zeros before or after the input samples?
After.
> How are you defining time after you do this?
The time delay must be expressed in number of samples of the final sampling frequency.
> So, you will have (where N is the length of the half-band filter and D1,
D2,
> etc. are the filter delays): > > D1=(N-1)/2 > followed by the delay of the upsampler which I will assume is zero > D2=(N-1)/4 because N has not changed but the time scale has changed by a > factor of 2 due to the upsampling. > etc.
I thought so to. The first thing that I wrote: D = (N-1)/2 UpSample by 2: D1 = D UpSample by 4: D2 = D1*2 + D1 UpSample by 8 :D3 = D2*2 + D1 But the actual numbers are like this: UpSample by 2: D1 = D + 1 UpSample by 4: D2 = D1 * 2 + D1 - 6 This if course was found by guessing. I also tested the filter and works perfectly. Frequency response is as it should be. And time domain samples align up exactly. (interpolated and non interpolated version). I must be missing something, but I dont know what. This is a call to Intel SPL routine, so I dont know what is happening behind it.
> Oh yes, I am assuming that the multipliers and adders take no time. If
this
> isn't the case, then you have to add the time for them to work - to the > filter delay.
You are correct. Thanks! Atmapuri.
Hi!

Got something working:

D =  (N-1)/2
UpSample by 2: D1 = D  + 1
UpSample by 4: D2 = D1*2 + D
UpSample by 8 :D3 = D2*2 + D + 1
UpSample by 16:D4 = D3*2 + D
UpSample by 32:D5 = D4*2 + D + 1
....

Bits me why...
--
Atmapuri

"Atmapuri" <Janez.Makovsek@usa.net> wrote in message
news:ZwBbb.3523\$2B6.674188@news.siol.net...
> Hi! > > > If they are cascaded then the delay is D1 + D2 + D3 ..... +Dn > > Yes, but the sampling frequency is changing. This is true for > a constant frequency. > > > A halfband filter is of odd length with an even number of delays. > > So N1-1 is the number of delays. (N1-1)/2 is half the number of delays. > > If the first tap on the filter has zero delay, then the delay of the > filter > > is just (N1-1)/2 isn't it? > > Example: > > > > Filter length 5. > > Delay of first tap =0 > > Delay of middle tap=2 > > Delay of filter=2 > > (5-1)/2 = 2. > > > > When you upsample are you adding zeros before or after the input
samples?
> > After. > > > How are you defining time after you do this? > > The time delay must be expressed in number of samples of the final > sampling frequency.
Ah! Good to have a definition of the objective.... OK. Well, it seems to me that the original sampling interval is a multiple of the interpolation ratio "I". If the original sampling interval is T, and the interpolation ratio is 4, then the final sampling interval is T/4 and any sample intervals in the original frame are increased by the same ratio at the output. So, for odd-length filters, calculating forward: D1=(N1-1)/2 samples After upsampling, (increase the number of sample intervals by 2) D1=N1-1 samples D2=(N2-1)/2 samples D1+D2=N1-1+(N2-1)/2 samples after upsampling (increase the number of sample intervals by 2) D1+D2=2N1-2+N2-1 samples D3=(N3-1)/2 samples D1+D2+D3=2N1-1+N2-1+(N3-1)/2=(2N1-2)+(N2-1)+(N3-1)/2 samples after upsampling (increase the number of sample intervals by 2) D1+D2+D3=4N1-4+2N2-2+N3-1 samples D4=(N4-1)/2 samples D1+D2+D3+D4=(8/2)*(N1-4)+(4/2)*(N2-1)+(2/2)*(N3-1)+(1/2)*(N4-1) samples This is for interpolation ratios of 2 at each stage. You should be able to generalize it for interpolation ratios greater than 2 at each stage or for different interpolation ratios at each stage. Fred