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

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

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

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

Типы свёрток

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

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

Расчёт свёрток

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

Расчёт линейной свёртки

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

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

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

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

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

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

где:

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

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

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

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

• симметрично отобразить одну из последовательностей относительно оси ординат;

• произвести перемножение этих двух последовательностей.

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

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

либо

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

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

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

Расчёт циклической свёртки

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

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

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

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

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

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

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

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

Расчёт апериодической свёртки

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

Связь линейной и циклической свёрток

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

$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}.$

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

$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.$

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

Вычисление свёртки с помощью преобразования Фурье

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

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

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

Вычислительная сложность

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

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

Уменьшение размерности пространства при многомерной свёртке

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

$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}).$

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

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

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

Пример программы

Ниже приведён пример реализации линейной свёртки, написанный на 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.