Свёртка последовательностей

Свёртка последовательностей — линейное преобразование двух числовых последовательностей. Результатом свёртки является последовательность, элементы которой получаются в результате перемножения и суммирования элементов исходных последовательностей таким образом, что члены одной последовательности берутся с возрастанием индексов, а члены другой — с убыванием (что и служит основанием для принятого названия данной операции). Различают линейную и циклическую свёртки, которые используются для конечных и периодических последовательностей соответственно.

Свёртка последовательностей ${\displaystyle a}$ и ${\displaystyle b}$ обозначается как ${\displaystyle a*b}$.

Свёртка последовательностей является частным случаем свёртки функций. Свёртка также тесно связана с взаимной корреляцией.

К традиционным типам свёрток относятся:

• линейная (апериодическая) свёртка;
• циклическая (круговая, периодическая) свёртка;
• свёртка с помощью дискретного преобразования Фурье.

Рассмотрим правила и последовательность расчёта каждого вида свёртки.

Пусть заданы две числовые последовательности:

${\displaystyle a=\left\{a_{0},a_{1},\ldots ,a_{N_{1}-1}\right\},}$

${\displaystyle b=\left\{b_{0},b_{1},\ldots ,b_{N_{2}-1}\right\}.}$

Для расчёта линейной свёртки этих последовательностей необходимо выполнить следующие действия:

• произвести расчёт количества элементов выходной последовательности по формуле:

${\displaystyle N_{out}=N_{1}+N_{2}-1,}$

где:

${\displaystyle N_{out}}$ — количество элементов в выходной последовательности;

${\displaystyle N_{1}}$ — количество элементов в первой последовательности;

${\displaystyle N_{2}}$ — количество элементов во второй последовательности;

• дополнить нулями обе последовательности так, чтобы количество элементов в обеих последовательностях было равно ${\displaystyle N_{out}}$;
• симметрично отобразить одну из последовательностей относительно оси ординат;
• произвести перемножение этих двух последовательностей.

В результате выполнения всех описанных выше операций получим линейную свёртку ${\displaystyle c}$ последовательностей ${\displaystyle a}$ и ${\displaystyle b}$, элементы которой вычисляются по одной из двух формул:

${\displaystyle c_{i}=\sum \limits _{k=0}^{N_{1}-1}a_{k}b_{i-k},\;i=0,\ldots ,N_{out}-1,}$

либо

${\displaystyle c_{i}=\sum \limits _{k=0}^{N_{2}-1}a_{i-k}b_{k},\;i=0,\ldots ,N_{out}-1.}$

Здесь подразумевается, что при ${\displaystyle i-k<0}$ элементы соответствующей последовательности равны нулю.

Убедиться в эквивалентности формул и, как следствие, в коммутативности операции свёртки можно с помощью простой замены индексов ${\displaystyle j=i-k}$ в одной из формул.

Рассмотрим теперь две числовые последовательности одинаковой длины ${\displaystyle N}$:

${\displaystyle a=\left\{a_{0},a_{1},\ldots ,a_{N-1}\right\},}$

${\displaystyle b=\left\{b_{0},b_{1},\ldots ,b_{N-1}\right\}.}$

Для получения периодической круговой свёртки ${\displaystyle c'}$ необходимо представить, что эти последовательности располагаются на двух окружностях, одна из которых находится внутри другой. Значения каждой из этих последовательностей равноудалены друг от друга. Для получения каждого значения круговой свёртки необходимо представить, что одна из последовательностей движется по окружности относительно другой по часовой стрелке. Сначала возьмём первое значение последовательности, которая вращается, последовательно умножим на значения другой последовательности и просуммируем результаты умножений и получим первое значение выходной последовательности ${\displaystyle c'}$. Затем данные действия повторим для каждого значения последовательности, которая вращается относительно другой. Количество элементов в выходной последовательности будет равно ${\displaystyle N}$.

