Все формулы РФ

Информатика / Алгоритмы и анализ данных

Линейная свёртка конечных последовательностей

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

Опубликовано: Обновлено:

Кодирование информацииАнализ данныхСтраницы с задачами и решениямиЕсть историческая справка

Формула

$$y_n=\sum_{k=-\infty}^{\infty}x_k h_{n-k},\qquad L_y=L_x+L_h-1$$
Схема Свёртка: (1;2;3) * (0,5;0,5)
Свёртка: (1;2;3) * (0,5;0,5)Свёртка: (1;2;3) * (0,5;0,5)00.511.522.531.5

Выходные отсчёты полного результата; у краёв вход продолжен нулями.

Обозначения

$xₖ$
входная последовательность, единица сигнала
$hₖ$
веса или импульсная характеристика фильтра, 1 для безразмерного усиления
$yₙ$
полный выход свёртки, единица x × единица h
$Lₓ,Lₕ,Lᵧ$
длины конечных входов и полного выхода, 1

Условия применения

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

Ограничения

Режимы same и valid возвращают лишь часть полного результата. Свёртка через ДПФ без достаточного дополнения нулями даёт круговой результат с наложенными краями. Нелинейные и зависящие от времени системы нельзя описать одной постоянной импульсной характеристикой.

Подробное объяснение

В сумме индекс n фиксирует номер выходного отсчёта. Для каждого k берётся вход xₖ и соответствующий коэффициент hₙ₋ₖ. Слагаемые вне диапазонов исчезают, поскольку входы продолжены нулями. На краях перекрывается меньше элементов, чем в середине, поэтому даже постоянный фрагмент может иметь меньший выход у границ.

Если вход состоит из одного импульса в точке k, выходом будет сдвинутая копия h с множителем xₖ. Любую конечную последовательность можно разложить на такие импульсы. Линейность позволяет сложить отклики, а стационарность — применять одинаковую форму отклика для каждого сдвига.

При индексах входов от нуля до Lₓ−1 и от нуля до Lₕ−1 первый возможный индекс суммы равен нулю, последний — Lₓ+Lₕ−2. Число индексов равно Lₓ+Lₕ−1. Нулевые крайние коэффициенты могут уменьшать фактическую область ненулевых значений, но длина полного массива по соглашению сохраняется.

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

Как пользоваться формулой

  1. Запишите оба массива с явными индексами от нуля и продолжите их нулями за пределами известных элементов.
  2. Определите длину полного выхода суммой длин минус один, чтобы не потерять начальный или конечный отсчёт.
  3. Для каждого выходного индекса сложите произведения пар, у которых сумма входных индексов равна этому индексу.
  4. Проверьте сумму выхода произведением сумм входов; отдельно укажите обрезку, если нужен укороченный режим.

Историческая справка

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

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

Историческая линия формулы

Линейная свёртка — стандартная операция анализа последовательностей и линейных стационарных систем. Её сумма следует из разложения входа по сдвинутым импульсам. Варианты прямого расчёта и расчёта через БПФ относятся к реализации одного математического определения.

Пример

Пусть x=(1;2;3), h=(1/2;1/2), оба массива безразмерны. Полная длина 3+2−1=4. Первый элемент y₀=1·1/2=0,5. Далее y₁=1·1/2+2·1/2=1,5; y₂=2·1/2+3·1/2=2,5; последний y₃=3·1/2=1,5. Итого y=(0,5;1,5;2,5;1,5). Сумма 6 совпадает с (1+2+3)·(1/2+1/2)=6. Края ниже среднего соседей внутри записи из-за нулевого продолжения. Для ускорения через ДПФ оба входа дополняют минимум до длины 4; преобразование длины 3 сложило бы последний элемент с первым и вернуло круговую свёртку (2;1,5;2,5). Полная длина четыре сохраняет оба края отклика.

Частая ошибка

Не заменяйте hₙ₋ₖ на hₙ₊ₖ: получится другое сопоставление индексов. Не отбрасывайте последний выходной элемент. Режим одинаковой с входом длины не равен полной свёртке. Нулевая сумма весов не означает нулевого выхода: она означает подавление постоянной составляющей в подходящих условиях.

Практика

Задачи с решением

Два коротких массива

Условие. Вычислите (1;2) * (1;−1).

Решение. y₀=1; y₁=−1+2=1; y₂=−2.

Ответ. (1;1;−2).

Длина БПФ

Условие. Длины входов 7 и 5. Какова минимальная длина ДПФ без наложения?

Решение. Полная свёртка содержит 7+5−1=11 элементов, поэтому длина ДПФ не меньше 11.

Ответ. 11; можно выбрать большую удобную длину.

Дополнительные источники

  • https://numpy.org/doc/stable/reference/generated/numpy.convolve.html
  • https://docs.scipy.org/doc/scipy/tutorial/signal.html
  • https://docs.scipy.org/doc/scipy/tutorial/fft.html

Связанные формулы

Информатика

Дискретное преобразование Фурье и обратная формула

$X_k=\sum_{n=0}^{N-1}x_n e^{-2\pi i kn/N},\qquad x_n=\frac1N\sum_{k=0}^{N-1}X_k e^{2\pi i kn/N}$

Дискретное преобразование Фурье переводит конечную последовательность в комплексные частотные коэффициенты. Обратная сумма восстанавливает все отсчёты; знак экспоненты и нормировку нужно выбирать согласованно.

Информатика

Окно Ханна: коэффициенты и поправка амплитуды

$w_n=\frac12\left(1-\cos\frac{2\pi n}{N-1}\right),\quad G_c=\frac1N\sum_{n=0}^{N-1}w_n,\quad N>1$

Симметричное окно Ханна плавно уменьшает края записи до нуля. Оно снижает дальнюю спектральную утечку ценой расширения главного лепестка и изменения амплитуды, поэтому масштаб спектра требует отдельной поправки.

Информатика

Частоты и амплитуды по коэффициентам ДПФ

$\Delta f=\frac{f_s}{N},\quad f_k=\frac{kf_s}{N},\quad A_k=\frac{2|X_k|}{N}\quad(0<k<N/2)$

Шаг частот ДПФ равен частоте дискретизации, делённой на длину записи. Для вещественной гармоники точно на внутреннем частотном отсчёте амплитуда равна удвоенному модулю коэффициента, делённому на число отсчётов.