The convolution of two vectors, u
and v
,
represents the area of overlap under the points as v
slides
across u
. Algebraically, convolution is the same
operation as multiplying polynomials whose coefficients are the elements
of u
and v
.
Let m = length(u)
and n = length(v)
.
Then w
is the vector of length m+n-1
whose k
th
element is
The sum is over all the values of j
that
lead to legal subscripts for u(j)
and v(k-j+1)
,
specifically j
=
max(1,k+1-n):1:min(k,m)
.
When m
=
n
,
this gives
w(1) = u(1)*v(1)
w(2) = u(1)*v(2)+u(2)*v(1)
w(3) = u(1)*v(3)+u(2)*v(2)+u(3)*v(1)
...
w(n) = u(1)*v(n)+u(2)*v(n-1)+ ... +u(n)*v(1)
...
w(2*n-1) = u(n)*v(n)