Иными словами, элементы циклической свёртки ${\displaystyle c'}$ вычисляются по формуле

${\displaystyle c'_{i}=\sum \limits _{k=0}^{N-1}a_{k}b_{((i-k))},\;i=0,\ldots ,N-1,}$

где ${\displaystyle ((i-k))=(i-k){\bmod {N}}}$.

Полученная последовательность эквивалентна свёртке двух периодических сигналов, то есть можно рассматривать последовательности ${\displaystyle a}$ и ${\displaystyle b}$ как определённые для всех ${\displaystyle i\in \mathbb {Z} }$ по формулам ${\displaystyle a_{i}=a_{((i))}}$ и ${\displaystyle b_{i}=b_{((i))}}$.

Для получения апериодической свёртки выполняется все те же операции, что и для получения круговой свёртки, но при этом последовательности могут иметь разное количество элементов (например, ${\displaystyle N_{1}}$ и ${\displaystyle N_{2}}$) и их необходимо дополнить нулями до количества ${\displaystyle N_{out}=N_{1}+N_{2}-1}$. При выполнении данного вида свёртки устраняется эффект кругового наложения, который возникает при круговой свёртке. Это альтернативный способ вычисления линейной свёртки.

Описанный выше подход позволяет установить связь между вычислением линейной и циклической свёрток. Для этого в формуле для элементов циклической свёртки разделим сумму на две, соответствующие случаям ${\displaystyle i-k\geqslant 0}$ и ${\displaystyle i-k<0}$:

${\displaystyle c'_{i}=\sum \limits _{k=0}^{i}a_{k}b_{i-k}+\sum \limits _{k=i+1}^{N-1}a_{k}b_{N+i-k}.}$

Полагая теперь в первой сумме ${\displaystyle b_{i-k}=0}$ при ${\displaystyle k>i}$, а во второй ${\displaystyle b_{N+i-k}=0}$ при ${\displaystyle k<i}$, можно изменить границы суммирования и получить связь линейной и циклической свёрток в виде

${\displaystyle c'_{i}=\sum \limits _{k=0}^{N-1}a_{k}b_{i-k}+\sum \limits _{k=0}^{N-1}a_{k}b_{N+i-k}=c_{i}+c_{N+i},\;i=0,\ldots ,N-1.}$

Линейную свёртку можно вычислять как циклическую, если второе слагаемое в этой формуле равно нулю, то есть равны нулю произведения ${\displaystyle a_{k}b_{N+i-k}}$ для всех ${\displaystyle i}$ и ${\displaystyle k}$. Чтобы обеспечить выполнение этого условия, можно выбирать длину ${\displaystyle N}$ циклической свёртки так, чтобы она была не меньше, чем ${\displaystyle N_{out}=N_{1}+N_{2}-1}$, дополняя при этом входные последовательности нулями.

Для вычисления свёртки с помощью дискретного преобразования Фурье необходимо дополнить нулями обе входные последовательности так, чтобы количество элементов в этих последовательностях равнялось ${\displaystyle N_{out}}$. Далее необходимо произвести прямое преобразование Фурье каждой из последовательностей. Затем преобразованные последовательности поэлементно перемножаются, после чего производится обратное преобразование результата умножения.

Вычисление свёртки описанным способом осуществимо благодаря теореме о свёртке.

Для проверки правильности расчётов линейной, циклической или свёртки с помощью преобразования Фурье можно произвести дополнительно расчёт одной из двух других типов свёртки, так как выходные последовательности должны быть равны при одинаковых входных последовательностях.

Вычисление свёртки требует ${\displaystyle O(N^{2})}$ операций. Это количество может быть существенно уменьшено с помощью вычисления свёртки различными быстрыми алгоритмами.

Чаще всего для уменьшения количества операций свёртка вычисляется с помощью двух преобразований Фурье, каждое из которых рассчитывается с помощью быстрых алгоритмов. Это позволяет снизить вычислительную сложность операции свёртки до ${\displaystyle O(N\log N)}$.

Пусть в пространстве ${\displaystyle \mathbb {Z} ^{n}}$ заданы два дискретных комплексных сигнала ${\displaystyle f}$ и ${\displaystyle g}$. Определим свёртку ${\displaystyle y=f*g}$ этих сигналов как

${\displaystyle y(k_{1},\ldots ,k_{n})=\sum \limits _{i_{1}=-\infty }^{+\infty }\ldots \sum \limits _{i_{n}=-\infty }^{+\infty }f(i_{1},\ldots ,i_{n})g(k_{1}-i_{1},\ldots ,k_{n}-i_{n}).}$

Зададим также операцию понижения размерности пространства на измерение ${\displaystyle i_{j}}$ или суммирования сигнала по ${\displaystyle i_{j}}$ как

${\displaystyle f[\mathbb {Z} ^{n}-i_{j}]=\sum \limits _{i_{j}=-\infty }^{+\infty }f(i_{1},\ldots ,i_{n}),j\in 1...n.}$

Теорема. Для произвольного измерения ${\displaystyle i_{j}}$ пространства ${\displaystyle \mathbb {Z} ^{n}}$ результат свёртки ${\displaystyle y=f*g}$ с последующим суммированием по ${\displaystyle i_{j}}$ есть ${\displaystyle y[\mathbb {Z} ^{n}-i_{j}]}$, что эквивалентно предварительному суммированию по ${\displaystyle i_{j}}$ сигналов ${\displaystyle f}$ и ${\displaystyle g}$ с последующей свёрткой: ${\displaystyle y[\mathbb {Z} ^{n}-i_{j}]=f[\mathbb {Z} ^{n}-i_{j}]*g[\mathbb {Z} ^{n}-i_{j}]}$. ^[1]

Ниже приведён пример реализации линейной свёртки, написанный на C++:

/*
 * Размер выходной последовательности равен M + N - 1
 */
vector<double> conv(const vector<double>& x, const vector<double>& h) {
	if ((x.size() == 0) && (h.size() == 0)) {
		return vector<double>();
	}

	vector<double> a;
	vector<double> b;
	if (x.size() < h.size()) {
		a = x;
		b = h;
	} else {
		a = h;
		b = x;
	}

	vector<double> result(a.size() + b.size() - 1, 0);
	for (size_t k = 0; k < a.size(); k++) {
		for (size_t l = 0; l < b.size(); l++) {
			result[l + k] += a[k] * b[l];
		}
	}
	return result;
}

• Секционная свёртка

• Рабинер Л., Гоулд Б. Глава 2. Теория линейных дискретных систем // Теория и применение цифровой обработки сигналов. — М.: Мир, 1978. — С. 72—81. — 848 с.
• Блейхут Р.^[англ.] Быстрые алгоритмы цифровой обработки сигналов. — М.: Мир, 1989.