Hi Oli,
My answer to your question is simple: In practice, we don't
compute a recursive moving-sum the way you describe.
Simple pseudocode for the filter would be
for (n = 0; n < N; n++)
{
y[n] = y[n-1] + x[n]- x[n - L];
}
This is NOT equivalent to the cascade of the feedforward section
followed by the feedback section you describe. One reason is that
the node between the two summers does not exist.
--Randy
Oli Filth wrote:
> Hi,
>
> I have a conundrum which I'm tying myself in knots thinking about; if
> anyone can shed any light it would be much appreciated!
>
> Take as a simple example the moving-sum filter:
>
> L-1
> H(z) = Sum { z^-n }
> n=0
>
> = 1 - z^-L
> --------
> 1 - z^-1
>
> The numerator includes a zero at DC, the denominator gives a pole at DC,
> and so these cancel, giving non-zero response at DC.
>
> However, if we implement the filter recursively:
> (I hope my ASCII art comes out ok...)
>
> +------+
> ---+--->| z^-L |------+
> | +------+ | -
> | v
> +----------------->0-----------------+----->
> ^ |
> | +------+ |
> +-----| z^-1 |<---+
> +------+
>
> This is equivalent to:
>
> +------+
> ---+--->| z^-L |------+
> | +------+ | -
> | v
> +----------------->0--->0-----------------+----->
> ^ |
> | +------+ |
> +-----| z^-1 |<---+
> +------+
>
> i.e. implementing the feedforward section before the feedback section,
> and doing the two additions separately.
>
> The feedforward section has already killed the DC component, so we can't
> recover it.
>
> So my question is, how does the recursive moving-sum filter manage to
> work (and we know it does), if it appears to be exactly equivalent to
> something that blocks DC?
>
>
> --
> Oli
Online · Live + on demand
February 9-11, 2027
Price goes up Nov 1: register now to lock in today's rate
Register Now →
Question on pole-zero cancellation
Started by ●June 7, 2006
Reply by ●June 7, 20062006-06-07
Reply by ●June 7, 20062006-06-07
Jerry Avins said the following on 08/06/2006 02:09:> Rune Allnor wrote: > > > As happens all too frequently, I'm confused. I assume that we agree that > a transversal moving-sum filter is just the common FIR structure with > all coefficients equal to unity.Yup.> The recursive form I know uses a delay, an adder, and a subtracter: > > +------+ > ---+--->| z^-L |------+ > | +------+ | - > | v > +----------- + --->0------->Perhaps I don't understand your diagram, but isn't that more of a comb filter than a moving sum? ;)> Although that is mathematically the same as > > +------+ > ---+--->| z^-L |------+ > | +------+ | - > | v > +----------------->0-----------------+-----> > ^ | > | +------+ | > +-----| z^-1 |<---+ > +------+ > > why look for trouble? Maybe if you built the filter the more elaborate > way, you would find it.I'm not implying that there would be trouble; the filter works in practice. I was just trying to resolve what appeared to me to be a paradox: the very fact that it works, but yet the "rigorous" maths appeared to say otherwise. -- Oli
Reply by ●June 7, 20062006-06-07
Randy Yates said the following on 08/06/2006 02:22:> Hi Oli, > > My answer to your question is simple: In practice, we don't > compute a recursive moving-sum the way you describe. > > Simple pseudocode for the filter would be > > for (n = 0; n < N; n++) > { > y[n] = y[n-1] + x[n]- x[n - L]; > } > > This is NOT equivalent to the cascade of the feedforward section > followed by the feedback section you describe. One reason is that > the node between the two summers does not exist.But in any practical implementation of the above code, the summation would have to be performed in two steps (well I guess you could design a 3-input binary adder; maybe they already exist - my knowledge of DSP hardware is somewhat limited...). Even if that weren't the case, (a+b+c) == a+(b+c) will always be true (except in floating point, obviously). -- Oli
Reply by ●June 7, 20062006-06-07
Oli Filth wrote:> Randy Yates said the following on 08/06/2006 02:22: > > Hi Oli, > > > > My answer to your question is simple: In practice, we don't > > compute a recursive moving-sum the way you describe. > > > > Simple pseudocode for the filter would be > > > > for (n = 0; n < N; n++) > > { > > y[n] = y[n-1] + x[n]- x[n - L]; > > } > > > > This is NOT equivalent to the cascade of the feedforward section > > followed by the feedback section you describe. One reason is that > > the node between the two summers does not exist. > > But in any practical implementation of the above code, the summation > would have to be performed in two steps (well I guess you could design a > 3-input binary adder; maybe they already exist - my knowledge of DSP > hardware is somewhat limited...). > > Even if that weren't the case, (a+b+c) == a+(b+c) will always be true > (except in floating point, obviously).Yes, I have no argument with your statements. I don't believe that changes my answer. Let's ask a question from a different direction: Where in the code I provide is the node I referred to? To save a post/response cycle, it doesn't exist. Yes, you usually perform addition in two steps, but you don't keep around the intermediate computation, which is what the cascade implementation you blocked out would have to do. And it is precisely that node that causes the problem! --Randy> > > -- > Oli
Reply by ●June 7, 20062006-06-07
Randy Yates said the following on 08/06/2006 02:44:> Oli Filth wrote: >> Randy Yates said the following on 08/06/2006 02:22: >>> Hi Oli, >>> >>> My answer to your question is simple: In practice, we don't >>> compute a recursive moving-sum the way you describe. >>> >>> Simple pseudocode for the filter would be >>> >>> for (n = 0; n < N; n++) >>> { >>> y[n] = y[n-1] + x[n]- x[n - L]; >>> } >>> >>> This is NOT equivalent to the cascade of the feedforward section >>> followed by the feedback section you describe. One reason is that >>> the node between the two summers does not exist. >> But in any practical implementation of the above code, the summation >> would have to be performed in two steps (well I guess you could design a >> 3-input binary adder; maybe they already exist - my knowledge of DSP >> hardware is somewhat limited...). >> >> Even if that weren't the case, (a+b+c) == a+(b+c) will always be true >> (except in floating point, obviously). > > Yes, I have no argument with your statements. I don't > believe that changes my answer. > > Let's ask a question from a different direction: Where in the code I > provide is the node I referred to? > > To save a post/response cycle, it doesn't exist. Yes, you > usually perform addition in two steps, but you don't keep > around the intermediate computation, which is what the > cascade implementation you blocked out would have to > do. And it is precisely that node that causes the problem!Why would it matter whether the variable is named or anonymous? Isn't that just a matter of high-level language syntax? The node becomes explicit when you compile your code to machine-code. Diagram repeated for reference: +------+ ---+--->| z^-L |------+ | +------+ | - | v +----------------->0--->0-----------------+-----> ^ | | +------+ | +-----| z^-1 |<---+ +------+ -- Oli
Reply by ●June 7, 20062006-06-07
You're right, Oli! I've been misinterpreting this for years. I thought it was the way in which the operations were being performed that caused this to work. It isn't - I just modeled it in Matlab and I get recovery of DC even when I compute with the zero first. It appears to be just as Tim has stated - this works because we're using perfect arithmetic. The transient generated by the zero section gets integrated by the integrator section back into a perfect DC signal. As Tim said, if there was a finite-precision multiplication involved, so that the result had some error, this wouldn't work, or wouldn't work as well. That's why you want to avoid this structure in practice. Thanks for helping me learn something new. --Randy Oli Filth wrote:> Randy Yates said the following on 08/06/2006 02:44: > > Oli Filth wrote: > >> Randy Yates said the following on 08/06/2006 02:22: > >>> Hi Oli, > >>> > >>> My answer to your question is simple: In practice, we don't > >>> compute a recursive moving-sum the way you describe. > >>> > >>> Simple pseudocode for the filter would be > >>> > >>> for (n = 0; n < N; n++) > >>> { > >>> y[n] = y[n-1] + x[n]- x[n - L]; > >>> } > >>> > >>> This is NOT equivalent to the cascade of the feedforward section > >>> followed by the feedback section you describe. One reason is that > >>> the node between the two summers does not exist. > >> But in any practical implementation of the above code, the summation > >> would have to be performed in two steps (well I guess you could design a > >> 3-input binary adder; maybe they already exist - my knowledge of DSP > >> hardware is somewhat limited...). > >> > >> Even if that weren't the case, (a+b+c) == a+(b+c) will always be true > >> (except in floating point, obviously). > > > > Yes, I have no argument with your statements. I don't > > believe that changes my answer. > > > > Let's ask a question from a different direction: Where in the code I > > provide is the node I referred to? > > > > To save a post/response cycle, it doesn't exist. Yes, you > > usually perform addition in two steps, but you don't keep > > around the intermediate computation, which is what the > > cascade implementation you blocked out would have to > > do. And it is precisely that node that causes the problem! > > Why would it matter whether the variable is named or anonymous? Isn't > that just a matter of high-level language syntax? The node becomes > explicit when you compile your code to machine-code. > > > Diagram repeated for reference: > > +------+ > ---+--->| z^-L |------+ > | +------+ | - > | v > +----------------->0--->0-----------------+-----> > ^ | > | +------+ | > +-----| z^-1 |<---+ > +------+ > > > -- > Oli
Reply by ●June 7, 20062006-06-07
By the way, your quandary is resolved (I believe) by realizing that you're thinking purely steady-state and ignoring the transient effects. Yes, steady-state, the differencer produces a zero, and if that was all there was, you could never recover DC. But it isn't just the steady-state zero that gets input to the integrator, but the transient as well. --Randy Randy Yates wrote:> You're right, Oli! > > I've been misinterpreting this for years. I thought it was the > way in which the operations were being performed that caused > this to work. It isn't - I just modeled it in Matlab and I get recovery > of DC even when I compute with the zero first. > > It appears to be just as Tim has stated - this works > because we're using perfect arithmetic. The transient > generated by the zero section gets integrated by the > integrator section back into a perfect DC signal. As > Tim said, if there was a finite-precision multiplication > involved, so that the result had some error, this > wouldn't work, or wouldn't work as well. That's why > you want to avoid this structure in practice. > > Thanks for helping me learn something new. > > --Randy > > Oli Filth wrote: > > Randy Yates said the following on 08/06/2006 02:44: > > > Oli Filth wrote: > > >> Randy Yates said the following on 08/06/2006 02:22: > > >>> Hi Oli, > > >>> > > >>> My answer to your question is simple: In practice, we don't > > >>> compute a recursive moving-sum the way you describe. > > >>> > > >>> Simple pseudocode for the filter would be > > >>> > > >>> for (n = 0; n < N; n++) > > >>> { > > >>> y[n] = y[n-1] + x[n]- x[n - L]; > > >>> } > > >>> > > >>> This is NOT equivalent to the cascade of the feedforward section > > >>> followed by the feedback section you describe. One reason is that > > >>> the node between the two summers does not exist. > > >> But in any practical implementation of the above code, the summation > > >> would have to be performed in two steps (well I guess you could design a > > >> 3-input binary adder; maybe they already exist - my knowledge of DSP > > >> hardware is somewhat limited...). > > >> > > >> Even if that weren't the case, (a+b+c) == a+(b+c) will always be true > > >> (except in floating point, obviously). > > > > > > Yes, I have no argument with your statements. I don't > > > believe that changes my answer. > > > > > > Let's ask a question from a different direction: Where in the code I > > > provide is the node I referred to? > > > > > > To save a post/response cycle, it doesn't exist. Yes, you > > > usually perform addition in two steps, but you don't keep > > > around the intermediate computation, which is what the > > > cascade implementation you blocked out would have to > > > do. And it is precisely that node that causes the problem! > > > > Why would it matter whether the variable is named or anonymous? Isn't > > that just a matter of high-level language syntax? The node becomes > > explicit when you compile your code to machine-code. > > > > > > Diagram repeated for reference: > > > > +------+ > > ---+--->| z^-L |------+ > > | +------+ | - > > | v > > +----------------->0--->0-----------------+-----> > > ^ | > > | +------+ | > > +-----| z^-1 |<---+ > > +------+ > > > > > > -- > > Oli
Reply by ●June 8, 20062006-06-08
Oli Filth wrote:> Jerry Avins said the following on 08/06/2006 02:09: > >> Rune Allnor wrote: >> >> >> As happens all too frequently, I'm confused. I assume that we agree that >> a transversal moving-sum filter is just the common FIR structure with >> all coefficients equal to unity. > > > Yup. > > >> The recursive form I know uses a delay, an adder, and a subtracter: >> >> +------+ >> ---+--->| z^-L |------+ >> | +------+ | - >> | v >> +----------- + --->0-------> > > > Perhaps I don't understand your diagram, but isn't that more of a comb > filter than a moving sum? ;) > > >> Although that is mathematically the same as >> >> +------+ >> ---+--->| z^-L |------+ >> | +------+ | - >> | v >> +----------------->0-----------------+-----> >> ^ | >> | +------+ | >> +-----| z^-1 |<---+ >> +------+ >> >> why look for trouble? Maybe if you built the filter the more elaborate >> way, you would find it. > > > I'm not implying that there would be trouble; the filter works in > practice. I was just trying to resolve what appeared to me to be a > paradox: the very fact that it works, but yet the "rigorous" maths > appeared to say otherwise.The filter works because in practice, we don't build it the way you describe. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●June 8, 20062006-06-08
Oli Filth wrote:> > However, if we implement the filter recursively: > (I hope my ASCII art comes out ok...) > > +------+ > ---+--->| z^-L |------+ > | +------+ | - > | v > +----------------->0-----------------+-----> > ^ | > | +------+ | > +-----| z^-1 |<---+ > +------+ > > This is equivalent to: > > +------+ > ---+--->| z^-L |------+ > | +------+ | - > | v > +----------------->0--->0-----------------+-----> > ^ | > | +------+ | > +-----| z^-1 |<---+ > +------+ > > i.e. implementing the feedforward section before the feedback section, > and doing the two additions separately. > > The feedforward section has already killed the DC component, so we can't > recover it. > > So my question is, how does the recursive moving-sum filter manage to > work (and we know it does), if it appears to be exactly equivalent to > something that blocks DC?this is the similar to asking what happens if we multiply by zero before we divide by zero. r b-j
Reply by ●June 8, 20062006-06-08
"Rune Allnor" <allnor@tele.ntnu.no> wrote in message news:1149711635.111729.85600@j55g2000cwa.googlegroups.com...> > Oli Filth skrev: > > Hi, > > > > I have a conundrum which I'm tying myself in knots thinking about; if > > anyone can shed any light it would be much appreciated! > > > > Take as a simple example the moving-sum filter: > > > > L-1 > > H(z) = Sum { z^-n } > > n=0 > > > > = 1 - z^-L > > -------- > > 1 - z^-1 > > > > The numerator includes a zero at DC, the denominator gives a pole at DC, > > and so these cancel, giving non-zero response at DC. > > > > However, if we implement the filter recursively: > > (I hope my ASCII art comes out ok...) > > > > +------+ > > ---+--->| z^-L |------+ > > | +------+ | - > > | v > > +----------------->0-----------------+-----> > > ^ | > > | +------+ | > > +-----| z^-1 |<---+ > > +------+ > > > > This is equivalent to: > > > > +------+ > > ---+--->| z^-L |------+ > > | +------+ | - > > | v > > +----------------->0--->0-----------------+-----> > > ^ | > > | +------+ | > > +-----| z^-1 |<---+ > > +------+ > > > > i.e. implementing the feedforward section before the feedback section, > > and doing the two additions separately. > > > > The feedforward section has already killed the DC component, so we can't > > recover it. > > > > So my question is, how does the recursive moving-sum filter manage to > > work (and we know it does), if it appears to be exactly equivalent to > > something that blocks DC? > > Because the zero at DC is exactly cancelled by a pole. Note that the > second block scheme of yours is an expanded representation of the > total system, not the actual system. You can multiply any number by 1, > no matter how the factor 1 is represented, provided the representation > is exact. > > Any transfer function H(z) can be expanded in a similar way: > > H(z) = 1*H(z) = (1-z)/(1-z)*H(z) > > (* means multiplication) and we have the same "paradox" you > found above. > > Rune >This can be found by looking at the numerator and denominator as polynomials. If there is no common factor we say they are relatively prime. ie the Greatest common diviser is unity. I think Euclids algorithm or some such can find this out. Alternatively in State-Space the system must be controllable or observable (depending on the realisation). M.P -- Posted via a free Usenet account from http://www.teranews.com
