why we want to do folding while performing convolution

Rune Allnor wrote:
> steve wrote:
> > intuitively why do you need to flip it? I don't know
>
> The folding/flipping/convolving pops straight out as a result of the
> intuitive arguments behind and derivation of the convolution sum
> formula. The flipping as such may not be "intuitive", but once you
> have derived the convolution sum formula using ONLY the linear
> systems properties of superposition and shift invariance, you
> can easily see how the "flipping" results, you can see why it
> occurs, and once you have seen these two, you don't need an
> argument as to why one "wants" to do the flipping.

I suspected that a detailed derivation with appropriate assumptions
would be the only way to get there, but I was hoping for a short cut
answer, lazy me :)


>
> The ommision of the derivation of the convolution sum formula
> this way, is one of the greatest dis-services modern DSP texts
> do to the profession. The convolution sum fomula is so
> fundamental that everybody should be able to derive it in
> the way indicated above. I sent a sketch of this derivation
> to Rick Lyons for his 3rd edition. It remains to be seen
> if he incorporates it if and when a 3rd edition is released.
>
> BTW, I only did this derivation a year ago or so, myself.
> Only then, after having dabbled with DSP for some 15 years,
> could I convince myself that I understand what convolution is
> all about.

I think that is a typical situation in engineering, in general,
undergrad engineering studies are basically using formula's without
understanding, or at most robotic derivation without meaning. Tests
should really be essay format, not constantly flipping equations
around.

It seems the more advanced the post grad courses are, the more they
require fundamental understanding of the most basic concepts. The more
advanced, the simpler the concept is explored.  I suppose physics is
the most extreme example.

I will try working out the derivation...


  



> 
> Rune

steve wrote:
> [...]
> I think that is a typical situation in engineering, in general,
> undergrad engineering studies are basically using formula's without
> understanding, or at most robotic derivation without meaning.

I'm not sure that's true. For example, the "Signals and Systems"
text I referred you to is (or was) the undergraduate linear system
theory text for MIT's engineering program, and as I said, it has
the best derivation of convolution I've ever seen.

--Randy

Rune Allnor schrieb:

> steve wrote:
> > intuitively why do you need to flip it? I don't know
>
> The folding/flipping/convolving pops straight out as a result of the
> intuitive arguments behind and derivation of the convolution sum
> formula. The flipping as such may not be "intuitive", but once you
> have derived the convolution sum formula using ONLY the linear
> systems properties of superposition and shift invariance, you
> can easily see how the "flipping" results, you can see why it
> occurs, and once you have seen these two, you don't need an
> argument as to why one "wants" to do the flipping.

It is essentially a question of phase. Say you have a filter kernel
which you want to apply to a signal. You do two different linear
operations, resulting in two output signals.

1. Apply the kernel using the standard convolution sum method.
2. Apply the kernel using the standard correlation sum method (which is
the same as 1 but with the kernel not flipped in time).

What is the difference between the two output signals? Discuss this
using the frequency response of the kernel.

Regards,
Andor

steve skrev:
> Rune Allnor wrote:
> > steve wrote:
> > > intuitively why do you need to flip it? I don't know
> >
> > The folding/flipping/convolving pops straight out as a result of the
> > intuitive arguments behind and derivation of the convolution sum
> > formula. The flipping as such may not be "intuitive", but once you
> > have derived the convolution sum formula using ONLY the linear
> > systems properties of superposition and shift invariance, you
> > can easily see how the "flipping" results, you can see why it
> > occurs, and once you have seen these two, you don't need an
> > argument as to why one "wants" to do the flipping.
>
> I suspected that a detailed derivation with appropriate assumptions
> would be the only way to get there, but I was hoping for a short cut
> answer, lazy me :)

The derivation is ridiculously simple, once explained by drawing
graphs on a blackboard. It ought to be possible to obtain within
the first six lessons (well, four really) of an intro course in DSP.
I am not sure I would be able to teach it that fast, but a more
seasoned lecturer than me ought to be able to achieve it that fast.

