why we want to do folding while performing convolution

jim wrote:
> Andor wrote:
> >
> > Chris Bore wrote:
> > > The flip in convolution makes the frequency domain behavior easier to
> > > understand.
> > >
> > > Convolving two signals is represented in the frequency domain by
> > > multiplying their frequency soectra. So it is a simple and easy to
> > > understand model of a frequency dokmain operation.
> > >
> > > If you did it without the flip, that would be correlation. Correlation
> > > is represented in the frequency domain by multiplying the complex
> > > conjugate of one signal by the frequency spectrum of the other. The
> > > complex conjugate makes this less easy to intuitively understand, so
> > > convolution is often used (eg for filtering).
> >
> > You are right. Both convolution and correlation (which can be viewed as
> > convolution with the time-reversed kernel) have a simple interpretation
> > in the frequency domain. If you are not interested in the phase
> > response of the filtering, you do not have to flip the kernel, ie. you
> > can perform correlation instead of convolution.
> >
> > By the way, the time-inversion of the kernel produces slightly more
> > than just the conjugate frequency response. Remember that for a DFT
> > pair x[n] and X[k] (with x[n]) real we have
> >
> > x[-n] <-> X[-k] = X[k]* (because of Hermitian symmetry).
> >
> > But x[-n] is not the time-reversed vector, because x[-n] = (x(0),
> > x(N-1), x(N-2), .... , x(1)), ie. we have to apply a left-shift to get
> > the time-reversed vector (x(N-1), x(N-2), ..., x(1), x(0)). In the
> > frequency domain, this left-shift translates into a transform (shift
> > theorem) with the matrix
> >
> > diag(1, exp(2 pi j 1/N), ..., exp(2 pi j (N-1)/N) )
> >
> > ie. in addition to the conjuagation of the frequency response there is
> > a linear-phase shift.
>
> Yes, but the linear phase term is strictly an artifact of your chosen
> indexing system. If you choose to index the convolution kernel using the
> center of the kernel as the zero reference point the linear phase term
> disappears.

That's true. But choosing the center of the kernel as zero-index can
only be done for kernels of an odd size ...

>
> 	Another way to view it is any finite convolution kernel can be
> decomposed into two parallel kernels - one that is symmetric and one
> that is anti-symmetric (symmetry about the mid-point). The symmetric
> part requires no flipping to perform convolution as that would be
> redundant. The anti-symmetric part needs to be flipped, but you can
> instead of flipping the ordering just flip the signs of the coefficients
> (or simply negate the result after summation) as that will accomplish
> the same thing. After the 2 parts are convolved separately with the
> input sequence the result can be summed to get the same output as
> conventional convolution.
>
> 	If the convolution is structured in this way as two parallel operations
> its easy to see that the symmetric part maps to the real part in the
> frequency domain and the anti-symmetric part maps to the imaginary
> component of the frequency domain. So the frequency response of such a
> decomposed kernel cam be easily computed as a sum of cosines for the
> symmetrical part and a sum of sines for the anti-symmetrical with no
> linear phase term hanging on to cloud things. The linear phase term to
> which you refer is purely a result of the conventional index numbering
> scheme which references what is perceived to be the origin point.

Nice explanation.

Regards,
Andor

Andor wrote:

> 
> That's true. But choosing the center of the kernel as zero-index can
> only be done for kernels of an odd size ...

Well, not really. If you limit your indexing capability to whole
integers then you are saddled with that limitation (in other words, if
you require your reference zero to land on a sample point only odd sized
kernels will be allowed). But there is no mathematical reason preventing
you from setting zero to half way between two samples. 

-jim 

> 
> >
> >       Another way to view it is any finite convolution kernel can be
> > decomposed into two parallel kernels - one that is symmetric and one
> > that is anti-symmetric (symmetry about the mid-point). The symmetric
> > part requires no flipping to perform convolution as that would be
> > redundant. The anti-symmetric part needs to be flipped, but you can
> > instead of flipping the ordering just flip the signs of the coefficients
> > (or simply negate the result after summation) as that will accomplish
> > the same thing. After the 2 parts are convolved separately with the
> > input sequence the result can be summed to get the same output as
> > conventional convolution.
> >
> >       If the convolution is structured in this way as two parallel operations
> > its easy to see that the symmetric part maps to the real part in the
> > frequency domain and the anti-symmetric part maps to the imaginary
> > component of the frequency domain. So the frequency response of such a
> > decomposed kernel cam be easily computed as a sum of cosines for the
> > symmetrical part and a sum of sines for the anti-symmetrical with no
> > linear phase term hanging on to cloud things. The linear phase term to
> > which you refer is purely a result of the conventional index numbering
> > scheme which references what is perceived to be the origin point.
> 
> Nice explanation.
> 
> Regards,
> Andor

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

jim wrote:
> 
> Andor wrote:

   ...

