"Fred Marshall" <fmarshallx@remove_the_x.acm.org> schrieb im Newsbeitrag
news:Ro2dnVQxgIhfmGzfRVn-hg@centurytel.net...
>
> "Raghavendra Mahuli" <raghavendra.ma@in.bosch.com> wrote in message
> news:dcpnam$1co$1@ns2.fe.internet.bosch.com...
> > Convolution is similar to long-multiplication which we learnt in
school...
> > so for ease of understanding, take signals 101 and 11 where both start
> > from
> > origin. now reverse 11. and-
> >
> > 101 x 11
> > -------------------
> > 1 0 1
> > 1 0 1 x
> > ---------------------
> > 1 1 1 1
> >
> > to find the origin, find out how many are to the right of origin in
> > unreversed signal... in this case it is 3..
> >
> > so our convolution sum in 1 1 1 1 , the signal starts at -1
>
> I'm intrigued but don't understand your notation. Can you elaborate
please?
>
> What happens if the sequence isn't single-bit?
>
> Fred
>
>
What he wanted to say was: a _multiplication_ of (integer) Numbers equals to
a _convolution_ of its digits. in decimal:
11 x 11=
11
+ 11
-----
121
121 x 121 =
121
+_242
+__121
-------
14641
Got the picture?
This was actually an auto-convolution (Convolution of a signal with itself)
resulting in a Gaussian Bell-curve afer a few steps. just do it with
14641 x 14641 and 'forget' the decimal carriage (allowing digits higher than
9 per column) and you'll see
But this is not the fastest but the slowest method to do a convolution (for
a pc).
For human beings it may be the fastest method because i don't think a FFT is
easier to write on paper.
or take 12 x 2001. think the first number as the signal and the second as
the impulse giving 24012.
Reply by ●August 5, 20052005-08-05
Fred Marshall wrote:
> "Mark Borgerding" <mark@borgerding.net> wrote in message
> news:ouAIe.45458$B52.11261@tornado.ohiordc.rr.com...
> > Fred Marshall wrote:
> >> "Raghavendra Mahuli" <raghavendra.ma@in.bosch.com> wrote in message
...
> > Multiplying two numbers is the same as convolving the coefficients of two
> > polynomials. The base is immaterial.
> >
> > In algebraic terms:
> > (aB^2 + bB + c )(xB^2 + yB + z)
> > evaluates to
> > axB^4 (ay+bx)B^3 + (az+by+cx)B^2 + (bz+cy)B + cz
> >
> > just as
> > conv( [a b c] , [x y z] )
> > evaluates to
> > [a ay+bx az+by+cx bz+cy c]
> That's really interesting!
> I think you meant ax and cz tho...
Yes. Good catch. The first and last term should be ax,cz.
I was just checking to see if you were awake ;)
>
> Now, back to the OP's question. I'm wondering how this approach makes
> convolution *fast* with pencil and paper. That's not obvious to me.
Beats me. I was just commenting on an interesting side thread.
I think it's pretty cool: some of the places convolution pops up.
Something I noted about statistics, but haven't actually proven ( or
perhaps remembered): adding together two or more random variables
yields a probability distribution function (pdf) that is the
convolution of the constituent pdfs.
That led me to think that perhaps the quality that psychologists try to
quantify as IQ is given its Gaussian distribution by the sum of a large
number of more uniformly distributed factors. Just as repeatedly
convolving a rectangular pulse with itself yields a Gaussian pulse,
adding together many uniformly distributed random variables yields a
Gaussian distributed rv.
--
Mark Borgerding
Reply by Fred Marshall●August 5, 20052005-08-05
"Mark Borgerding" <mark@borgerding.net> wrote in message
news:ouAIe.45458$B52.11261@tornado.ohiordc.rr.com...
> Fred Marshall wrote:
>> "Raghavendra Mahuli" <raghavendra.ma@in.bosch.com> wrote in message
>> news:dcpnam$1co$1@ns2.fe.internet.bosch.com...
>>
>>>Convolution is similar to long-multiplication which we learnt in
>>>school...
>>>so for ease of understanding, take signals 101 and 11 where both start
>>>from
>>>origin. now reverse 11. and-
>>>
>>> 101 x 11
>>>-------------------
>>> 1 0 1
>>>1 0 1 x
>>>---------------------
>>>1 1 1 1
>>>
>>>to find the origin, find out how many are to the right of origin in
>>>unreversed signal... in this case it is 3..
>>>
>>>so our convolution sum in 1 1 1 1 , the signal starts at -1
>>
>>
>> I'm intrigued but don't understand your notation. Can you elaborate
>> please?
>>
>> What happens if the sequence isn't single-bit?
>>
>> Fred
>>
>>
>
> Multiplying two numbers is the same as convolving the coefficients of two
> polynomials. The base is immaterial.
>
> In algebraic terms:
> (aB^2 + bB + c )(xB^2 + yB + z)
> evaluates to
> axB^4 (ay+bx)B^3 + (az+by+cx)B^2 + (bz+cy)B + cz
>
> just as
> conv( [a b c] , [x y z] )
> evaluates to
> [a ay+bx az+by+cx bz+cy c]
>
> It doesn't matter if the base B is 2 (as in the previous example), 10 (as
> in decimal numbers), or 4294967296 (as might be useful for an extended
> precision integer library)
>
> -- Mark Borgerding
That's really interesting!
I think you meant ax and cz tho...
Now, back to the OP's question. I'm wondering how this approach makes
convolution *fast* with pencil and paper. That's not obvious to me.
Fred
Reply by Mark Borgerding●August 4, 20052005-08-04
Fred Marshall wrote:
> "Raghavendra Mahuli" <raghavendra.ma@in.bosch.com> wrote in message
> news:dcpnam$1co$1@ns2.fe.internet.bosch.com...
>
>>Convolution is similar to long-multiplication which we learnt in school...
>>so for ease of understanding, take signals 101 and 11 where both start
>>from
>>origin. now reverse 11. and-
>>
>> 101 x 11
>>-------------------
>> 1 0 1
>>1 0 1 x
>>---------------------
>>1 1 1 1
>>
>>to find the origin, find out how many are to the right of origin in
>>unreversed signal... in this case it is 3..
>>
>>so our convolution sum in 1 1 1 1 , the signal starts at -1
>
>
> I'm intrigued but don't understand your notation. Can you elaborate please?
>
> What happens if the sequence isn't single-bit?
>
> Fred
>
>
Multiplying two numbers is the same as convolving the coefficients of
two polynomials. The base is immaterial.
In algebraic terms:
(aB^2 + bB + c )(xB^2 + yB + z)
evaluates to
axB^4 (ay+bx)B^3 + (az+by+cx)B^2 + (bz+cy)B + cz
just as
conv( [a b c] , [x y z] )
evaluates to
[a ay+bx az+by+cx bz+cy c]
It doesn't matter if the base B is 2 (as in the previous example), 10
(as in decimal numbers), or 4294967296 (as might be useful for an
extended precision integer library)
-- Mark Borgerding
Reply by Fred Marshall●August 3, 20052005-08-03
"Raghavendra Mahuli" <raghavendra.ma@in.bosch.com> wrote in message
news:dcpnam$1co$1@ns2.fe.internet.bosch.com...
> Convolution is similar to long-multiplication which we learnt in school...
> so for ease of understanding, take signals 101 and 11 where both start
> from
> origin. now reverse 11. and-
>
> 101 x 11
> -------------------
> 1 0 1
> 1 0 1 x
> ---------------------
> 1 1 1 1
>
> to find the origin, find out how many are to the right of origin in
> unreversed signal... in this case it is 3..
>
> so our convolution sum in 1 1 1 1 , the signal starts at -1
I'm intrigued but don't understand your notation. Can you elaborate please?
What happens if the sequence isn't single-bit?
Fred
Reply by ●August 3, 20052005-08-03
Convolution is similar to long-multiplication which we learnt in school...
so for ease of understanding, take signals 101 and 11 where both start from
origin. now reverse 11. and-
101 x 11
-------------------
1 0 1
1 0 1 x
---------------------
1 1 1 1
to find the origin, find out how many are to the right of origin in
unreversed signal... in this case it is 3..
so our convolution sum in 1 1 1 1 , the signal starts at -1
"Jane" <lunaliu3@yahoo.com> wrote in message
news:dc1o5i$10k$1@news.Stanford.EDU...
> Hi,
>
> Does anybody have the fastest method (using paper and pencil) to calculate
> the convolution:
>
> y[n]=x[n]*h[n]
>
> where x[n]=u[n-3] - u[n-14], h[n]=u[n-5] - u[n-8], where u[n] is the step
> function, u[n]=1 for n>=0, and u[n]=0 for n<0.
>
> Can you do it in 2 minutes?
>
>
Reply by ●July 26, 20052005-07-26
Jane wrote:
> "Jes�s Cid-Sueiro" <jcid@ing.uc3m.es> wrote in message
> news:dc2mq3$3o5$1@khitai.uc3m.es...
>
>>Noting that u[n]*u[n] = n u[n] =r[n] (which is a ramp with slope 1),
>>
>>y[n] = r[n-8] - r[n-11] - r[n-19] + r[n-22]
>>
>>which is a ramp starting at 8, becoming horizontal at 11, decreasing with
>>slope 1 at 19 and zero starting from 22.
>>
>>J.
>>
>
>
> Wow, this is the fastest method... !!! Yet just a small problem: when you
> say it starts at 8, you mean y[8]=0 or y[8]=1?
>
> Formal computation shows that y[8] should be 1, am I right? And also
> y[20]=1, y[21]=y[22]=... =0...
>
> So your result should be shifted a little bit to make it correct?
You are right... I should have started with...
"Noting that u[n]*u[n] = (n+1)*u[n] = r[n] ..."
Reply by Jane●July 26, 20052005-07-26
"Jes�s Cid-Sueiro" <jcid@ing.uc3m.es> wrote in message
news:dc2mq3$3o5$1@khitai.uc3m.es...
> Noting that u[n]*u[n] = n u[n] =r[n] (which is a ramp with slope 1),
>
> y[n] = r[n-8] - r[n-11] - r[n-19] + r[n-22]
>
> which is a ramp starting at 8, becoming horizontal at 11, decreasing with
> slope 1 at 19 and zero starting from 22.
>
> J.
>
Wow, this is the fastest method... !!! Yet just a small problem: when you
say it starts at 8, you mean y[8]=0 or y[8]=1?
Formal computation shows that y[8] should be 1, am I right? And also
y[20]=1, y[21]=y[22]=... =0...
So your result should be shifted a little bit to make it correct?
Reply by Fred Marshall●July 25, 20052005-07-25
"Jane" <lunaliu3@yahoo.com> wrote in message
news:dc1o5i$10k$1@news.Stanford.EDU...
> Hi,
>
> Does anybody have the fastest method (using paper and pencil) to calculate
> the convolution:
>
> y[n]=x[n]*h[n]
>
> where x[n]=u[n-3] - u[n-14], h[n]=u[n-5] - u[n-8], where u[n] is the step
> function, u[n]=1 for n>=0, and u[n]=0 for n<0.
>
> Can you do it in 2 minutes?
Easily. I did it in just over 1 minute. Here's how:
I drew a "cartoon" of both functions to set the specifications.
Then I went and got a timer. Set the timer and started:
I realized that one of them has to be reversed before "sliding", so I drew
another cartoon of it.
Then I noted that 8 seconds had to pass before the first overlap and put a
sample at 8 seconds.
I continued figuring out where the next overlap would be in time and put a
new sample at that point.
It was easier because only one pair of samples coincided at the same time.
It was easier because no samples had other than unity weight.
All you have to do is figure out when the samples coincide - which is very
simple to visualize.
When I was done the clock had gone 1 minute and 5 seconds.
There was no temporal scaling except to label the times of the samples. It
was easy to do the simple arithmetic in my head and drawing scaled cartoons
wasn't necessary. If it had been more complex then perhaps scaled drawings
(in time) would have been helpful - assuming no computer.
So, I think that visualization with a little help from the pencil and paper
is the fastest method.
Fred
Reply by Jerry Avins●July 25, 20052005-07-25
Jeroen Boschma wrote:
> Jane wrote:
>
>>"Jeroen Boschma" <jeroen.boschma@tno.nl> wrote in message
>>news:42E480E9.849E19EA@tno.nl...
>>
>>>Jane wrote:
>>>
>>>>Hi,
>>>>
>>>>Does anybody have the fastest method (using paper and pencil) to
>>>>calculate
>>>>the convolution:
>>>>
>>>>y[n]=x[n]*h[n]
>>>>
>>>>where x[n]=u[n-3] - u[n-14], h[n]=u[n-5] - u[n-8], where u[n] is the
>>>>step
>>>>function, u[n]=1 for n>=0, and u[n]=0 for n<0.
>>>>
>>>>Can you do it in 2 minutes?
>>>
>>>No, maybe 30 seconds. Tops... You really have to understand how the
>>>convolution works. Lets say you
>>>write it as y[n] = sum_m x[m] h[n-m]
>>>
>>>a) Figure out how x[m] and h[m] look like, and draw them with horizontal
>>>axis 'm'.
>>>b) Mirror h[m] around m=0. This gives you h[n-m] for n=0.
>>>c) By shifting h[n-m] to the right, you observe the convolution for n>0.
>>>Now look at four special
>>>points:
>>>1) h[n-m] and x[m] start to overlap, this is where output y[n] becomes
>>>non-zero
>>>2) h[n-m] and x[m] start to overlap completely, this is where output y[n]
>>>has max value
>>>3) h[n-m] and x[m] end to overlap completely, this is where output y[n]
>>>still has max value
>>>4) h[n-m] and x[m] end to overlap, this is where output y[n] becomes zero
>>>again
>>>
>>>That gives y[n]. Fill in the details of the convolution yourself.
>>>
>>> Jeroen
>>
>>Slow slow slow slow slow slow ... need so many steps... :=)
>
>
> Looks a lot of work maybe, but like I said: if you have some experience you can make the sketch of
> y[n] in seconds...
>
> Jeroen
I did it in under 3 minutes, but I had to find the quadrule pad first.
Jerry
--
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������