In text, the derivation becomes a bit more difficult, since it takes a
lot of words to explain what is obvious when demonstrated with
a graph on a blackboard.

Rune

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).

Chris
=====================
Chris Bore
BORES Signal Processing
www.bores.com

sk wrote:
> hi all
> can u explain in detail why there is need for folding when we perform
> convolution operation with an (practical)example?
> 
> thanks in advance
> sk

"sk" <sangeetha.kolandasamy@gmail.com> asked in message 
news:1153200837.599418.248170@35g2000cwc.googlegroups.com...
> can u explain in detail why there is need for folding when we perform
> convolution operation with an (practical)example?

Let the unit response of a filter be denoted by h[n], and let
x[n] denote the input.  Think of the input as the sum of many
different delayed and scaled unit inputs:

       t = 0             t = 1                  t = 2               t = 3 
.......   t = n

x =  x[0],                0,                     0,                     0, 
.....               0
                         +
       0,                x[1],                      0,                    0, 
.....               0
                          +
       0,                    0,                  x[2],                    0, 
......              0
                           +
          and so on

The output produced by the first signal is
h[0]x[0],      h[1]x[0],             h[2]x[0],         h[3]x[0], ..... 
h[n]x[0], .....

by the second
            0,     h[0]x[1],            h[1]x[1],          h[2]x[2],...... 
h[n-1]x[1], ......

by the third
            0,                0,             h[0]x[2],         h[1]x[2], 
.....     h[n-2]x[2],

and so on.  By the principle of linearity and superposition, the output due
to x at any time instant is obtained by adding up the entries in each 
column.
In particular, at time n, the output is

h[n]x[0] + h[n-1]x[1] + h[n-2]x[2] + ......

which explains why "flipping" is needed in convolution.  No need to
drag in Fourier transforms and the like.

Hope this helps.

--Dilip Sarwate 

Dilip V. Sarwate wrote:
< [...]

Simply excellent, Dilip! 

--Randy

Dilip V. Sarwate skrev:
> "sk" <sangeetha.kolandasamy@gmail.com> asked in message
> news:1153200837.599418.248170@35g2000cwc.googlegroups.com...
> > can u explain in detail why there is need for folding when we perform
> > convolution operation with an (practical)example?
>
> Let the unit response of a filter be denoted by h[n], and let
> x[n] denote the input.  Think of the input as the sum of many
> different delayed and scaled unit inputs:
>
>        t = 0             t = 1                  t = 2               t = 3
> .......   t = n
>
> x =  x[0],                0,                     0,                     0,
> .....               0
>                          +
>        0,                x[1],                      0,                    0,
> .....               0
>                           +
>        0,                    0,                  x[2],                    0,
> ......              0
>                            +
>           and so on
>
> The output produced by the first signal is
> h[0]x[0],      h[1]x[0],             h[2]x[0],         h[3]x[0], .....
> h[n]x[0], .....
>
> by the second
>             0,     h[0]x[1],            h[1]x[1],          h[2]x[2],......
> h[n-1]x[1], ......
>
> by the third
>             0,                0,             h[0]x[2],         h[1]x[2],
> .....     h[n-2]x[2],
>
> and so on.  By the principle of linearity and superposition, the output due
> to x at any time instant is obtained by adding up the entries in each
> column.
> In particular, at time n, the output is
>
> h[n]x[0] + h[n-1]x[1] + h[n-2]x[2] + ......
>
> which explains why "flipping" is needed in convolution.  No need to
> drag in Fourier transforms and the like.
>
> Hope this helps.
>
> --Dilip Sarwate

Hi Dilip.

This is exactly the derivation I hinted at in my posts. I am
pleased to see that I was right in that a more seasoned
lecturer than me would be able to teach this in no time.
Based on your post, I'll be able to express the derivation
in text too, not only by means of graphics.

Thanks.

Rune

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.

Regards,
Andor

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.

	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.

-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 =----