>> ie. in addition to the conjuagation of the frequency response there is
>> a linear-phase shift.
> 
> Yes, but the linear phase term is strictly an artifact of your chosen
> indexing system. If you choose to index the convolution kernel using the
> center of the kernel as the zero reference point the linear phase term
> disappears.

Sure, but practical circuits are causal, so we describe them that way. 
Otherwise, an explicit time reference would be needed. If "tomorrow" 
were relative to whenever, it wouldn't mean much.

   ...

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jerry Avins wrote:
> 
> jim wrote:
> >
> > Andor wrote:
> 
>    ...
> 
> >> ie. in addition to the conjuagation of the frequency response there is
> >> a linear-phase shift.
> >
> > Yes, but the linear phase term is strictly an artifact of your chosen
> > indexing system. If you choose to index the convolution kernel using the
> > center of the kernel as the zero reference point the linear phase term
> > disappears.
> 
> Sure, but practical circuits are causal, so we describe them that way.
> Otherwise, an explicit time reference would be needed. If "tomorrow"
> were relative to whenever, it wouldn't mean much.
> 

The discussion was in regard to convolution of finite and discrete
impulse responses which practical circuits do not have. I've never seen
"tomorrow" labeled on a calender. You can make anything appear wrong if
you take out the context.

-jim

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

jim wrote:
> Andor wrote:
>
> >
> > That's true. But choosing the center of the kernel as zero-index can
> > only be done for kernels of an odd size ...
>
> Well, not really. If you limit your indexing capability to whole
> integers then you are saddled with that limitation (in other words, if
> you require your reference zero to land on a sample point only odd sized
> kernels will be allowed). But there is no mathematical reason preventing
> you from setting zero to half way between two samples.

Interesting. Let's say you have a first order difference filter (two
coefficients). How does a symmetric indexing scheme work with this
filter?

I wrote:
> jim wrote:
> > Andor wrote:
> >
> > >
> > > That's true. But choosing the center of the kernel as zero-index can
> > > only be done for kernels of an odd size ...
> >
> > Well, not really. If you limit your indexing capability to whole
> > integers then you are saddled with that limitation (in other words, if
> > you require your reference zero to land on a sample point only odd sized
> > kernels will be allowed). But there is no mathematical reason preventing
> > you from setting zero to half way between two samples.
>
> Interesting. Let's say you have a first order difference filter (two
> coefficients). How does a symmetric indexing scheme work with this
> filter?

Banlimited interpolation makes this into an IIR filter. Hardly the kind
of operation that simplifies the analysis. I prefer the linear-phase
term :-).

Regards,
Andor

Andor wrote:
> 
> jim wrote:
> > Andor wrote:
> >
> > >
> > > That's true. But choosing the center of the kernel as zero-index can
> > > only be done for kernels of an odd size ...
> >
> > Well, not really. If you limit your indexing capability to whole
> > integers then you are saddled with that limitation (in other words, if
> > you require your reference zero to land on a sample point only odd sized
> > kernels will be allowed). But there is no mathematical reason preventing
> > you from setting zero to half way between two samples.
> 
> Interesting. Let's say you have a first order difference filter (two
> coefficients). How does a symmetric indexing scheme work with this
> filter?


First of all as you stated in the first post that I replied to, the
shift theorem tells you how much to shift to eliminate the linear phase
term, so you should be able to work it out from that alone. Remember,
The indices themselves are shifts and the entire kernel can be
decomposed into single shifted impulses. If instead you choose to
decompose into symmetrical and anti symmetrical parts then each part is
composed of matched pairs of impulses where the distance between is
increasing by 2.

For computing the frequency response for kernel of length N that can be
boiled down to this:

For a odd length filter -> sum of sines and cosines with even multiples
of Pi (0, 2, 4, ... N-1)

For a even length filter -> sum of sines and cosines with odd multiples
of Pi (1, 3, 5, ... N-1)



So if your filter was [3 -1]. That decomposes to [1 1] and [2 -2]

and thus the frequency response is cos(pi) +  2*sin(pi) 


-jim

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

Andor wrote:
> jim wrote:
>> Andor wrote:
>>
>>> That's true. But choosing the center of the kernel as zero-index can
>>> only be done for kernels of an odd size ...
>> Well, not really. If you limit your indexing capability to whole
>> integers then you are saddled with that limitation (in other words, if
>> you require your reference zero to land on a sample point only odd sized
>> kernels will be allowed). But there is no mathematical reason preventing
>> you from setting zero to half way between two samples.
> 
> Interesting. Let's say you have a first order difference filter (two
> coefficients). How does a symmetric indexing scheme work with this
> filter?

Not so hard if you allow me to ignore the distinction between an index 
and an argument. (t - 1) and (t) become (t - 1/2) and (t + 1/2).

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

