fastest convolution

"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 

"Jes&#4294967295;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?

Jane wrote:
> "Jes&#4294967295;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] ..."

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

"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

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

"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 

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

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