Свертка двух векторов, u и v, представляет область перекрытия под точками как v слайды поперек u. Алгебраически свертка - это та же операция, что и умножение многочленов, коэффициенты которых являются элементами u и v.
Давайте m = length(u) и n = length(v) . Тогда w - вектор длины m+n-1 чей k-й элемент -
Сумма превышает все значения j которые приводят к юридическим индексам для u(j) и v(k-j+1), в частности j = max(1,k+1-n):1:min(k,m). Когда m = n, это дает
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)
