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