I need to convolve two polynomials which are the same - only one has all its roots outside the unity circle and the other within.eg a(z^-1) =a0+a1z^-1 + a2z^-2 +... with a(z) = a0+a1z+a2z^2+... ie one is causal in terms of z^-1 and the other is in terms of z (or can be interpreted thus). I can easily multiply the two and get a formula (a Laurent series) - but for large orders of polynomial this formula ( convolution) takes time. I was thinking to do a convolution in the freq domain ie V=F^-1[ F[X.X}} where X is a vector composed of the elements of the polynomial a. Since the result is symmetric then the convolution will be the same order as the original polynomial (I would just ignore the - ve or positive results - one of them I would keep. However, one of the polynomials is uncausal. When I set up the FFT time vectors with the elements of the a polynomial, how does this effect things? Hardy
Convolution
Started by ●July 17, 2009
Reply by ●July 17, 20092009-07-17
The DFT/FFT assumes that the region of convergence includes the unit circle, therefore you won't get the acausal version of the signal correctly. At this point I'm not sure how or if you could use a FFT to do this. Cheers, Dave On Jul 16, 11:32�pm, HardySpicer <gyansor...@gmail.com> wrote:> I need to convolve two polynomials which are the same - only one has > all its roots outside the unity circle and the other within.eg > > a(z^-1) =a0+a1z^-1 + a2z^-2 +... with a(z) = a0+a1z+a2z^2+... > > ie one is causal in terms of z^-1 and the other is in terms of z (or > can be interpreted thus). > > I can easily multiply the two and get a formula (a Laurent series) - > but for large orders of polynomial this formula ( convolution) takes > time. I was thinking to do a convolution in the freq domain ie > > V=F^-1[ F[X.X}} where X is a vector composed of the elements of the > polynomial a. Since the result is symmetric then the convolution will > be the same order as the original polynomial (I would just ignore the - > ve or positive results - one of them I would keep. However, one of the > polynomials is uncausal. When I set up the FFT time vectors with the > elements of the a polynomial, how does this effect things? > > Hardy
Reply by ●July 17, 20092009-07-17
Dave wrote:> The DFT/FFT assumes that the region of convergence includes the > unit circle, therefore you won't get the acausal version of the > signal correctly. > > At this point I'm not sure how or if you could use a FFT to do > this.First, if a(z) satisfies the condition you cite then so does a(1/z). Second, analytic considerations don't rear their heads with finite- order polynomials. All that's necessary is that the DFT be zero padded enough to implement linear convolution.> On Jul 16, 11:32�pm, HardySpicer <gyansor...@gmail.com> wrote:>> a(z^-1) =a0+a1z^-1 + a2z^-2 +... with a(z) = a0+a1z+a2z^2+...>> I can easily multiply the two and get a formula (a Laurent >> series) - but for large orders of polynomial this formula ( >> convolution) takes time. I was thinking to do a convolution in >> the freq domain>> However, one of the polynomials is uncausal. When I set up the >> FFT time vectors with the elements of the a polynomial, how does >> this effect things?The easiest way to think about it is to use the reversed polynomial of a(z), which is a(1/z) * z^degree(a), in place of a(1/z) itself and account for the time shift when indexing into the IDFT result. Martin -- Quidquid latine scriptum est, altum videtur.
Reply by ●July 17, 20092009-07-17
For some reason I was thinking about a system with poles. With a finite order it is essentially FIR which converges everywhere, so using the FFT isn't a problem. You just have to zero pad you sequences so that the terms line up properly i.e the z^1 terms line up for each poly, the z^2 terms line up for each poly , etc. Then you just need to zero pad again to eliminate the effect of circular convolution using the FFT. Cheers, Dave On Jul 17, 11:15�am, Martin Eisenberg <martin.eisenb...@udo.edu> wrote:> Dave wrote: > > The DFT/FFT assumes that the region of convergence includes the > > unit circle, therefore you won't get the acausal version of the > > signal correctly. > > > At this point I'm not sure how or if you could use a FFT to do > > this. > > First, if a(z) satisfies the condition you cite then so does a(1/z). > Second, analytic considerations don't rear their heads with finite- > order polynomials. All that's necessary is that the DFT be zero > padded enough to implement linear convolution. > > > On Jul 16, 11:32�pm, HardySpicer <gyansor...@gmail.com> wrote: > >> a(z^-1) =a0+a1z^-1 + a2z^-2 +... with a(z) = a0+a1z+a2z^2+... > >> I can easily multiply the two and get a formula (a Laurent > >> series) - but for large orders of polynomial this formula ( > >> convolution) takes time. I was thinking to do a convolution in > >> the freq domain > >> However, one of the polynomials is uncausal. When I set up the > >> FFT time vectors with the elements of the a polynomial, how does > >> this effect things? > > The easiest way to think about it is to use the reversed polynomial > of a(z), which is a(1/z) * z^degree(a), in place of a(1/z) itself and > account for the time shift when indexing into the IDFT result. > > Martin > > -- > Quidquid latine scriptum est, altum videtur.
Reply by ●July 17, 20092009-07-17
On Jul 17, 11:15�am, Dave <dspg...@netscape.net> wrote:> For some reason I was thinking about a system with poles. With a > finite order it is essentially FIR which converges everywhere, so > using the FFT isn't a problem. You just have to zero pad you sequences > so that the �terms line up properly i.e �the �z^1 terms line up for > each poly, the z^2 terms line up for each poly , etc. > Then �you just need to zero pad again to eliminate the effect of > circular convolution using the FFT. > > Cheers, > Dave > > On Jul 17, 11:15�am, Martin Eisenberg <martin.eisenb...@udo.edu> > wrote: > > > Dave wrote: > > > The DFT/FFT assumes that the region of convergence includes the > > > unit circle, therefore you won't get the acausal version of the > > > signal correctly. > > > > At this point I'm not sure how or if you could use a FFT to do > > > this. > > > First, if a(z) satisfies the condition you cite then so does a(1/z). > > Second, analytic considerations don't rear their heads with finite- > > order polynomials. All that's necessary is that the DFT be zero > > padded enough to implement linear convolution. > > > > On Jul 16, 11:32�pm, HardySpicer <gyansor...@gmail.com> wrote: > > >> a(z^-1) =a0+a1z^-1 + a2z^-2 +... with a(z) = a0+a1z+a2z^2+... > > >> I can easily multiply the two and get a formula (a Laurent > > >> series) - but for large orders of polynomial this formula ( > > >> convolution) takes time. I was thinking to do a convolution in > > >> the freq domain > > >> However, one of the polynomials is uncausal. When I set up the > > >> FFT time vectors with the elements of the a polynomial, how does > > >> this effect things? > > > The easiest way to think about it is to use the reversed polynomial > > of a(z), which is a(1/z) * z^degree(a), in place of a(1/z) itself and > > account for the time shift when indexing into the IDFT result. > > > Martin > > > -- > > Quidquid latine scriptum est, altum videtur.I figured it out. It is possible. Hardy
Reply by ●July 17, 20092009-07-17
On Jul 17, 11:15�am, Dave <dspg...@netscape.net> wrote:> For some reason I was thinking about a system with poles. With a > finite order it is essentially FIR which converges everywhere, so > using the FFT isn't a problem. You just have to zero pad you sequences > so that the �terms line up properly i.e �the �z^1 terms line up for > each poly, the z^2 terms line up for each poly , etc. > Then �you just need to zero pad again to eliminate the effect of > circular convolution using the FFT. > > Cheers, > Dave > > On Jul 17, 11:15�am, Martin Eisenberg <martin.eisenb...@udo.edu> > wrote: > > > Dave wrote: > > > The DFT/FFT assumes that the region of convergence includes the > > > unit circle, therefore you won't get the acausal version of the > > > signal correctly. > > > > At this point I'm not sure how or if you could use a FFT to do > > > this. > > > First, if a(z) satisfies the condition you cite then so does a(1/z). > > Second, analytic considerations don't rear their heads with finite- > > order polynomials. All that's necessary is that the DFT be zero > > padded enough to implement linear convolution. > > > > On Jul 16, 11:32�pm, HardySpicer <gyansor...@gmail.com> wrote: > > >> a(z^-1) =a0+a1z^-1 + a2z^-2 +... with a(z) = a0+a1z+a2z^2+... > > >> I can easily multiply the two and get a formula (a Laurent > > >> series) - but for large orders of polynomial this formula ( > > >> convolution) takes time. I was thinking to do a convolution in > > >> the freq domain > > >> However, one of the polynomials is uncausal. When I set up the > > >> FFT time vectors with the elements of the a polynomial, how does > > >> this effect things? > > > The easiest way to think about it is to use the reversed polynomial > > of a(z), which is a(1/z) * z^degree(a), in place of a(1/z) itself and > > account for the time shift when indexing into the IDFT result. > > > Martin > > > -- > > Quidquid latine scriptum est, altum videtur.What I did was just work out the Periodogram (mag squared) using zero padding and then take the inverse FFT. Throw away the last N/2 points. a(z).a(z^-1) = !(a(z))!^2. Hardy
Reply by ●July 18, 20092009-07-18
HardySpicer wrote:> What I did was just work out the Periodogram (mag squared) using > zero padding and then take the inverse FFT. Throw away the last > N/2 points. a(z).a(z^-1) = !(a(z))!^2.This is true only for real coefficients a_i which you didn't specify. Then, indeed, convolving a sequence with its own time reversal is the same as autocorrelation. With a complex sequence you'd have a conjugate to few in there (or one too many, since conj is self- inverse). Martin -- Quidquid latine scriptum est, altum videtur.
Reply by ●July 18, 20092009-07-18
On Jul 18, 2:50�am, Martin Eisenberg <martin.eisenb...@udo.edu> wrote:> HardySpicer wrote: > > What I did was just work out the Periodogram (mag squared) using > > zero padding and then take the inverse FFT. Throw away the last > > N/2 points. a(z).a(z^-1) = !(a(z))!^2. > > This is true only for real coefficients a_i which you didn't specify. > Then, indeed, convolving a sequence with its own time reversal is the > same as autocorrelation. With a complex sequence you'd have a > conjugate to few in there (or one too many, since conj is self- > inverse). > > Martin > > -- > Quidquid latine scriptum est, altum videtur.yes agreed - thanks folks
