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?
fastest convolution
Started by ●July 25, 2005
Reply by ●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?I thought that was why they invented computers! :-) P.S. Is this a homework question? -- Jon Harris SPAM blocker in place: Remove 99 (but leave 7) to reply
Reply by ●July 25, 20052005-07-25
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
Reply by ●July 25, 20052005-07-25
"Jon Harris" <jon99_harris7@hotmail.com> wrote in message news:vt_Ee.2332$9y3.662@trnddc06...> "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? > > I thought that was why they invented computers! :-) > > P.S. Is this a homework question? > > -- > Jon Harris > SPAM blocker in place: > Remove 99 (but leave 7) to reply >Not a HW problem.
Reply by ●July 25, 20052005-07-25
"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. > > JeroenSlow slow slow slow slow slow ... need so many steps... :=)
Reply by ●July 25, 20052005-07-25
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
Reply by ●July 25, 20052005-07-25
Jane skrev:> 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?Yes, I can. Even if this seems to be a homework question, I'll show you how. Use an A4 paper (or your local equivalent) of the kind with 5mm x 5mm squares already in it. Start with laying out three coordinate systems with horizontal axis 0 <= x <= 25 and vertical axis 0 <= y <= 1, then a fourth coordinate system with 0 <= y <= 5. Make sure the horizontal axes are aligned vertically. This is a maths question, so I don't mention the term "impulse response", but if you were an engineer, I would explain the next step in terms of x[n] being the impulse response and h[n] being the input signal to an LTI system. But I don't mention those terms. Now, in the uppermost axis, plot x[n] scaled by the first non-zero coefficient of h[n], and delayed by an amount corresponding to the same coefficient. Repeat for the non-zero coefficients of h[n], there are three non-zero coefficients (OK, maybe there are four, it's too hot to day to work out absolutely all details). Having done that, add vertically across the axes to produce y[n]. Your paper ought to look something like this after you are through (use a fized-width font to view): ^ 1 | o o o o o o o o o o o o | | | | | | | | | | | | | +-o-o-o-o-o-o-o-------------------------o-o-o-o-o-o-o------> : : ^ : 1 | o o o o o o o o o o o o | | | | | | | | | | | | | +-o-o-o-o-o-o-o-o-------------------------o-o-o-o-o-o------> : : ^ : 1 | o o o o o o o o o o o o | | | | | | | | | | | | | +-o-o-o-o-o-o-o-o-o-------------------------o-o-o-o-o------> : : : : ^ y[n] : | : 3 | o o o o o o o o o o 2 | o | | | | | | | | | | o 1 | o | | | | | | | | | | | | o +-o-o-o-o-o-o-o-----------------------------o-o-o-o-o-o-o--> 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 n 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 The vertical line of colon's shows what samples to add to produce sample y[11]. Once you know the technique, it ought not to take more than 2 minutes to do, for a reasonable number of rectangular functions like above. As a bonus, extend the technique to the case where h[n] = {3 2 1} for n={0 1 2} 0 otherwise. You got as much time for the computation as you needed for the original problem, plus another 10 s. Rune
Reply by ●July 25, 20052005-07-25
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. 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? > >
Reply by ●July 25, 20052005-07-25
The method Jeroen mentioned is the standard way of doing convolution by hand. You can find in any introductory text. When you say slow, and too many steps, are you saying you have a new way of doing this? Can you share your idea? John> > Slow slow slow slow slow slow ... need so many steps... :=) >
Reply by ●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... > > JeroenI 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. �����������������������������������������������������������������������
