Информатика · объяснение и практика

Как получить полный отклик конечного фильтра свёрткой

Вычислить линейную свёртку конечного сигнала с конечным импульсным откликом, сохранить края и отличить её от круговой.

Синие фигурные скобки держат между собой оранжевый квадрат.

Вузовский уровень · Все вузовские темы

В теме Методы алгоритмов: углубление · Учебная карта

Главная мысль

Линейная свёртка складывает произведения пар отсчётов с одинаковой суммой индексов. Если последовательности имеют длины N и M, полный результат содержит N+M−1 отсчётов, включая начальный и конечный переходные участки.

Метод и условия

Зафиксируйте начало каждой последовательности: в этом инструменте первый введённый элемент имеет индекс ноль. За пределами введённого списка продолжение равно нулю. Для выходного индекса k берутся только пары j и k−j, существующие в двух списках. Каждый вклад x[j]h[k−j] добавляется к одному и тому же выходному отсчёту. Можно выполнять вычисление и в другом порядке: перемножать все пары и складывать произведение в ячейку с индексом j+i.

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

Проверка и типичная ошибка

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

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

Пример

Для x=(1,2,3) и h=(1,−1) выход равен (1,1,1,−3). Средний отсчёт y[2] получается как 3·1+2·(−1)=1.

Четвёртый отсчёт равен −3, потому что после конца входа следуют нули. Сумма выхода нулевая и совпадает с (1+2+3)(1−1).

От чтения к действию

А теперь — вы

Сколько отсчётов содержит полная линейная свёртка списков длины 5 и 3?

Частые вопросы

Это круговая свёртка?

Нет. Индексы не заворачиваются, а отсутствующие отсчёты считаются нулями.

Нужно нормировать h?

Только если это требует ваша модель. Фильтр разности [1,−1] имеет нулевую сумму, и нормировать его на сумму нельзя.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться