Секционная (секционированная) свёртка — метод вычисления свёртки, используемый, когда количество элементов одной из входных последовательностей во много раз больше, чем количество элементов другой. Основные методы вычисления секционной свёртки — и .
Вычисление Пусть — неограниченная последовательность, — последовательность длины , — некоторое натуральное число. Метод перекрытия с суммированием Для вычисления линейной свёртки методом перекрытия с суммированием необходимо разделить последовательность на смежные секции длины :
где
Тогда
Длина каждой из частичных свёрток в данной сумме равна , то есть имеется участок длины , на котором -я и -я частичные свёртки перекрываются, поэтому их отсчёты на участке перекрытия нужно сложить. Отсюда и происходит название данного метода.
Метод перекрытия с накоплением Пусть теперь длина секций последовательности равна и у этих секций есть участки перекрытия длиной . Для каждой секции вычисляется циклическая свёртка и , содержащая отсчёт и обозначаемая . Необходимо отбросить последние отсчётов этой последовательности, а остальные присоединить к последовательности . После выполнения этой процедуры для каждого получится искомая последовательность .
Замечание Число удобно выбирать так, чтобы число было степенью двойки. Тогда каждую из частичных свёрток можно эффективно выполнять с помощью быстрых алгоритмов, значительно снижая вычислительную сложность.
Примечания
Литература
Категория:Математический анализ Категория:Обработка сигналов