Дискретная свертка (конволюция) [5,17,21].

Свертка – основной процесс в цифровой обработке сигналов. Поэтому важно уметь эффективно ее вычислять.

Уравнение дискретной свертки двух функций (сигналов) может быть получено непосредственно из интегрального уравнения свертки при замене интегрирования суммированием мгновенных значений функций с шагом Dt:

y(kDt) = Dth(nDt) s(kDt-nDt). (8.4.1)

При выполнении дискретной свертки мы имеем дело с цифровыми массивами, при этом шаг дискретизации для массивов по физическому аргументу свертки должен быть равным и принимается за 1, а в качестве аргумента используется нумерация отсчетов в массивах:

y(k) =h(n) s(k-n) ºh_n s_k-n º y_k. (8.4.1')

y(k) = h(n) _* s(k-n) º s(k) _* h(n) º s_{k *} h_n.

Техника свертки приведена на рис. 8.4.1. Для вычисления свертки массив одной из функций (s_k- входного сигнала) располагается по ходу возрастания номеров. Массив второй функции (h_n - более короткой, оператор свертки), строится параллельно первому массиву в обратном порядке (по ходу уменьшения номеров, в режиме обратного времени). Для вычисления y_k значение h₀ располагается против s_k, все значения s_k-n перемножаются с расположенными против них значениями h_n и суммируются. Результаты суммирования являются выходным значением функции y_k, после чего оператор h_n сдвигается на один номер k вперед (или функция s_k сдвигается ему навстречу) и вычисление повторяется для номера k+1 и т.д.

Рис. 8.4.1. Техника дискретной свертки.

В начальный момент свертки при вычислении значений y_k оператор h_n, построенный в режиме обратного времени, "зависает" для значений k-n при n>k против отсутствующих отсчетов входной функции. "Зависание" исключают либо заданием начальных условий - дополнительных отсчетов, чаще всего нулевых или равных первому отсчету входной функции, либо началом свертки с отсчета входной функции k = n с соответствующим сокращением интервала выходной функции. Для операторов со значениями -n (вперед по времени) такой же момент может наступать и в конце входного массива.

Пример.Уравнение свертки: y_k =b_n x_k-n = b_o x_k + b₁ x_k-1 + b₂ x_k-2. Значения оператора bn:

b_o = 5, b₁ = 3, b₂ = 2. Входной сигнал: x_k = {0,1,0,0,0}, начальные условия: x_-n = 0.

Расчет выходного сигнала:

y_o = 5x_o + 3x_-1+ 2_x-2 = 5 · 0 + 3 · 0 + 2 · 0 = 0, y₁ = 5x₁ + 3x_o + 2x_-1 = 5 · 1 + 3 · 0 + 2 · 0 = 5,

y₂ = 5x₂ + 3x₁ + 2x_o = 5 · 0 + 3 · 1 + 2 · 0 = 3, y₃ = 5x₃ + 3x₂ + 2x₁ = 5 · 0 + 3 · 0 + 2 · 1 = 2,

y₄ = 5x₄ + 3x₃ + 2x₂ = 5 · 0 + 3 · 0 + 2 · 0 = 0, y₅ = 5x₅ + 3x₄ + 2x₃ = 5 · 0 + 3 · 0 + 2 · 0 = 0

Выходной сигнал: yk = {0, 5, 3, 2, 0}

Заметим: свертка функции оператора с единичным входным сигналом представляет собой повторение функции оператора свертки на выходе.

На рис. 8.4.2 приведен пример выполнения дискретной свертки каузальным (односторонним) и четным (симметричным, двусторонним) оператором одного и того же сигнала.

Рис. 8.4.2. Примеры выполнения дискретной свертки.

Прямое вычисление свертки требует K·N умножений, где K – длина исходного сигнала, а N – длина ядра свертки. Как длина сигнала, так и длина ядра свертки может достигать нескольких тысяч точек, и число умножений становится огромным.

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

s(k) Û S(w), h(n) Û H(w), Y(w) = S(w)×H(w), Y(w) Û y(k).

С появлением алгоритмов БПФ, позволяющих быстро вычислять преобразования Фурье, вычисление свертки через частотную область стало широко использоваться. При значительных размерах сигналов и длины ядра свертки такой подход позволяет в сотни раз

сократить время вычисления свертки.

Выполнение произведения спектров может производиться только при одинаковой их длине, и оператор h(n) перед ДПФ необходимо дополнять нулями до размера функции s(k).

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

Рис. 8.4.3. Результаты двух видов свертки.

На рис. 8.4.3 приведены результаты свертки сигнала s_k, заданного на интервале k=(0-50), с функцией h_n = a×exp(-a×n), a = 0.1. Свертка, выполненная через ДПФ, в левой части интервала резко отличается от линейной свертки. Характер искажения становится понятным, если дополнить главный интервал с левой стороны его периодическим продолжением (на рисунке показана часть левого бокового периода, свертка с которым заходит в главный период). Для операторов h_n со значениями n, вперед по положению, аналогичные искажения появятся и в правой части главного периода. Для устранения таких искажений сигнальная функция должна продлеваться нулями на размер оператора h(n), что исключит наложение боковых периодов главной трассы функции.

При выполнении свертки через БПФ ощутимое повышение скорости вычислений появляется только при большой длине функций и операторов (например, M>1000, N>100). Следует также обращать внимание на разрядность результатов, т.к. перемножение чисел дает увеличение разрядности в 2 раза. При ограниченной разрядности числового представления с соответствующим округлением это может приводить к погрешностям суммирования.

В системах оперативной обработки данных часто возникает потребность вычислить свертку сигнала, поступающего на вход системы последовательными порциями (например, от датчиков скважинных приборов). В таких случаях применяется секционная свертка. Суть ее состоит в том, что каждая из этих частей сворачивается с ядром отдельно, а полученные части объединяются. Для объединения достаточно размещать их друг за другом с перекрытием в N-1 точку (N – длина ядра свертки), и производить суммирование в местах перекрытия.