Adaptive Filter | ADPCM | ADSP | ADSP-2181 | Aliasing | AMR | Anti-Aliasing | ARMA | Autocorrelation | AutoCovariance | Beamforming | Bessel | Blackfin | Butterworth | C6713 | CCS | Chebyshev | CIC Filter | Circular Convolution | Code Composer Studio | Comb Filter | Compression | Convolution | Cross Correlation | DCT | Decimation | Deconvolution | Demodulation | DM642 | DSP Boards | DSP/BIOS | DTMF | Echo Cancellation | Equalization | Equalizer | ETSI | EZLITE (Ez-kit Lite) | FFT | FFTW | FIR Filter | Fixed Point | FSK | G.711 | G.723 | G.729 | Gaussian Noise | Goertzel | GPIO | Hilbert Transform | IFFT | IIR Filter | Interpolation | Invariance | JTAG | Kalman | Laplace Transform | Levinson | LPC | McBSP | MIPS | Modulation | MPEG | Multirate | Notch Filter | Nyquist | OFDM | Oversampling | Pink Noise | Pitch | PLL | Polyphase | QAM | QDMA | Quantization | Quantizer | Radar | Random Noise | Reed Solomon | Remez | Resampling | RTDX | Sampling | Sharc | TI C6711 | Undersampling | Viterbi | Wavelets | White Noise | Wiener Filter | Windowing | XDS510PP | Z Transform

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

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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=A0pm, 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) =3Da0+a1z^-1 + a2z^-2 +... with a(z) =3D 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=3DF^-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

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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.

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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=A0am, 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=A0pm, HardySpicer <gyansor...@gmail.com> wrote:
> >> a(z^-1) =3Da0+a1z^-1 + a2z^-2 +... with a(z) =3D 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.

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

On Jul 17, 11:15=A0am, 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 =A0terms line up properly i.e =A0the =A0z^1 terms line up for
> each poly, the z^2 terms line up for each poly , etc.
> Then =A0you just need to zero pad again to eliminate the effect of
> circular convolution using the FFT.
>
> Cheers,
> Dave
>
> On Jul 17, 11:15=A0am, 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=A0pm, HardySpicer <gyansor...@gmail.com> wrote:
> > >> a(z^-1) =3Da0+a1z^-1 + a2z^-2 +... with a(z) =3D 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

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

On Jul 17, 11:15=A0am, 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 =A0terms line up properly i.e =A0the =A0z^1 terms line up for
> each poly, the z^2 terms line up for each poly , etc.
> Then =A0you just need to zero pad again to eliminate the effect of
> circular convolution using the FFT.
>
> Cheers,
> Dave
>
> On Jul 17, 11:15=A0am, 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=A0pm, HardySpicer <gyansor...@gmail.com> wrote:
> > >> a(z^-1) =3Da0+a1z^-1 + a2z^-2 +... with a(z) =3D 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) =3D !(a(z))!^2.

Hardy

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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.

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

On Jul 18, 2:50=A0am, 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) =3D !(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

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.