Небольшой пост о том, как понять Convolution

Как мы учимся свертке

Свертка - одна из первых концепций, которую изучает каждый студент, изучающий коммуникационную технику. Это настолько фундаментально для изучения сигналов и систем, и тем не менее, представлено в виде уравнения с объяснениями, которые сосредоточены на том, как сворачивать, а не почему.

То, как мы обучаем и изучаем свертку, запутано :)

Помните, как мы это узнали? Если x [n] на входе в систему LTI с импульсной характеристикой h [n], выход y [n] задается операцией свертки:

y[n] = ∑ₖ h[k] x[n-k]

Ну и дела, красивое уравнение, но что оно означает, спросили мы. И у нас есть визуальное переворачивание, скольжение и умножение, накопление!

Скажем, я даю вам две последовательности:

x1 = [1, 2, 1, 0, 0, 2, 1, 2]
x2 = [3, 0, 0, 3, 0, 0, 1]

И я прошу у вас вывод свертки. Что бы вы сделали? Особенно, если у вас нет Matlab, Octave или Python. Можете ли вы оценить уравнение y [n] = ∑ₖ h [k] x [n-k] для двух вышеуказанных последовательностей?

Вместо этого просто запустите свой обычный калькулятор. Умножьте два числа (которые вы получите, прочитав последовательность справа налево): 21200121 x 1003003. Результат (21263784963363), который вы получите (опять же, считываемые цифры справа налево) - это выходной сигнал свертки! Верно, свертка из простого регулярного умножения. Не верите мне? Попробуйте!

Чтобы проверить правильность ответа, вот результат свертки с использованием Python scipy.Signal:

from scipy import signal
yc = signal.convolve(x1, x2)
print(yc)
[3 6 3 3 6 9 4 8 7 3 6 2 1 2]

Приведу еще один пример: x1 = [2, 1, 1, 0, 0, 0, 2, 2], x2 = [1, 0, 0, 0, 2, 0, 2, 2]. Умножьте 22000112 x 22020001 = 48442488240112, что при чтении справа налево является выходом свертки.

Конечно, в этом нет ничего удивительного для многих из вас, кто понимает, что такое свертка на самом деле. В конце концов, шаблон умножения, который у нас есть для чисел, представляющих собой последовательности единиц, уже намекает на это:
11 x 11 = 121
111 x 111 = 12321
1111 x 1111 = 1234321
и так далее. Узнаете закономерность? Свертка двух прямоугольных волн дает треугольник.

Для юношей описанный выше трюк работает не для всех последовательностей. Вы можете видеть, что даже для чисел, содержащих только цифру 1, этот шаблон разбивается на длину 10: 1111111111 x 1111111111 = 123456789 00 987654321. . Больше не треугольник - обратите внимание на два нуля посередине.

Так почему этот трюк умножения работает и почему не для всех последовательностей? Это работает, потому что операция свертки так же важна, как умножение двух последовательностей. Как нам умножить две последовательности? Конечно, сделав их коэффициентами многочлена! Скажем, у нас есть две последовательности [a0, a1, a2] и [b0, b1, b2]. Создайте многочлены
(a0 + a1x + a2x²)
(b0 + b1x + b2x²)

Умножьте и сгруппируйте члены:
(a0b0) + (a0b1 + a1b0) * x + (a0b2 + a1b1 + a2b0) * x² + (a1b2 + a2b1) * x³ + (a2b2) * x⁴

Теперь вы можете считывать выходные данные свертки как коэффициенты полученного многочлена.

Когда уловка умножения не работает? Когда любой из коэффициентов выходного полинома становится больше 10. Потому что свертка не «переносит» цифры, как в десятичном представлении.

Еще одна проверка: свертка последовательности длины m и последовательности длины n имеет выходную длину m + n-1. Последовательность длины m является полиномом степени m-1, поэтому член высшего порядка будет x⁽ⁿ⁻¹⁾ * x⁽ᵐ⁻¹⁾ = x⁽ⁿ⁺ᵐ⁻²⁾. Если полином имеет степень (m + n-2), он имеет m + n - 1 коэффициентов.

Это дает нам интуицию. В конце концов, мы изучаем алгебру в школе, а свертку изучаем только в «Сигналах и системах 101» во время разработки. Почему бы не развить то, что мы уже узнали и с чем нам комфортно?

Это не значит, что метод «перевернуть и умножить» бесполезен. Эта интерпретация чрезвычайно полезна, когда вы смотрите на двумерную свертку. Вы можете визуализировать это как переворачивание (как по горизонтали, так и по вертикали) вашего 2D-ядра, наложение его на первый образец (верхний левый угол) ваших 2D-данных, а затем просто перетащите ядро ​​вниз, пока не дойдете до последней строки первого столбца, сбросив до верхний ряд второго столбца, перетащите вниз. Промойте и повторяйте, пока не дойдете до образца в последнем столбце последней строки. Вот быстрый и грязный код Python, связывающий вход 8x8 с ядром 4x4:

import numpy as np
import matplotlib.pyplot as plt
from scipy import signal

hker = np.random.randint(low=0, high=4, size=(4,4))
hkerf = hker[::-1,:]
hkerf = hkerf[:,::-1]
x2d = np.random.randint(low=0, high=4, size=(8,8))
x2dpad = np.zeros((14,14))
x2dpad[3:3+8,3:3+8]=x2d
y2d = np.zeros((11,11))

for row in range(11):
  for col in range(11):
    y2d[row,col]=np.dot(hkerf.flatten(),x2dpad[row:row+4,col:col+4].flatten())

y2dc = signal.convolve2d(hker,x2d)

plt.stem(y2d.flatten(), use_line_collection=True)
plt.plot(y2dc.flatten(),'ro')

Способ настройки уравнения y [n] = h [k] x [n-k] также является важным строительным блоком для понимания цифровых фильтров и выполнения вычислений с дискретными преобразованиями Фурье. Однако, хотя мы должны быть обучены строгости, мы не должны терять интуицию на этом пути.

Кстати, я мог бы закончить этот пост одним абзацем, сказав, что свертка - это то же самое, что и полиномиальное умножение. Но где в этом веселье ?!