jim wrote:
> Andor wrote:
> >
> > jim wrote:
> > > Andor wrote:
> > >
> > > >
> > > > That's true. But choosing the center of the kernel as zero-index can
> > > > only be done for kernels of an odd size ...
> > >
> > > Well, not really. If you limit your indexing capability to whole
> > > integers then you are saddled with that limitation (in other words, if
> > > you require your reference zero to land on a sample point only odd sized
> > > kernels will be allowed). But there is no mathematical reason preventing
> > > you from setting zero to half way between two samples.
> >
> > Interesting. Let's say you have a first order difference filter (two
> > coefficients). How does a symmetric indexing scheme work with this
> > filter?
>
>
> First of all as you stated in the first post that I replied to, the
> shift theorem tells you how much to shift to eliminate the linear phase
> term, so you should be able to work it out from that alone.

The shift theorem works only for integer shifts. For non-integer shifts
periodic interpolation in time-domain is performed. This does not
result in the same filter as with bandlimited interpolation. For
example, the first difference filter h =  [1 -1] using a shift of 1/2
results in the zero filter (h[k] = cos(2 pi k) => h[k+1/2] = cos(2 pi
(k+1/2)) = 0). Contrast this to bandlimited interpolation of h when
shifted by 1/2 which results in the two-sided antisymmetric IIR  filter

h_{1/2} = [ ... -0.339531, 0.848826, 0, -0.848826, 0.339531, .... ]


> Remember,
> The indices themselves are shifts and the entire kernel can be
> decomposed into single shifted impulses. If instead you choose to
> decompose into symmetrical and anti symmetrical parts then each part is
> composed of matched pairs of impulses where the distance between is
> increasing by 2.
>
> For computing the frequency response for kernel of length N that can be
> boiled down to this:
>
> For a odd length filter -> sum of sines and cosines with even multiples
> of Pi (0, 2, 4, ... N-1)
>
> For a even length filter -> sum of sines and cosines with odd multiples
> of Pi (1, 3, 5, ... N-1)
>
>
>
> So if your filter was [3 -1]. That decomposes to [1 1] and [2 -2]
>
> and thus the frequency response is cos(pi) +  2*sin(pi)

I'm not quite sure where you are going with your calculation. The
frequency response of the filter [3 -1] is

H(w) = 3 - exp(-j w),

and its magnitude squared response is

|H(w)|^2 = 10 - 6 cos(w).

I don't see how your formula can be turned into either of those.
Anycase, we were discussing the frequency domain equivalent of
time-reversing the filter kernel. It is easy to show in this example
how time-reversion implies conjugation of the frequency response and
the multiplication of the linear-phase term corresponding to a time
shift:

H_r(w) = -1 + 3 exp(-j w) = exp(-j w) (- exp(j w) + 3) = exp(-j w)
H(w)*

Regards,
Andor

Andor wrote:

> The shift theorem works only for integer shifts.


OK. then it can't be done.

-jim



> For non-integer shifts
> periodic interpolation in time-domain is performed. This does not
> result in the same filter as with bandlimited interpolation. For
> example, the first difference filter h =  [1 -1] using a shift of 1/2
> results in the zero filter (h[k] = cos(2 pi k) => h[k+1/2] = cos(2 pi
> (k+1/2)) = 0). Contrast this to bandlimited interpolation of h when
> shifted by 1/2 which results in the two-sided antisymmetric IIR  filter
> 
> h_{1/2} = [ ... -0.339531, 0.848826, 0, -0.848826, 0.339531, .... ]
> 
> > Remember,
> > The indices themselves are shifts and the entire kernel can be
> > decomposed into single shifted impulses. If instead you choose to
> > decompose into symmetrical and anti symmetrical parts then each part is
> > composed of matched pairs of impulses where the distance between is
> > increasing by 2.
> >
> > For computing the frequency response for kernel of length N that can be
> > boiled down to this:
> >
> > For a odd length filter -> sum of sines and cosines with even multiples
> > of Pi (0, 2, 4, ... N-1)
> >
> > For a even length filter -> sum of sines and cosines with odd multiples
> > of Pi (1, 3, 5, ... N-1)
> >
> >
> >
> > So if your filter was [3 -1]. That decomposes to [1 1] and [2 -2]
> >
> > and thus the frequency response is cos(pi) +  2*sin(pi)
> 
> I'm not quite sure where you are going with your calculation. The
> frequency response of the filter [3 -1] is
> 
> H(w) = 3 - exp(-j w),
> 
> and its magnitude squared response is
> 
> |H(w)|^2 = 10 - 6 cos(w).
> 
> I don't see how your formula can be turned into either of those.
> Anycase, we were discussing the frequency domain equivalent of
> time-reversing the filter kernel. It is easy to show in this example
> how time-reversion implies conjugation of the frequency response and
> the multiplication of the linear-phase term corresponding to a time
> shift:
> 
> H_r(w) = -1 + 3 exp(-j w) = exp(-j w) (- exp(j w) + 3) = exp(-j w)
> H(w)*
> 
> Regards,
> Andor

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----